Adleman–Pomerance–Rumely primality test

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 fields.

It was later improved by

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

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

Software implementations

• UBASIC provides an implementation under the name APRT-CLE (APR Test CL extended)
• A 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.
• Jean Penné's LLR uses APR-CL on certain types of prime tests as a fallback option.

References

• JSTOR 2006975
  .
• JSTOR 2007581
  .
• ISBN 978-0-8176-3743-9
  .
• APR and APR-CL