Fermat's little theorem states that if p is prime and a is not divisible by p, then 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.
This congruence is unlikely to hold for a random a if p is composite.
[1] Therefore, if the equality does hold for one or more values of a, then we say that p is probably prime.
, because the congruence relation is compatible with exponentiation.
In this case n is called Fermat pseudoprime to base a.
If we do pick an a such that then a is known as a Fermat witness for the compositeness of n. Suppose we wish to determine whether n = 221 is prime.
We check the above congruence and find that it holds: Either 221 is prime, or 38 is a Fermat liar, so we take another a, say 24: So 221 is composite and 38 was indeed a Fermat liar.
Using fast algorithms for modular exponentiation and multiprecision multiplication, the running time of this algorithm is O(k log2n log log n) = Õ(k log2n), 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 for details.
[1]: Theorem 1 Even worse, there are infinitely many Carmichael numbers.
For these numbers, repeated application of the Fermat primality test performs the same as a simple random search for factors.
Instead, other more powerful extensions of the Fermat test, such as Baillie–PSW, Miller–Rabin, and Solovay–Strassen are more commonly used.
As mentioned above, most applications use a Miller–Rabin or Baillie–PSW test for primality.
Libgcrypt uses a similar process with base 2 for the Fermat test, but OpenSSL 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.
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, uses a Fermat pretest followed by Miller–Rabin tests).