Fermat's primality test is a test, prich determines, whether the given integer is a prime or not. It is based on Fermat's little theorem, which states that for every prime p and its coprime a it holds that:

{ a^{p-1} \\equiv 1 \\bmod p}

If the equality does not hold, then we can be sure that the number is not a prime. If it does hold, the number might be a prime.


Example

Testing: 15
We choose: a = 5

We suppose:
 {2^{14} \\equiv 1 \\bmod 15}

The test:
 2^{14} = 2^{4} \\cdot 2^{4} \\cdot 2^{4} \\cdot 2^{2} = 16 \\cdot 16 \\cdot 16 \\cdot 4 = 1 \\cdot 1 \\cdot 1 \\cdot 4 = 4 \\;\\; in \\;\\; Z_{15}

Number 5 is a witness that 15 is not a prime.

Example 2

Testing: 15
We choose: a = 4

We suppose:
{4^{14} \\equiv 1 \\bmod 15}

The test:
 4^{14} = (4^2)^7 = 16^7 = 1^7 = 1 \\;\\; in \\;\\; Z_{15}

Number 4 implies that 15 is a prime, however it is not (we have determined that it is composite by the previous test). Let's denote number 4 as Fermat liar.

The flaw

The main flaw of the Fermat's primality test is existence of Carmichael numbers. The Carmichael numbers are absolute Fermat's pseudoprimes, which means that they will always pass this test as primes (regardless which base we choose). This implies that there is no way to compute the probability that the number is (not) a prime, provided it has passed through k iterations of the test.

For this reason Fermat's test is not often used in favor to other primality tests – for example Rabin-Miller, Solovay-Strassen or Lehmann test.








  1. Home
  2. Mathematics
  3. Primality
       
 

Place for your banner

Here is the position ready for our customer's banners.