Primality Test

A test to determine whether or not a given number is Prime. The Rabin-Miller Strong Pseudoprime Test is aparticularly efficient Algorithm used by Mathematica version 2.2 (Wolfram Research, Champaign, IL). Likemany such algorithms, it is a probabilistic test using Pseudoprimes, and can potentially (althoughwith very small probability) falsely identify a Composite Number as Prime (although not vice versa). UnlikePrime Factorization, primality testing is believed to be a P-Problem (Wagon 1991). In order to guaranteeprimality, an almost certainly slower algorithm capable ofgenerating a Primality Certificate must be used.

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

• Reduction Theorem
• Redundancy
• Reeb Foliation
• Reef Knot
• Re-Entrant Circuit
• Refinement
• Reflection
• Reflection Property
• Reflection Relation
• Reflexible
• Reflexible Map
• Reflexive Closure
• Reflexive Graph
• Reflexive Reduction
• Reflexive Relation
• Reflexivity
• Region
• Regression
• Regression Coefficient
• Regula Falsi
• Regular Function
• Regular Graph
• Regular Isotopy
• Regular Isotopy Invariant
• Regularity Theorem