Description
Fermat's Little Theorem: If p is prime and a not divisible by p, then a^(p−1) ≡ 1 (mod p). The test: pick random a; compute a^(n−1) mod n. If ≠ 1, n is composite. If = 1, n may be prime (or a Fermat pseudoprime). Probabilistic; fails for Carmichael numbers. Time O(k log² n) for k iterations.
See also: Miller–Rabin, AKS, Sieve
Algorithm Flowchart
graph TD
A["Input: n, iterations k"]
B["n ≤ 1 or even? → composite"]
C["Pick random a in 2..n-2"]
D{"a^n−1 mod n = 1?"}
E["Composite (certain)"]
F["Probably prime\n(repeat k times)"]
A --> B
B --> C
C --> D
D -->|No| E
D -->|Yes| F
classDef red fill:#ff6b6b,color:#fff
classDef green fill:#51cf66,color:#fff
classDef lavender fill:#e6e6fa,color:#333
class A red
class B,C,F green
class D lavender
class E red
See also
Extended Euclidean (modular inverse) · Prime Generation · Sieve of Eratosthenes