Visualizza wikitesto di Test di primalità di Adleman-Pomerance-Rumely

Nella [[teoria computazionale dei numeri]], il '''test di primalità di Adleman-Pomerance-Rumely''' è un [[algoritmo]] per determinare se un numero è [[Numero primo|primo]]. Diversamente da altri algoritmi più efficienti per questo scopo, esso evita l'uso di numeri causali, perciò è un [[test di primalità]] [[algoritmo deterministico|deterministico]]. Prende il nome dai suoi scopritori, [[Leonard Adleman]], [[Carl Pomerance]] e [[Robert Rumely]]. Il test implica l'aritmetica nei [[Estensione ciclotomica|campi ciclotomici]].

Fu migliorato in seguito da [[Henri Cohen (matematico)|Henri Cohen]] e [[Hendrik Willem Lenstra]] e chiamato APRT-CL (o APRCL). È usato spesso con [[UBASIC]] sotto il nome APRT-CLE (APRT-CL esteso) e può testare la primalità di un intero ''n'' nel tempo:

: <math>O((\ln n)^{c\,\ln\,\ln\,\ln n}).</math>

==Bibliografia==
* {{cita testo| cognome1=Adleman | nome1=Leonard M. | wkautore1=Leonard Adleman | cognome2=Pomerance | nome2=Carl | wkautore2=Carl Pomerance | cognome3=Rumely | nome3=Robert S. | wkautore3=Robert Rumely | titolo=On distinguishing prime numbers from composite numbers | rivista=[[Annals of Mathematics]] |volume=117 | numero=1 | anno=1983 | pagine=173–206 | doi=10.2307/2006975 }}
* {{cita testo| cognome1=Cohen | nome1=Henri | wkautore1=Henri Cohen (matematico)| 
cognome2=Lenstra | nome2=Hendrik W., Jr. | wkautore2=Hendrik Lenstra | titolo=Primality testing and Jacobi sums | rivista=[[Mathematics of Computation]] | volume=42 | anno=1984 | pagine=297–330 | numero=165 | doi=10.2307/2007581 }}
* {{cita libro | cognome=Riesel | nome=Hans | linkautore=Hans Riesel | titolo=Prime Numbers and Computer Methods for Factorization | url=https://archive.org/details/primenumberscomp0000ries | editore=Birkhauser | anno=1994 | isbn=0-8176-3743-5 | pagine=131–136 }}

==Collegamenti esterni==
* {{cita web|http://primes.utm.edu/prove/prove4_1.html|APR and APR-CL|lingua=en}}
* {{en}} Una [https://www.alpertron.com.ar/ECM.HTM applet di fattorizzazione] che usa APR-CL in certe condizioni (codice sorgente incluso)
* {{en}} [https://web.archive.org/web/20190929045643/http://pari.math.u-bordeaux.fr/ Pari/GP] usa conditionalmente APR-CL nella sua implementazione di isprime().

{{Portale|Informatica|Matematica}}

[[Categoria:Test di primalità]]