Algoritmo ECPP
L'ECPP (dall'inglese Elliptic Curve Primality Proving) è un test di primalità basato sulle curve ellttiche. È un algoritmo che funziona per tutti gli interi e non solo per quelli di una qualche forma particolare ed è, al momento, fondamentalmente il più veloce algoritmo conosciuto per testare la primalità di un numero generico. Tuttavia, l'esatta complessità computazionale non è nota. Euristicamente, l'ECPP fornisce la primalità di un numero in un tempo:
per qualche ε>0[1] 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 forme quadratiche tali che p-1 si fattorizzi trivialmente sul gruppo.
Attualmente (aprile 2008), il più grande primo conosciuto, la cui primalità sia stata provata con l'ECPP è il primo di Mills
che consta di 20.562 cifre.
Note
- ^ A. K. Lenstra, Jr., Lenstra, Jr., H. W., Algorithms in number theory, in Handbook of Theoretical Computer Science: Algorithms and Complexity, A, The MIT Press, 1990, pp. 673–715.
- ^ Martin, Marcel. ECPP records (multiprocessor). Retrieved on 2007-06-09.
- ^ Caldwell, Chris. The Top Twenty: Elliptic Curve Primality Proof from the Prime Pages. Retrieved on 2007-06-09.
Collegamenti esterni
- Elliptic Curves and Primality Proving di Atkin e Morain
- La pagina relativa al'ECPP su MathWorld
- Chris Caldwell, I più grandi numeri provati essere primi con l'ECPP
- François Morain, "The ECPP home page"
- Marcel Martin, Un'implementazione per Windows dell'algoritmo
