Quadratic Frobenius test

The quadratic Frobenius test (QFT) is a probabilistic primality test to test whether a number is a probable prime. It is named after Ferdinand Georg Frobenius. The test uses the concepts of quadratic polynomials and the Frobenius automorphism. A composite passing this test is called a Frobenius pseudoprime.

Concept

Grantham's stated goal when developing the algorithm was to provide a test that primes would always pass and composites would pass with a probability of less than 1/7710.[1]:33

The test was later extended by Damgård and Frandsen to a test called extended quadratic Frobenius test (EQFT).[2]

Algorithm

Let n be a positive integer such that n is odd, (b2 + 4c | n) = −1 and (−c | n) = 1, where (x | n) denotes the Jacobi symbol. Set B = 50000. Then a QFT on n with parameters (b, c) works as follows:

(1) Test whether one of the primes less than or equal to the lower of the two values B and \sqrt{n} divides n. If yes, then stop as n is composite.
(2) Test whether \sqrt{n} \in \mathbb{Z}. If yes, then stop as n is composite.
(3) Compute x^{n+1 \over 2}\,\bmod\,\big(n,x^2-bx-c). If x^{n+1 \over 2} \notin \mathbb{Z} \big / n \mathbb{Z} then stop as n is composite.
(4) Compute x^{n+1}\,\bmod\,\big(n,x^2-bx-c). If x^{n+1} \not\equiv -c then stop as n is composite.
(5) Let n^2-1=2^{r}s with s odd. If x^s \not\equiv 1 \bmod\,\big(n,x^2-bx-c), and x^{2^{j}s} \not\equiv -1 \bmod\,\big(n,x^2-bx-c) for all 0 \leq j \leq r-2, then stop as n is composite.

If the QFT doesn't stop in steps (1)–(5), then n is a probable prime.

See also

References

  1. ↑ Grantham, J. (1998). "A Probable Prime Test With High Confidence". Journal of Number Theory (Academic Press) 72 (1): 32–47. doi:10.1006/jnth.1998.2247.
  2. ↑ Damgård, Ivan Bjerre; Frandsen, Gudmund Skovbjerg (2003). "An Extended Quadratic Frobenius Primality Test with Average and Worst Case Error Estimates". Lecture Notes in Computer Science. Fundamentals of Computation Theory (Springer Berlin Heidelberg) 2751: 118–131. doi:10.1007/978-3-540-45077-1_12. ISBN 978-3-540-45077-1. ISSN 1611-3349.