Finding strong pseudoprimes to several bases
Author:
Zhenxiang Zhang
Journal:
Math. Comp. 70 (2001), 863872
MSC (2000):
Primary 11Y11, 11A15, 11A51
Published electronically:
February 17, 2000
MathSciNet review:
1697654
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: Define to be the smallest strong pseudoprime to all the first prime bases. If we know the exact value of , we will have, for integers , a deterministic primality testing algorithm which is not only easier to implement but also faster than either the Jacobi sum test or the elliptic curve test. Thanks to Pomerance et al. and Jaeschke, are known for . Upper bounds for were given by Jaeschke. In this paper we tabulate all strong pseudoprimes (spsp's) to the first ten prime bases which have the form with odd primes and There are in total 44 such numbers, six of which are also spsp(31), and three numbers are spsp's to both bases 31 and 37. As a result the upper bounds for and are lowered from 28 and 29decimaldigit numbers to 22decimaldigit numbers, and a 24decimaldigit upper bound for is obtained. The main tools used in our methods are the biquadratic residue characters and cubic residue characters. We propose necessary conditions for to be a strong pseudoprime to one or to several prime bases. Comparisons of effectiveness with both Jaeschke's and Arnault's methods are given.
 1.
Leonard
M. Adleman, Carl
Pomerance, and Robert
S. Rumely, On distinguishing prime numbers from composite
numbers, Ann. of Math. (2) 117 (1983), no. 1,
173–206. MR
683806 (84e:10008), http://dx.doi.org/10.2307/2006975
 2.
W.
R. Alford, Andrew
Granville, and Carl
Pomerance, There are infinitely many Carmichael numbers, Ann.
of Math. (2) 139 (1994), no. 3, 703–722. MR 1283874
(95k:11114), http://dx.doi.org/10.2307/2118576
 3.
W.
R. Alford, Andrew
Granville, and Carl
Pomerance, On the difficulty of finding reliable witnesses,
Algorithmic number theory (Ithaca, NY, 1994) Lecture Notes in Comput.
Sci., vol. 877, Springer, Berlin, 1994, pp. 1–16. MR 1322705
(96d:11136), http://dx.doi.org/10.1007/3540586911_36
 4.
F.
Arnault, RabinMiller primality test: composite
numbers which pass it, Math. Comp.
64 (1995), no. 209, 355–361. MR 1260124
(95c:11152), http://dx.doi.org/10.1090/S00255718199512601242
 5.
A.
O. L. Atkin and F.
Morain, Elliptic curves and primality
proving, Math. Comp. 61
(1993), no. 203, 29–68. MR 1199989
(93m:11136), http://dx.doi.org/10.1090/S0025571819931199989X
 6.
W.Bosma and M.P. van der Hulst, Primality proving with cyclotomy, thesis, Univ. of Amsterdam, 1990.
 7.
H.
Cohen and A.
K. Lenstra, Implementation of a new primality
test, Math. Comp. 48
(1987), no. 177, 103–121,
S1–S4. MR
866102 (88c:11080), http://dx.doi.org/10.1090/S00255718198708661022
 8.
H.
Cohen and H.
W. Lenstra Jr., Primality testing and Jacobi
sums, Math. Comp. 42
(1984), no. 165, 297–330. MR 726006
(86g:11078), http://dx.doi.org/10.1090/S0025571819840726006X
 9.
David
A. Cox, Primes of the form
𝑥²+𝑛𝑦², A WileyInterscience
Publication, John Wiley & Sons, Inc., New York, 1989. Fermat, class
field theory and complex multiplication. MR 1028322
(90m:11016)
 10.
Kenneth
F. Ireland and Michael
I. Rosen, A classical introduction to modern number theory,
Graduate Texts in Mathematics, vol. 84, SpringerVerlag, New
YorkBerlin, 1982. Revised edition of Elements of number theory. MR 661047
(83g:12001)
 11.
Gerhard
Jaeschke, On strong pseudoprimes to several
bases, Math. Comp. 61
(1993), no. 204, 915–926. MR 1192971
(94d:11004), http://dx.doi.org/10.1090/S00255718199311929718
 12.
Gary
L. Miller, Riemann’s hypothesis and tests for primality,
J. Comput. System Sci. 13 (1976), no. 3,
300–317. Working papers presented at the ACMSIGACT Symposium on the
Theory of Computing (Albuquerque, N.M., 1975). MR 0480295
(58 #470a)
 13.
Louis
Monier, Evaluation and comparison of two efficient probabilistic
primality testing algorithms, Theoret. Comput. Sci.
12 (1980), no. 1, 97–108. MR 582244
(82a:68078), http://dx.doi.org/10.1016/03043975(80)900079
 14.
Carl
Pomerance, J.
L. Selfridge, and Samuel
S. Wagstaff Jr., The pseudoprimes to
25⋅10⁹, Math. Comp.
35 (1980), no. 151, 1003–1026. MR 572872
(82g:10030), http://dx.doi.org/10.1090/S00255718198005728727
 15.
Michael
O. Rabin, Probabilistic algorithm for testing primality, J.
Number Theory 12 (1980), no. 1, 128–138. MR 566880
(81f:10003), http://dx.doi.org/10.1016/0022314X(80)900840
 1.
 L.M.Adleman, C.Pomerance and R.S.Rumely, On distinguishing prime numbers from composite numbers., Annals of Math., 117 (1983), 173206. MR 84e:10008
 2.
 W.R.Alford, A.Granville and C.Pomerance, There are infinitely many Carmichael numbers, Annals of Math., 140 (1994), 703722. MR 95k:11114
 3.
 W.R.Alford, A.Granville and C.Pomerance, On the difficulty of finding reliable witnesses, Algorithmic Number Theory, pp.116, Lecture Notes in Computer Science, vol. 877, SpringerVerlag, Berlin, 1994. MR 96d:11136
 4.
 F.Arnault, RabinMiller primality test: Composite numbers which pass it, Math. Comp., 64 (1995), 355361. MR 95c:11152
 5.
 A.O.L.Atkin and F.Morain, Elliptic curves and primality proving, Math. Comp., 61 (1993), 2968. MR 93m:11136
 6.
 W.Bosma and M.P. van der Hulst, Primality proving with cyclotomy, thesis, Univ. of Amsterdam, 1990.
 7.
 H.Cohen and A.K.Lenstra, Implementation of a new primality test, Math. Comp., 48 (1987), 103121. MR 88c:11080
 8.
 H.Cohen and H.W.Lenstra,Jr., Primality testing and Jacobi sums, Math. Comp., 42 (1984), 297330. MR 86g:11078
 9.
 D.A.Cox, Primes of the form , Interscience, New York, 1989. MR 90m:11016
 10.
 K.Ireland and M.Rosen, A classical introduction to modern number theory, SpringerVerlag, New York, 1982. MR 83g:12001
 11.
 G.Jaeschke, On strong pseudoprimes to several bases, Math. Comp., 61 (1993),915926. MR 94d:11004
 12.
 G.Miller, Riemann's hypothesis and tests for primality, J.Comput. and System Sc., 13 (1976),300317. MR 58:470a
 13.
 Louis Monier, Evaluation and comparison of two efficient probabilistic primality testing algorithms, Theoretical Computer Science, 12 (1980), 97108. MR 82a:68078
 14.
 C.Pomerance, J.L.Selfridge and Samuel S.Wagstaff,Jr., The pseudoprimes to , Math. Comp., 35 (1980), 10031026. MR 82g:10030
 15.
 M.O.Rabin, Probabilistic algorithms for testing primality, J.Number Theory, 12 (1980), 128138. MR 81f:10003
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC (2000):
11Y11,
11A15,
11A51
Retrieve articles in all journals
with MSC (2000):
11Y11,
11A15,
11A51
Additional Information
Zhenxiang Zhang
Affiliation:
Department of Mathematics, Anhui Normal University, 241000 Wuhu, Anhui, P. R. China;
State Key Laboratory of Information Security, Graduate School USTC, 100039 Beijing, P. R. China
Email:
zhangzhx@mail.ahwhptt.net.cn
DOI:
http://dx.doi.org/10.1090/S0025571800012151
PII:
S 00255718(00)012151
Keywords:
Strong pseudoprimes,
RabinMiller test,
biquadratic residue characters,
cubic residue characters,
Chinese remainder theorem
Received by editor(s):
August 1, 1997
Received by editor(s) in revised form:
June 22, 1998, and May 24, 1999
Published electronically:
February 17, 2000
Additional Notes:
Supported by the China State Educational Commission Science Foundation and by NSF of China Grant 10071001.
Dedicated:
Dedicated to the memory of P. Erdős (1913–1996)
Article copyright:
© Copyright 2000
American Mathematical Society
