Skip to content
Tutorials Center
My learning

Topics

Lesson 189 of 225 ยท Math and Bit Manipulation

Fermat Test, Mersenne Primes and Pollard's Rho

Learn the Fermat primality test and Carmichael numbers, the Lucas-Lehmer test for Mersenne primes, the idea behind AKS, and Pollard's rho to factor big integers.

The lesson Sieve and Primality showed trial division, the sieve and Miller-Rabin. Those cover most needs, but the story of primality testing has more characters. Some are historic (Fermat's test and the numbers that fool it), some are specialized (Lucas-Lehmer, used to find the largest known primes), and one solves the opposite problem: Pollard's rho splits a large composite number into factors much faster than trial division.

You will write each one in Python and watch it work. Python's built-in big integers and three-argument pow(a, e, m) make these algorithms short.

Fermat's little theorem as a test

If p is prime and a is not a multiple of p, then a^(p-1) % p == 1. Flip it around: if a^(n-1) % n != 1, then n is definitely composite. If the result is 1, n is probably prime. Try a few random bases a to lower the chance of error.

Python The Fermat primality test

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Carmichael numbers: the test's weak spot

Some composite numbers pass the Fermat test for every base that shares no factor with them. The smallest is 561 = 3 x 11 x 17. These Carmichael numbers are rare but there are infinitely many, so the plain Fermat test cannot be trusted for adversarial input.

Python Carmichael numbers fool Fermat

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Miller-Rabin repairs this by also checking the square roots of 1 on the way, which is why it is the standard choice. Fermat remains a fine teaching tool and a quick first filter.

Lucas-Lehmer: testing Mersenne numbers

A Mersenne number has the form M_p = 2^p - 1. When M_p is prime it is a Mersenne prime, and every known one is tied to an even perfect number. The Lucas-Lehmer test decides this exactly and quickly for odd p:

TEXT
s = 4
repeat p - 2 times:  s = (s*s - 2) mod M_p
M_p is prime  <=>  s == 0
Python Lucas-Lehmer for Mersenne primes

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The test only applies to Mersenne numbers, but that is exactly where the search for record primes lives: the biggest known primes are almost all Mersenne primes, because this test is so cheap.

Solovay-Strassen and the Jacobi symbol

The Solovay-Strassen test is a probabilistic cousin of Fermat's test that no Carmichael number can fool. It uses Euler's criterion: for an odd prime n and any a not divisible by n,

TEXT
a^((n-1)/2)  โ‰ก  (a/n)   (mod n)

where (a/n) is the Jacobi symbol, which is 1, -1 or 0. For a prime n it equals the Legendre symbol: 1 if a is a nonzero square modulo n and -1 if it is not. The Jacobi symbol extends this to any odd n and can be computed fast without factoring, using the rules below (the same flipping rule as quadratic reciprocity):

  • (a/n) = (a mod n / n).
  • (2/n) = 1 if n mod 8 is 1 or 7, and -1 if it is 3 or 5.
  • (a/n) = (n/a) * (-1) when a and n are both odd and both are 3 mod 4; otherwise flip without the sign change.
  • (0/n) = 0 and (1/n) = 1.

For a composite n, at least half of all bases a break the equation, so each random base catches a composite with probability at least 1/2. After k bases the chance of a wrong "prime" is at most 2^-k.

Python Jacobi symbol and Solovay-Strassen

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Lucas primality test (n - 1 method)

Fermat's test can only prove that a number is probably prime. Lucas turned it around: if you know the prime factors of n - 1, you can get a proof of primality. The number n is prime if there is a base a such that

  1. a^(n-1) โ‰ก 1 (mod n), and
  2. a^((n-1)/q) โ‰ข 1 (mod n) for every prime factor q of n - 1.

Together these say that a has order exactly n - 1 modulo n, which is only possible when n is prime. The catch is factoring n - 1, which is the hard problem again, so the test is used when n - 1 factors easily (Fermat numbers, numbers built as k * 2^m + 1) or inside Pocklington-style certificates.

Python Lucas n-1 primality test

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

If the first base fails condition 2, try the next base; a composite number never satisfies both conditions for any base, so False is final.

AKS: primality in polynomial time

For a long time nobody knew whether primality could be decided deterministically in polynomial time. In 2002 Agrawal, Kayal and Saxena showed it can. The AKS algorithm rests on a polynomial identity:

n is prime if and only if (x + a)^n = x^n + a (mod n) for coprime a.

You can check the identity directly for small n: the binomial coefficients in (x + a)^n must all be divisible by n, apart from the first and last. The real AKS performs the check modulo a small polynomial x^r - 1, which is what makes it fast. It is mostly of theoretical interest: in practice Miller-Rabin is much faster.

Python The identity behind AKS

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The identity gives an exact prime test, but checking n - 1 coefficients costs O(n), no better than trial division. AKS' cleverness is shrinking that cost.

Pollard's rho: factoring without trial division

Trial division needs up to sqrt(n) steps. Pollard's rho finds a factor of a composite n in about n^(1/4) expected steps by exploiting the birthday paradox.

Pick a pseudo-random sequence x -> (x*x + c) mod n. Modulo a hidden factor p the sequence repeats after about sqrt(p) steps, but modulo n it does not yet. When two terms agree mod p but not mod n, then gcd(x_i - x_j, n) is a nontrivial factor. Floyd's tortoise and hare (one pointer moves twice as fast) detects the cycle without storing the sequence.

Python Pollard's rho

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The is_prime helper is the Miller-Rabin test with fixed bases; it decides when to stop splitting, because rho never terminates usefully on a prime. The expected cost is about n^(1/4) multiplications, so a 20-digit semiprime with two 10-digit factors takes thousands of steps instead of billions.

Rho is the workhorse for numbers up to around 10^18 in competitive programming. For hundreds of digits, other methods (the quadratic and number field sieves) take over, which is why RSA keys use 2048-bit numbers.

Common mistakes

  • Trusting a single Fermat base. pow(2, n - 1, n) == 1 is true for composites like 341. Use several bases, or Miller-Rabin.
  • Forgetting that Carmichael numbers exist. A "composite that passes every base" is not a bug in your code.
  • Applying Lucas-Lehmer to ordinary numbers. It only works for 2^p - 1 with prime p.
  • Looping forever in rho. When gcd returns n itself, restart with a different c (and a different starting value if you wish).
  • Calling rho on a prime. It never finds a factor of a prime. Test primality first.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. If a^(n-1) mod n is not 1 for some a coprime to n, what do you know?

    Fermat's little theorem says primes always give 1, so any other result is a proof that n is composite.
  2. 2. What is special about 561?

    561 = 3 x 11 x 17 and a^560 mod 561 equals 1 for every a coprime to it.
  3. 3. The Lucas-Lehmer test decides primality for numbers of which form?

    It is specific to Mersenne numbers, which is why it can be so fast and is used to find record primes.
  4. 4. How many steps does Pollard's rho need to find a factor of n, roughly?

    The sequence modulo the smallest factor p repeats after about sqrt(p) steps, and the smallest factor is at most sqrt(n).

Summary

  • The Fermat test proves compositeness with a witness a where a^(n-1) mod n != 1; passing is only "probably prime".
  • Carmichael numbers such as 561 pass for all coprime bases, which is why Miller-Rabin is preferred.
  • Lucas-Lehmer decides Mersenne numbers 2^p - 1 with a short recurrence; AKS proved that primality is in P through a polynomial identity.
  • Pollard's rho finds a factor in about n^(1/4) steps using a pseudo-random sequence, Floyd cycle detection and gcd.

Next: Chinese Remainder Theorem