Un algoritm evident ar fi incercarea tuturor numerelor $X$ intre $1$ si $N-1$ si verificarea proprietatii din enunt pentru $X$. O astfel de solutie are complexitatea {$O(N)$} si obtine 30 de puncte. Sursa se poate gasi 'aici':job_detail/223241?action=view-source.
O complexitate mai buna se obtine folosind "teorema lui Euler":http://en.wikipedia.org/wiki/Euler%27s_theorem, din care avem ca {$A^phi(N)^$} este congruent cu $1$, modulo $N$, unde {$phi(N)$} reprezinta numarul numerelor mai mici decat $N$ si prime cu $N$. Cum {$A^phi(N)^ = A * A^phi(N)-1^$} rezulta ca {$A^phi(N)-1^$} este inversul modular al lui {$A$}. Solutia problemei va fi deci {$A^phi(N)-1^ modulo N$}. Putem folosi 'exponentierea in timp logaritmic':problema/lgput pentru a calcula {$A^phi(N)-1^ modulo N$} in complexitate {$O(log{~2~}N)$}. Putem sa calculam {$phi(N)$} in complexitate <tex>O(\sqrt{N})</tex>. Pentru cazul particular cand $N$ este prim, $phi(N) = N-1$, deci raspunsul va fi $A^N-2^$ (dupa cum reiese si din "mica teorema a lui Fermat":http://en.wikipedia.org/wiki/Fermat%27s_little_theorem). O implementare ce se bazeaza pe aceasta idee se gaseste 'aici':job_detail/227473?action=view-source.
O complexitate mai buna se obtine folosind "teorema lui Euler":http://en.wikipedia.org/wiki/Euler%27s_theorem, din care avem ca {$A^phi(N)^$} este congruent cu $1$, modulo $N$, unde {$phi(N)$} reprezinta numarul numerelor mai mici decat $N$ si prime cu $N$. Cum {$A^phi(N)^ = A * A^phi(N)-1^$} rezulta ca {$A^phi(N)-1^$} este inversul modular al lui {$A$}. Solutia problemei va fi deci {$A^phi(N)-1^ modulo N$}. Putem folosi 'exponentierea in timp logaritmic':problema/lgput pentru a calcula {$A^phi(N)-1^ modulo N$} in complexitate {$O(log{~2~}N)$}. In plus, putem calcula {$phi(N)$} in complexitate <tex>O(\sqrt{N})</tex>. Pentru cazul particular cand $N$ este prim, $phi(N) = N-1$, deci raspunsul va fi $A^N-2^$ (dupa cum reiese si din "mica teorema a lui Fermat":http://en.wikipedia.org/wiki/Fermat%27s_little_theorem). O implementare ce se bazeaza pe aceasta idee se gaseste 'aici':job_detail/227473?action=view-source.
Complexitatea optima pentru determinarea inversului modular este {$O(log{~2~}P)$}. Putem folosi principiul 'extins al lui Euclid':problema/euclid3: oricare ar fi $A$ si $N$ numere intregi exista doua numere $X$ si $Y$ de asemenea intregi astfel incat {$A * X + N * Y = cmmdc(A, N)$}. Cum in problema determinarii inversului modular avem {$cmmdc(A, N) = 1$}, exista $X$ si $Y$ astfel incat {$A * X + N * Y = 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.
Complexitatea optima pentru determinarea inversului modular este {$O(log{~2~}P)$}. Putem folosi principiul 'extins al lui Euclid':problema/euclid3: oricare ar fi $A$ si $N$ numere intregi exista doua numere $X$ si $Y$ de asemenea intregi astfel incat {$A * X + N * Y = cmmdc(A, N)$}. Cum in problema determinarii inversului modular avem {$cmmdc(A, N) = 1$}, exista $X$ si $Y$ astfel incat {$A * X + N * Y = 1$}. Considerand ecuatia modulo $N$, deoarece {$N * Y$} este divizibil cu {$N$}, avem {$A * X$} congruent cu {$1$} (modulo $N$), deci $X$ este inversul modular pentru {$A$}. Coeficientii $X$ si $Y$ pot fi determinati in timp logaritmic. {$X$} poate sa fie si negativ, deci trebuie sa adaugam $N$ la $X$ pana cand devine pozitiv. O astfel de solutie se poate gasi 'aici':job_detail/226687?action=view-source.
h2. Aplicatii
O aplicatie foarte utila a inversilor modulari este calcularea combinarilor, modulo un numar prim $P$ dat. De exemplu, avem:
Alte aplicatii ce folosesc notiunile prezentate mai sus se regasesc in urmatoarele probleme:
* "Stand in Line":http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=23&page=show_problem&problem=2115 (uva)
* "functii":problema/functii
* 'Functii':problema/functii
== include(page="template/taskfooter" task_id="inversmodular") ==
