Counting Frobenius Pseudoprimes

Abstract

We generalize the work of Erdos-Pomerance and Fiori-Shallue on counting Frobenius pseudoprimes from the cases of degree one and two respectively to arbitrary degree. More specifically we provide formulas for counting the number of false witnesses for a number $n$ with respect to Grantham's Frobenius primality test. We also provide conditional assymptotic lower bounds on the average number of Frobenius pseudoprimes and assymptotic upper bounds on the same.