computational number theory In mathematics and computer science, computational number theory, also known as algorithmic number theory, is the study of computational methods for investigating and solving problems in number theory and arithmetic geometry, including algorithm ...

, the Adleman–Pomerance–Rumely primality test is an

algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...

for determining whether a number is

prime A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...

. Unlike other, more efficient algorithms for this purpose, it avoids the use of random numbers, so it is a

deterministic Determinism is a philosophical view, where all events are determined completely by previously existing causes. Deterministic theories throughout the history of philosophy have developed from diverse and sometimes overlapping motives and cons ...

primality test A primality test is an algorithm for determining whether an input number is prime. Among other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating whet ...

. It is named after its discoverers,

Leonard Adleman Leonard Adleman (born December 31, 1945) is an American computer scientist. He is one of the creators of the RSA encryption algorithm, for which he received the 2002 Turing Award, often called the Nobel prize of Computer science. He is also kno ...

Carl Pomerance Carl Bernard Pomerance (born 1944 in Joplin, Missouri) is an American number theorist. He attended college at Brown University and later received his Ph.D. from Harvard University in 1972 with a dissertation proving that any odd perfect number ...

, and

Robert Rumely Robert Scott Rumely (born 1952) is a professor of mathematics at the University of Georgia who specializes in number theory and arithmetic geometry. He is one of the inventors of the Adleman–Pomerance–Rumely primality test. Life Rumely was bo ...

. The test involves arithmetic in

cyclotomic field In number theory, a cyclotomic field is a number field obtained by adjoining a complex root of unity to , the field of rational numbers. Cyclotomic fields played a crucial role in the development of modern algebra and number theory because of ...

s. It was later improved by Henri Cohen and

Hendrik Willem Lenstra Hendrik Willem Lenstra Jr. (born 16 April 1949, Zaandam) is a Dutch mathematician. Biography Lenstra received his doctorate from the University of Amsterdam in 1977 and became a professor there in 1978. In 1987 he was appointed to the facult ...

, commonly referred to as APR-CL. It can test primality of an integer ''n'' in time: :

(\log n)^.

Software implementations

UBASIC UBASIC is a freeware ( public domain software without source code) BASIC interpreter written by Yuji Kida at Rikkyo University in Japan, specialized for mathematical computing. Features UBASIC is a ready-to-run language that does not need to ...

provides an implementation under the name APRT-CLE (APR Test CL extended) *
factoring applet
that uses APR-CL on certain conditions (source code included)
Pari/GP
uses APR-CL conditionally in its implementation of isprime().
mpz_aprcl
is an open source implementation using C and GMP.

uses APR-CL on certain types of prime tests as a fallback option.

References

* * *

Primality tests {{numtheory-stub