Algoritmo ECPP: differenze tra le versioni

Versione delle 21:37, 10 set 2015

Versione attuale delle 20:39, 9 feb 2023

(Una versione intermedia di un altro utente non mostrate)

Riga 3:

per qualche ε>0<ref name="Lenstra">{{Cita pubblicazione|cognome=Lenstra, Jr.|nome=A. K.|coautori=Lenstra, Jr., H. W.|titolo=Algorithms in number theory|rivista=Handbook of Theoretical Computer Science: Algorithms and Complexity|volume=A|editore=The MIT Press|città=Amsterdam and New York|pagine=673–715|anno=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 dell'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.

Al 2011 il più grande primo conosciuto la cui primalità sia stata provata con l'ECPP è il primo LR che consta di 26.643 cifre.<ref>{{Cita web|lingua=fr|titolo=Quelques nombres premiers prouvés par mes programmes|editore=polytechnique.fr|url=http://www.lix.polytechnique.fr/~morain/Primes/myprimes.html}}</ref>

==Note==

Riga 9:

== Collegamenti esterni ==

* {{Collegamenti esterni}}

* {{MathWorld|EllipticCurvePrimalityProving|Elliptic Curve Primality Proving}}

* {{en}} Chris Caldwell, [http://primes.utm.edu/prove/prove4_2.html I più grandi numeri provati essere primi con l'ECPP]

* {{en}} François Morain, [http://www.lix.polytechnique.fr/~morain/Prgms/ecpp.english.html "The ECPP home page"]