Fermat's Primality Test
   HOME

TheInfoList



OR:

The Fermat primality test is a
probabilistic Probability is a branch of mathematics and statistics concerning events and numerical descriptions of how likely they are to occur. The probability of an event is a number between 0 and 1; the larger the probability, the more likely an e ...
test to determine whether a number is a
probable prime In number theory, a probable prime (PRP) is an integer that satisfies a specific condition that is satisfied by all prime numbers, but which is not satisfied by most composite numbers. Different types of probable primes have different specific co ...
.


Concept

Fermat's little theorem In number theory, Fermat's little theorem states that if is a prime number, then for any integer , the number is an integer multiple of . In the notation of modular arithmetic, this is expressed as a^p \equiv a \pmod p. For example, if and , t ...
states that if ''p'' is prime and ''a'' is not divisible by ''p'', then :a^ \equiv 1 \pmod. If one wants to test whether ''p'' is prime, then we can pick random integers ''a'' not divisible by ''p'' and see whether the congruence holds. If it does not hold for a value of ''a'', then ''p'' is composite. This congruence is unlikely to hold for a random ''a'' if ''p'' is composite. Therefore, if the equality does hold for one or more values of ''a'', then we say that ''p'' is probably prime. However, note that the above congruence holds trivially for a \equiv 1 \pmod, because the congruence relation is compatible with exponentiation. It also holds trivially for a \equiv -1 \pmod if ''p'' is odd, for the same reason. That is why one usually chooses a random ''a'' in the interval 1 < a < p - 1. Any ''a'' such that :a^ \equiv 1 \pmod when ''n'' is composite is known as a ''Fermat liar''. In this case ''n'' is called
Fermat pseudoprime In number theory, the Fermat pseudoprimes make up the most important class of pseudoprimes that come from Fermat's little theorem. Definition Fermat's little theorem states that if p is prime and a is coprime to p, then a^-1 is divisible by p. F ...
to base ''a''. If we do pick an ''a'' such that :a^ \not\equiv 1 \pmod then ''a'' is known as a ''Fermat witness'' for the compositeness of ''n''.


Example

Suppose we wish to determine whether ''n'' = 221 is prime. Randomly pick 1 < ''a'' < 220, say ''a'' = 38. We check the above congruence and find that it holds: :a^ = 38^ \equiv 1 \pmod. Either 221 is prime, or 38 is a Fermat liar, so we take another ''a'', say 24: :a^ = 24^ \equiv 81 \not\equiv 1 \pmod. So 221 is composite and 38 was indeed a Fermat liar. Furthermore, 24 is a Fermat witness for the compositeness of 221.


Algorithm

The algorithm can be written as follows: :Inputs: ''n'': a value to test for primality, ''n''>3; ''k'': a parameter that determines the number of times to test for primality :Output: ''composite'' if ''n'' is composite, otherwise ''probably prime'' :Repeat ''k'' times: ::Pick ''a'' randomly in the range , ''n'' − 2::If a^\not\equiv1 \pmod n, then return ''composite'' :If composite is never returned: return ''probably prime'' The ''a'' values 1 and ''n'' − 1 are not used as the equality holds for all ''n'' and all odd ''n'' respectively, hence testing them adds no value.


Complexity

Using fast algorithms for
modular exponentiation Modular exponentiation is exponentiation performed over a modulus. It is useful in computer science, especially in the field of public-key cryptography, where it is used in both Diffie–Hellman key exchange and RSA public/private keys. Modula ...
and multiprecision multiplication, the running time of this algorithm is , where ''k'' is the number of times we test a random ''a'', and ''n'' is the value we want to test for primality; see
Miller–Rabin primality test The Miller–Rabin primality test or Rabin–Miller primality test is a probabilistic primality test: an algorithm which determines whether a given number is likely to be prime, similar to the Fermat primality test and the Solovay–Strassen pr ...
for details.


Flaw

There are infinitely many
Fermat pseudoprime In number theory, the Fermat pseudoprimes make up the most important class of pseudoprimes that come from Fermat's little theorem. Definition Fermat's little theorem states that if p is prime and a is coprime to p, then a^-1 is divisible by p. F ...
s to any given basis ''a'' > 1. Even worse, there are infinitely many
Carmichael number In number theory, a Carmichael number is a composite number which in modular arithmetic satisfies the congruence relation: : b^n\equiv b\pmod for all integers . The relation may also be expressed in the form: : b^\equiv 1\pmod for all integers b ...
s. These are numbers n for which all values of a with \operatorname(a, n) = 1 are Fermat liars. For these numbers, repeated application of the Fermat primality test performs the same as a simple random search for factors. While Carmichael numbers are substantially rarer than prime numbers (Erdös' upper bound for the number of Carmichael numbers is lower than the prime number function n/log(n)) there are enough of them that Fermat's primality test is not often used in the above form. Instead, other more powerful extensions of the Fermat test, such as Baillie–PSW, Miller–Rabin, and Solovay–Strassen are more commonly used. In general, if n is a composite number that is not a Carmichael number, then at least half of all :a\in(\mathbb/n\mathbb)^* (i.e. \operatorname(a,n)=1) are Fermat witnesses. For proof of this, let a be a Fermat witness and a_1, a_2, ..., a_s be Fermat liars. Then :(a\cdot a_i)^ \equiv a^\cdot a_i^ \equiv a^ \not\equiv 1\pmod and so all a \cdot a_i for i = 1, 2, ..., s are Fermat witnesses.


Applications

As mentioned above, most applications use a Miller–Rabin or Baillie–PSW test for primality. Sometimes a Fermat test (along with some trial division by small primes) is performed first to improve performance. GMP since version 3.0 uses a base-210 Fermat test after trial division and before running Miller–Rabin tests.
Libgcrypt Libgcrypt is a cryptography library developed as a separated module of GnuPG. It can also be used independently of GnuPG, but depends on its error-reporting library Libgpg-error. It provides functions for all fundamental cryptographic building b ...
uses a similar process with base 2 for the Fermat test, but
OpenSSL OpenSSL is a software library for applications that provide secure communications over computer networks against eavesdropping, and identify the party at the other end. It is widely used by Internet servers, including the majority of HTTPS web ...
does not. In practice with most big number libraries such as GMP, the Fermat test is not noticeably faster than a Miller–Rabin test, and can be slower for many inputs. As an exception, OpenPFGW uses only the Fermat test for probable prime testing. The program is typically used with multi-thousand digit inputs with a goal of maximum speed with very large inputs. Another well known program that relies only on the Fermat test is PGP where it is only used for testing of self-generated large random values (an open source counterpart,
GNU Privacy Guard GNU Privacy Guard (GnuPG or GPG) is a free-software replacement for Symantec's cryptographic software suite PGP. The software is compliant with the now obsoleted , the IETF standards-track specification of OpenPGP. Modern versions of PGP are ...
, uses a Fermat pretest followed by Miller–Rabin tests).


References

* {{number theoretic algorithms Primality tests Modular arithmetic