Primality Tests

A prime number is a natural number (greater than 1) that has exactly two factors, 1 and itself. In order to check if a number is prime or not, we can count the number of factors. 

The basic techniques to checking for primes include:

• Brute Force to count the number of factors a number has
• Find all the factors from 1 to \(\sqrt n\)

Sieve of Eratosthenes

This method is useful to search for all prime numbers in a given range and it works as follows:

• Iterate from 2 to sqrt(N), call it i
• For each i, we cross out all the multiples of i, i.e. 2*i, 3*i .. and so on
• If i is already crossed out, we don’t do anything, because if i is already crossed out, we are ensured that all multiples of i are already crossed out in our previous iterations
• In the end, we print out all the numbers that are not crossed out

Miller-Rabin Test

The Miller-Rabin primality test is a fast, probabilistic algorithm used to determine if a large number \(n\) is "probably prime". It is widely used in cryptography and computer science because it is significantly faster than deterministic tests (such as AKS) for large numbers, with a complexity of \(O(k \log^3 n)\).

Here is an overview of how it works:

let s > 0 and d odd > 0 such that n − 1 = 2sd  # by factoring out powers of 2 from n − 1
repeat k times:
    a ← random(2, n − 2)  # n is always a probable prime to base 1 and n − 1
    x ← ad mod n
    repeat s times:
        y ← x2 mod n
        if y = 1 and x ≠ 1 and x ≠ n − 1 then # nontrivial square root of 1 modulo n
            return “composite”
        x ← y
    if y ≠ 1 then
        return “composite”
return “probably prime”

Here are some of the features of the algorithm to remember:

Speed: It is highly efficient for very large numbers.

Probabilistic: It can prove a number is composite, but only that it is "probably" prime.

Deterministic Variant: If the generalized Riemann hypothesis is assumed, the test can be made deterministic for all numbers.