In
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 Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...
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 the metaphysical view that all events within the universe (or multiverse) can occur only in one possible way. Deterministic theories throughout the history of philosophy have developed from diverse and sometimes overlapping mo ...
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 wheth ...
. 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. He is also known for the creation of the field of DNA computin ...
,
Carl Pomerance, and
Robert Rumely. The test involves arithmetic in
cyclotomic field
In algebraic number theory, a cyclotomic field is a number field obtained by adjoining a complex root of unity to \Q, the field of rational numbers.
Cyclotomic fields played a crucial role in the development of modern algebra and number theory ...
s.
It was later improved by
Henri Cohen and
Hendrik Willem Lenstra, commonly referred to as APR-CL. It can test primality of an integer ''n'' in time:
:
Software implementations
*
UBASIC provides an implementation under the name APRT-CLE (APR Test CL extended)
*
factoring appletthat uses APR-CL on certain conditions (source code included)
Pari/GPuses APR-CL conditionally in its implementation of isprime().
mpz_aprclis an open source implementation using C and GMP.
uses APR-CL on certain types of prime tests as a fallback option.
References
*
*
*
Primality tests
Quasi-polynomial time algorithms
{{numtheory-stub