miller-rabin test

Work in Progress

Concept

Theorem 2.5.4

Theorem 2.5.4. Let odd prime satisfy with odd. Every nonzero satisfies , or for some .

  • layman explanation: repeated squaring from the odd part must reach one through minus one unless it started at one.

Proof. If , Fermat gives . Choose the least with . Then

Definition 2.5.5. For odd composite , a base violating both alternatives is a strong witness; otherwise it is a strong liar.

Theorem 2.5.6

Theorem 2.5.6. For composite , at most half of are strong liars.

  • layman explanation: all bases that fool one round fit inside a proper subgroup, so they cannot occupy more than half the units.

Proof. If , every strong liar has order dividing both and , hence dividing ; thus it lies in . This subgroup is proper because

If has at least two prime-power factors, let be maximal with some and set . Every strong liar lies in . CRT chooses modulo one prime power and modulo the complementary factor, so is simultaneously and on different components and hence is neither . Thus is proper. In either case Lagrange gives size at most half.

Application

Independent rounds reduce the course bound to after rounds; 64 rounds give at most under this theorem.