Average liar count for degree-2 Frobenius pseudoprimes

Thumbnail Image
Files
Fiori-average-liar.pdf(38.12 MB)
Fiori-average-liarVR.pdf(6.38 MB)
Date
2020
Authors
Fiori, Andrew
Shallue, Andrew
Journal Title
Journal ISSN
Volume Title
Publisher
American Mathematical Society
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 cases, providing evidence for the existence of several challenge pseudoprimes.
Description
Accepted author manuscript
Keywords
Primality testing , Pseudoprime , Frobenius pseudoprime , Lucas pseudoprime
Citation
Fiori, A., & Shallue, A. (2020). Average liar count for degree-2 Frobenius pseudoprimes. Mathematics of Computation, 89(321), 493-514. https://doi.org/10.1090/mcom/3452
URI
https://hdl.handle.net/10133/5942
Collections
Fiori, Andrew