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. 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, $\left({\frac {b^{2}+4c}{n}}\right)=-1$ and $\left({\frac {-c}{n}}\right)=1$ , where $\left({\frac {x}{n}}\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 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.

(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.
^ Damgård, Ivan Bjerre; Frandsen, Gudmund Skovbjerg (2003). An Extended Quadratic Frobenius Primality Test with Average and Worst Case Error Estimates (PDF). Lecture Notes in Computer Science. Fundamentals of Computation Theory. 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.

[Grantham-1] 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.

[DamFran-2] Damgård, Ivan Bjerre; Frandsen, Gudmund Skovbjerg (2003). An Extended Quadratic Frobenius Primality Test with Average and Worst Case Error Estimates (PDF). Lecture Notes in Computer Science. Fundamentals of Computation Theory. 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.

[1]

[2]

v t Number-theoretic algorithms
Primality tests	AKS APR Baillie–PSW Elliptic curve Pocklington Fermat Lucas Lucas–Lehmer Lucas–Lehmer–Riesel Proth's theorem Pépin's Quadratic Frobenius Solovay–Strassen Miller–Rabin
Prime-generating	Sieve of Atkin Sieve of Eratosthenes Sieve of Sundaram Wheel factorization
Integer factorization	Continued fraction (CFRAC) Dixon's Lenstra elliptic curve (ECM) Euler's Pollard's rho p − 1 p + 1 Quadratic sieve (QS) General number field sieve (GNFS) Special number field sieve (SNFS) Rational sieve Fermat's Shanks's square forms Trial division Shor's
Multiplication	Ancient Egyptian Long Karatsuba Toom–Cook Schönhage–Strassen Fürer's
Euclidean division	Binary Chunking Fourier Goldschmidt Newton-Raphson Long Short SRT
Discrete logarithm	Baby-step giant-step Pollard rho Pollard kangaroo Pohlig–Hellman Index calculus Function field sieve
Greatest common divisor	Binary Euclidean Extended Euclidean Lehmer's
Modular square root	Cipolla Pocklington's Tonelli–Shanks Berlekamp Kunerth
Other algorithms	Chakravala Cornacchia Exponentiation by squaring Integer square root Integer relation (LLL; KZ) Modular exponentiation Montgomery reduction Schoof
Italics indicate that algorithm is for numbers of special forms

Quadratic Frobenius test

Contents

Concept[]

Algorithm[]

See also[]

References[]