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 è primo. Diversamente da altri algoritmi più efficienti per questo scopo, esso evita l'uso di numeri causali, perciò è un test di primalità deterministico. Prende il nome dai suoi scopritori, Leonard Adleman, Carl Pomerance e Robert Rumely. Il test implica l'aritmetica nei campi ciclotomici.

Fu migliorato in seguito da 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:

$O((\ln n)^{c\,\ln \,\ln \,\ln n}).$

Bibliografia

• Leonard M. Adleman, Carl Pomerance e Robert S. Rumely, On distinguishing prime numbers from composite numbers, in Annals of Mathematics, vol. 117, n. 1, 1983, 173–206, DOI:10.2307/2006975.
• Henri Cohen e Hendrik W., Jr. Lenstra, Primality testing and Jacobi sums, in Mathematics of Computation, vol. 42, n. 165, 1984, 297–330, DOI:10.2307/2007581.
• Hans Riesel, Prime Numbers and Computer Methods for Factorization, Birkhauser, 1994, pp. 131–136, ISBN 0-8176-3743-5.

Collegamenti esterni

• (EN) APR and APR-CL, su primes.utm.edu.
• (EN) Una applet di fattorizzazione che usa APR-CL in certe condizioni (codice sorgente incluso)
• (EN) Pari/GP usa conditionalmente APR-CL nella sua implementazione di isprime().