Din teorema rezulta ca {$X^phi(P)^ = X * X^phi(P)-1^$} este congruent cu $1$, modulo $P$, deci {$X^phi(P)-1^$} este inversul modular al lui {$X$}. Solutia problemei va fi deci {$X^phi(P)-1^ modulo P$}. Putem folosi 'exponentierea in timp logaritmic':problema/lgput pentru a calcula {$X^phi(P)-1^ modulo P$} in complexitate {$O(log{~2~}P)$}.Pentru cazul particular cand $P$ este prim, $phi(P) = P - 1$, deci raspunsul va fi $X^P-2^$.
O implementare ce se bazeaza pe aceasta idee se gaseste 'aici':job_detail/227473?action=view-source.

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 cmmdc($N$,$P$)=1, 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. {$A$} poate sa fie si negativ, deci trebuie sa adaugam $P$ la $A$ pana devine pozitiv.

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 cmmdc({$N$},{$P$})=1, 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. {$A$} poate sa fie si negativ, deci trebuie sa adaugam $P$ la $A$ pana devine pozitiv.

O astfel de solutie se poate gasi 'aici':job_detail/226687?action=view-source.