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$, se verifica relatia:
$N$^{$P$}^ = {$N$} (% $P$ ).

Pentru intelegerea mai buna a solutiei doresc sa mentionez ca Z ~p~ cu inmultirea formeaza un grup, si asta inseamna ca orice element din Z ~p~ are un invers, unic, deci putem inmulti prin el, chiar daca nu il stim.

Pentru intelegerea mai buna a solutiei doresc sa mentionez ca Z{~p~} cu inmultirea formeaza un grup, si asta inseamna ca orice element din Z{~p~} are un invers, unic, deci putem inmulti prin el, chiar daca nu il stim.

In alte cuvinte $N$^{$P$}^ = {$N$} (%$P$) | * $N$^-1^
$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, si anume 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( $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$ ).

A 2-a solutie, se bazeaza pe un simplu principiu. Anume cel al euclidului extins, si anume 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( $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$ ).