Algoritmo ECPP

L'ECPP (dall'inglese Elliptic Curve Primality Proving) è un test di primalità basato sulle curve ellittiche. È 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:

O ( ( log ⁡ n ) 5 + ε ) {\displaystyle O((\log n)^{5+\varepsilon })\,}

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 dell'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.

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.[2]

Note

  1. ^ A. K. Lenstra, Jr., Lenstra, Jr., H. W., Algorithms in number theory, in Handbook of Theoretical Computer Science: Algorithms and Complexity, A, Amsterdam and New York, The MIT Press, 1990, pp. 673–715.
  2. ^ (FR) Quelques nombres premiers prouvés par mes programmes, su lix.polytechnique.fr.

Collegamenti esterni

  • (EN) Eric W. Weisstein, Algoritmo ECPP, su MathWorld, Wolfram Research. Modifica su Wikidata
  • (EN) Chris Caldwell, I più grandi numeri provati essere primi con l'ECPP
  • (EN) François Morain, "The ECPP home page"
  • (EN) Marcel Martin, Un'implementazione per Linux dell'algoritmo
  Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica