Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

Request Permissions   Purchase Content 
 
 

 

Strong pseudoprimes to the first eight prime bases


Authors: Yupeng Jiang and Yingpu Deng
Journal: Math. Comp. 83 (2014), 2915-2924
MSC (2010): Primary 11Y11, 11A51
DOI: https://doi.org/10.1090/S0025-5718-2014-02830-5
Published electronically: May 5, 2014
MathSciNet review: 3246815
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Define $ \psi _m$ to be the smallest strong pseudoprime to the first $ m$ prime bases. The exact value of $ \psi _m$ is known for $ 1\le m \le 8$. Z. Zhang has found a 19-decimal-digit number $ Q_{11}=3825\,12305\,65464\,13051$ which is a strong pseudoprime to the first 11 prime bases and he conjectured that $ \psi _9=\psi _{10}=\psi _{11}=Q_{11}.$ We tabulate all the strong pseudoprimes $ n\le Q_{11}$ to the first eight prime bases, and prove Zhang's conjecture.


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

  • [1] François G. Dorais and Dominic Klyve, A Wieferich prime search up to $ 6.7\times 10^{15}$, J. Integer Seq. 14 (2011), no. 9, Article 11.9.2, 14. MR 2859986
  • [2] Gerhard Jaeschke, On strong pseudoprimes to several bases, Math. Comp. 61 (1993), no. 204, 915-926. MR 1192971 (94d:11004), https://doi.org/10.2307/2153262
  • [3] Joshua Knauer and Jörg Richstein, The continuing search for Wieferich primes, Math. Comp. 74 (2005), no. 251, 1559-1563 (electronic). MR 2137018 (2006a:11006), https://doi.org/10.1090/S0025-5718-05-01723-0
  • [4] 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 (82g:10030), https://doi.org/10.2307/2006210
  • [5] Michael O. Rabin, Probabilistic algorithm for testing primality, J. Number Theory 12 (1980), no. 1, 128-138. MR 566880 (81f:10003), https://doi.org/10.1016/0022-314X(80)90084-0
  • [6] Zhenxiang Zhang, Finding strong pseudoprimes to several bases, Math. Comp. 70 (2001), no. 234, 863-872. MR 1697654 (2001g:11009), https://doi.org/10.1090/S0025-5718-00-01215-1
  • [7] Zhenxiang Zhang, Finding $ C_3$-strong pseudoprimes, Math. Comp. 74 (2005), no. 250, 1009-1024 (electronic). MR 2114662 (2005k:11243), https://doi.org/10.1090/S0025-5718-04-01693-X
  • [8] Zhenxiang Zhang, Two kinds of strong pseudoprimes up to $ 10^{36}$, Math. Comp. 76 (2007), no. 260, 2095-2107 (electronic). MR 2336285 (2008h:11114), https://doi.org/10.1090/S0025-5718-07-01977-1
  • [9] Zhenxiang Zhang and Min Tang, Finding strong pseudoprimes to several bases. II, Math. Comp. 72 (2003), no. 244, 2085-2097 (electronic). MR 1986825 (2004c:11008), https://doi.org/10.1090/S0025-5718-03-01545-X

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11Y11, 11A51

Retrieve articles in all journals with MSC (2010): 11Y11, 11A51


Additional Information

Yupeng Jiang
Affiliation: Key Laboratory of Mathematics Mechanization, NCMIS, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, China, 100190
Email: jiangyupeng@amss.ac.cn

Yingpu Deng
Affiliation: Key Laboratory of Mathematics Mechanization, NCMIS, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, China, 100190
Email: dengyp@amss.ac.cn

DOI: https://doi.org/10.1090/S0025-5718-2014-02830-5
Keywords: Strong pseudoprimes, Chinese Remainder Theorem
Received by editor(s): August 23, 2012
Received by editor(s) in revised form: January 26, 2013, and April 5, 2013
Published electronically: May 5, 2014
Additional Notes: This research was supported by the NNSF of China (Grant Nos. 11071285, 61121062), 973 Project (2011CB302401) and the National Center for Mathematics and Interdisciplinary Sciences, CAS
Article copyright: © Copyright 2014 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society