Skip to content
Tutorials Center
My learning

Topics

Lesson 20 of 37 ยท Primality and Factoring

The Fermat Primality Test

Use Fermat's little theorem to test whether a number is probably prime, see why liars and Carmichael numbers break the test, and code it in Python.

How do you decide whether a 300-digit number is prime? Trial division would take longer than the age of the universe. We need a test that does not try to find a factor at all. It should look for some property that every prime has and most composites lack.

Fermat's little theorem gives us exactly that property. If p is prime and p does not divide a, then a^(p-1) โ‰ก 1 (mod p). Turn the statement around and you get a test: if you find an a with a^(n-1) mod n โ‰  1, the number n is certainly composite. This lesson builds that test, shows where it fails, and prepares the ground for the stronger Miller-Rabin test.

The test in one line

Python's three-argument pow(a, e, n) computes a**e % n by repeated squaring, so even huge exponents are fast. The Fermat test is therefore tiny.

Python A first Fermat test

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A True is a proof: n is composite, and the base a is called a Fermat witness. A False proves nothing. For n = 91 = 7 ร— 13 you will see that base 3 gives False (it is a liar) while bases 2 and 5 give True, so one False never settles the question.

Liars

If n is composite but a^(n-1) โ‰ก 1 (mod n) anyway, then a is a Fermat liar for n, and n is called a pseudoprime to base a. The smallest base-2 pseudoprime is 341 = 11 ร— 31. Let us count how many liars each composite has.

Python Counting Fermat liars

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Normally the liars form a subgroup of the multiplicative group modulo n. A proper subgroup holds at most half of the elements. So for most composites, at least half of the bases are witnesses, and picking random bases quickly exposes n. Check 15 and 21 above: the share of liars is small.

Carmichael numbers: the test's worst case

Some composites have a liar for every base coprime to them. These are the Carmichael numbers: 561, 1105, 1729, 2465, 2821, ... The first one is 561 = 3 ร— 11 ร— 17. Korselt's criterion says that n is Carmichael exactly when n is composite, squarefree, and p - 1 divides n - 1 for every prime p dividing n. For 561: 2 | 560, 10 | 560, 16 | 560.

Python Finding Carmichael numbers by Korselt's criterion

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The last line shows the loophole: a base that shares a factor with n is still a witness, but only because gcd(a, n) > 1 already reveals a factor. Carmichael numbers are rare (there are infinitely many, proven in 1994) but they mean the plain Fermat test cannot be trusted as a primality certificate.

The probabilistic test

A practical version picks random bases and gives up on the first witness.

Python A randomized Fermat test

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice that 561 is declared "probably prime" unless the random base happens to share a factor with it, which is unlikely. This is why real software uses Miller-Rabin instead.

flowchart TD
    A["Pick base a"] --> B["Compute a^(n-1) mod n"]
    B -->|"not 1"| C["n is composite (proof)"]
    B -->|"equals 1"| D["n is probably prime"]
    D --> E["Repeat with another base"]

The Fermat test: a result other than 1 is a proof, a result of 1 is only evidence.

Never use the Fermat test to generate cryptographic primes. Carmichael numbers can be constructed deliberately and will pass every coprime base.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. If pow(a, n - 1, n) is not 1, what can you conclude?

    Every prime n and base a not divisible by n satisfy Fermat's little theorem, so a failure is a proof of compositeness.
  2. 2. What is a Fermat liar?

    A liar is a base that makes a composite number look prime.
  3. 3. What makes 561 special?

    561 = 3 ร— 11 ร— 17 satisfies Korselt's criterion, so it passes the Fermat test for all coprime bases.
  4. 4. Why is pow(a, e, n) preferred to a**e % n?

    The three-argument form never builds the huge integer a**e.

Summary

  • Fermat's little theorem: for prime p and p โˆค a, a^(p-1) โ‰ก 1 (mod p).
  • A base with a^(n-1) โ‰ข 1 is a witness and proves n composite.
  • A base with a^(n-1) โ‰ก 1 for composite n is a liar; most composites have few liars.
  • Carmichael numbers (561, 1105, 1729, ...) fool every coprime base.
  • Use pow(a, e, n) for fast modular exponentiation.

Next: The Miller-Rabin Test