Quadratic Frobenius test

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]

Let n be a positive integer such that n is odd, and let b and c be integers such that ${\displaystyle \left({\frac {b^{2}+4c}{n}}\right)=-1}$ and ${\displaystyle \left({\frac {-c}{n}}\right)=1}$, where ${\displaystyle \left({\frac {\cdot }{\cdot }}\right)}$ denotes the Jacobi symbol. Set ${\displaystyle B=50000}$. Then a QFT on n with parameters (b, c) works as follows:

(1) Test whether any of the primes less than or equal to ${\displaystyle \min(B,{\sqrt {n}})}$ divides n. If yes, then stop: n is composite.

(2) Test whether ${\displaystyle {\sqrt {n}}\in \mathbb {Z} }$. If yes, then stop: n is composite.

(3) Compute ${\displaystyle x^{n+1 \over 2}\,{\bmod {\,}}{\big (}n,x^{2}-bx-c)}$. If ${\displaystyle x^{n+1 \over 2}\notin \mathbb {Z} {\big /}n\mathbb {Z} }$, then stop: n is composite.

(4) Compute ${\displaystyle x^{n+1}\,{\bmod {\,}}{\big (}n,x^{2}-bx-c)}$. If ${\displaystyle x^{n+1}\not \equiv -c}$, then stop: n is composite.

(5) Let ${\displaystyle n^{2}-1=2^{r}s}$ with s odd. If ${\displaystyle x^{s}\not \equiv 1{\bmod {\,}}{\big (}n,x^{2}-bx-c)}$, and ${\displaystyle x^{2^{j}s}\not \equiv -1{\bmod {\,}}{\big (}n,x^{2}-bx-c)}$ for all ${\displaystyle 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 ${\displaystyle A\equiv B{\bmod {\,}}(n,\,f(x))}$ means that ${\displaystyle A-B=H(x)\cdot n+K(x)\cdot f(x)}$, where H and K are polynomials.)

• Integers modulo n
• Multiplicative group of integers modulo n