Adleman–Pomerance–Rumely primality test

From Wikipedia, the free encyclopedia

The Adleman–Pomerance–Rumely primality test (APR) is a deterministic algorithm that tests if a positive integer is prime. It is named after its discoverers, Leonard Adleman, Carl Pomerance, and Robert Rumely.

It was later improved by Henri Cohen and Arjen Lenstra and called APRT-CL. It is often used with UBASIC under the name APRT-CLE (APRT-CL extended) and has complexity

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

[edit] External links

APR and APR-CL
A factoring applet that uses APR-CL on certain conditions (source code included)

v • d • e Number-theoretic algorithms

Primality tests	AKS · APR · Ballie-PSW · ECPP · Fermat · Lucas–Lehmer · Lucas–Lehmer (Mersenne numbers) · Lucas–Lehmer–Riesel · Proth's theorem · Pépin's · Solovay-Strassen · Miller-Rabin · Trial division

Sieving algorithms	Sieve of Atkin · Sieve of Eratosthenes · Sieve of Sundaram · Wheel factorization

Integer factorization algorithms	CFRAC · Dixon's · ECM · Euler's · Pollard's rho · P - 1 · P + 1 · QS · GNFS · SNFS · rational sieve · Fermat's · Shanks' square forms · Trial division · Shor's algorithm

Other algorithms	Ancient Egyptian multiplication · Aryabhata · Binary GCD · Chakravala · Euclidean · Extended Euclidean · integer relation algorithm · integer square root · Modular exponentiation · Shanks-Tonelli

Italics indicate that algorithm is for numbers of special forms; bold indicates deterministic algorithm for primality tests.