Adleman-Pomerance-Rumely Primality Test

A modified Miller's Primality Test which gives a guarantee of Primality or Compositeness. The Algorithm's running time for a number $N$ has been proved to be as ${\mathcal O}((\ln N)^{c\ln\ln\ln N})$ for some $c>0$. It was simplified by Cohen and Lenstra (1984), implemented by Cohen and Lenstra (1987), and subsequently optimized by Bosma and van der Hulst (1990).

References

Adleman, L. M.; Pomerance, C.; and Rumely, R. S. ``On Distinguishing Prime Numbers from Composite Number.'' Ann. Math. 117, 173-206, 1983.

Bosma, W. and van der Hulst, M.-P. ``Faster Primality Testing.'' In Advances in Cryptology, Proc. Eurocrypt '89, Houthalen, April 10-13, 1989 (Ed. J.-J. Quisquater). New York: Springer-Verlag, 652-656, 1990.

Brillhart, J.; Lehmer, D. H.; Selfridge, J.; Wagstaff, S. S. Jr.; and Tuckerman, B. Factorizations of $b^n\pm 1$, $b=2$, $3, 5, 6, 7, 10, 11, 12$ Up to High Powers, rev. ed. Providence, RI: Amer. Math. Soc., pp. lxxxiv-lxxxv, 1988.

Cohen, H. and Lenstra, A. K. ``Primality Testing and Jacobi Sums.'' Math. Comput. 42, 297-330, 1984.

Cohen, H. and Lenstra, A. K. ``Implementation of a New Primality Test.'' Math. Comput. 48, 103-121, 1987.

Mihailescu, P. ``A Primality Test Using Cyclotomic Extensions.'' In Applied Algebra, Algebraic Algorithms and Error-Correcting Codes (Proc. AAECC-6, Rome, July 1988). New York: Springer-Verlag, pp. 310-323, 1989.