liveBook · Manning

Fermat primality test

As explained in Hacking Cryptography

The Fermat primality test checks randomly selected integer bases against Fermat’s congruence to identify probable primes and composites.

The Fermat primality test samples integer bases a and checks whether a^(p−1) ≡ 1 (mod p). A failed check proves that p is composite; repeated successes make p only probably prime. section 8.2.2

A practical test follows this loop:

  • Use an RNG to choose a base a for each iteration. section 8.2.2
  • Check the congruence against candidate p; immediately reject p when it fails. section 8.2.2
  • After the configured iterations, classify p as likely prime rather than certainly prime. section 8.2.2

The test is probabilistic and has a dangerous exception: Carmichael numbers such as 1,105 can pass for many bases despite being composite. Miller–Rabin is presented as a more reliable alternative. section 8.2.2

How Hacking Cryptography covers it

How deep it goes
Explains the congruence, iteration flow, RNG role, and Carmichael-number failure, but defers to Miller–Rabin for stronger testing.
Examples
Uses random bases, repeated iterations, and the composite Carmichael number 1,105 as concrete test cases.
What you can do after
Evaluate candidate integers, immediately identify composites, and assign increasing but non-certain confidence to probable primes.
How it connects
Connects Fermat’s little theorem, modular arithmetic, random-number generation, prime generation, Carmichael numbers, and Miller–Rabin testing.
Cover of Hacking Cryptography
liveBookmanning.com
Read Hacking Cryptography on liveBook Get the book at manning.com

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Hacking Cryptography. The section links point to the parts of the book it draws on.