Primality Testing and Significance

I know - testing for primality is a pain. It's usually a time-intensive process that requires a lot of scratch paper if you're doing it out by hand. But guess what? It's a pain for computers too! Okay, maybe they're a little faster than us, but a lot of important cybersecurity protocols depend upon the fact that computers are as bad at testing for primality as we are!

Unfortunately for both humans and computers, the most efficient way of testing for primality is by trial division. Trial division is exactly what it sounds like. Say you have the number 103. Trial division involves taking all the numbers - 1, 2, 3, 4, 5, etc. - up to 103 and checking if they divide into 103. Does that sound slow? That's because it is slow. You can save time by only testing primes up to the smallest integer that's larger than $\sqrt{n}$, where n is the number that we're testing for primality. Why does this work? Well, after $\sqrt{n}$, the factors just start repeating. For example, let's look at the factor pairs of 100:

(1, 100) (2, 50) (4, 25) (5, 20) (10, 10) (20, 5) (25, 4) (50, 2) (100, 1)

After 10 and 10, they all start repeating! We don't need to test anything past 10, which is the square root of 100.

If you're programming a computer to test for primes, you can basically do it the same way. The easiest way is to give the computer a list of primes to test with. That way, if n is divisible by any of the primes less than $\sqrt{n}$, the computer can say the number is composite and skip testing any other numbers.

But how does the computer find the list of prime numbers? Obviously, it's a pain to put them all in manually. So it uses a nifty little algorithm represented here:

What the computer is doing is it's starting from the smallest prime number, 2. It marks 2 as prime p. Then it goes and marks all the other numbers that are divisible by 2 as composite. After it's finished, it moves onto 3 and marks it as the new prime p. Then it marks all the multiples of 3 as composite and moves onto the next number. When the algorithm terminates, all the prime numbers should be marked.

The computer can do this pretty quickly for numbers up to 1000 or 10000 - way faster than we can! However, it's not invincible. Once you start making the upper bound really big, the computer starts to take a little longer to find all of the primes. And even if it has a really big list of primes, say you ask the computer to determine if a number like:

15226050279225333605356183781326374297180681149613 80688657908494580122963258952897654000350692006139

is prime. We certainly can't do this practically, and believe it or not, it takes the computer forever as well! It has to first determine all the primes up to the square root of that number and then test all the primes to see if they divide into that number (which has a 100 digits, so it's square root is still super big). This number is called a semiprime, which means it is the product of two other prime numbers. It's factorization is:

37975227936943673922808872755445627854565536638199 × 40094690950920881030683735292761468389214899724061.

This took a parallel computer a few days to solve! And this isn't even a very big semiprime!

Why is this important, you might wonder? Well, the most widely used public-key cryptosystem today is called RSA. The core idea behind breaking the RSA encryption (more commonly known as the RSA problem) is based on multiplying two extremely large prime numbers to form a semiprime, which is used as a public key to encrypt data transmissions. If you don't know the private key, which is one of the two large prime numbers that are factors of the semiprime, it takes computers a really long time to find it by itself! That's why this cryptosystem is so simple, and yet so frustrating to computers.

For now, prime numbers remain as annoying to computers as they are to us! Who knew that we could find such a simple way to trick them?

For more information, visit the expii article about Crytography and RSA encryption!

Non-deterministic Primality Tests

We have seen a quite efficient primality testing. But prime factorizations are required mostly because of its use in Cryptography. For that pupose, usually the values of $n$ are quite large, like $100$ or more digits. There is no way we can find the factorization of $n$ that large within a feasible time, if the prime factors are large too. So, what do we do?

In fact there are fast deterministic prime factorizations as well, for example, AKS Primality Test. But it has a running time $O(\log^{12}n)$. Do not panic if you don't understand what it means. A simple explanation is that for a certain $n$, we will have to do around $\log^{12}n$ operations in order to determine whether $n$ is prime or not, if we use this algorithm. So, if $n$ is around $10^{100}$, it will take about $200^{12}$ operations. This is still not a feasible runtime for our purpose, Assume a computer can do $10^9$ operations in one second, then calculate how many hours it would take to find out if $n$ is prime.

This is why Non-deterministic or Probabilistic algorithms were established, which usually involves comparatively small number of operations. Using this method, we can't say for sure if $n$ is prime, but we can say that $n$ is probably a prime, with a very high probability. Usually, in such a method, we take the help of some auxiliary numbers, say $a$. Then we do the same thing over and over until a certain accuracy is achieved. The error in the output of a probabilistic algorithm is of the magnitude $2^{-k}$ where $k$ is the number of iterations.

Let's see an example, though a bad one for the sake of simplicity. We know from Fermat's little theorem that, if $p$ is a prime, and $a$ is not divisible by $p$ then $a^{p-1}\equiv1\pmod p$.

Now think this way. We are given the integer $n$. Choose an arbitrary integer $a$. If $\gcd(a,n)>1$, we have already found a divisor of $n$. So, let's consider the case where $\gcd(a,n)=1$. If $n$ was a prime, we would have had $a^{n-1}\equiv1\pmod n$. So, we check if $a^{n-1}\equiv1\pmod n$. If this not true, we can definitely say, $n$ is not a prime. But since the converse is not true, we can't be sure if $n$ is prime. But there is a chance that $n$ is prime. Therefore, we choose another random number $a$ and do the same thing if $\gcd(a,n)=1$. If we do this many times and find that $a^{n-1}\equiv1\pmod n$ holds in all cases, the probability is high that $n$ is a prime.

Hope you understand we need non-deterministic primality tests and how it works. If you are interested, you can check out Pollard-Rho Primality Test, Brent-Pollard-Rho Primality Test etc. Brent used an optimized version of Pollard Rho primality test to factorize some Fermat numbers. So you see, this idea really is important and cool.

Primality Testing

Primality testing means a systematic way to determine if a natural number $n$ is a prime or not. From the definition of primes we have a not-so-fast way (we will say algorithm instead of way from now) to determine if $n$ is a prime.

Firstly, if $n$ is even and greater than $2$, we can exclude it easily. So we will focus only on odd $n$. Since all divisors of an odd number is odd, we need to divide $n$ by only odd numbers. That is not a great optimization either, but can be improved. We will not divide $n$ by any number greater than $\dfrac n2$. Because no number greater than $\dfrac n2$ will divide it except $n$. Now, we will have to do around $\dfrac n4$ divisions in order to decide if $n$ is prime (why?). But what if $n$ is around $10^3$? Shall we divide it by like $250$ numbers? That's still too much. Keep looking for more holes so that we don't have to do unnecessary division.

Yes, you should already get that if we already divided $n$ by $3$, we don't need to divide $n$ by $9$ or $15$ again! In other words, we don't need to divide by any number that is not prime. This is indeed a great optimization. But still the number of primes can be large for large $n$ too. So, we should optimize even further. Think more.

Notice that $15$ is composite and it has prime factors $3$ and $5$. $35$ has prime factors $5$ and $7$. These observations tell you anything? Think what would happen if $n$ is composite. It must have a prime factor, right? In fact it must have a prime factor that is smaller than or equal to other prime factors. In above examples, $3$ and $5$ are those primes. For $n=9$, $3$ is such a prime. Now, assume that this prime is $p$. That is, if $n=pk$ then $p\leq k$. Multiplying this inequality by $p$ we get $p^2\leq pk=n$, or $p\leq\sqrt n$. Bingo! If $n$ is composite, it must have a prime factor less than or equal to $\sqrt n$. This is another great optimization.

Though this is a trial and error process to determine if $n$ is prime, but it is deterministic. That is, we can surely say, after this algorithm if $n$ is prime or not. There are some non-deterministic algorithm for primality testing, such as Brent-Pollard-Rho prime factorization.

Use the final optimized algorithm in Primality testing to test if $479$ is a prime.

How can we test if $n$ is prime?

If you answered the previous question successfully, then one solution may be that you tried to divide $n$ by all integer from $2$ to $n-1$. But is there a better process? One optimization is to divide by only odd numbers if $n$ is odd. Try to optimize the process for large $n$.