Adleman–Pomerance–Rumely primality test
Encyclopedia
In computational number theory
, the Adleman–Pomerance–Rumely primality test is an algorithm
for determining whether a number is prime
. Unlike other, more efficient algorithms for this purpose, it avoids the use of random numbers, so it is a deterministic
primality test
. It is named after its discoverers, Leonard Adleman
, Carl Pomerance
, and Robert Rumely. The test involves arithmetic in cyclotomic field
s.
It was later improved by Henri Cohen and Hendrik Willem Lenstra and called APRT-CL (or APRCL). It is often used with UBASIC
under the name APRT-CLE (APRT-CL extended) and can test primality of an integer n in time:
Computational number theory
In mathematics, computational number theory, also known as algorithmic number theory, is the study of algorithms for performing number theoretic computations...
, the Adleman–Pomerance–Rumely primality test is an algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
for determining whether a number is prime
Prime number
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...
. Unlike other, more efficient algorithms for this purpose, it avoids the use of random numbers, so it is a deterministic
Deterministic algorithm
In computer science, a deterministic algorithm is an algorithm which, in informal terms, behaves predictably. Given a particular input, it will always produce the same output, and the underlying machine will always pass through the same sequence of states...
primality test
Primality test
A primality test is an algorithm for determining whether an input number is prime. Amongst other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating whether the input number is prime or not...
. It is named after its discoverers, Leonard Adleman
Leonard Adleman
Leonard Max Adleman is an American theoretical computer scientist and professor of computer science and molecular biology at the University of Southern California. He is known for being a co-inventor of the RSA cryptosystem in 1977, and of DNA computing...
, Carl Pomerance
Carl Pomerance
Carl Bernard Pomerance is a well-known 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 has at least 7 distinct prime factors. He immediately joined the faculty at the...
, and Robert Rumely. The test involves arithmetic in cyclotomic field
Cyclotomic field
In number theory, a cyclotomic field is a number field obtained by adjoining a complex primitive root of unity to Q, the field of rational numbers...
s.
It was later improved by Henri Cohen and Hendrik Willem Lenstra and called APRT-CL (or APRCL). It is often used with UBASIC
UBASIC
UBASIC is a freeware BASIC interpreter written by Yuji Kida at Rikkyo University in Japan, specialized for mathematical computing.-Features:...
under the name APRT-CLE (APRT-CL extended) and can test primality of an integer n in time:
External links
- APR and APR-CL
- A factoring applet that uses APR-CL on certain conditions (source code included)
- Pari/GP uses APR-CL conditionally in its implementation of isprime.