Average liar count for degree-2 Frobenius pseudoprimes

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.