Adleman-Pomerance-Rumely primality test

From Wikipedia, the free encyclopedia

Categories: Computer science stubs | Number theory stubs | Primality tests

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

Failed to parse (Missing texvc executable; please see math/README to configure.): (\log n)^{O(\log\,\log \,\log n)}

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) · 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.