fermat test
Concept
Theorem 2.5.1
Theorem 2.5.1. If
- layman explanation: every nonzero residue modulo a prime returns to one after exactly the group-size exponent.
Proof. Since
Proposition 2.5.2
Proposition 2.5.2. If composite
- layman explanation: once one unit exposes compositeness, the units that hide it form at most half the group.
Proof. Let
so
Definition 2.5.3. A failing base is a Fermat witness; a passing base for composite
Application
The Fermat test quickly proves compositeness but cannot reject Carmichael numbers; continue with miller-rabin test.