In number theory, a Frobenius pseudoprime is a pseudoprime that passes a specific probable prime test described by Jon Grantham in a 1998 preprint and published in 2000. It has been studied by other authors for the case of quadratic polynomials.
Contents
Frobenius pseudoprimes w.r.t. quadratic polynomials
Frobenius pseudoprimes are defined with respect to a fixed monic polynomial. The case of a degree-2 (quadratic) polynomial
A composite number n is a Frobenius
and
where
Both conditions hold for all primes, hence this constitutes a probable prime test.
Condition (1) is the same condition that defines a Lucas pseudoprime, hence every Frobenius
Example
Frobenius pseudoprimes with respect to the Fibonacci polynomial
While 323 is the first Lucas pseudoprime with respect to the Fibonacci polynomial
Another case, Frobenius pseudoprimes with respect to the quadratic polynomial
In this case, the first Frobenius pseudoprime with respect to the quadratic polynomial
The quadratic polynomial
Notice there are only 3 such pseudoprimes below 500000, while there are many Frobenius (1, -1) and (3, -1) pseudoprimes below 500000.
Every entry in this sequence is a Fermat pseudoprime to base 5 as well as a Lucas (3,-5) pseudoprime, but the converse is not true: 642001 is both a psp-5 and a Lucas (3,-5) pseudoprime, but is not a Frobenius (3,-5) pseudoprime.
Using parameter selection ideas first laid out in Baillie and Wagstaff (1980) as part of the Baillie-PSW primality test and used by Grantham in his quadratic Frobenius test, one can create even better quadratic tests. For instance, for the parameters (P,2), where P is the first odd integer that satisfies
Relations to other pseudoprimes
For quadratic polynomials
Every Frobenius pseudoprime to
Alternate formulations
An alternate formulation is given by Khashin. Given a number n, not a perfect square, where c is the smallest odd prime with Jacobi symbol
Note the additional condition of choosing a parameter based on the Jacobi symbol finding a quadratic non-residue. This is similar to the method from Baillie and Wagstaff shown in the examples section. This makes far stronger tests, and is one reason for the success of the Baillie-PSW primality test. Similar to the example, Khashin notes that no pseudoprime has been found for his test. He further shows that any that exist under 260 must have a factor less than 19 or have c > 128.
Strong Frobenius pseudoprimes
Strong Frobenius pseudoprimes are also defined. Details on implementation for quadratic polynomials can be found in Crandall and Pomerance.
Properties
The computational cost of the Frobenius pseudoprimality test with respect to quadratic polynomials is roughly three times the cost of a strong pseudoprimality test (e.g. a single round of the Miller-Rabin primality test), 1.5 times that of a Lucas pseudoprimality test, and slightly more than a Baillie-PSW primality test.
Note that the quadratic Frobenius test is stronger than the Lucas test. For example, 1763 is a Lucas pseudoprime to (P, Q) = (3, -1) since U1764(3,-1) ≡ 0 (mod 1763) (U(3,-1) is given in A006190), and it also passes the Jacobi step since
While the quadratic Frobenius test does not have formal error bounds beyond that of the Lucas test, it can be used as the basis for methods with much smaller error bounds. Note that these have more steps, additional requirements, and non-negligible additional computation beyond what is described on this page. It is important to note that the error bounds for these methods do not apply to the standard or strong Frobenius tests with fixed values of (P,Q) described on this page.
Based on this idea of pseudoprimes, algorithms with strong worst-case error bounds can be built. The quadratic Frobenius test, using a quadratic Frobenius test plus other conditions, has a bound of
Given the same computational effort, these offer better worst-case bounds than the commonly used Miller-Rabin primality test.