The Fermat test, its failure on Carmichael numbers, and the strong pseudoprime test that repairs it.
Engineering / MathematicsClassical Primality and Factoring2 min readKV-MATH-0647
The Fermat test is the starting point for all compositeness testing. It has a fatal flaw which the strong test repairs, and the repair costs essentially nothing.
The Fermat test
a^(n-1) = 1 (mod n) for every a coprime to n, if n is primeFailure proves compositeness; success proves nothing.
The strong test
Write the exponent as an odd number times a power of two. For a prime, the sequence of repeated squarings from the odd power must reach one through a specific pattern.
n - 1 = d * 2^s with d oddThen either a^d = 1, or a^(d*2^r) = -1 for some r below s.
The strong pseudoprime test
Factor out powers of twoFrom one less than the candidate.
Check for oneIf the result is one, the test passes.
Square repeatedlyChecking for minus one at each step.
Declare compositeIf neither condition is met.
Why it is stronger
Error probability
Probability a composite passes a random base < 1/4And in practice far smaller for most composites.
Error probability with independent random bases
Number of random bases
Error bound
1
Below one quarter
10
Below one in a million
20
Below one in a trillion
40
Negligible for any practical purpose
Deterministic variants
Finding a factor
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 8.2. Structural reference unverified: the source file was not available during authoring; chapter and section numbers are taken from the published edition and have not been checked against a physical copy.
