Un algoritm evident ar fi incercarea tuturor numerelor $X$ intre $1$ si $P-1$ si verificarea proprietatii din enunt pentru $X$. O astfel de solutie are complexitatea {$O(P)$} si obtine 30 de puncte. Sursa se poate gasi 'aici':job_detail/223241?action=view-source.

Complexitatea optima pentru determinarea inversului modular este {$O(log{~2~}P)$}. Din "mica teorema a lui Fermat":http://en.wikipedia.org/wiki/Fermat%27s_little_theorem stim ca

Complexitatea optima pentru determinarea inversului modular este {$O(log{~2~}P)$}. Din "mica teorema a lui Fermat":http://en.wikipedia.org/wiki/Fermat%27s_little_theorem stim ca $P | X^P-1^-1$, pentru orice numar prim $P$ si pentru orice $X$ prim cu $P$. Demonstratia acestei teoreme se bazeaza pe teoria grupurilor. Din teorema rezulta ca {$X^P-1^ = X * X^P-2^$} este congruent cu $1$, modulo $P$, deci {$X^P-2^$} este inversul modular al lui {$X$}. Solutia problemei va fi deci {$X^P-2^ modulo P$}. Putem folosi 'exponentierea in timp logaritmic':problema/lgput pentru a calcula {$X^P-2^ modulo P$} in complexitate {$O(log{~2~}P)$}. O implementare ce se bazeaza pe aceasta idee se gaseste 'aici':job_detail/223243?action=view-source.

Exista doua solutii eficiente pentru aceasta problema, fiecare cu avantaje si dezavantaje, le voi discuta pe ambele in ceea ce urmeaza:
Pentru prima solutie trebuie sa apelam la teorema lui Ferma care zice ca pentru orice $P$ prim si $N$ , $1 ≤ N ≤ P - 1$, se verifica relatia:
$N$^{$phi(P)$}^ = {$1$} (%{$P$}).
In alte cuvinte
$N$^{$P-1$}^ = {$1$} (%{$P$}), deci :
$N$ * $N$^{$P-2$}^ = {$1$} (%{$P$});
De unde se observa ca $N$^{$P-2$}^ este defapt $X$ -ul cautat. Deci solutia, pe scurt pentru cei care nu sunt prea interesati de demonstratie este sa ridicam $N$ la puterea $P-2$, modulo $P$, si acest numar va fi rezultatul dorit. Ridicarea la putere se face in timp logaritmic, deci complexitate finala este O(log{~2~}$P$). O astfel de implementare se poate vedea "aici":http://infoarena.ro/job_detail/223243?action=view-source .
A 2-a solutie, se bazeaza pe un simplu principiu, anume cel al euclidului extins, care zice ca exista doua numere $A$ si $B$, intregi, astfel incat $A$ * $N$ + $B$ * $P$ = cmmdc({$N$},{$P$}). Nu voi intra in detalii in legatura cu algoritmul de gasire a acestor numere $A$ si $B$, algoritm care se gaseste in Cormen sau chiar pe "infoarena":http://infoarena.ro/problema/euclid3. Se presupune ca le putem gasi in complexitate O(log{~2~}{$M$}). cmmdc({$N$},{$P$}) = 1, deoarece $N$ ≤ $P-1$ iar $P$ este prim. Deci avem ca $A$ * $N$ + $B$ * $P$ = $1$, ecuatie care o transformam in $Z{~p~}$ ,in alte cuvinte modulo $P$, si rezulta $A$ * $N$ + $0$ = $1$, fiindca $B$ * $P$ e divizibil cu $P$,din motive evidente. $A$ * $N$ = $1$ (% $P$ ), Se observa din nou ca $A$ este $X$ -ul cautat. Din pacate acum $A$ -ul poate sa fie si negativ, deci trebuie sa adaugam $P$ la $A$ pana devine pozitiv. Complexitatea O(log{~2~} $P$).
 

O alta abordare optima se bazeaza pe principiul 'extins al lui Euclid':problema/euclid3: oricare ar fi $N$ si $P$ numere intregi exista doua numere intregi $A$ si $B$ astfel incat {$A * N + B * P = cmmdc(N, P)$}. Cum in problema determinarii inversului modular avem $P$ prim, exista A si B astfel incat {$A * N + B * P = 1$}. Considerand ecuatia modulo $P$, deoarece {$B * P$} este divizibil cu {$P$}, avem {$A * N$} congruent cu {$1$} (modulo $P$), deci A este inversul modular pentru {$N$}. Complexitatea acestui algoritm este tot {$O(log{~2~}P)$}, deoarece coeficientii $A$ si $B$ pot fi determinati in timp logaritmic.
 
*Din pacate acum $A$ -ul poate sa fie si negativ, deci trebuie sa adaugam $P$ la $A$ pana devine pozitiv.?*

h4. Avantaje si Dezavantaje