The Fermat primality test is a probabilistic test to determine if a number is composite or probably prime. A randomized algorithm is an algorithm which is allowed to flip a truly random coin. ...

Concept

Fermat's little theorem states that if p is prime and , then Fermats little theorem (not to be confused with Fermats last theorem) states that if p is a prime number, then for any integer a, This means that if you take some number a, multiply it by itself p times and subtract a, the result is divisible by p...

.

If we want to test if n is prime, then we can pick random a's in the interval and see if the equality holds. If the equality does not hold for a value of a, then n is composite. If the equality does hold for many values of a, then we can say that n is probably prime, or a pseudoprime. A pseudoprime is a probable prime (an integer which shares a property common to all prime numbers) which is not actually prime. ...

It may be in our tests that we do not pick any value for a such that the equality fails. Any a such that

when n is composite is known as a Fermat liar. If we do pick an a such that

then a is known as a Fermat witness for the compositeness of n.

Algorithm and running time

The algorithm can be written as follows:

Inputs: n: a value to test for primality; 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 [1, n − 1]

if a^{n − 1} mod n ≠ 1 then return composite

return probably prime

Using fast algorithms for modular exponentiation, the running time of this algorithm is O(k × log³n), where k is the number of times we test a random a, and n is the value we want to test for primality. Jump to: navigation, search Modular exponentiation is a type of exponentiation performed over a modulus. ...

Flaws

There are certain values of n known as Carmichael numbers for which all values of a for which gcd(a,n)=1 are Fermat liars. Although Carmichael numbers are rare, there are enough of them that Fermat's primality test is often not used in favor of other primality tests such as Miller-Rabin and Solovay-Strassen. In number theory, a Carmichael number is a composite positive integer n which satisfies the congruence bn − 1 ≡ 1 (mod n) for all integers b which are relatively prime to n (see modular arithmetic). ... A primality test is an algorithm for determining whether an input number is prime. ... The Miller-Rabin primality test is a primality test: an algorithm which determines whether a given number is prime, similar to the Fermat primality test and the Solovay-Strassen primality test. ... The Solovay-Strassen primality test is a probabilistic test to determine if a number is composite or probably prime. ...

In general, if n is not a Carmichael number then at least half of all

are Fermat witnesses. For proof of this let a be a Fermat witness and a₁, a₂, ..., a_s be Fermat liars. Then

and so all a × a_i for i = 1, 2, ..., s are Fermat witnesses.

Usage

The encryption program PGP uses this primality test in its algorithms. Pgp is an acronym for: Pretty Good Privacy, a computer program for the encryption and decryption of data; P-glycoprotein, a type of protein Party for the Government of the People (Partido por el Gobierno del Pueblo} Pearl of Great Price the ICAO code for Perm Airlines This page concerning...