Average liar count for degree-2 Frobenius pseudoprimes

Fiori, Andrew; Shallue, Andrew

doi:10.1090/mcom/3452

Average liar count for degree-$2$ Frobenius pseudoprimes
HTML articles powered by AMS MathViewer

by Andrew Fiori and Andrew Shallue;

Math. Comp. 89 (2020), 493-514

DOI: https://doi.org/10.1090/mcom/3452

Published electronically: May 24, 2019

HTML | PDF | Request permission

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

R. C. Baker and G. Harman, Shifted primes without large prime factors, Acta Arith. 83 (1998), no. 4, 331–361.
R. Baillie and S. S. Wagstaff, Jr., Lucas pseudoprimes, Math. Comp. 35 (1980), no. 152, 1391–1417.
C. Dartyge, G. Martin, and G. Tenenbaum, Polynomial values free of large prime factors, Period. Math. Hungar. 43 (2001), no. 1-2, 111–119.
P. Erdős and C. Pomerance, On the number of false witnesses for a composite number, Math. Comp. 46 (1986), no. 173, 259–279.
J. Grantham, Frobenius pseudoprimes, Math. Comp. 70 (2001), no. 234, 873–891.
J. Grantham, There are infinitely many Perrin pseudoprimes, J. Number Theory 130 (2010), no. 5, 1117–1128.
R. K. Guy, Unsolved Problems in Number Theory, third ed., Problem Books in Mathematics, Springer-Verlag, New York, 2004.
E. W. Howe, Higher-order Carmichael numbers, Math. Comp. 69 (2000), no. 232, 1711–1719.
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.
S. Lang, Algebra, third ed., Graduate Texts in Mathematics, vol. 211, Springer-Verlag, New York, 2002.
L. Monier, Evaluation and comparison of two efficient probabilistic primality testing algorithms, Theoret. Comput. Sci. 12 (1980), no. 1, 97–108.
C. Pomerance, On the distribution of pseudoprimes, Math. Comp. 37 (1981), no. 156, 587–593.
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.
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.