The Adleman–Pomerance–Rumely primality test (APR) 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 Henri Cohen and Arjen 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:
External links
- APR and APR-CL
- A factoring applet that uses APR-CL on certain conditions (source code included)
References
- Adleman, Leonard M.; Pomerance, Carl and Rumely, Robert S. (1983). "On distinguishing prime numbers from composite numbers". Ann. Math. 117: pp. 173–206.
- Cohen, Henri; Lenstra, Hendrik W. Jr. (1984). "Primality testing and Jacobi sums". Math. Comp. 42: pp. 297–330.
- Riesel, Hans (1994). Prime numbers and computer methods for factorization. Birkhauser. pp. 131–136. ISBN 0-8176-3743-5.
|
||||||||||||||||||||||||||
| O(n log n) | This algorithms-related article is a stub. You can help Wikipedia by expanding it. |
 |
This number theory-related article is a stub. You can help Wikipedia by expanding it. |
This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)
