Diferente pentru problema/inversmodular intre reviziile #80 si #117

Diferente intre titluri:

inversmodular
Invers modular

Diferente intre continut:

== include(page="template/taskheader" task_id="inversmodular") ==
Se dau doua numere $N$ si $P$, cu $1 ≤ N ≤ P-1$, iar $P$ prim. Sa se determine $X$ intre $1$ si $P-1$ astfel incat $N * X$ sa fie congruent cu {$1$}, modulo $P$ (restul impartirii lui {$N * X$} la $P$ sa fie {$1$}).
Se dau doua numere $A$ si $N$, cu $1 ≤ A ≤ N-1$, prime intre ele (cel mai mare divizor comun al lor este $1$). Sa se determine $X$ intre $1$ si $N-1$ astfel incat $A * X$ sa fie congruent cu {$1$}, modulo $N$ (restul impartirii lui {$A * X$} la $N$ sa fie {$1$}). Numarul $X$ se va numi inversul modular al lui $A$.
h2. Date de intrare
Fisierul de intrare $inversmodular.in$ va contine pe prima linie numerele $N$ si $P$, separate printr-un spatiu.
Fisierul de intrare $inversmodular.in$ va contine pe prima linie numerele $A$ si $N$, separate printr-un spatiu.
h2. Date de ieşire
h2. Restricţii
* $1 ≤ P ≤ 2.000.000.000$
* $1 ≤ N ≤ P-1$
* $1 &le; A < N &le; 2.000.000.000$
* Pentru $60%$ din teste $N$ este prim.
h2. Exemplu
h2. Indicaţii de rezolvare
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.
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.
Complexitatea optima pentru determinarea inversului modular este {$O(log{~2~}P)$}. Din "teorema lui Fermat":http://en.wikipedia.org/wiki/Fermat%27s_little_theorem
O complexitate mai buna se obtine folosind "teorema lui Euler":http://en.wikipedia.org/wiki/Euler%27s_theorem, din care avem ca <tex>A^{\varphi(N)} \equiv 1 (mod N)</tex>, unde <tex>\varphi(N)</tex> reprezinta numarul numerelor mai mici decat $N$ si prime cu $N$. Cum <tex>A^{\varphi(N)} = A * A^{\varphi(N)-1}</tex> rezulta ca <tex>A^{\varphi(N)-1}</tex> este inversul modular al lui {$A$}. Solutia problemei va fi deci <tex>A^{\varphi(N)-1} mod N</tex>. Putem folosi 'exponentierea in timp logaritmic':problema/lgput pentru a calcula aceasta putere in complexitate {$O(log{~2~}N)$}. In plus, putem calcula <tex>\varphi(N)</tex> in complexitate <tex>O(\sqrt{N})</tex>. Pentru cazul particular cand $N$ este prim, <tex>\varphi(N) = N-1</tex>, 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.
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 &le; N &le; 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$ &le; $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$).
 
Complexitatea optima pentru determinarea inversului modular este {$O(log{~2~}N)$}. 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/228208?action=view-source.
h4. Avantaje si Dezavantaje
h2. Aplicatii
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.
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.
Ambele rezolvari pot fi extinse la cazul cand $P$ nu este prim si cmmdc($N$,$P$) = $1$.
O aplicatie foarte utila a inversilor modulari este calcularea combinarilor, modulo un numar prim $P$ dat. De exemplu, avem:
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! * (N-P)!^-1^ * P!^-1^$.
 
h4. Probleme similare
 
* "p11174":http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=23&page=show_problem&problem=2115
<tex>C^K_N = \frac{N!}{K!*(N-K)!} = N! * (K!)^{-1} * [(N-K)!]^{-1}</tex>
Prin <tex>(K!)^{-1}</tex> si <tex>[(N-K)!]^{-1}</tex> se inteleg inversii modulari ai acestor numere, modulo {$P$}. Astfel putem calcula o combinare de ordin $N$, modulo $P$, in timp {$O(N)$}.
Alte aplicatii ce folosesc notiunile prezentate mai sus se regasesc in urmatoarele probleme:
* 'Functii':problema/functii
* 'Jap2':problema/jap2
* "The equation":http://acm.sgu.ru/problem.php?contest=0&problem=106, sgu
* "Stand in Line":http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=23&page=show_problem&problem=2115, uva
== include(page="template/taskfooter" task_id="inversmodular") ==

Nu exista diferente intre securitate.

Diferente intre topic forum:

 
3451