Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



Two kinds of strong pseudoprimes up to $ 10^{36}$

Author: Zhenxiang Zhang
Journal: Math. Comp. 76 (2007), 2095-2107
MSC (2000): Primary 11Y11, 11A15, 11A51
Published electronically: April 17, 2007
MathSciNet review: 2336285
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Let $ n>1$ be an odd composite integer. Write $ n-1=2^sd$ with $ d$ odd. If either $ b^d \equiv 1 $ mod $ n$ or $ b^{2^rd}\equiv -1$ mod $ n$ for some $ r=0, 1, \dots, s-1$, then we say that $ n$ is a strong pseudoprime to base $ b$, or spsp($ b$) for short. Define $ \psi_t$ to be the smallest strong pseudoprime to all the first $ t$ prime bases. If we know the exact value of $ \psi_t$, we will have, for integers $ n<\psi_t$, a deterministic efficient primality testing algorithm which is easy to implement. Thanks to Pomerance et al. and Jaeschke, the $ \psi_t$ are known for $ 1 \leq t \leq 8$. Conjectured values of $ \psi_9,\dots,\psi_{12}$ were given by us in our previous papers (Math. Comp. 72 (2003), 2085-2097; 74 (2005), 1009-1024).

The main purpose of this paper is to give exact values of $ \psi_t'$ for $ 13\leq t\leq 19$; to give a lower bound of $ \psi_{20}'$: $ \psi_{20}'>10^{36}$; and to give reasons and numerical evidence of K2- and $ C_3$-spsp's $ <10^{36}$ to support the following conjecture: $ \psi_t=\psi_t'<\psi_t''$ for any $ t\geq 12$, where $ \psi_t'$ (resp. $ \psi_t''$) is the smallest K2- (resp. $ C_3$-) strong pseudoprime to all the first $ t$ prime bases. For this purpose we describe procedures for computing and enumerating the two kinds of spsp's $ <10^{36}$ to the first 9 prime bases. The entire calculation took about 4000 hours on a PC Pentium IV/1.8GHz. (Recall that a K2-spsp is an spsp of the form: $ n=pq$ with $ p,q$ primes and $ q-1=2(p-1)$; and that a $ C_3$-spsp is an spsp and a Carmichael number of the form: $ n=q_1q_2q_3$ with each prime factor $ q_i\equiv 3$ mod $ 4$.)

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

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, People’s Republic of China

Keywords: K2-strong pseudoprimes, $C_3$-strong pseudoprimes, the least strong pseudoprime to the first $t$ prime bases, Rabin-Miller test, biquadratic residue characters, Chinese remainder theorem.
Received by editor(s): March 8, 2006
Received by editor(s) in revised form: July 8, 2006
Published electronically: April 17, 2007
Additional Notes: The author was supported by the NSF of China Grant 10071001
Dedicated: Dedicated to the memory of Kencheng Zeng (1927–2004)
Article copyright: © Copyright 2007 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.