Strong pseudoprimes to twelve prime bases

Sorenson, Jonathan; Webster, Jonathan

doi:10.1090/mcom/3134

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