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
x2-Px+Q
D=P2-4Q
Un(P,Q)
Vn(P,Q)
A composite number n is a Frobenius
(P,Q)
(1) \gcd(n,2QD)=1,
(2) Un-\delta(P,Q)\equiv0\pmodn,
(3) Vn-\delta(P,Q)\equiv2Q(1-\delta)/2\pmod{n},
\delta=\left(\tfracDn\right)
When condition (2) is satisfied, condition (3) becomes equivalent to
(3') Vn(P,Q)\equivP\pmod{n}.
(P,Q)
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 .)
Every Frobenius
(P,Q)
(P,Q)
(P,Q)
|Q|
|Q|>1
(P,Q)
(P,Q)
|Q|
|Q|>1
(P,Q)
(P,Q)
While each Frobenius
(P,Q)
(P,Q)=(1,-1)
Every Frobenius pseudoprime to
x3-x-1
x3-rx2+sx-1
Frobenius pseudoprimes with respect to the Fibonacci polynomial
x2-x-1
Fn=Un(1,-1)
Ln=Vn(1,-1)
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, ... .
While 323 is the first Lucas pseudoprime with respect to the Fibonacci polynomial
x2-x-1
\left(\tfrac{5}{n}\right)=-1
Another case, Frobenius pseudoprimes with respect to the quadratic polynomial
x2-3x-1
(3,-1)
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, ...
In this case, the first Frobenius pseudoprime with respect to the quadratic polynomial
x2-3x-1
\left(\tfrac{13}{119}\right)=-1
The quadratic polynomial
x2-3x-5
(P,Q)=(3,-5)
13333, 44801, 486157, 1615681, 3125281, 4219129, 9006401, 12589081, 13404751, 15576571, 16719781, ….
Notice there are only 3 such pseudoprimes below 500,000, while there are many Frobenius (1, −1) and (3, −1) pseudoprimes below 500,000.
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: 642,001 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 pair need not to be a Fermat pseudoprime for base ||, 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
\delta=-1
Q ≠ \pm1
P
Q
1015
Vn+1\equiv2Q\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
(P,Q)
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
\left(\tfrac{D}{n}\right)=-1
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
\left(\tfrac{c}{n}\right)=-1
(1+\sqrt{c})n\equiv(1-\sqrt{c})\pmodn
(P,Q)=(2,1-c)
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 U1764(3,–1) ≡ 0 (mod 1763) (U(3,–1) is given in), and it also passes the Jacobi step since
\left(\tfrac{13}{1763}\right)=-1
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,[8] using a quadratic Frobenius test plus other conditions, has a bound of
\tfrac{1}{7710}
\tfrac{1}{131040t}
\tfrac{256}{{331776}t}
\tfrac{1}{{4096}t}
\tfrac{16}{336442t}
Given the same computational effort, these offer better worst-case bounds than the commonly used Miller–Rabin primality test.