Frobenius pseudoprime

Definition of Frobenius pseudoprimes with respect to a monic quadratic polynomial ${\displaystyle x^{2}-Px+Q}$, where the discriminant ${\displaystyle D=P^{2}-4Q}$ is not a square, can be expressed in terms of Lucas sequences ${\displaystyle U_{n}(P,Q)}$ and ${\displaystyle V_{n}(P,Q)}$ as follows.

A composite number n is a Frobenius ${\displaystyle (P,Q)}$ pseudoprime if and only if

${\displaystyle (1)\qquad \gcd(n,2QD)=1,}$

${\displaystyle (2)\qquad U_{n-\delta }(P,Q)\equiv 0{\pmod {n}},}$ and

${\displaystyle (3)\qquad V_{n-\delta }(P,Q)\equiv 2Q^{(1-\delta )/2}{\pmod {n}},}$

where ${\displaystyle \delta =\left({\tfrac {D}{n}}\right)}$ is the Jacobi symbol.

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

${\displaystyle (3')\qquad V_{n}(P,Q)\equiv P{\pmod {n}}.}$

Therefore, Frobenius ${\displaystyle (P,Q)}$ pseudoprime n can be equivalently defined by conditions (1-2) and (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 prime test. (If condition (1) fails, 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 you should try different parameters P and Q which are not multiples of n.)

Every Frobenius ${\displaystyle (P,Q)}$ pseudoprime is also

• a Lucas pseudoprime with parameters ${\displaystyle (P,Q)}$, since it is defined by conditions (1) and (2);[2][3][5]
• a Dickson pseudoprime with parameters ${\displaystyle (P,Q)}$, since it is defined by conditions (1) and (3');[5]
• a Fermat pseudoprime base ${\displaystyle |Q|}$ when ${\displaystyle |Q|>1}$.

Converse of none of these statements is true, making the Frobenius ${\displaystyle (P,Q)}$ pseudoprimes a proper subset of each of the sets of Lucas pseudoprimes and Dickson pseudoprimes with parameters ${\displaystyle (P,Q)}$, and Fermat pseudoprimes base ${\displaystyle |Q|}$ when ${\displaystyle |Q|>1}$. Furthermore, it follows that for the same parameters ${\displaystyle (P,Q)}$, a composite number is a Frobenius pseudoprime if and only if it is both Lucas and Dickson pseudoprime. In other words, for every fixed pair of parameters ${\displaystyle (P,Q)}$, the set of Frobenius pseudoprimes equals the intersection of the sets of Lucas and Dickson pseudoprimes.

While each Frobenius ${\displaystyle (P,Q)}$ pseudoprime is a Lucas pseudoprime, it is not necessarily a strong Lucas pseudoprime. For example, 6721 is the first Frobenius pseudoprime for ${\displaystyle (P,Q)=(1,-1)}$, which is not a strong Lucas pseudoprime.

Every Frobenius pseudoprime to ${\displaystyle x^{3}-x-1}$ is also a restricted Perrin pseudoprime. Analogous statements hold for other cubic polynomials of the form ${\displaystyle x^{3}-rx^{2}+sx-1}$.[2]

Frobenius pseudoprimes with respect to the Fibonacci polynomial ${\displaystyle x^{2}-x-1}$ are determined in terms of the Fibonacci numbers ${\displaystyle F_{n}=U_{n}(1,-1)}$ and Lucas numbers ${\displaystyle L_{n}=V_{n}(1,-1)}$. Such Frobenius pseudoprimes form the sequence:

4181, 5777, 6721, 10877, 13201, 15251, 34561, 51841, 64079, 64681, 67861, 68251, 75077, 90061, 96049, 97921, 100127, 113573, 118441, 146611, 161027, 162133, 163081, 186961, 197209, 219781, 231703, 252601, 254321, 257761, 268801, 272611, 283361, 302101, 303101, 330929, 399001, 430127, 433621, 438751, 489601, ... (sequence A212424 in the OEIS).

While 323 is the first Lucas pseudoprime with respect to the Fibonacci polynomial ${\displaystyle x^{2}-x-1}$, 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 ${\displaystyle \left({\tfrac {5}{n}}\right)=-1}$ for this polynomial[3]).

Another case, Frobenius pseudoprimes with respect to the quadratic polynomial ${\displaystyle x^{2}-3x-1}$ can be determined using the Lucas ${\displaystyle (3,-1)}$ sequence and are:

119, 649, 1189, 4187, 12871, 14041, 16109, 23479, 24769, 28421, 31631, 34997, 38503, 41441, 48577, 50545, 56279, 58081, 59081, 61447, 75077, 91187, 95761, 96139, 116821, 127937, 146329, 148943, 150281, 157693, 170039, 180517, 188501, 207761, 208349, 244649, 281017, 311579, 316409, 349441, 350173, 363091, 371399, 397927, 423721, 440833, 459191, 473801, 479119, 493697, ... (sequence A327655 in the OEIS)

In this case, the first Frobenius pseudoprime with respect to the quadratic polynomial ${\displaystyle x^{2}-3x-1}$ is 119, which is also the first Lucas pseudoprime with respect to the same polynomial. Besides, ${\displaystyle \left({\tfrac {13}{119}}\right)=-1}$.

The quadratic polynomial ${\displaystyle x^{2}-3x-5}$, i.e. ${\displaystyle (P,Q)=(3,-5)}$, has sparser pseudoprimes as compared to many other simple quadratics. Using the same process as above, we get the sequence:

13333, 44801, 486157, 1615681, 3125281, 4219129, 9006401, 12589081, 13404751, 15576571, 16719781, ….

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. (note that Lucas pseudoprime for a (P, Q) pair need not to be a Fermat pseudoprime for base |Q|, e.g. 14209 is a Lucas (1, −3) pseudoprime, but not a Fermat pseudoprime for base 3.

Strong Frobenius pseudoprimes are also defined.[2] Details on implementation for quadratic polynomials can be found in Crandall and Pomerance.[3]

By imposing the restrictions that ${\displaystyle \delta =-1}$ and ${\displaystyle Q\neq \pm 1}$, the authors of [6] show how to choose ${\displaystyle P}$ and ${\displaystyle Q}$ such that there are only five odd, composite numbers less than ${\displaystyle 10^{15}}$ for which (3) holds, that is, for which ${\displaystyle V_{n+1}\equiv 2Q{\pmod {n}}}$.

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 ${\displaystyle (P,Q)}$, 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 ${\displaystyle \left({\tfrac {D}{n}}\right)=-1}$, there are no pseudoprimes below ${\displaystyle 2^{64}}$.

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

${\displaystyle (1+{\sqrt {c}})^{n}\equiv (1-{\sqrt {c}}){\pmod {n}}}$.

While all prime n pass this test, a composite n passes it if and only if n is a Frobenius pseudoprime for ${\displaystyle (P,Q)=(2,1-c)}$. 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⁶⁰ must have a factor less than 19 or have c > 128.

• Pseudoprime
• Lucas pseudoprime
• Ferdinand Georg Frobenius
• Quadratic Frobenius test

• Weisstein, Eric W. "Frobenius Pseudoprime". MathWorld.
• Weisstein, Eric W. "Strong Frobenius Pseudoprime". MathWorld.
• Jacobsen, Dana Pseudoprime Statistics, Tables, and Data (data for Frobenius (1,-1) and (3,-5) pseudoprimes)