In number theory, a Frobenius pseudoprime is a pseudoprime, whose definition was inspired by the quadratic Frobenius test described by Jon Grantham in a 1998 preprint and published in 2000.
[1][2] Frobenius pseudoprimes can be defined with respect to polynomials of degree at least 2, but they have been most extensively studied in the case of quadratic polynomials.
[3][4] The definition of Frobenius pseudoprimes with respect to a monic quadratic polynomial
is not a square, can be expressed in terms of Lucas sequences
(If condition (1) fails, then either the greatest common divisor is less than n, in which case it is a non-trivial factor and n is composite, or the GCD equals n, in which case one should try different parameters P and Q which are not multiples of n.) Every Frobenius
pseudoprime is also The converse of none of these statements is true, making the Frobenius
Analogous statements hold for other cubic polynomials of the form
[2] Frobenius pseudoprimes with respect to the Fibonacci polynomial
, the first Frobenius pseudoprime with respect to the same polynomial is 4181 (Grantham stated it as 5777[2] but multiple authors have noted this is incorrect and is instead the first pseudoprime with
Another case, Frobenius pseudoprimes with respect to the quadratic polynomial
sequence and are: In this case, the first Frobenius pseudoprime with respect to the quadratic polynomial
, has sparser pseudoprimes as compared to many other simple quadratics.
[2] Details on implementation for quadratic polynomials can be found in Crandall and Pomerance.
The conditions defining Frobenius pseudoprime can be used for testing a given number n for probable primality.
, but rather select them in a certain way depending on the input number n in order to decrease the proportion of false positives, i.e., composite numbers that pass the test.
Sometimes such composite numbers are commonly called Frobenius pseudoprimes, although they may correspond to different parameters.
Using parameter selection ideas first laid out in Baillie and Wagstaff (1980)[7] as part of the Baillie–PSW primality test and used by Grantham in his quadratic Frobenius test,[8] one can create even better quadratic tests.
In particular, it was shown that choosing parameters from quadratic non-residues modulo n (based on the Jacobi symbol) makes far stronger tests, and is one reason for the success of the Baillie–PSW primality test.
For instance, for the parameters (P,2), where P is the first odd integer that satisfies
[9] For a given non-square number n, it first computes a parameter c as the smallest odd prime having Jacobi symbol
Similar to the above example, Khashin notes that no pseudoprime has been found for his 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 OEIS: A006190), and it also passes the Jacobi step since
This property can be clearly seen when the algorithm is formulated as shown in Crandall and Pomerance Algorithm 3.6.9[3] or as shown by Loebenberger,[4] as the algorithm does a Lucas test followed by an additional check for the Frobenius condition.
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.
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.
Müller in 2001 proposed the MQFT test with bounds of essentially
[10] Damgård and Frandsen in 2003 proposed the EQFT with a bound of essentially
[11] Seysen in 2005 proposed the SQFT test with a bound of
[12] Given the same computational effort, these offer better worst-case bounds than the commonly used Miller–Rabin primality test.