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$^{$P$}^ = {$N$} (%{$P$}).
Pentru intelegerea mai buna a solutiei doresc sa mentionez ca Z{~p~}(multimea tuturor resturilor posibile la impartirea cu $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$^{$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 .

h4. Avantaje si Dezavantaje
Ne vom referi la primul algoritm optim(cel cu ridicarea la putere) ca prima rezolvare si la celalalt algoritm ca a 2a rezolvare ,pentru dezambiguizare.

Prima rezolvare are urmatoarele avantaje: e usor de demonstrat si implicit de tinut minte, e usor de implementat si nu foloseste functii recursive si nici nu face operatii care sa incetineasca programul. Dezavantajul consta in faptul ca solutia nu e flexibila si nu poate fi extinsa pentru cazul cand cmmdc({$P$},{$N$}) = $1$.
A 2-a rezolvare e mai greu de implementat, poate da overflow si in practica se comporta mai prost decat prima, desi complexitatea e aceeasi. Dar aceasta problema poate fi adaptata pentru cazul cand $P$ nu este prim si se stie doar ca $N$ si $P$ sunt relativ prime, in alte cuvinte au cmmdc({$P$},{$N$}) = $1$.

Prima rezolvare are urmatoarele avantaje: e usor de demonstrat si implicit de tinut minte, e usor de implementat si nu foloseste functii recursive si nici nu face operatii care sa incetineasca programul.
A 2-a rezolvare e mai greu de implementat, poate da overflow si in practica se comporta mai prost decat prima, desi complexitatea e aceeasi.

h4. Folosinta:

Cel mai des Inversul modular se foloseste in dinamici,mai ales cand avem combinari sau aranjamente si trebuie sa calculam modulo un numar prim. De exemplu in loc sa calculam $combinari(N,P)= N!/(((N-P)!*P!)$ calculam $combinari(N,P) = N! * INV($(N-P)$!) * INV($P$!)$.

Cel mai des Inversul modular se foloseste in dinamici,mai ales cand avem combinari sau aranjamente si trebuie sa calculam modulo un numar prim. De exemplu in loc sa calculam $combinari(N,P)= N!/(((N-P)!*P!)$ calculam $combinari(N,P) = N! * (N-P)!^-1^ * P!^-1^$.

h4. Probleme similare