Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Average liar count for degree-$ 2$ Frobenius pseudoprimes

Authors: Andrew Fiori and Andrew Shallue
Journal: Math. Comp. 89 (2020), 493-514
MSC (2010): Primary 11Y11; Secondary 11A41
Published electronically: May 24, 2019
Full-text PDF
View in AMS MathViewer New

Abstract | References | Similar Articles | Additional Information

Abstract: In this paper we obtain lower and upper bounds on the average number of liars for the Quadratic Frobenius Pseudoprime Test of Grantham [Math. Comp. 70 (2001), pp. 873-891], generalizing arguments of Erdős and Pomerance [Math. Comp. 46 (1986), pp. 259-279] and Monier [Theoret. Comput. Sci. 12 (1980), 97-108]. These bounds are provided for both Jacobi symbol $ \pm 1$ cases, providing evidence for the existence of several challenge pseudoprimes.

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

  • [BH98] R. C. Baker and G. Harman, Shifted primes without large prime factors, Acta Arith. 83 (1998), no. 4, 331-361.
  • [BW80] R. Baillie and S. S. Wagstaff, Jr., Lucas pseudoprimes, Math. Comp. 35 (1980), no. 152, 1391-1417.
  • [DMT01] C. Dartyge, G. Martin, and G. Tenenbaum, Polynomial values free of large prime factors, Period. Math. Hungar. 43 (2001), no. 1-2, 111-119.
  • [EP86] P. Erdős and C. Pomerance, On the number of false witnesses for a composite number, Math. Comp. 46 (1986), no. 173, 259-279.
  • [Gra01] J. Grantham, Frobenius pseudoprimes, Math. Comp. 70 (2001), no. 234, 873-891.
  • [Gra10] J. Grantham, There are infinitely many Perrin pseudoprimes, J. Number Theory 130 (2010), no. 5, 1117-1128.
  • [Guy04] R. K. Guy, Unsolved Problems in Number Theory, third ed., Problem Books in Mathematics, Springer-Verlag, New York, 2004.
  • [How00] E. W. Howe, Higher-order Carmichael numbers, Math. Comp. 69 (2000), no. 232, 1711-1719.
  • [HW08] G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, sixth ed., Oxford University Press, Oxford, 2008, revised by D. R. Heath-Brown and J. H. Silverman, with a foreword by Andrew Wiles.
  • [Lan02] S. Lang, Algebra, third ed., Graduate Texts in Mathematics, vol. 211, Springer-Verlag, New York, 2002.
  • [Mon80] L. Monier, Evaluation and comparison of two efficient probabilistic primality testing algorithms, Theoret. Comput. Sci. 12 (1980), no. 1, 97-108.
  • [Pom81] C. Pomerance, On the distribution of pseudoprimes, Math. Comp. 37 (1981), no. 156, 587-593.
  • [PSW80] C. Pomerance, J. L. Selfridge, and S. S. Wagstaff, Jr., The pseudoprimes to $ 25\cdot 10^{9}$, Math. Comp. 35 (1980), no. 151, 1003-1026.
  • [Xyl11] T. Xylouris, Über die Nullstellen der Dirichletschen L-Funktionen und die kleinste Primzahl in einer arithmetischen Progression, Bonner Mathematische Schriften [Bonn Mathematical Publications], 404, Universität Bonn, Mathematisches Institut, Bonn, 2011, dissertation for the degree of Doctor of Mathematics and Natural Sciences at the University of Bonn, Bonn, 2011.

Similar Articles

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

Retrieve articles in all journals with MSC (2010): 11Y11, 11A41

Additional Information

Andrew Fiori
Affiliation: Department of Mathematics and Computer Science, University of Lethbridge, C526 University Hall, 4401 University Drive, Lethbridge, Alberta, T1K 3M4, Canada

Andrew Shallue
Affiliation: Department of Mathematics, Illinois Wesleyan University, 1312 Park Street, Bloomington, Illinois 61701

Keywords: Primality testing, pseudoprime, Frobenius pseudoprime, Lucas pseudoprime
Received by editor(s): July 18, 2017
Received by editor(s) in revised form: May 26, 2018, October 26, 2018, February 8, 2019, March 8, 2019, and March 24, 2019
Published electronically: May 24, 2019
Additional Notes: The first author gratefully acknowledges support from the Pacific Institute for Mathematical Sciences (PIMS)
The second author was supported by an Artistic and Scholarly Development grant from Illinois Wesleyan University
Article copyright: © Copyright 2019 American Mathematical Society