Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Rabin-Miller primality test: composite numbers which pass it

Author: F. Arnault
Journal: Math. Comp. 64 (1995), 355-361
MSC: Primary 11Y11; Secondary 11A15, 11A51
MathSciNet review: 1260124
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The Rabin-Miller primality test is a probabilistic test which can be found in several algebraic computing systems (such as Pari, Maple, ScratchPad) because it is very easy to implement and, with a reasonable amount of computing, indicates whether a number is composite or "probably prime" with a very low probability of error. In this paper, we compute composite numbers which are strong pseudoprimes to several chosen bases. Because these bases are those used by the ScratchPad implementation of the test, we obtain, by a method which differs from a recent one by Jaeschke, composite numbers which are found to be "probably prime" by this test.

References [Enhancements On Off] (What's this?)

  • [1] C. Batut, Aspects algorithmiques du système de calcul arithmétique en multiprécision PARI, Thesis, Bordeaux I University, France, 1989.
  • [2] B. W. Char, K. O. Geddes, G. H. Gonnet, B. L. Leong, M. B. Monagan, and S. M. Watt, Maple library reference manual, Springer-Verlag, New York, 1991.
  • [3] H. Cohen, Cryptographie, factorisation et primalité: l'utilisation des courbes elliptiques, J. Annuelle Soc. Math. France, 1987.
  • [4] D. A. Cox, Primes of the form $ {x^2} + n{y^2}$, Interscience, New York, 1989.
  • [5] J. D. Dixon, Factorization and primality tests, Amer. Math. Monthly 91 (1974), 333-352. MR 750520 (87c:11121a)
  • [6] IBM Computer Algebra Group, The Scratchpad computer algebra system interactive environment users guide (R. Sutor, ed.), 1989.
  • [7] K. Ireland and M. Rosen, A classical introduction to modern number theory, Springer-Verlag, New York, 1982. MR 661047 (83g:12001)
  • [8] G. Jaeschke, On strong pseudoprimes to several bases, Math. Comp. 61 (1993), 915-926. MR 1192971 (94d:11004)
  • [9] R. Jenks and R. Sutor, Axiom, the scientific computation system, Springer-Verlag, New York, 1992. MR 1179424 (95k:68089)
  • [10] D. E. Knuth, The art of computer programming. Vol. 2: Semi-numerical algorithms, Addison-Wesley, Reading, MA, 1973. MR 633878 (83i:68003)
  • [11] C. Pomerance, J. L. Selfridge, and S. S. Wagstaff, Jr., The pseudoprimes to $ 25 \cdot {10^9}$, Math. Comp. 35 (1980), 1003-1026. MR 572872 (82g:10030)
  • [12] M. O. Rabin, Probabilistic algorithms for testing primality, J. Number Theory 12 (1980), 128-138. MR 566880 (81f:10003)
  • [13] H. Riesel, Prime numbers and computer methods for factorizations, Birkhäuser, Boston, MA, 1985. MR 897531 (88k:11002)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 11Y11, 11A15, 11A51

Retrieve articles in all journals with MSC: 11Y11, 11A15, 11A51

Additional Information

Keywords: Primality testing, strong pseudoprimes, biquadratic reciprocity
Article copyright: © Copyright 1995 American Mathematical Society

American Mathematical Society