The quadratic Frobenius test (QFT) is a
probabilistic
Probability is the branch of mathematics concerning numerical descriptions of how likely an Event (probability theory), event is to occur, or how likely it is that a proposition is true. The probability of an event is a number between 0 and ...
primality test
A primality test is an algorithm for determining whether an input number is prime. Among other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating whet ...
to determine whether a number is a
probable prime. It is named after
Ferdinand Georg Frobenius
Ferdinand Georg Frobenius (26 October 1849 – 3 August 1917) was a German mathematician, best known for his contributions to the theory of elliptic functions, differential equations, number theory, and to group theory. He is known for the famous ...
. 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
Composite or compositing may refer to:
Materials
* Composite material, a material that is made from several different substances
** Metal matrix composite, composed of metal and other parts
** Cermet, a composite of ceramic and metallic materials
...
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
Jacobi symbol for various ''k'' (along top) and ''n'' (along left side). Only are shown, since due to rule (2) below any other ''k'' can be reduced modulo ''n''. Quadratic residues are highlighted in yellow — note that no entry with a ...
. 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
In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to modular arithmetic was developed by Carl Friedrich Gauss in his book ...
*
Multiplicative group of integers modulo n
References
{{Number-theoretic algorithms, state=collapsed
Primality tests