Contents

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]

Algorithm[edit]

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 QFTonn 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 ${\displaystyle B}$ and ${\displaystyle {\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.)

See also[edit]

• Integers modulo n
• Multiplicative group of integers modulo n

References[edit]