## Strong pseudoprimes to twelve prime bases

HTML articles powered by AMS MathViewer

- by Jonathan Sorenson and Jonathan Webster PDF
- Math. Comp.
**86**(2017), 985-1003 Request permission

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

- 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**, DOI 10.1007/3-540-58691-1_{3}6 - Eric Bach,
*Explicit bounds for primality testing and related problems*, Math. Comp.**55**(1990), no. 191, 355–380. MR**1023756**, DOI 10.1090/S0025-5718-1990-1023756-8 - Daniel Bleichenbacher,
*Efficiency and security of cryptosystems based on number theory*, Ph.D. thesis, Swiss Federal Institute of Technology Zurich, 1996. - 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**, DOI 10.1007/s00209-002-0449-z - Richard Crandall and Carl Pomerance,
*Prime numbers*, Springer-Verlag, New York, 2001. A computational perspective. MR**1821158**, DOI 10.1007/978-1-4684-9316-0 - 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** - P. Erdös,
*On pseudoprimes and Carmichael numbers*, Publ. Math. Debrecen**4**(1956), 201–206. MR**79031** - 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** - Henryk Iwaniec,
*On the Brun-Titchmarsh theorem*, J. Math. Soc. Japan**34**(1982), no. 1, 95–123. MR**639808**, DOI 10.2969/jmsj/03410095 - 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 - Yupeng Jiang and Yingpu Deng,
*Strong pseudoprimes to the first eight prime bases*, Math. Comp.**83**(2014), no. 290, 2915–2924. MR**3246815**, DOI 10.1090/S0025-5718-2014-02830-5 - A. Languasco and A. Zaccagnini,
*A note on Mertens’ formula for arithmetic progressions*, J. Number Theory**127**(2007), no. 1, 37–46. MR**2351662**, DOI 10.1016/j.jnt.2006.12.015 - Francesco Pappalardi,
*On the order of finitely generated subgroups of $\textbf {Q}^*\pmod p$ and divisors of $p-1$*, J. Number Theory**57**(1996), no. 2, 207–222. MR**1382747**, DOI 10.1006/jnth.1996.0044 - Francesco Pappalardi,
*On the $r$-rank Artin conjecture*, Math. Comp.**66**(1997), no. 218, 853–868. MR**1377664**, DOI 10.1090/S0025-5718-97-00805-3 - 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 - A. Schönhage and V. Strassen,
*Schnelle Multiplikation grosser Zahlen*, Computing (Arch. Elektron. Rechnen)**7**(1971), 281–292 (German, with English summary). MR**292344**, DOI 10.1007/bf02242355 - 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**, DOI 10.1007/11792086_{1}5 - 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**, DOI 10.1007/978-3-642-14518-6_{2}6 - 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**, DOI 10.1007/978-3-540-24847-7_{3}1 - Zhenxiang Zhang,
*Two kinds of strong pseudoprimes up to $10^{36}$*, Math. Comp.**76**(2007), no. 260, 2095–2107. MR**2336285**, DOI 10.1090/S0025-5718-07-01977-1

## Additional Information

**Jonathan Sorenson**- Affiliation: Department of Computer Science and Software Engineering, Butler University, Indianapolis, Indiana 46208
- MR Author ID: 334195
- Email: sorenson@butler.edu
**Jonathan Webster**- Affiliation: Department of Mathematics and Actuarial Science, Butler University, Indianapolis, Indiana 46208
- MR Author ID: 903429
- Email: jewebste@butler.edu
- 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.
- © Copyright 2016 American Mathematical Society
- Journal: Math. Comp.
**86**(2017), 985-1003 - MSC (2010): Primary 11Y11, 11Y16; Secondary 11A41, 68W40, 68W10
- DOI: https://doi.org/10.1090/mcom/3134
- MathSciNet review: 3584557