fermat test

Work in Progress

Concept

Theorem 2.5.1

Theorem 2.5.1. If is prime and , then .

  • layman explanation: every nonzero residue modulo a prime returns to one after exactly the group-size exponent.

Proof. Since has elements, Lemma 2.3.2 gives

Proposition 2.5.2

Proposition 2.5.2. If composite has one with , then at least half the units are Fermat witnesses.

  • layman explanation: once one unit exposes compositeness, the units that hide it form at most half the group.

Proof. Let . Then

so is a subgroup. Since , it is proper; Lagrange gives and therefore . Its complement consists of witnesses.

Definition 2.5.3. A failing base is a Fermat witness; a passing base for composite is a Fermat liar; a composite for which every unit lies is a Carmichael number.

Application

The Fermat test quickly proves compositeness but cannot reject Carmichael numbers; continue with miller-rabin test.