Adleman–Pomerance–Rumely primalitetstest

Inom beräkningstalteori är Adleman -Pomerance-Rumely-primalitetstestet en algoritm för att avgöra om ett tal är primtal . Till skillnad från andra, mer effektiva algoritmer för detta ändamål undviker den användningen av slumptal, så det är ett deterministiskt primatitetstest . Den är uppkallad efter dess upptäckare, Leonard Adleman , Carl Pomerance och Robert Rumely . Testet involverar aritmetik i cyklotomiska fält .

Den förbättrades senare av Henri Cohen och Hendrik Willem Lenstra , vanligen kallad APR-CL . Det kan testa primaliteten för ett heltal n i tiden:

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

Mjukvaruimplementationer

• UBASIC tillhandahåller en implementering under namnet APRT-CLE (APR Test CL extended)
• En factoring-applet som använder APR-CL på vissa villkor (källkod ingår)
• Pari/GP använder APR-CL villkorligt i sin implementering av isprime().
• mpz_aprcl är en implementering med öppen källkod som använder C och GMP.
• Jean Pennés LLR använder APR-CL på vissa typer av prime-tester som ett reservalternativ.

•   Adleman, Leonard M. ; Pomerance, Carl ; Rumely, Robert S. (1983). "Om att skilja primtal från sammansatta tal". Annals of Mathematics . 117 (1): 173–206. doi : 10.2307/2006975 . JSTOR 2006975 .
•   Cohen, Henri ; Lenstra, Hendrik W., Jr. (1984). "Primalitetstestning och Jacobi-summor" . Beräkningsmatematik . 42 (165): 297–330. doi : 10.2307/2007581 . JSTOR 2007581 .
•   Riesel, Hans (1994). Primtal och datormetoder för faktorisering . Birkhäuser. s. 131 –136. ISBN 978-0-8176-3743-9 .
• APR och APR-CL