Finding -strong pseudoprimes

Author:
Zhenxiang Zhang

Journal:
Math. Comp. **74** (2005), 1009-1024

MSC (2000):
Primary 11Y11, 11A15, 11A51.

Published electronically:
November 2, 2004

MathSciNet review:
2114662

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Let be odd primes and . Put

Then we call the

*kernel*, the triple the

*signature*, and the

*height*of , respectively. We call a -number if it is a Carmichael number with each prime factor . If is a -number and a strong pseudoprime to the bases for , we call a -spsp . Since -numbers have probability of error (the upper bound of that for the Rabin-Miller test), they often serve as the exact values or upper bounds of (the smallest strong pseudoprime to all the first prime bases). If we know the exact value of , we will have, for integers , a deterministic efficient primality testing algorithm which is easy to implement.

In this paper, we first describe an algorithm for finding -spsp(2)'s, to a given limit, with heights bounded. There are in total -spsp's with heights . We then give an overview of the 21978 - spsp(2)'s and tabulate of them, which are -spsp's to the first prime bases up to ; three numbers are spsp's to the first 11 prime bases up to 31. No -spsp's to the first prime bases with heights were found. We conjecture that there exist no -spsp's to the first prime bases with heights and so that

which was found by the author in an earlier paper. We give reasons to support the conjecture. The main idea of our method for finding those -spsp's is that we loop on candidates of signatures and kernels with heights bounded, subject those candidates of -spsp's and their prime factors to Miller's tests, and obtain the desired numbers. At last we speed our algorithm for finding larger -spsp's, say up to , with a given signature to more prime bases. Comparisons of effectiveness with Arnault's and our previous methods for finding -strong pseudoprimes to the first several prime bases are given.

**1.**W. R. Alford, A. Granville and C. Pomerance,*There are infinitely many Carmichael numbers*, Annals of Math.**140**(1994), 703-722. MR**95k:11114****2.**F. Arnault,*Constructing Carmichael numbers which are strong pseudoprimes to several bases*, J. Symbolic Computation**20**(1995), 151-161. MR**96k:11153****3.**D. Bleichenbacher,*Efficiency and Security of Cryptosystems Based on Number Theory*, ETH Ph. D. dissertation 11404, Swiss Federal Institute of Technology, Zurich (1996).**4.**R. Crandall and C. Pomerance,*Prime numbers, a computational perspective*, Springer-Verlag, New York, 2001. MR**2002a:11007****5.**I. Damgård, P. Landrock, and C. Pomerance,*Average case estimates for the strong probable prime test*, Math. Comp.**61**(1993), 177-194. MR**94b:11124****6.**G. Jaeschke,*On strong pseudoprimes to several bases*, Math. Comp.**61**(1993), 915-926. MR**94d:11004****7.**G. Miller,*Riemann's hypothesis and tests for primality*, J. Comput. and System Sci.**13**(1976), 300-317. MR**58:470a****8.**R. G. E. Pinch,*All Carmichael numbers with three prime factors up to*, http://www. chalcedon.demon.co.uk/carpsp.html.**9.**C. Pomerance, J. L. Selfridge and Samuel S. Wagstaff, Jr.,*The pseudoprimes to*, Math. Comp.**35**(1980), 1003-1026. MR**82g:10030****10.**M. O. Rabin,*Probabilistic algorithms for testing primality*, J. Number Theory**12**(1980), 128-138. MR**81f:10003****11.**Zhenxiang Zhang,*Finding strong pseudoprimes to several bases*, Math. Comp.**70**(2001), 863-872.`http://www.ams.org/journal-getitem?pii=S0025-5718-00-01215-1`MR**2001g:11009****12.**Zhenxiang Zhang and Min Tang,*Finding strong pseudoprimes to several bases*. II, Math. Comp.**72**(2003), 2085-2097.`http://www.ams.org/journal-getitem?pii=S0025-5718-03- 01545-X`MR**2004c:11008**

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, Peoples Republic of China

Email:
zhangzhx@mail.ahwhptt.net.cn

DOI:
http://dx.doi.org/10.1090/S0025-5718-04-01693-X

Keywords:
Carmichael numbers,
$C_3$-numbers,
strong pseudoprimes,
$C_3$-spsp's,
Rabin-Miller test,
Chinese Remainder Theorem.

Received by editor(s):
August 16, 2003

Received by editor(s) in revised form:
January 8, 2004

Published electronically:
November 2, 2004

Additional Notes:
Supported by the NSF of China Grant 10071001, the SF of Anhui Province Grant 01046103, and the SF of the Education Department of Anhui Province Grant 2002KJ131.

Article copyright:
© Copyright 2004
American Mathematical Society