Algoritmo ECPP: differenze tra le versioni

Versione delle 13:33, 3 ago 2011

Versione delle 14:53, 20 set 2011

Riga 1:

L''''ECPP''' (dall'inglese ''Elliptic Curve Primality Proving'') è un [[test di primalità]] basato sulle [[curva ellittica|curve ellittiche]]. È un [[algoritmo]] che funziona per tutti gli [[numero intero|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 [[Teoria della complessità computazionale|complessità computazionale]] non è nota. [[euristica|EuristicamenteEuristica]]mente, l'ECPP fornisce la primalità di un numero in un tempo:

:<math> O((\log n)^{5+\epsilon})\, </math>

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|publisher=The MIT Press|___location=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 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.

Riga 6:

==Note==

{{<references}} />

== Collegamenti esterni ==

Riga 12:

* La [http://mathworld.wolfram.com/EllipticCurvePrimalityProving.html pagina relativa al'ECPP] su [[MathWorld]]

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

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

*Marcel Martin, [http://www.ellipsa.net/public/primo/index.html Un'implementazione per Windows dell'algoritmo]

{{Portale|matematica}}

[[Categoria:Test di primalità]]