A Brief overview of Primality Tests

Prime Numbers in a Nutshell

A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers - Wikipedia Page of 'Prime Numbers'

In essence, a prime number is only divisible by 1 and itself. Identifying prime numbers efficiently is a classic problem in computer science and mathematics. Here, we'll first explore some simple methods to determine if a number is prime.

Simple Methods

Naive Iteration

The simplest way to check if a number is prime is to test by dividing with all smaller numbers.

def is_prime_naive(n: int) -> bool:
    if n <= 2:
        return True

    for i in range(2, n): #Checking all numbers from 2..n
        if n%i == 0:
            return False
        else:
            i += 1
    
    return True

The method is fairly straightforward, but for every number, in the worst case has to perform n-1 checks, effectively a complexity.

Naive + Reduced Range

We can improve the previous result by checking divisors up to the square root of n.

def is_prime_reduced_range(n: int) -> bool:
    if n <= 2:
        return True

    i = 2
    while i * i <= n: # Effectively putting range from 2..root(n)
        if n%i == 0:
            return False
        else:
            i += 1
    
    return True

Why? Because we see that if is divisible by some number , then . Now we have two cases where:

if , then
and if , then either one has to be smaller than
Thus, we only have to check number till , to find a suitable divisor, effectively a complexity.

Naive + Reduced Range

We can take this quite further by using a simple observation.
Every number can be shown in the form:

Where is another number, is the quotient when is divided by and is the remainder.
Now we can say for certain that when we are trying to minimize and maximize .

So let's take , every number henceforth can be shown as anyone of the forms:

Out of these we can clearly see:

and have as their factor

has as its factor

Thus we are left with and with no apparent factors at first. Thus we can safely claim, that any prime number, must be in the form or .

Now we can use this property to decrease our search time even more, by only checking divisibility with number which are less that and are of the form and .

def is_prime_reduced_range_2(n: int) -> bool:
    if n <= 2:
        return True
    
    if n%2 == 0 or n%3 == 0: # Checking divisibility by 2 and 3
        return False

    i = 6
    while i * i <= n: # Effective range is still 2..root(n)
	     # Checking only those numbers,
	     # which are of the form 6k + 1 and 6k + 5
	     #
	     # For simplicty i here,
	     # is changed to 6k+1 and 6k-1.
	     # This can be implemented by offsetting k
        if n%(i-1) == 0 or n%(i+1) == 0:
            return False
        else:
            i += 6
    
    return True

Here the complexity remains , as we are simply reducing sample size by a constant of 6.

Benchmark Results

Now, we can compare the performances of the program.
On running this program on input 9737333 we see the following results:

Benchmark	Runtime	Operations^[1]	VS^[2]
`is_prime_reduced_range_2`	106 us	9.40K op/s	1×
`is_prime_reduced_range`	640 us	1.56K op/s	6×
`is_prime_naive`	1.87 s	0.535 op/s	17577×

Our last two methods are quite on par, with the difference clearly being times, which can be credited to our method.

And as our naive method did a lot of unnecessary calculations, it has been left in the dust.

Probabilistic Methods

As numbers become larger, our simple methods, although quite efficient, cannot keep up. In this case, we resort to probabilistic tests, with our main trade-off being speed for accuracy. These tests provide a probabilistic guarantee of primality, which means they can identify composite numbers with certainty but may have a small chance of misidentifying a composite number as prime.

Fermat Primality Test

The Fermat Primality Test is based on Fermat's Little Theorem, which states that for a number and a number where is co-prime to :

If is anything other than 1, we can classify as a composite number. But, if , then may or may not be a prime.

This test is relatively simple to implement using modular exponentiation, as discussed in The Trick of Exponentiation > Modular Exponentiation.

Here is a Python implementation of the Fermat Primality Test:

import random

def fermat_primality_test(n, k=5):
    # Base cases
    if n <= 1:
        return False
    if n <= 3:
        return True
    
    # Perform the test k times
    for _ in range(k):
        # Pick a random integer in the range [2, n-2]
        a = random.randint(2, n - 2)
        
        # Compute a^(n-1) % n
        if pow(a, n - 1, n) != 1:
            return False
    
    return True

# Example usage
n = 97
print(fermat_primality_test(n))  # Output: True or False (with high probability)

Miller Rabin

The Miller-Rabin Primality Test is a more sophisticated probabilistic test that provides a stronger guarantee than the Fermat Primality Test. It is based on the properties of strong pseudo-primes and is widely used in practice due to its reliability.

The test involves the following steps:

Express as with being an odd number.
Pick a random integer such that .
Compute . If or , then passes this round.
Repeatedly square up to times, if any iteration results in , then passes this round.
If none of the above steps result in passing, then is composite.

Here is a Python implementation of the Miller-Rabin Primality Test:

import random

def miller_rabin_primality_test(n, k=5):
    # Base cases
    if n <= 1:
        return False
    if n <= 3:
        return True
    if n % 2 == 0:
        return False
    
    # Write n-1 as 2^s * d with d being odd
    s, d = 0, n - 1
    while d % 2 == 0:
        s += 1
        d //= 2
    
    # Perform the test k times
    for _ in range(k):
        a = random.randint(2, n - 2)
        x = pow(a, d, n)
        
        if x == 1 or x == n - 1:
            continue
        
        for _ in range(s - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    
    return True

# Example usage
n = 97
print(miller_rabin_primality_test(n))  # Output: True or False (with high probability)

Bogo primality test

^[3]
The prime-counting function is a function that counts number of prime numbers , and is denoted by .

We can use this property to get a probabilistic guess of whether a number is prime or not.

Furthermore we can decide our probability as

Gauss to the rescue

Now in the end of the 18th century Gauss and Legendre conjectured the following

Here if we consider our range to be , we can calculate the probability as follows:
which we can simplify to:

Now we can calculate the probability for a few numbers and see the results

Due to the nature of log, the function deteriorates slowly, this is good, but can we do better?

Something more precise

In 1899, de la Vallée Poussin proved:

Here the important part is the function, also known as the logarithmic integral, which can be defined as:

Now we can use as our approximation for . Which on substituting in to gives us:

We can create a similar table to see how this function behaves,

We see higher probabilities for the numbers, which can be attributed to the lower error of .

But can we push this further?

Enter Dudek

In 2015 Dudek (2015) proved that the Riemann hypothesis implies that for all x ≥ 2 there is a prime p satisfying:

which can be considered a tighter formula relative to Betrand's postulate which states there exists one prime number , such that

We will go ahead with Dudek as it give a shorter interval. Now as we have an inequality for simplicity we can assume , i.e. let the interval end at the input itself.

Simply to find the probability of a number being prime, we need only check the number of primes in the interval .

Now using our , we can find the number of primes inside our limits, which we can do as follows

where is number if primes in that range.

Now we can define our as:
which on expansion becomes:
Here we can use , to solve the numerator, let's see how the data turns out

And for , we get the following values,

Bogo conclusion

Now all that is use these probabilities, and toss a coin, hoping to get the correct answer.

Conclusion

That was quite a lot of prime testing methods. Due to their unpredictable distribution, we can as of now at best use heuristics or do rigorous testing to check primality. Perhaps in the future, we could have a simple , solution to check any number.

Operations per second↩︎
Runtime in relation to the fastest function↩︎
This section is a joke take on primality test methods↩︎