Test de primalidad de Adleman-Pomerance-Rumely

En teoria de números computacional, la prova de primalidad de Adleman-Pomerance-Rumely és un algoritme per a determinar si un número és primer. A diferència d'atres algoritmes més eficients per a este fi, evita l'us de números aleatoris, per lo que és un test de primalidad determinístico. Du el nom dels seus descobridors, Leonard Adleman, Carl Pomerance i Robert Rumely. La prova involucra aritmètica en cossos ciclotòmics.

Més tart va ser millorat per Henri Cohen i Hendrik Lenstra, i és comunament denominat com APR-CL. Pot provar la primalidad d'un sancer n en el temps:

$(\log n{)}^{O(\log \log \log n)}.$

Implementacions de software

• UBASIC proporciona una implementació baix el nom de APRT-CLE (APR Test CL estendre)
• Una aplicació de factorisació que usa APR-CL en certes condicions (còdic font inclós)
• Pari/GP usa APR-CL condicionalmente en la seua implementació de isprime().
• mpz_aprcl és una implementació de còdic obert que utilisa C i GMP.
• LLR de Jean Penné usa APR-CL en certs tipos de proves principals com una opció alternativa.

Bibliografia

• Adleman, Leonard M.; Pomerance, Carl; Rumely, Robert S.(1983).«On distinguishing prime numbers from composite numbers».Annals of Mathematics.117(1): 173–206.doi:10.2307/2006975.
• Riesel, Hans (1994). Prime Numbers and Computer Methods for Factorization, Birkhäuser, pp. 131–136. ISBN 978-0-8176-3743-9.
• TAE i TAE-CL