Quadratic Frobenius test

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 n be a positive integer such that n is odd, (b² + 4c | n) = −1 and (−c | n) = 1, where (x | n) 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 n divides n. If yes, then stop as n is composite. (2) Test whether n ∈ Z . If yes, then stop as n is composite. (3) Compute x n + 1 2 mod ( n , x 2 − b x − c ) . If x n + 1 2 ∉ Z / n Z then stop as n is composite. (4) Compute x n + 1 mod ( n , x 2 − b x − c ) . If x n + 1 ≢ − c then stop as n is composite. (5) Let n 2 − 1 = 2 r s with s odd. If x s ≢ 1 mod ( n , x 2 − b x − c ) , and x 2 j s ≢ − 1 mod ( n , x 2 − b x − c ) for all 0 ≤ j ≤ r − 2 , then stop as n is composite.

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