Frobenius pseudoprime

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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. [1] [2] It has been studied by other authors for the case of quadratic polynomials. [3] [4]

The test for quadratic polynomials[edit]

A Frobenius test is defined in terms of a monic polynomial. The case of a degree-2 polynomial (a quadratic) is common and can be shown in terms of Lucas sequences, lending itself to fast implementations.

For the polynomial \scriptstyle x^2 - Px + Q, where \scriptstyle D = P^2-4Q is not a square, n a composite number, \scriptstyle\gcd(n,2QD)=1, and k the Jacobi symbol \scriptstyle\left(\tfrac{D}{n}\right), n is a Frobenius (P,Q) pseudoprime if and only if

 \text{  } (1) \text{     } U_{n-k} \equiv 0 \pmod n

and

 \text{  } (2) \text{     } V_{n-k} \equiv \begin{cases}2Q&\mbox{if }k=-1\\2&\mbox{if }k=1\mbox{.}\end{cases}

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 (P,Q) pseudoprime is also a Lucas (P,Q) pseudoprime, but because of the additional condition (2), the converse is not true.

Example[edit]

Frobenius pseudoprimes with respect to the quadratic polynomial \scriptstyle x^2-3x-1 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, ...

The quadratic polynomial \scriptstyle x^2-3x-5, with \scriptstyle (P,Q)=(3,-5), has sparse pseudoprimes compared to many other simple quadratics. Using the same process above we get the sequence:

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

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.

Using parameter selection ideas first laid out in Baillie and Wagstaff 1980 [5] as part of the Baillie-PSW primality test and used by Grantham in his Quadratic Frobenius Test [6] we can create even better quadratic tests, for instance using the parameters (P,2) where P is the first odd that satisfies \scriptstyle\left(\tfrac{D}{n}\right) = -1, which has no pseudoprimes less than \scriptstyle 2^{64}.

Relations to other pseudoprimes[edit]

For quadratic polynomials \scriptstyle x^2-Px+Q, every Frobenius (P,Q) pseudoprime is also a Lucas (P,Q) pseudoprime. [2] [3] [7] 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 \scriptstyle V_k indicate it must also be a Dickson pseudoprime of the second kind.[7]

Every Frobenius pseudoprime to x^3-rx^2+sx-1 is also a Perrin pseudoprime.[2]

Alternate formulations[edit]

An alternate formulation is given by Khashin.[8] Given a number n, not a perfect square, where c is the smallest odd prime with Jacobi symbol \left(\tfrac{c}{n}\right)=-1, n is a either a prime or Frobenius pseudoprime if:

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

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.[5] 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 260 must have a factor less than 19 or have c > 128.

Strong Frobenius pseudoprimes[edit]

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

Properties[edit]

The computational cost of the Frobenius pseudoprime test for quadratic polynomials is roughly three times the cost of a strong pseudoprime test (e.g. a single round of the Miller-Rabin primality test), 1.5 times that of a Lucas pseudoprime 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 = 0 (mod 1763) where U is OEISA006190, and it also passes the Jacobi step since \left(\tfrac{13}{1763}\right) = -1, but it fails the Frobenius test to x2 - 3x - 1. 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. 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[6] has a bound of \tfrac{1}{7710}. Müller in 2001 proposed the MQFT test with bounds of essentially \tfrac{1}{131040^t}. [9] Damgård and Frandsen in 2003 proposed the EQFT with a bound of essentially \tfrac{256}{{331776}^t}. [10] Seysen in 2005 proposed the SQFT test with a bound of \tfrac{1}{{4096}^t} and a SQFT3 test with a bound of \tfrac{16}{336442^t}. [11]

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

See also[edit]

References[edit]

  1. ^ Jon Grantham (1998). Frobenius pseudoprimes (Report). preprint. 
  2. ^ a b c d Jon Grantham (2001). "Frobenius pseudoprimes". Mathematics of Computation 70 (234): 873–891. doi:10.1090/S0025-5718-00-01197-2. 
  3. ^ a b c d Richard Crandall; Carl Pomerance (2005). Prime numbers: A computational perspective (2nd ed.). Springer-Verlag. ISBN 0-387-25282-7. 
  4. ^ a b Daniel Loebenberger (2008). "A Simple Derivation for the Frobenius Pseudoprime Test" (PDF). IACR Cryptology ePrint Archive 2008. 
  5. ^ a b Robert Baillie; Samuel S. Wagstaff, Jr. (October 1980). "Lucas Pseudoprimes" (PDF). Mathematics of Computation 35 (152): 1391–1417. doi:10.1090/S0025-5718-1980-0583518-6. MR 583518. 
  6. ^ a b Jon Grantham (1998). "A Probable Prime Test With High Confidence". Journal of Number Theory (Academic Press) 72 (1): 32–47. doi:10.1006/jnth.1998.2247. 
  7. ^ a b Andrzej Rotkiewicz (2003). "Lucas and Frobenius pseudoprimes" (PDF). Annales Mathematicae Silesianae (Wydawnictwo Uniwersytetu Śląskiego) 17: 17–39. 
  8. ^ A bot will complete this citation soon. Click here to jump the queue arXiv:1307.7920.
  9. ^ Siguna Müller (2001). "A Probable Prime Test with Very High Confidence for N Equiv 1 Mod 4". Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology. ASIACRYPT. pp. 87–106. doi:10.1007/3-540-45682-1_6. ISBN 3-540-42987-5. 
  10. ^ Ivan Bjerre Damgård; Gudmund Skovbjerg Frandsen (October 2006). "An Extended Quadratic Frobenius Primality Test with Average- and Worst-Case Error Estimate" (PDF). Journal of Cryptology 19 (4): 489–520. doi:10.1007/s00145-006-0332-x. 
  11. ^ Martin Seysen. A Simplified Quadratic Frobenius Primality Test, 2005, http://eprint.iacr.org/2005/462

External links[edit]