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.

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

Algorithm
Let  be a positive integer such that  is odd,  and , where  denotes the Jacobi symbol. Set . Then a QFT on  with parameters (, ) works as follows:

(1) Test whether one of the primes less than or equal to the lower of the two values  and  divides . If yes, then stop as  is composite.
(2) Test whether . If yes, then stop as  is composite.
(3) Compute . If  then stop as  is composite.
(4) Compute . If  then stop as  is composite.
(5) Let  with  odd. If , and  for all , then stop as  is composite.

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

(The notation  means that , where H and K are polynomials.)

See also
 Integers modulo n
 Multiplicative group of integers modulo n

References

Primality tests