View source for Frobenius pseudoprime

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.
<ref name="Grantham98">{{cite report |author=Jon Grantham |title=Frobenius pseudoprimes |date=1998 |publisher=preprint |url=http://www.pseudoprime.com/pseudo1.ps}}</ref>
<ref name="Grantham01">{{cite journal |author=Jon Grantham |title=Frobenius pseudoprimes |journal=Mathematics of Computation |volume=70 |issue=234 |pages=873–891 |year=2001 |doi=10.1090/S0025-5718-00-01197-2}}</ref>
It has been studied by other authors for the case of quadratic polynomials.
<ref name="CP05">{{cite book | title=Prime numbers: A computational perspective | edition=2nd | author=Richard Crandall | authorlink=Richard Crandall |author2=Carl Pomerance | authorlink2=Carl Pomerance | publisher=[[Springer-Verlag]] | year=2005 | isbn=978-0-387-25282-7}}</ref>
<ref name="Loebenberger08">{{cite journal | author = Daniel Loebenberger | title = A Simple Derivation for the Frobenius Pseudoprime Test | journal = IACR Cryptology ePrint Archive | volume = 2008 | year = 2008 | url = https://eprint.iacr.org/2008/124.pdf}}</ref>

==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 <math>\scriptstyle x^2 - Px + Q</math>, where <math>\scriptstyle D = P^2-4Q</math> is not a square, is common and can be expressed in terms of [[Lucas sequence]]s <math>U_n(P,Q)</math> and <math>V_n(P,Q)</math>, leading to fast implementations for testing pseudoprimality.

A [[composite number]] ''n'' is a Frobenius <math>(P,Q)</math> pseudoprime if and only if <math>\textstyle\gcd(n,2QD)=1</math>,
:<math> (1) \qquad U_{n-k}(P,Q) \equiv 0 \pmod n</math>
and
:<math> (2) \qquad V_{n-k}(P,Q) \equiv \begin{cases}2Q\pmod n&\mbox{if }k=-1\\2\pmod n&\mbox{if }k=1\mbox{,}\end{cases}</math>
where <math>\scriptstyle k=\left(\tfrac{D}{n}\right)</math> is the [[Jacobi symbol]].

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 <math>(P,Q)</math> pseudoprime is also a Lucas <math>(P,Q)</math> pseudoprime, but because of the additional condition (2), the converse is not true.  On the other hand, some Frobenius pseudoprimes are not [[Lucas_pseudoprime#Strong_Lucas_pseudoprimes|strong Lucas pseudoprimes]] for the same parameters, e.g. 6721 is the first such number for <math>(P,Q) = (1,-1)</math>.

==Example==
Frobenius pseudoprimes with respect to the Fibonacci polynomial <math>\scriptstyle x^2-x-1</math> are determined in terms of the [[Fibonacci numbers]] <math>F_n = U_n(1,-1)</math> and [[Lucas numbers]] <math>L_n = V_n(1,-1)</math>. 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, … {{OEIS|id=A212424}}.

While 323 is the first [[Lucas pseudoprime]] with respect to the Fibonacci polynomial <math>\scriptstyle x^2-x-1</math>, the first Frobenius pseudoprime with respect to the same polynomial is 4181 (Grantham indicates it is 5777<ref name="Grantham01"/> but multiple authors have noted this is incorrect and is instead the first pseudoprime with <math>\left(\tfrac{5}{n}\right)=-1</math> for this polynomial<ref name="CP05"/>).

Another case, Frobenius pseudoprimes with respect to the quadratic polynomial <math>\scriptstyle x^2-3x-1</math> can be determined using the Lucas (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, ….

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

The quadratic polynomial <math>\scriptstyle x^2-3x-5</math>, with <math>\scriptstyle (P,Q)=(3,-5)</math>, has sparse 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'' or base −''Q'', e.g. 14209 is a Lucas (1, −3) pseudoprime, but not a Fermat pseudoprime for base 3.

Using parameter selection ideas first laid out in Baillie and Wagstaff (1980)<ref name="lpsp">{{cite journal |author2=[[Samuel S. Wagstaff, Jr.]]|title=Lucas Pseudoprimes|journal=Mathematics of Computation|date=October 1980|volume=35|issue=152|pages=1391–1417|url=http://mpqs.free.fr/LucasPseudoprimes.pdf|author=Robert Baillie| mr=583518| doi=10.1090/S0025-5718-1980-0583518-6 }}</ref>
as part of the [[Baillie-PSW primality test]] and used by Grantham in his [[quadratic Frobenius test]],<ref name="QFT">{{cite journal | author = Jon Grantham | title = A Probable Prime Test With High Confidence | journal = Journal of Number Theory | volume = 72 | issue = 1 | pages = 32–47 | date = 1998 |eprint = 1903.06823 | doi = 10.1006/jnth.1998.2247| citeseerx = 10.1.1.56.8827 }}</ref>
one can create even better quadratic tests. For instance, for the parameters (''P'',2), where ''P'' is the first odd integer that satisfies <math>\scriptstyle\left(\tfrac{D}{n}\right) = -1</math>, there are no pseudoprimes below <math>\scriptstyle 2^{64}</math>.

==Relations to other pseudoprimes==

For quadratic polynomials <math>\scriptstyle x^2-Px+Q</math>, every Frobenius (P,Q) pseudoprime is also a Lucas (P,Q) pseudoprime.
<ref name="Grantham01"/>
<ref name="CP05"/>
<ref name="Rotkiewicz03">{{cite journal | author = Andrzej Rotkiewicz | title = Lucas and Frobenius pseudoprimes | journal = Annales Mathematicae Silesianae | volume = 17 | date = 2003 | pages=17–39 | publisher = Wydawnictwo Uniwersytetu Śląskiego | url = http://www.sbc.org.pl/Content/33711/2003_03.pdf}}</ref>
This immediately follows from condition (1) which defined a Lucas (P,Q) pseudoprime.
The converse is not true, making the Frobenius pseudoprimes a subset of the Lucas pseudoprimes for a given (P,Q).  The condition on <math>\scriptstyle V_k</math> means it is a [[Dickson pseudoprime]] of the second kind.<ref name="Rotkiewicz03"/>

Every Frobenius pseudoprime to <math>x^3-rx^2+sx-1</math> is also a [[Perrin pseudoprime]].<ref name="Grantham01"/>

==Alternate formulations==

An alternate formulation is given by Khashin.<ref name="Khashin13">{{cite arXiv |last=Khashin |first=Sergey |eprint=1307.7920 |class=math.NT |date=July 2013|title=Counterexamples for Frobenius primality test }}</ref> Given a number ''n'', not a perfect square, where ''c'' is the smallest odd prime with Jacobi symbol <math>\left(\tfrac{c}{n}\right)=-1</math>, ''n'' is either a prime or Frobenius pseudoprime if:

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

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.<ref name="lpsp"/> 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 2<sup>60</sup> must have a factor less than 19 or have ''c'' > 128.

==Strong Frobenius pseudoprimes==
Strong Frobenius pseudoprimes are also defined.<ref name="Grantham01"/>  Details on implementation for quadratic polynomials can be found in Crandall and Pomerance.<ref name="CP05"/>

==Properties==

The computational cost of the Frobenius pseudoprimality test with respect to quadratic polynomials  is roughly three times the cost of a [[strong pseudoprime|strong pseudoprimality]] test (e.g. a single round of the [[Miller-Rabin primality test]]), 1.5 times that of a [[Lucas pseudoprime|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 {{oeis|id=A006190}}), 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> - 3''x'' - 1.  This property can be clearly seen when the algorithm is formulated as shown in Crandall and Pomerance Algorithm 3.6.9<ref name="CP05"/> or as shown by Loebenberger,<ref name="Loebenberger08"/> 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.  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]],<ref name="QFT"/> using a quadratic Frobenius test plus other conditions, has a bound of <math>\tfrac{1}{7710}</math>. Müller in 2001 proposed the MQFT test with bounds of essentially <math>\tfrac{1}{131040^t}</math>.
<ref>{{cite conference | author = Siguna Müller | title = A Probable Prime Test with Very High Confidence for N Equiv 1 Mod 4 | conference = ASIACRYPT | booktitle = Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology | year = 2001 | pages = 87–106 | isbn = 3-540-42987-5 | doi = 10.1007/3-540-45682-1_6}}</ref>
Damgård and Frandsen in 2003 proposed the EQFT with a bound of essentially <math>\tfrac{256}{{331776}^t}</math>.
<ref>{{cite journal | author = Ivan Bjerre Damgård | author2 = Gudmund Skovbjerg Frandsen | title = An Extended Quadratic Frobenius Primality Test with Average- and Worst-Case Error Estimate | journal = Journal of Cryptology | date = October 2006 | volume = 19 | number = 4 | pages = 489–520 | doi = 10.1007/s00145-006-0332-x | url = http://www.brics.dk/RS/03/9/BRICS-RS-03-9.pdf}}</ref>
Seysen in 2005 proposed the SQFT test with a bound of <math>\tfrac{1}{{4096}^t}</math> and a SQFT3 test with a bound of <math>\tfrac{16}{336442^t}</math>.
<ref>Martin Seysen. [http://eprint.iacr.org/2005/462 A Simplified Quadratic Frobenius Primality Test], 2005.</ref>

Given the same computational effort, these offer better worst-case bounds than the commonly used [[Miller-Rabin primality test]].

==See also==
*[[Pseudoprime]]
*[[Lucas pseudoprime]]
*[[Ferdinand Georg Frobenius]]
*[[Quadratic Frobenius test]]

== References ==
{{reflist|colwidth=30em}}

== External links ==
* {{MathWorld|urlname=FrobeniusPseudoprime|title=Frobenius Pseudoprime}}
* {{MathWorld|urlname=StrongFrobeniusPseudoprime|title=Strong Frobenius Pseudoprime}}
* Jacobsen, Dana [http://ntheory.org/pseudoprimes.html Pseudoprime Statistics, Tables, and Data] (data for Frobenius (1,-1) and (3,-5) pseudoprimes)

{{Classes of natural numbers}}

[[Category:Pseudoprimes]]