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

HTML articles powered by AMS MathViewer

- by Zhenxiang Zhang;
- Math. Comp.
**76**(2007), 2095-2107 - DOI: https://doi.org/10.1090/S0025-5718-07-01977-1
- Published electronically: April 17, 2007
- PDF | Request permission

## 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

- Richard Crandall and Carl Pomerance,
*Prime numbers*, 2nd ed., Springer, New York, 2005. A computational perspective. MR**2156291** - Ivan Damgård, Peter Landrock, and Carl Pomerance,
*Average case error estimates for the strong probable prime test*, Math. Comp.**61**(1993), no. 203, 177–194. MR**1189518**, DOI 10.1090/S0025-5718-1993-1189518-9 - Richard K. Guy,
*Unsolved problems in number theory*, 3rd ed., Problem Books in Mathematics, Springer-Verlag, New York, 2004. MR**2076335**, DOI 10.1007/978-0-387-26677-0 - 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 - Gary L. Miller,
*Riemann’s hypothesis and tests for primality*, J. Comput. System Sci.**13**(1976), no. 3, 300–317. MR**480295**, DOI 10.1016/S0022-0000(76)80043-8 - Louis Monier,
*Evaluation and comparison of two efficient probabilistic primality testing algorithms*, Theoret. Comput. Sci.**12**(1980), no. 1, 97–108. MR**582244**, DOI 10.1016/0304-3975(80)90007-9 - 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 - Zhenxiang Zhang,
*Finding strong pseudoprimes to several bases*, Math. Comp.**70**(2001), no. 234, 863–872. MR**1697654**, DOI 10.1090/S0025-5718-00-01215-1 - Zhenxiang Zhang,
*Finding $C_3$-strong pseudoprimes*, Math. Comp.**74**(2005), no. 250, 1009–1024. MR**2114662**, DOI 10.1090/S0025-5718-04-01693-X - Zhenxiang Zhang and Min Tang,
*Finding strong pseudoprimes to several bases. II*, Math. Comp.**72**(2003), no. 244, 2085–2097. MR**1986825**, DOI 10.1090/S0025-5718-03-01545-X

## Bibliographic Information

**Zhenxiang Zhang**- Affiliation: Department of Mathematics, Anhui Normal University, 241000 Wuhu, Anhui, People’s Republic of China
- Email: zhangzhx@mail.wh.ah.cn, ahnu_zzx@sina.com
- 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
- © Copyright 2007
American Mathematical Society

The copyright for this article reverts to public domain 28 years after publication. - Journal: Math. Comp.
**76**(2007), 2095-2107 - MSC (2000): Primary 11Y11, 11A15, 11A51
- DOI: https://doi.org/10.1090/S0025-5718-07-01977-1
- MathSciNet review: 2336285

Dedicated: Dedicated to the memory of Kencheng Zeng (1927–2004)