Primality Test

A test to determine whether or not a given number is Prime. The Rabin-Miller Strong Pseudoprime Test is a particularly efficient Algorithm used by Mathematica ${}^{\scriptstyle\circledRsymbol}$ version 2.2 (Wolfram Research, Champaign, IL). Like many such algorithms, it is a probabilistic test using Pseudoprimes, and can potentially (although with very small probability) falsely identify a Composite Number as Prime (although not vice versa). Unlike Prime Factorization, primality testing is believed to be a P-Problem (Wagon 1991). In order to guarantee primality, an almost certainly slower algorithm capable of generating a Primality Certificate must be used.

See also Adleman-Pomerance-Rumely Primality Test, Fermat's Little Theorem Converse, Fermat's Primality Test, Fermat's Theorem, Lucas-Lehmer Test, Miller's Primality Test, Pépin's Test, Pocklington's Theorem, Proth's Theorem, Pseudoprime, Rabin-Miller Strong Pseudoprime Test, Ward's Primality Test, Wilson's Theorem

References

Beauchemin, P.; Brassard, G.; Crépeau, C.; Goutier, C.; and Pomerance, C. ``The Generation of Random Numbers that are Probably Prime.'' J. Crypt. 1, 53-64, 1988.

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. lviii-lxv, 1988.

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

Knuth, D. E. The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, 2nd ed. Reading, MA: Addison-Wesley, 1981.

Riesel, H. Prime Numbers and Computer Methods for Factorization, 2nd ed. Boston, MA: Birkhäuser, 1994.

Wagon, S. Mathematica in Action. New York: W. H. Freeman, pp. 15-17, 1991.