Fermat's primality test - Simple English Wikipedia

# Fermat's primality test

### From Wikipedia, a free encyclopedia written in simple English for easy reading.

Fermat's primality test is an algorithm. It is a recipe for computers. It can test if a given number p is probably prime. There is a flaw however: There are numbers that pass the test, and that are not prime.

## [edit] Concept

Fermat's little theorem states that if p is prime and , then

  .

If we want to test if n is prime, then we can pick random a's in the interval and see if the equation above holds. If the equality does not hold for a value of a, then n is composite (not prime). If the equality does hold for many values of a, then we can say that n is probably prime, or a pseudoprime.

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.

pmod(n) is the modulo operation. Its result is what remains, if you divide p by n. As an example:

## [edit] What the test is used for

The RSA algorithm for public-key encryption can be done in such a way that it uses this test. This is useful in cryptography

Retrieved from "http://simple.wikipedia.org../../../f/e/r/Fermat%27s_primality_test.html"

Categories: Computer science | Mathematics

##### Views

- Article
- Talk
- Newest version

##### Search

##### In other languages

- Deutsch
- English
- Español
- Français
- Tiếng Việt
- 中文