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