Strengthening the Baillie-PSW primality test
HTML articles powered by AMS MathViewer
- by Robert Baillie, Andrew Fiori and Samuel S. Wagstaff, Jr.;
- Math. Comp. 90 (2021), 1931-1955
- DOI: https://doi.org/10.1090/mcom/3616
- Published electronically: March 22, 2021
- HTML | PDF | Request permission
Abstract:
In 1980, the first and third authors proposed a probabilistic primality test that has become known as the Baillie-PSW primality test. Its power to distinguish between primes and composites comes from combining a Fermat probable prime test with a Lucas probable prime test. No odd composite integers have been reported to pass this combination of primality tests if the parameters are chosen in an appropriate way. Here, we describe a significant strengthening of this test that comes at almost no additional computational cost. This is achieved by including in the test Lucas-V pseudoprimes, of which there are only five less than $10^{15}$.References
- M. R. Albrecht, J. Massimo, K. G. Paterson, and J. Somorovsky, Prime and prejudice: primality testing under adversarial conditions, ACM SIGSAC Conference on Computer and Communications Security, October 15–19, 2018, Toronto, Ontario, Canada, pp. 281–298, DOI 10.1145/3243734.3243787. Available at https://eprint.iacr.org/2018/749.pdf
- W. R. Alford, Andrew Granville, and Carl Pomerance, There are infinitely many Carmichael numbers, Ann. of Math. (2) 139 (1994), no. 3, 703–722. MR 1283874, DOI 10.2307/2118576
- 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
- F. Arnault, The Rabin-Monier theorem for Lucas pseudoprimes, Math. Comp. 66 (1997), no. 218, 869–881. MR 1408370, DOI 10.1090/S0025-5718-97-00836-3
- Robert Baillie and Samuel S. Wagstaff Jr., Lucas pseudoprimes, Math. Comp. 35 (1980), no. 152, 1391–1417. MR 583518, DOI 10.1090/S0025-5718-1980-0583518-6
- R. Baillie, A. Fiori, and S. S. Wagstaff, Jr., Strengthening the Baillie-PSW primality test, https://arxiv.org/abs/2006.14425v1, 2020.
- David Bressoud and Stan Wagon, A course in computational number theory, Key College Publishing, Emeryville, CA; in cooperation with Springer-Verlag, New York, 2000. With 1 CD-ROM (Windows, Macintosh and UNIX). MR 1756372
- John Brillhart, D. H. Lehmer, and J. L. Selfridge, New primality criteria and factorizations of $2^{m}\pm 1$, Math. Comp. 29 (1975), 620–647. MR 384673, DOI 10.1090/S0025-5718-1975-0384673-1
- Richard Crandall and Carl Pomerance, Prime numbers, 2nd ed., Springer, New York, 2005. A computational perspective. MR 2156291
- P. Erdös, On pseudoprimes and Carmichael numbers, Publ. Math. Debrecen 4 (1956), 201–206. MR 79031, DOI 10.5486/pmd.1956.4.3-4.16
- J. Feitsma, Pseudoprimes. Feitsma’s web page is http://www.janfeitsma.nl/math/psp2/index. Statistics on psp(2) are at http://www.janfeitsma.nl/math/psp2/statistics. The database of all psp(2) $< 2^{64}$ is at http://www.cecm.sfu.ca/Pseudoprimes/index-2-to-64.html.
- Andrew Fiori and Andrew Shallue, Average liar count for degree-2 Frobenius pseudoprimes, Math. Comp. 89 (2020), no. 321, 493–514. MR 4011553, DOI 10.1090/mcom/3452
- Jon Grantham, A probable prime test with high confidence, J. Number Theory 72 (1998), no. 1, 32–47. MR 1643284, DOI 10.1006/jnth.1998.2247
- Jon Grantham, Frobenius pseudoprimes, Math. Comp. 70 (2001), no. 234, 873–891. MR 1680879, DOI 10.1090/S0025-5718-00-01197-2
- D. Jacobsen, Pseudoprime statistics, tables, and data. http://ntheory.org/pseudoprimes.html. The counts of lpsp and slpsp to $10^{15}$ from method A (or A*) are given in the columns labeled “#LPSP Lucas-Selfridge OEIS A217120” and “#SLPSP Strong Lucas-Selfridge OEIS A217255”.
- A. Korselt, Probléme chinois, L’Intermédiaire des Mathématiciens, 6 (1899), 142–143.
- Louis Monier, Evaluation and comparison of two efficient probabilistic primality testing algorithms, Theoret. Comput. Sci. 12 (1980), no. 1, 97–108. MR 582244, DOI 10.1016/0304-3975(80)90007-9
- R. Pinch, The Carmichael numbers up to $10^{21}$, Anne-Maria Ernvall-Hytönen, Matti Jutila, Juhani Karhumäki, Arto Lepistö (Eds.), Proceedings of conference on algorithmic number theory, TUCS General Publication, Turku Centre for Computer Science, pp. 129–131, 2007. https://tucs.fi/publications/attachment.php?fname=G46.pdf
- R. G. E. Pinch, The Carmichael numbers up to $10^{15}$, Math. Comp. 61 (1993), no. 203, 381–391. MR 1202611, DOI 10.1090/S0025-5718-1993-1202611-7
- Carl Pomerance, A new lower bound for the pseudoprime counting function, Illinois J. Math. 26 (1982), no. 1, 4–9. MR 638549
- C. Pomerance, Are there counterexamples to the Baillie-PSW primality test? In H. W. Lenstra, Jr., J. K. Lenstra, and P. Van Emde Boas (Eds.), Dopo le parole angeboden aan Dr. A. K. Lenstra. Amsterdam, 1984. https://www.math.dartmouth.edu/~carlp/dopo.pdf
- 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
- Andrzej Rotkiewicz, Lucas and Frobenius pseudoprimes, Ann. Math. Sil. 17 (2003), 17–39. MR 2076674
- D. B. Staple, The combinatorial algorithm for computing $\pi (x)$, Master’s Degree Thesis at Dalhousie University, https://arxiv.org/abs/1503.01839, August 2015.
- A. J. van der Poorten and A. Rotkiewicz, On strong pseudoprimes in arithmetic progressions, J. Austral. Math. Soc. Ser. A 29 (1980), no. 3, 316–321. MR 569519
- H. C. Williams, On numbers analogous to the Carmichael numbers, Canad. Math. Bull. 20 (1977), no. 1, 133–143. MR 447099, DOI 10.4153/CMB-1977-025-9
- H. C. Williams. Édouard Lucas and primality testing. Wiley, New York, New York, 1998.
- Thomas Wright, Infinitely many Carmichael numbers in arithmetic progressions, Bull. Lond. Math. Soc. 45 (2013), no. 5, 943–952. MR 3104986, DOI 10.1112/blms/bdt013
Bibliographic Information
- Robert Baillie
- Affiliation: Independent Mathematician, State College, Pennsylvania 16803-3029
- MR Author ID: 407930
- ORCID: 0000-0001-9826-727X
- Email: rjbaillie@frii.com
- Andrew Fiori
- Affiliation: Department of Mathematics and Computer Science, University of Lethbridge, 4401 University Drive, Lethbridge, Alberta, T1K 3M4 Canada
- MR Author ID: 997971
- ORCID: 0000-0001-6322-8705
- Email: andrew.fiori@uleth.ca
- Samuel S. Wagstaff, Jr.
- Affiliation: Department of Computer Sciences, Center for Education and Research in Information Assurance and Security, Purdue University, West Lafayette, Indiana 47907-1398
- MR Author ID: 179915
- Email: ssw@cerias.purdue.edu
- Received by editor(s): June 22, 2020
- Received by editor(s) in revised form: October 30, 2020
- Published electronically: March 22, 2021
- Additional Notes: The second author’s work was supported partially by the University of Lethbridge and NSERC. The third author’s work was supported by the CERIAS Center at Purdue University
- © Copyright 2021 American Mathematical Society
- Journal: Math. Comp. 90 (2021), 1931-1955
- MSC (2020): Primary 11Y11; Secondary 11A51
- DOI: https://doi.org/10.1090/mcom/3616
- MathSciNet review: 4273120