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. 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.

Frobenius pseudoprimes w.r.t. quadratic polynomials

The definition of Frobenius pseudoprimes with respect to a monic quadratic polynomial <math>x^2 - Px + Q</math>, where the discriminant <math>D = P^2-4Q</math> is not a square, can be expressed in terms of Lucas sequences <math>U_n(P,Q)</math> and <math>V_n(P,Q)</math> as follows.

A composite number n is a Frobenius <math>(P,Q)</math> pseudoprime if and only if

:<math> (1) \qquad \gcd(n,2QD)=1,</math>

:<math> (2) \qquad U_{n-\delta}(P,Q) \equiv 0 \pmod n,</math> and

:<math> (3) \qquad V_{n-\delta}(P,Q) \equiv 2Q^{(1-\delta)/2} \pmod{n},</math>

where <math>\delta=\left(\tfrac Dn\right)</math> is the Jacobi symbol.

When condition (2) is satisfied, condition (3) becomes equivalent to

:<math> (3') \qquad V_n(P,Q) \equiv P\pmod{n}.</math>

Therefore, a Frobenius <math>(P,Q)</math> pseudoprime can be equivalently defined by conditions (1–3), or by conditions (1–2) and (3′).

Since conditions (2) and (3) hold for all primes which satisfy the simple condition (1), they can be used as a probable primality test. (If condition (1) fails, then either the greatest common divisor is less than , in which case it is a non-trivial factor and is composite, or the GCD equals , in which case one should try different parameters and which are not multiples of .)

Relations to other pseudoprimes

Every Frobenius <math>(P,Q)</math> pseudoprime is also

  • a Lucas pseudoprime with parameters <math>(P,Q)</math>, since it is defined by conditions (1) and (2);
  • a Dickson pseudoprime with parameters <math>(P,Q)</math>, since it is defined by conditions (1) and (3'); show how to choose <math>P</math> and <math>Q</math> such that there are only five odd, composite numbers less than <math>10^{15}</math> for which (3) holds, that is, for which <math>V_{n+1} \equiv 2 Q \pmod {n} </math>.

Pseudoprimality tests

The conditions defining Frobenius pseudoprime can be used for testing a given number n for probable primality. Often such tests do not rely on fixed parameters <math>(P,Q)</math>, 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) as part of the Baillie–PSW primality test and used by Grantham in his quadratic Frobenius test, 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 <math>\left(\tfrac{D}{n}\right) = -1</math>, there are no pseudoprimes below 2<sup>64</sup>.

Yet another test is proposed by Khashin. For a given non-square number n, it first computes a parameter c as the smallest odd prime having Jacobi symbol <math>\left(\tfrac{c}{n}\right)=-1</math>, and then verifies the congruence:

:<math>(1 + \sqrt{c})^n \equiv (1 - \sqrt{c}) \pmod n</math>.

While all prime n pass this test, a composite n passes it if and only if n is a Frobenius pseudoprime for <math>(P,Q)=(2,1-c)</math>. Similar to the above example, Khashin notes that no pseudoprime has been found for his test. He further shows that any that exist under 2<sup>60</sup> must have a factor less than 19 or have c > 128.

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 (i.e. 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 U<sub>1764</sub>(3,−1) ≡ 0 (mod 1763) (U(3,−1) is given in ), and it also passes the Jacobi step since <math>\left(\tfrac{13}{1763}\right) = -1</math>, but it fails the Frobenius test to x<sup>2</sup> − 3x − 1. This property can be clearly seen when the algorithm is formulated as shown in Crandall and Pomerance Algorithm 3.6.9 Damgård and Frandsen in 2003 proposed the EQFT with a bound of essentially <math>\tfrac{256}