Algoritmo ECPP
Da Wikipedia, l'enciclopedia libera
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:
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]
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
