Rabin-Miller primality test: composite numbers which pass it
HTML articles powered by AMS MathViewer
- by F. Arnault PDF
- Math. Comp. 64 (1995), 355-361 Request permission
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
-
C. Batut, Aspects algorithmiques du système de calcul arithmétique en multiprécision PARI, Thesis, Bordeaux I University, France, 1989.
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.
H. Cohen, Cryptographie, factorisation et primalité: l’utilisation des courbes elliptiques, J. Annuelle Soc. Math. France, 1987.
D. A. Cox, Primes of the form ${x^2} + n{y^2}$, Interscience, New York, 1989.
- John D. Dixon, Factorization and primality tests, Amer. Math. Monthly 91 (1984), no. 6, 333–352. MR 750520, DOI 10.2307/2322136 IBM Computer Algebra Group, The Scratchpad computer algebra system interactive environment users guide (R. Sutor, ed.), 1989.
- Kenneth F. Ireland and Michael I. Rosen, A classical introduction to modern number theory, Graduate Texts in Mathematics, vol. 84, Springer-Verlag, New York-Berlin, 1982. Revised edition of Elements of number theory. MR 661047
- Gerhard Jaeschke, On strong pseudoprimes to several bases, Math. Comp. 61 (1993), no. 204, 915–926. MR 1192971, DOI 10.1090/S0025-5718-1993-1192971-8
- Richard D. Jenks and Robert S. Sutor, AXIOM, Numerical Algorithms Group, Ltd., Oxford; Springer-Verlag, New York, 1992. The scientific computation system; With a foreword by David V. Chudnovsky and Gregory V. Chudnovsky. MR 1179424
- Donald E. Knuth, The art of computer programming. Vol. 2, 2nd ed., Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms. MR 633878
- Carl Pomerance, J. L. Selfridge, and Samuel S. Wagstaff Jr., The pseudoprimes to $25\cdot 10^{9}$, Math. Comp. 35 (1980), no. 151, 1003–1026. MR 572872, DOI 10.1090/S0025-5718-1980-0572872-7
- Michael O. Rabin, Probabilistic algorithm for testing primality, J. Number Theory 12 (1980), no. 1, 128–138. MR 566880, DOI 10.1016/0022-314X(80)90084-0
- Hans Riesel, Prime numbers and computer methods for factorization, Progress in Mathematics, vol. 57, Birkhäuser Boston, Inc., Boston, MA, 1985. MR 897531, DOI 10.1007/978-1-4757-1089-2
Additional Information
- © Copyright 1995 American Mathematical Society
- Journal: Math. Comp. 64 (1995), 355-361
- MSC: Primary 11Y11; Secondary 11A15, 11A51
- DOI: https://doi.org/10.1090/S0025-5718-1995-1260124-2
- MathSciNet review: 1260124