Există două modalități de a rezolva această problemă.
Prima modalitate este de a utiliza algoritmul euclidian extins.
Euclid algoritmul caută GCD a două numere. Algoritmul euclidian avansat prezintă simultan GCD ca o combinație liniară întregă a numerelor originale:
După cum este ușor de văzut, dacă A și C nu sunt relativ prime, atunci nu există nici o soluție, iar dacă acestea sunt - coeficientul A este elementul invers dorit (pentru dovada poate fi înlocuită în formula B de mai sus C și să ia ambele părți ale C-mod) .
Algoritmul recursiv este destul de simplu. La următoarea etapă, cea mai mare dintre cele două numere (pentru certitudine, a) este reprezentată ca c + k ∙ b. după care algoritmul se numește recursiv pentru (b, c):
Prin urmare, avem Ka = Kc1 și Kb = Kb1 - Kc1 ∙ k
Obținem aproximativ următorul algoritm:
Algoritmul iterativ este la fel de ușor de implementat, dar mai greu de înțeles. Cea mai ușoară cale este de a folosi matrice. În primul rând, ar trebui să scriem transformarea coeficienților în forma matricială:
Acești factori de matrice pot fi acumulați:
Se obține următorul algoritm:
Acum, că avem GCD, rămâne de a găsi GCD (A, C), verificați dacă acesta este egal cu 1 și ia (Ka% C), ca numărul invers celui dorit.
Ore - pe ordinea de log A iterații cp de bază (datorită faptului că cel mai rău caz pentru algoritmul lui Euclid - numerele lui Fibonacci adiacente).
A doua modalitate este de a folosi formula lui Euler
Dacă numărul C este cunoscut în prealabil sau dacă este suficient timp pentru pregătire, putem folosi formula Euler:
Întrucât problema soluționării divizoarelor comune nontrivială A și C încă nu are o soluție, restricția nu ne împiedică.
În conformitate cu formula, răspunsul este A ^ (φ (C) - 1)% C. Se poate găsi rapid folosind algoritmul de exponentializare rapidă:
Corectitudinea acestui algoritm este ușor de demonstrat dacă observăm că a ^ x * b este invariant.
Desigur, după primirea răspunsului va fi necesar să verificăm dacă este corect, dacă este incorectă - prin urmare, nu există nici un răspuns (A și C au divizii comune).
Acest algoritm va funcționa mai repede decât algoritmul lui Euclid, deoarece aici baza logaritmului este mai mare, iar iterațiile în sine sunt mai simple. Dar pentru a aplica acest algoritm, este necesar să știm în avans φ (C)
Articole similare
Trimiteți-le prietenilor: