Skip to content
Tutorials Center
My learning

Topics

Lesson 7 of 40 ยท Math Foundations

Primes and Primality Testing

Test whether a number is prime with trial division, the Fermat test and Miller-Rabin in Python, then generate random large primes for cryptographic keys.

A prime number is an integer greater than 1 whose only divisors are 1 and itself: 2, 3, 5, 7, 11, 13 and so on. Primes are the atoms of arithmetic, because every integer can be written as a product of primes in exactly one way. In cryptography they are raw material: RSA keys are built from two huge primes, Diffie-Hellman works inside a group defined by a large prime, and elliptic curves are defined over a prime field.

This leads to a practical question: how do you get a 1024-bit prime? You cannot look one up in a table; you generate a random odd number of the right size and test whether it is prime, repeating until one passes. So we need a fast primality test. In this lesson you will start with the obvious slow method, see why it fails for big numbers, and build the Miller-Rabin test that real software uses.

Trial division

The simplest test: try dividing n by every number from 2 up to the square root of n. If none divides it, n is prime. You only need to go as far as the square root because any factor larger than that pairs with a smaller one.

Python Trial division and a sieve

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.

This works for six-digit or twelve-digit numbers, but a 1024-bit number has about 308 digits. Its square root has about 154 digits, so trial division would need on the order of 2512 steps, more than any computer could ever perform. We need something that runs in time proportional to the number of digits, not to the size of the number.

Fermat's little theorem as a test

Pierre de Fermat observed that if p is prime and a is not a multiple of p, then:

ap-1 โ‰ก 1 (mod p)

You can use this as a test. Pick a base a, compute pow(a, n - 1, n) (fast, see modular arithmetic). If the result is not 1, then n is certainly composite. If the result is 1, then n is probably prime. The theorem itself is explored in Euler's theorem and the Chinese remainder theorem.

Python The Fermat test and its blind spot

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 number 561 is a Carmichael number: composite, yet it passes the Fermat test for every base that is coprime to it. Carmichael numbers are rare but infinite in supply, so a test that can be fooled by a whole family of numbers is not good enough when an attacker might choose the input.

Miller-Rabin

The Miller-Rabin test closes this hole with a stronger property. Write n - 1 = 2^s * d with d odd. If n is prime, then for any base a, either a^d is 1 mod n, or one of a^d, a^(2d), a^(4d), ..., a^(2^(s-1) d) is -1 mod n. The reason: modulo a prime, the only square roots of 1 are 1 and -1, so the chain of squarings that ends at 1 must pass through -1 or start at 1. For a composite n, most bases a break this pattern, and at least three quarters of all bases are such witnesses, even for Carmichael numbers.

flowchart TD
    A["Write n - 1 = 2^s * d"] --> B["Pick random base a"]
    B --> C["x = a^d mod n"]
    C --> D{"x = 1 or x = n-1 ?"}
    D -- "yes" --> OK["passes this round"]
    D -- "no" --> E["Square x up to s-1 times"]
    E --> F{"reaches n-1 ?"}
    F -- "yes" --> OK
    F -- "no" --> COMP["composite for sure"]
    OK --> G["Repeat with new bases"]

One Miller-Rabin round. A composite survives a round with probability at most 1/4.

After k independent rounds, the chance that a composite survives all of them is at most 4-k. With 40 rounds that is below 2-80, far smaller than the probability of a hardware error.

Python Miller-Rabin

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 handles 127-bit numbers instantly and has no problem with Carmichael numbers. Notice the structure: composite answers are certain, prime answers are probabilistic. Cryptographic libraries run it with enough rounds that the error probability is negligible.

Generating random primes

To generate a prime, pick a random odd number with the top bit set (so it has the full size) and test it. The prime number theorem says that primes near n have density about 1 / ln n, so for a 512-bit number about one in 355 numbers is prime, and about one in 177 odd numbers. That means a few hundred random tries are enough.

Python Generate a random prime

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.

Warning: The fixed seed here is only to make the lesson reproducible. A prime for a real key must come from a secure random source such as Python's secrets module or the operating system, because a predictable generator gives an attacker the key. See randomness and entropy.

In practice, libraries also make sure that the primes are not too close together, and that p - 1 shares no small factors with the public exponent. These details come back in RSA from scratch.

Primes are plentiful, factoring is hard

The density of primes guarantees that there are an astronomical number of 1024-bit primes: around 21014, so two honest users will never pick the same one by chance. At the same time, multiplying two primes is trivial, while recovering them from the product is the factoring problem, for which no efficient algorithm is known on ordinary computers. This asymmetry is the basis of RSA.

Python Multiplying is easy, factoring is not

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.

Even this toy took half a million divisions for a 13-digit number. For a 617-digit RSA-2048 modulus, the best known classical algorithms need a number of operations that is far beyond reach. This is why key sizes are measured in thousands of bits.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why is trial division unusable for testing a 1024-bit number?

    You must test every divisor up to the square root, which for a 1024-bit number is about 2^512 candidates, far more than could ever be computed.
  2. 2. What does it mean when a Fermat test with a given base returns 'composite'?

    If a^(n-1) is not 1 mod n, then n cannot be prime. Only the 'probably prime' answer is uncertain.
  3. 3. What makes Miller-Rabin better than the plain Fermat test?

    For every odd composite, at least three quarters of the bases are witnesses, so each random round catches it with probability at least 3/4.
  4. 4. Roughly how many random odd 512-bit numbers must you test to find a prime?

    The density of primes near n is about 1/ln(n). For 512 bits ln(n) is about 355, so one in about 177 odd numbers is prime.

Summary

  • A prime has no divisors except 1 and itself; cryptography needs huge primes.
  • Trial division and the sieve work for small numbers but explode for large ones.
  • The Fermat test is fast but can be fooled by Carmichael numbers such as 561.
  • Miller-Rabin is the standard probabilistic test: composites are rejected with certainty, and the chance of a false "prime" falls by a factor of 4 per round.
  • To generate a prime, pick random odd numbers of the right size and test them; about one in a few hundred works for 512 bits. Use a secure random source in real code.
  • Multiplying primes is easy; factoring the product is believed to be hard, which RSA relies on.

Next: Euler's Theorem and the Chinese Remainder Theorem.