Super Simple Primality Testing

Awhile ago I was asked how to determine if an integer is prime, which is an important problem. Much of today’s internet security relies on prime numbers–for generating public & private encryption keys. There are other uses too. So, labeling a number prime is well studied. What I want to do in this post is to cover basic algorithms, which rely on testing divisibility of a given number among a list of possible divisors–a search space; and if none divide, the number is prime. By investigating the relationship between a number and its divisors we can reduce the space of possible divisors, and write down a nice sub-linear primality testing algorithm.

Following first principles, an integer $N$ is prime if $\exists a < N$ so that $a\ |\ N$. We could then simply try dividing $N$ by all numbers less than $N$. Here’s our version $0$ algorithm:

def isPrime(N):
	if type(N) is not int:
		raise ValueError("N must be a positive integer")
	if N < 2:
		return False
	for x in range(2,N):
		if N % x == 0: 
			return False
	return True

Run this code on a few low integer values, and you’ll see that isPrime is correct and fast. But for large integers not so fast–just try it on 12312345451; your IPyhon shell will hang. But no worries, we can reduce the search space. Consider the number $12$ and its divisors ${1,2,3,4,6}$, or $25$ and its divisors ${1, 5}$. Each divisor is at most half the number it divides. Let’s formalize this.

Lemma. A Let $a,b, N \in \mathbb{Z}^{+}$, and $N = a \cdot b$ -- both $a$ and $b$ divide $N$. Then $a$ and $b$ are both less than $\frac{N}{2}$

proof:

Suppose $a > \frac{N}{2}$, then \(N = a \cdot b > \frac{N}{2} \cdot b \ \Longrightarrow b < 2.\) Since $b$ is an integer, $b = 1$, a contradiction because $b$ is assumed to be a non-trivial divisor.

Okay, we cut the number of comparisons in half. Great! But we can do better. Note that large divisors of $N$ are necessarily paired with small divisors. Based on the lemma, these large divisors are near $\frac{N}{2}$. Clearly, $\frac{N}{2}$ is a sharp upper bound on divisors. Instead we want an upper bound on small divisors, or at least show that if $N$ has divisors, at least one is bounded sub-linearly in $N$. Which we can do.

Lemma. B Let $a,b, N \in \mathbb{Z}^{+}$, and $N = a \cdot b$ -- both $a$ and $b$ divide $N$. Then either $a \leq \sqrt{N}$ or $b \leq \sqrt{N}$.

proof:

Suppose not. Both $a$ and $b$ are greater than $\sqrt{N}$. Then, $a \cdot b > N$.

Now this is great! The preceding lemma reduces our search space considerably–e.g. if $N$ has order $1 \times 10^9$, then we only need to check divisibility for $\sim 1 \times 10^5$ numbers. Here’s the version $1$ algorithm, which uses the insight provided by Lemma. B:

def isPrime(N):
	if type(N) is not int:
		raise ValueError("N must be a positive integer")
	if N < 2:
		return False
	x = 2
	while x*x <= N:
		if N % x == 0: 
			return False
		x+=1	
	return True

Since I don’t have a ground truth set of primes, I used a web based app I found, to find a few known large primes. I confirmed that the above algorithm correctly identified them as prime.