Adleman-Pomerance-Rumely Primality Test

A modified Miller's Primality Test which gives a guarantee of Primality orCompositeness. The Algorithm's running time for a number has been proved to beas for some . It was simplified by Cohen and Lenstra (1984), implemented byCohen 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 , , 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.

• Newman-Conway Sequence
• Newton-Cotes Formulas
• Newtonian Form
• Newton Number
• Newton-Raphson Fractal
• Newton-Raphson Method
• Newton's Backward Difference Formula
• Newton's Diverging Parabolas
• Newton's Divided Difference Interpolation Formula
• Newton's Formulas
• Newton's Forward Difference Formula
• Newton's Identities
• Newton's Iteration
• Newton's Method
• Newton's Parallelogram
• Newton's Relations
• Newton's Theorem
• Next Prime
• Nexus Number
• Neyman-Pearson Lemma
• Nicholson's Formula
• Nicomachus's Theorem
• Nicomedes' Conchoid
• Nielsen-Ramanujan Constants
• Nielsen's Spiral