Pagini recente » Diferente pentru problema/cate3cifre intre reviziile 4 si 3 | Diferente pentru problema/tablite intre reviziile 35 si 13 | Monitorul de evaluare | Diferente pentru problema/balbaiala intre reviziile 4 si 3 | Diferente pentru problema/inversmodular intre reviziile 82 si 83
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.
