Quadratic Frobenius test

The quadratic Frobenius test (QFT) is a probabilistic primality test to determine 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. It should not be confused with the more general Frobenius test using a quadratic polynomial – the QFT restricts the polynomials allowed based on the input, and also has other conditions that must be met. A composite passing this test is a Frobenius pseudoprime, but the converse is not necessarily true.

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, and let b and c be integers such that $\left({\frac {b^{2}+4c}{n}}\right)=-1$ and $\left({\frac {-c}{n}}\right)=1$ , where $\left({\frac {\cdot }{\cdot }}\right)$ 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: n is composite.

(2) Test whether

{\sqrt {n}}\in \mathbb {Z}

. If yes, then stop: 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: n is composite.

(4) Compute

x^{n+1}\,{\bmod {\,}}{\big (}n,x^{2}-bx-c)

. If

x^{n+1}\not \equiv -c

, then stop: 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: n is composite.

If the QFT does not stop in steps (1)–(5), then n is a probable prime.

(The notation $A\equiv B{\bmod {\,}}(n,\,f(x))$ means that $A-B=H(x)\cdot n+K(x)\cdot f(x)$ , where H and K are polynomials.)

References

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