Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Fermat primality test
Summary
The Fermat primality test is a probabilistic test to determine whether a number is a probable prime.
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. 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 , because the congruence relation is compatible with exponentiation. It also holds trivially for if p is odd, for the same reason. That is why one usually chooses a random a in the interval .
Any a such that
when n is composite is known as a Fermat liar. 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. Randomly pick 1 < a < 220, say a = 38. 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. Furthermore, 24 is a Fermat witness for the compositeness of 221.
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 [2, n − 2]
If , 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.
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.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.