Primality test

A primality test is an algorithm that determines whether an integer is prime.

Unlike factoring algorithms, efficient primality tests actually do exist, but there is a slight catch.

Trial division

Trial division is the most basic brute-force implementation of a primality test:

algorithm is_prime is
    input: one integer, n > 1
    output: true if n is prime, false if n is composite

    for f = 2 to (n - 1)
        if n mod f = 0
            return false
    return true

This algorithm can be made more efficient if we understand that, for any two integers whose product is the integer \(n\), one of the integers must be greater than or equal to \(\sqrt{n}\), while the other must be less than or equal to \(\sqrt{n}.\) If this is not the case, their imbalanced product will end up being either larger or smaller than \(n.\) Here's the improved algorithm:

algorithm is_prime is
    input: one integer, n > 1
    output: true if n is prime, false if n is composite

    for f = 2 to floor(√n) (floor function ensures √n is an integer)
        if n mod f = 0
            return false
    return true

With the \(6k \pm 1\) optimization, the algorithm can be further improved to skip any factors that are multiples of \(2\) or \(3\), making it faster to check larger integers for primality:

algorithm is_prime is
    input: one integer, n > 1
    output: true if n is prime, false if n is composite

    if n ≤ 3
        return true
    if n mod 2 = 0 or n mod 3 = 0
        return false
    f ← 5
    while f ≤ floor(√n) (floor function ensures √n is an integer)
        if n mod f = 0 or n mod (f + 2) = 0
            return false
        f ← f + 6
    return true

Even though we've improved trial division a lot, it could still be much better. Notice that, if we wanted to, we could report the factor that divided \(n\) instead of returning false. Trial division always provides information about which factor divided \(n.\) However, in primality testing, all we want to know is whether an integer is prime or composite, not what the specific factors are.

You might think this is really weird, but it's actually possible to quickly determine that an integer is composite without having any idea what its factors are, as is the case in probabilistic tests.

Probabilistic tests

Sacrificing absolute certainty, probabilistic primality tests significantly reduce computational complexity. This means that, rather than guaranteeing an integer is prime, these kinds of tests can guess with a high degree of correctness that an integer is "probably prime." The probability of error can be minimized with more iterations, making this method ideal for large integers.

Due to having polynomial time complexity, probabilistic tests are considered efficient.

I'd show you an example of a probabilistic test, but for now, I'm just going to say they involve testing integers for properties that only primes can have, and making guesses based on that. If you're really curious, check out the Miller-Rabin primality test.