Algoritmo ECPP: differenze tra le versioni

Versione delle 12:29, 12 dic 2010

Versione delle 22:39, 18 apr 2011

Riga 3:

per qualche ε>0<ref name="Lenstra">{{cite journal|last=Lenstra, Jr.|first=A. K.|coauthors=Lenstra, Jr., H. W.|title=Algorithms in number theory|journal=Handbook of Theoretical Computer Science: Algorithms and Complexity|volume=A|publisher=The MIT Press|___location=Amsterdam and New York|pages=673–715|year=1990}}</ref> ed è dunque più veloce dell'[[algoritmo AKS]]. In alcune versioni, l'esponente del logaritmo può essere ridotto a 4+ε attraverso alcuni ragionamenti euristici. L'idea alla base dell'ECPP è la stessa di molti altri test di primalità e consiste nel cercare di costruire un gruppo la cui dimensione implichi la primalità del numero investigato. Nel caso del'ECCP, il gruppo in questione è quello associato a una curva ellittica su un insieme finito di [[forma quadratica|forme quadratiche]] tali che ''p''-1 si fattorizzi trivialmente sul gruppo.

Attualmente (aprile 20082011), il più grande primo conosciuto, la cui primalità sia stata provata con l'ECPP è il [[primo LR che consta di Mills]]26.643 cifre.<ref>{{cite journal|author=N. Lygeros, F. Morain, O. Rozier|url=http://www.lix.polytechnique.fr/~morain/Primes/myprimes.html}}</ref>

:<math>(((((((((2^3+3)^3+30)^3+6)^3+80)^3+12)^3+450)^3+894)^3+3636)^3+70756)^3+97220,</math><ref>Martin, Marcel. [http://www.ellipsa.net/primo/record.html#03 ''ECPP records (multiprocessor)'']. Retrieved on [[2007-06-09]].</ref><ref>Caldwell, Chris. [http://primes.utm.edu/top20/page.php?id=27 ''The Top Twenty: Elliptic Curve Primality Proof''] from the [[Prime Pages]]. Retrieved on [[2007-06-09]].</ref>

che consta di 20.562 cifre.

==Note==