18.7 Primality Testing

Prime numbers occupy a central position in number theory. They are the building blocks of the integers, appear throughout algebraic structures, and form the foundation of modern public-key cryptography. Many algorithms depend on quickly determining whether a given integer is prime.

At first glance, primality testing seems simple. A number is prime if it has no divisors other than 1 and itself. However, when the input contains hundreds or thousands of digits, naive approaches become impractical. Efficient primality testing therefore focuses on eliminating unnecessary work and exploiting number-theoretic structure.

This section develops increasingly powerful primality tests, beginning with straightforward divisor checking and ending with probabilistic algorithms suitable for very large integers.

Problem

Given an integer:

determine whether:

is prime.

Examples:

2     → prime
3     → prime
17    → prime
21    → composite
91    → composite

The challenge is to perform this test efficiently for large values of n.

Definition of a Prime Number

A prime number is a positive integer greater than one whose only positive divisors are:

1
n

Examples:

Composite numbers possess additional divisors.

Examples:

4 = 2 × 2
6 = 2 × 3
8 = 2 × 4
9 = 3 × 3

The distinction appears simple, but identifying it efficiently is the real challenge.

Naive Primality Test

The most direct approach checks every possible divisor.

def is_prime_naive(n):
    if n < 2:
        return False

    for d in range(2, n):
        if n % d == 0:
            return False

    return True

Example:

print(is_prime_naive(17))
print(is_prime_naive(21))

Output:

True
False

While correct, this approach requires:

O(n)

divisions.

For large inputs, it is far too slow.

Divisor Pair Observation

Suppose:

n = a × b

If both factors exceed:

√n

then:

a × b > n

which is impossible.

Therefore, every composite number must have at least one factor less than or equal to:

√n

This leads immediately to a much better algorithm.

Square Root Test

Instead of checking every possible divisor, check only divisors up to the square root.

from math import isqrt

def is_prime(n):
    if n < 2:
        return False

    for d in range(2, isqrt(n) + 1):
        if n % d == 0:
            return False

    return True

Example:

print(is_prime(97))

Output:

True

Complexity:

O(√n)

This improvement is dramatic.

For:

n = 1,000,000,007

the algorithm checks about:

31,623

divisors instead of a billion.

Eliminating Even Divisors

Every even number greater than two is composite.

Therefore:

from math import isqrt

def is_prime(n):
    if n < 2:
        return False

    if n == 2:
        return True

    if n % 2 == 0:
        return False

    limit = isqrt(n)

    for d in range(3, limit + 1, 2):
        if n % d == 0:
            return False

    return True

Only odd candidates are tested.

This roughly halves the work.

The 6k ± 1 Observation

Every integer belongs to one of the forms:

6k
6k+1
6k+2
6k+3
6k+4
6k+5

Numbers of the forms:

6k
6k+2
6k+4

are even.

Numbers of the form:

6k+3

are divisible by 3.

Thus every prime greater than 3 must be:

6k−1

or:

6k+1

This further reduces the number of candidates.

from math import isqrt

def is_prime(n):
    if n <= 1:
        return False

    if n <= 3:
        return True

    if n % 2 == 0 or n % 3 == 0:
        return False

    i = 5

    while i <= isqrt(n):
        if n % i == 0 or n % (i + 2) == 0:
            return False

        i += 6

    return True

This version is often sufficient for ordinary applications.

Trial Division Example

Determine whether:

is prime.

Compute:

√221 ≈ 14.8

Check primes:

When testing:

we find:

221 = 13 × 17

Therefore:

is composite.

The search terminates immediately.

Fermat's Little Theorem

The next major improvement comes from number theory.

If:

is prime and:

is not divisible by p, then:

a^(p−1) ≡ 1 (mod p)

This is a consequence of entity["scientific_concept","Fermat's Little Theorem","number theory theorem"].

For example:

2^6 mod 7 = 1

and:

3^10 mod 11 = 1

The theorem suggests a primality test.

Given:

choose:

and compute:

a^(n−1) mod n

If the result is not:

then:

is definitely composite.

Fermat Primality Test

def fermat_test(n, a):
    return pow(a, n - 1, n) == 1

Example:

print(fermat_test(17, 2))

Output:

True

However, Fermat's test is only a one-way implication.

Failure proves compositeness.

Success does not guarantee primality.

Carmichael Numbers

Some composite numbers satisfy Fermat's congruence for many bases.

Example:

Factorization:

561 = 3 × 11 × 17

Despite being composite:

a^560 ≡ 1 (mod 561)

for many values of a.

Numbers with this behavior are called Carmichael numbers.

They fool the Fermat test.

Consequently, Fermat testing alone is insufficient for serious applications.

Miller-Rabin Overview

The most widely used practical primality test is the Miller-Rabin test.

It improves upon Fermat testing by examining the structure of:

n−1

and detecting many classes of composites that Fermat's test misses.

The algorithm:

Decomposes:

n−1 = 2^s × d

where:

is odd.

Performs repeated modular exponentiation.
Searches for witnesses that prove compositeness.

For a randomly chosen base, the probability of a composite number passing is extremely small.

A few rounds provide cryptographic-grade confidence.

Deterministic Miller-Rabin

For fixed-width integers, specific witness sets are known.

For 64-bit integers, testing a small collection of bases provides deterministic correctness.

Typical witness set:

Combined with Miller-Rabin, this yields exact primality testing for ordinary machine integers.

Complexity Analysis

Method	Complexity
Naive divisor test	O(n)
Square-root test	O(√n)
6k ± 1 test	O(√n)
Fermat test	O(log n) modular powers
Miller-Rabin	O(k log³ n)
Deterministic Miller-Rabin (64-bit)	Practical O(log³ n)

Here:

is the number of witness rounds.

Applications

Cryptography

RSA key generation repeatedly tests large candidate primes.

Hash Tables

Prime capacities often improve distribution properties.

Number Theory

Prime testing is a prerequisite for factorization algorithms.

Random Prime Generation

Modern cryptographic systems generate primes dynamically.

Finite Fields

Many algebraic structures rely on prime moduli.

Combinatorics

Prime moduli simplify modular arithmetic and inverse computation.

Common Mistakes

Testing Beyond the Square Root

Checking divisors larger than:

√n

wastes computation.

Forgetting Small Cases

The values:

require explicit handling.

Trusting Fermat Alone

Fermat testing is useful for filtering candidates but cannot prove primality.

Ignoring Overflow

Modular exponentiation must avoid intermediate overflow in fixed-width integer environments.

Using Floating-Point Square Roots

Floating-point rounding can occasionally introduce subtle errors.

Prefer:

isqrt()

when available.

Testing

def test_primes():
    assert is_prime(2)
    assert is_prime(3)
    assert is_prime(5)
    assert is_prime(97)

    assert not is_prime(1)
    assert not is_prime(4)
    assert not is_prime(21)
    assert not is_prime(221)

Boundary testing is particularly important because primality code often fails on small inputs.

Takeaway

Primality testing determines whether an integer possesses nontrivial divisors. Simple divisor checking leads naturally to the square-root bound, which reduces complexity from O(n) to O(√n). Number-theoretic results such as Fermat's Little Theorem enable much faster probabilistic tests, while Miller-Rabin provides practical primality testing for very large integers. These algorithms form the foundation of cryptography, finite-field arithmetic, random prime generation, and many advanced number-theoretic computations.