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 twelve prime bases


Authors: Jonathan Sorenson and Jonathan Webster
Journal: Math. Comp. 86 (2017), 985-1003
MSC (2010): Primary 11Y11, 11Y16; Secondary 11A41, 68W40, 68W10
DOI: https://doi.org/10.1090/mcom/3134
Published electronically: June 2, 2016
MathSciNet review: 3584557
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Let $ \psi _m$ be the smallest strong pseudoprime to the first $ m$ prime bases. This value is known for $ 1 \leq m \leq 11$. We extend this by finding $ \psi _{12}$ and $ \psi _{13}$. We also present an algorithm to find all integers $ n\le B$ that are strong pseudoprimes to the first $ m$ prime bases; with reasonable heuristic assumptions we can show that it takes at most $ B^{2/3+o(1)}$ time.


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

  • [1] 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), https://doi.org/10.1007/3-540-58691-1_36
  • [2] Eric Bach, Explicit bounds for primality testing and related problems, Math. Comp. 55 (1990), no. 191, 355-380. MR 1023756 (91m:11096), https://doi.org/10.2307/2008811
  • [3] Daniel Bleichenbacher, Efficiency and security of cryptosystems based on number theory, Ph.D. thesis, Swiss Federal Institute of Technology Zurich, 1996.
  • [4] Yann Bugeaud, Pietro Corvaja, and Umberto Zannier, An upper bound for the G.C.D. of $ a^n-1$ and $ b^n-1$, Math. Z. 243 (2003), no. 1, 79-84. MR 1953049, https://doi.org/10.1007/s00209-002-0449-z
  • [5] Richard Crandall and Carl Pomerance, Prime numbers, Springer-Verlag, New York, 2001. A computational perspective. MR 1821158
  • [6] 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
  • [7] P. Erdös, On pseudoprimes and Carmichael numbers, Publ. Math. Debrecen 4 (1956), 201-206. MR 0079031
  • [8] G. H. Hardy and E. M. Wright, An introduction to the theory of numbers, 5th ed., The Clarendon Press, Oxford University Press, New York, 1979. MR 568909 (81i:10002)
  • [9] Henryk Iwaniec, On the Brun-Titchmarsh theorem, J. Math. Soc. Japan 34 (1982), no. 1, 95-123. MR 639808 (83a:10082), https://doi.org/10.2969/jmsj/03410095
  • [10] 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
  • [11] Yupeng Jiang and Yingpu Deng, Strong pseudoprimes to the first eight prime bases, Math. Comp. 83 (2014), no. 290, 2915-2924. MR 3246815, https://doi.org/10.1090/S0025-5718-2014-02830-5
  • [12] A. Languasco and A. Zaccagnini, A note on Mertens' formula for arithmetic progressions, J. Number Theory 127 (2007), no. 1, 37-46. MR 2351662 (2009g:11136), https://doi.org/10.1016/j.jnt.2006.12.015
  • [13] Francesco Pappalardi, On the order of finitely generated subgroups of $ {\bf Q}^*\pmod p$ and divisors of $ p-1$, J. Number Theory 57 (1996), no. 2, 207-222. MR 1382747 (97d:11141), https://doi.org/10.1006/jnth.1996.0044
  • [14] Francesco Pappalardi, On the $ r$-rank Artin conjecture, Math. Comp. 66 (1997), no. 218, 853-868. MR 1377664 (97f:11082), https://doi.org/10.1090/S0025-5718-97-00805-3
  • [15] 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
  • [16] 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
  • [17] A. Schönhage and V. Strassen, Schnelle Multiplikation grosser Zahlen, Computing (Arch. Elektron. Rechnen) 7 (1971), 281-292 (German, with English summary). MR 0292344 (45 #1431)
  • [18] Jonathan P. Sorenson, The pseudosquares prime sieve, Algorithmic number theory, Lecture Notes in Comput. Sci., vol. 4076, Springer, Berlin, 2006, pp. 193-207. MR 2282925 (2007m:11168), https://doi.org/10.1007/11792086_15
  • [19] Jonathan P. Sorenson, Sieving for pseudosquares and pseudocubes in parallel using doubly-focused enumeration and wheel datastructures, Algorithmic number theory, Lecture Notes in Comput. Sci., vol. 6197, Springer, Berlin, 2010, pp. 331-339. MR 2721430 (2011m:11245), https://doi.org/10.1007/978-3-642-14518-6_26
  • [20] Damien Stehlé and Paul Zimmermann, A binary recursive gcd algorithm, Algorithmic number theory, Lecture Notes in Comput. Sci., vol. 3076, Springer, Berlin, 2004, pp. 411-425. MR 2138011 (2006e:11194), https://doi.org/10.1007/978-3-540-24847-7_31
  • [21] 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

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11Y11, 11Y16, 11A41, 68W40, 68W10

Retrieve articles in all journals with MSC (2010): 11Y11, 11Y16, 11A41, 68W40, 68W10


Additional Information

Jonathan Sorenson
Affiliation: Department of Computer Science and Software Engineering, Butler University, Indianapolis, Indiana 46208
Email: sorenson@butler.edu

Jonathan Webster
Affiliation: Department of Mathematics and Actuarial Science, Butler University, Indianapolis, Indiana 46208
Email: jewebste@butler.edu

DOI: https://doi.org/10.1090/mcom/3134
Received by editor(s): September 2, 2015
Published electronically: June 2, 2016
Additional Notes: This work was supported in part by a grant from the Holcomb Awards Committee.
Article copyright: © Copyright 2016 American Mathematical Society

American Mathematical Society