Algoritm ECPP
ECPP (din engleza Elliptic Curve Primality Proving ) este un test de primărie bazat pe curbe eliptice . Este un algoritm care funcționează pentru toate numerele întregi și nu doar pentru cele de o anumită formă și este, în acest moment, practic cel mai rapid algoritm cunoscut pentru testarea primalității unui număr generic. Cu toate acestea, complexitatea de calcul exactă este necunoscută. Din punct de vedere euristic , ECPP oferă primalitatea unui număr într-un timp:
pentru unele ε> 0 [1] și, prin urmare, este mai rapid decât algoritmul AKS . În unele versiuni, exponentul logaritmului poate fi redus la 4 + ε printr-un raționament euristic. Ideea din spatele ECPP este aceeași cu cea a multor alte teste de primalitate și constă în încercarea de a construi un grup a cărui dimensiune implică primalitatea numărului investigat. În cazul ECCP, grupul în cauză este cel asociat cu o curbă eliptică pe un set finit de forme pătratice astfel încât p -1 să fie luată în considerare în mod trivial pe grup.
Începând din 2011, cel mai mare prim cunoscut a cărui primărie a fost dovedită cu ECPP este primul LR care constă din 26.643 cifre. [2]
Notă
- ^ AK Lenstra, Jr., Lenstra, Jr., HW, Algoritmi în teoria numerelor , în Handbook of Theoretical Computer Science: Algorithms and Complexity , A, Amsterdam and New York, The MIT Press, 1990, pp. 673–715.
- ^ ( FR ) Quelques nombres premiers prouvés par mes programmes , pe lix.polytechnique.fr .
linkuri externe
- (EN) Eric W. Weisstein, Elliptic Curve Primality Proving , în MathWorld Wolfram Research.
- (EN) Chris Caldwell, un număr mai mare dovedit a fi primul cu ECPP
- ( RO ) François Morain, „Pagina principală ECPP”
- ( EN ) Marcel Martin, O implementare Linux a algoritmului
