Diferente intre titluri:
inversmodular
Invers modular
Diferente intre continut:
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.
Complexitatea optima pentru determinarea inversului modular este {$O(log{~2~}P)$}. Din "teorema lui Fermat":http://en.wikipedia.org/wiki/Fermat%27s_little_theorem
Complexitatea optima pentru determinarea inversului modular este {$O(log{~2~}P)$}. Din "mica teorema a lui Fermat":http://en.wikipedia.org/wiki/Fermat%27s_little_theorem stim ca
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:
Nu exista diferente intre securitate.
Topicul de forum nu a fost schimbat.
