Prime Numbers and Primality Tests
An Introduction to primality tests: understanding prime numbers and how to test them with the trial division method
Prime numbers play a crucial role in various fields of mathematics and computer science. They are the building blocks of the number system, used extensively in cryptography, number theory, and other applications. Determining whether a number is prime, known as a primality test, is a fundamental problem in mathematics.
In this article, we will explore the basics of prime numbers, introduce different types of primality tests, and delve into the trial division method with its optimizations. We will also briefly mention probabilistic primality tests, which will be covered in detail in a future article.
Prime Numbers
A prime number is a integer greater than \(1\) and has no positive divisors other than \(1\)and itself. \(1\) is neither prime nor composite. The set of positive integers can be divided into three classes, primes, composites and a unit (1). For example, \(5\) is prime because the only ways of writing it as a product, \(1 × 5\) or \(5 × 1\), involve \( 5\) itself.
Primality Test
Now that we understand prime numbers, how can we determine if a number is prime or not? There are two types of primality test, deterministic and probabilistic.
Deterministic Primality Test: This type of test can determine whether a number is prime with absolute certainty.
Probabilistic Primality Test: This type of test can tell us whether a number is probably prime or composite. It cannot determine primality with absolute certainty but works correctly most of the time. A composite number that passes a probabilistic test is called a pseudoprime.
In this article, we’ll see the basic trial division approach and how we can optimize that. There are also some probabilistic primality test, like Fermat primality test, Millar Rabin primality test etc. We'll discuss about them hopefully in another article.
Trial division
One bruteforce way to determine the primality of a number n is to go through each number \(a_i\) in the range \(a = [2, n – 1]\) and check whether n is divisible by \(a_i\). If any number divides n in the range \([2, n – 1]\), then we can conclude that the number \(n\) is not a prime number. But if we don’t find a single divisor of n in the range \([2, n – 1]\), that means \(n\) is a prime.
bool is_prime = true;
for (int i = 2; i < n; ++i) {
if (n % i == 0) {
is_prime = false;
break;
}
}
if ( is_prime ) cout << n << " is a prime number." << endl;
else cout << n << " is a composite number." << endl;
However, the time complexity of this naive algorithm is \(O(n)\), making it very slow for large numbers.
Optimized Trial Division
We can improve the naive trial division algorithm significantly with a very simple observation. It is sufficient to check in the range \([2, \sqrt{n}]\) to determine if \(n\) is prime or not? But Why? This is because every composite number has a divisor less than or equal to the square root of itself.
Suppose that \(n\) is a composite. Then we can write \(n=a \times b\) for integers \(a\) and \(b\) which are both greater than \(1\). If both \(a>\sqrt{n}\) and \(b>\sqrt{n}\) then we would have \(ab> \sqrt{n} \times \sqrt{n}\) thus \(ab > n\), which is a contradiction. Hence either \(a \leq \sqrt{n}\) or \(b \leq \sqrt{n}\), so if you check up-to\(\sqrt{n}\) and don’t find a divisor of \(n\) greater than \( 1\), then \(n\) must be a prime. Thus, we can conclude that a composite number has a divisor less than or equal to the square root of itself.
bool is_prime = true;
for (int i = 2; i * i <= n; ++i) {
if (n % i == 0) {
is_prime = false;
break;
}
}
if (is_prime) cout << n << " is a prime number" << endl;
else cout << n << " is a composite number" << endl;
What about the divisors greater that \(\sqrt{n}\)? There may be many divisors greater than \(\sqrt{n}\) but a composite number has at most one prime divisor greater than it’s square root. Assume there is such a divisor and denote it by \(p\). Then \(n = m \times p\) with \(p > \sqrt{n}\). Therefore \(m < \sqrt{n} \) as \(m = \frac{n}{p}\). Any other prime divisor of \(n\) must be a divisor of \(m\), which must be less than \(\sqrt{n}\) as m is less than \(\sqrt{n}.\)