|
L''''ECPP''' (dall'inglese ''Elliptic Curve Primality Proving'') è un [[test di primalità]] basato sulle [[curva ellittica|curve elltticheellittiche]]. ÉÈ 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|EuresticamenteEuristica]]mente, l'ECPP fornisce la primalità di un numero in un tempo:
:<math> O((\log n)^{5+\epsilonvarepsilon})\, </math>
per qualche ε>0<ref name="Lenstra">{{citeCita journalpubblicazione|lastcognome=Lenstra, Jr.|firstnome=A. K.|coauthorscoautori=Lenstra, Jr., H. W.|titletitolo=Algorithms in number theory|journalrivista=Handbook of Theoretical Computer Science: Algorithms and Complexity|volume=A|publishereditore=The MIT Press|___locationcittà=Amsterdam and New York|pagespagine=673–715|yearanno=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 testitest di primalità e consiste nel cercare di costruire un gruppo la cui dimensione implichi la primalità del numero investigato. Nel caso deldell'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.
AttualmenteAl (aprile 2008),2011 il più grande primo conosciuto, la cui primalità sia stata provata con l'ECPP è il [[primo LR che consta di Mills]]26.643 cifre.<ref>{{Cita web|lingua=fr|titolo=Quelques nombres premiers prouvés par mes programmes|url=http://www.lix.polytechnique.fr/~morain/Primes/myprimes.html}}</ref>
:<math>(((((((((2^3+3)^3+30)^3+6)^3+80)^3+12)^3+450)^3+894)^3+3636)^3+70756)^3+97220,</math><ref>Martin, Marcel. [http://www.ellipsa.net/primo/record.html#03 ''ECPP records (multiprocessor)'']. Retrieved on [[2007-06-09]].</ref><ref>Caldwell, Chris. [http://primes.utm.edu/top20/page.php?id=27 ''The Top Twenty: Elliptic Curve Primality Proof''] from the [[Prime Pages]]. Retrieved on [[2007-06-09]].</ref>
che consta di 20.562 cifre.
==Note==
{{<references}} />
== Collegamenti esterni ==
* {{Collegamenti esterni}}
*[http://citeseer.ist.psu.edu/rd/9227084%2C72628%2C1%2C0.25%2CDownload/http://citeseer.ist.psu.edu/cache/papers/cs/426/ftp:zSzzSzftp.inria.frzSzINRIAzSzpublicationzSzpubli-ps-gzzSzRRzSzRR-1256.pdf/atkin93elliptic.pdf Elliptic Curves and Primality Proving] di [[A. O. L. Atkin|Atkin]] e Morain
* {{en}} Chris Caldwell, [http://primes.utm.edu/prove/prove4_2.html I più grandi numeri provati essere primi con l'ECPP] ▼* La [http://mathworld.wolfram.com/EllipticCurvePrimalityProving.html pagina relativa al'ECPP] su [[MathWorld]]
* {{en}} François Morain, [http://www.lix.polytechnique.fr/~morain/Prgms/ecpp.english.html "The ECPP home page"]
▲*Chris Caldwell, [http://primes.utm.edu/prove/prove4_2.html I più grandi numeri provati essere primi con l'ECPP]
*François Morain{{en}} Marcel Martin, [http://www.lixellipsa.polytechnique.freu/~morainpublic/Prgmsprimo/ecpp.englishprimo.html "TheUn'implementazione ECPPper homeLinux page"dell'algoritmo]
*Marcel Martin, [http://www.ellipsa.net/public/primo/index.html Un'implementazione per Windows dell'algoritmo]
[[Categoria:Test di primalità]]
[[en:Elliptic curve primality proving]]
[[pl:Test pierwszości ECPP]]
| 