Primality Testing
Published: 2023-11-29 22:48:22

# Number Theory Basics

Most algorithms in cryptography depend on large prime numbers, and the fact that certain algorithms are hard. Encryption is basically the act of applying a mathematical function for which it is very hard to determine the inverse function without a key, but easy with the key.

There are many number theoretic algorithms which are fast and easy. The mother of them all number theoretic algorithms is Euclid's algorithm for finding the greatest common divisor:

Given that we can do division with remainder, if {% katex inline %}a > b{% endkatex %} and we want to compute GCD(a,b) we write

{% katex inline %}a = bq + r,{% endkatex %} and notice {% katex inline %}GCD(a,b) = GCD(b,r).{% endkatex %} Now we can iterate this. This is very fast; in fact its time complexity is {% katex inline %}O(log(a + b)){% endkatex %}!

If {% katex inline %}a{% endkatex %} and {% katex inline %}b{% endkatex %} are really large and hard to factor, we can compute their GCD extremely quickly without knowing how to factor them! In fact there is no known way to efficiently determine the prime factorization of a number - if I multiply two random 300-digit primes {% katex inline %}p{% endkatex %} and {% katex inline %}q{% endkatex %} it's impractical to find {% katex inline %}p{% endkatex %} and {% katex inline %}q{% endkatex %} if you only know the value of {% katex inline %}pq,{% endkatex %} although it is pretty easy to detect that {% katex inline %}pq{% endkatex %} is not prime. You could write code to do it, but your computer would not last long enough to execute it.

### Powers modulo {% katex inline %}p{% endkatex %}

If {% katex inline %}d{% endkatex %} is an integer, we write {% katex inline %}a \equiv b ~ (mod ~ d){% endkatex %} if {% katex inline %}a{% endkatex %} and {% katex inline %}b{% endkatex %} have the same remainder when we divide both by {% katex inline %}p.{% endkatex %}

If {% katex inline %}p{% endkatex %} is a prime number, we can define multiplication on {% katex %}{0,1,...,p-1}{% endkatex %}by taking the result _mod p_, that is, taking the remainder when we divide by {% katex inline %}p.{% endkatex %} We can also define exponents in a similar way: {% katex inline %}a^n{% endkatex %} is just the remainder when {% katex inline %}a^n{% endkatex %} is divided by {% katex inline %}p.{% endkatex %}

How do we actually compute {% katex inline %}a^n{% endkatex %} efficiently when {% katex inline %}a,p,n{% endkatex %} are all large?

The answer is repeated squaring. We can write{% katex inline %}n{% endkatex %}as a sum of powers of {% katex inline %}2{% endkatex %}, and calculate those powers of , i.e. if {% katex inline %}n = 453,{% endkatex %}
{% katex %}
453 = 256 + 128 + 64 + 4 + 1 = 2^8 + 2^7 + 2^6 + 2^2 + 2^0.{% endkatex %}

So if we want to compute {% katex inline %}17^{453},{% endkatex %} we actually only have to calculate the powers of {% katex inline %}17{% endkatex %} whose exponents belong to {% katex %}[1,2,4,8,16,32,64,128,256].{% endkatex %} All told, this is only {% katex inline %}12{% endkatex %} multiplication operations to compute {% katex inline %}17^{453}{% endkatex %} ({% katex inline %}8{% endkatex %} to compute the powers with exponents in the list, and {% katex inline %}4{% endkatex %} more to get the correct one).

### Logarithms modulo {% katex inline %}p{% endkatex %}

Another well known fact in number theory: for any prime number {% katex inline %}p,{% endkatex %}you can find a remainder {% katex inline %}a{% endkatex %} such that all of the different powers {% katex inline %}a, a^2, a^3, a^4, ... , a^{p-1}{% endkatex %} are different mod {% katex inline %}p{% endkatex %}; in this case we say that {% katex inline %}a{% endkatex %} is a _primitive root_ mod {% katex inline %}p.{% endkatex %}

We can get at most {% katex inline %}p-1{% endkatex %} different remainders, since no power of {% katex inline %}a{% endkatex %} will give a remainder {% katex inline %}0{% endkatex %}. Most values of {% katex inline %}a{% endkatex %} will not be primitive roots, but in practice it usually not that hard to find one such value fairly quickly.) Values of {% katex inline %}a{% endkatex %} with this property are called _primitive roots_. For example, the primitive roots mod {% katex inline %}5{% endkatex %} are {% katex inline %}2{% endkatex %} and {% katex inline %}3{% endkatex %}.

powers of 1: 1,1,1,1 (not all distinct mod 5)
powers of 2: 2,4,8,16 (all distinct mod 5)
powers of 3: 3,9,27,81 (all distinct mod 5)
powers of 4: 4,16,64,256 (not all distinct mod 5)

For a = 1,2,3,4 we have

{% katex inline %}a^4 \equiv 1 ~ (mod ~ 5){% endkatex %}

In fact, if {% katex inline %}p{% endkatex %} is a large odd number and {% katex inline %}1 < a < p - 1{% endkatex %} and 
{% katex inline %}a^{p-1} \equiv 1 ~ (mod ~ p){% endkatex %} then {% katex inline %}p{% endkatex %} is almost certainly prime, although there are a small number of "pseudoprimes" that pass this test which are not prime.

However, we can detect these pseudoprimes quickly with high probability! And we will want to do this, because even a failure rate of 1 in a million is enough to cause a lot of problems for a company like Google or American Express.

## The Miller-Rabin Primality Test

However, if {% katex inline %}p{% endkatex %} is a large pseudoprime that managed to sneak past the Fermat test, there are two cases that we might have to worry about here. The first is that the pseudoprime p could be a power of a prime, say p = {% katex inline %}p = v^k{% endkatex %} where {% katex inline %}v{% endkatex %} is prime.

Then {% katex inline %}p{% endkatex %} is already extremely unlikely to escape the Fermat test - a random guess will only pass with probability 1 in {% katex inline %}v^{k-1}.{% endkatex %} A relatively small number of Fermat tests with randomly chosen values of {% katex inline %}a{% endkatex %} will detect that {% katex inline %}p{% endkatex %} is not prime with an acceptably low failure rate.

For any true prime {% katex inline %}p{% endkatex %} and primitive root {% katex inline %}a{% endkatex %} we know {% katex inline %}a^{k(p-1)/2} \equiv p - 1 ~ (mod ~ p){% endkatex %} if {% katex inline %}k{% endkatex %} is odd, and 1 if {% katex inline %}k{% endkatex %} is even, and 1 and {% katex inline %}p-1{% endkatex %} are the only two square roots it has.

The other case is when {% katex inline %}p = vw{% endkatex %} where {% katex inline %}v,w{% endkatex %} are odd and greater than 1 but and have no prime factors. We can take advantage of their existence without being able to find {% katex inline %}v{% endkatex %} and {% katex inline %}w.{% endkatex %}

Anything that is 1 (mod {% katex inline %}v{% endkatex %}) and {% katex inline %}w-1{% endkatex %} (mod {% katex inline %}w{% endkatex %}) will be another square root in of 1 in mod {% katex inline %}p{% endkatex %} arithmetic, which will be different from 1 and {% katex inline %}p-1.{% endkatex %}

Now, the key idea here is that if I pick a random integer from 0 to {% katex inline %}p-1,{% endkatex %} the remainders mod v and mod w are independent and uniformly distributed. What we do here is decorate the Fermat test a little bit.

First, find the unique odd number d for which we can write

{% katex %}p - 1 = d \cdot 2^e.{% endkatex %}

Now, we will do Fermat tests, with a random number {% katex inline %}a{% endkatex %} as before, but keep track of sightly more information. In what follows, all calculations are to be reduced modulo {% katex inline %}p.{% endkatex %}

1.) Let {% katex inline %}m = a^d.{% endkatex %}

2.) Calculate {% katex inline %}m, m^2, ... , m^{2^e}.{% endkatex %}

If the last result isn't 1, you have failed the Fermat test and you know the result is composite. However, even if you did not, you can look at the last power of m in the list for which the value was different from 1. If it's not {% katex inline %}p-1,{% endkatex %} then you have failed the Rabin-Miller primality test.

There's an entirely elementary proof that the Rabin-Miller test fails with probability at least 1/2 when {% katex inline %}p{% endkatex %} is not prime.

## Sharing Secrets using Primes

We can think about logarithms as the inverse of exponentiation, similarly to how we do for positive real numbers. log({% katex inline %}b{% endkatex %}) ( with base {% katex inline %}a{% endkatex %}) is the power {% katex inline %}n{% endkatex %} for which {% katex inline %}a^n{% endkatex %} = {% katex inline %}b.{% endkatex %}

The key fact here is that when {% katex inline %}p{% endkatex %} is a large prime number, the "logarithm" operation is computationally intractable.

Given {% katex inline %}a{% endkatex %} and {% katex inline %}n,{% endkatex %} it's easy to find {% katex inline %}a^n.{% endkatex %} However, if we know the values of {% katex inline %}a{% endkatex %} and {% katex inline %}b,{% endkatex %} in general it is quite hard to find {% katex inline %}n{% endkatex %} such that 
{% katex %}
a^n ~ \equiv ~ b ~ (mod ~ p).
{% endkatex %}

So here's a quick way for two parties to exploit this fact and pass information while maintaining their own privacy:

Alice and Bob have a shared prime number {% katex inline %}p,q{% endkatex %} and primitive root {% katex inline %}a.{% endkatex %} (In fact {% katex inline %}a{% endkatex %} doesn't need to be a primitive root, but needs to just have many distinct powers.)

Each has a private key, say {% katex inline %}x{% endkatex %} for Alice and {% katex inline %}y{% endkatex %} for Bob (they named them after their sex chromosomes).

Alice tells Bob {% katex inline %}a^x{% endkatex %} and Bob tells Alice {% katex inline %}a^y.{% endkatex %}

The values of {% katex inline %}x{% endkatex %} and {% katex inline %}y{% endkatex %} are secure (difficult for either to steal from the other or for an eavesdropper to intercept), but they can both access the value of {% katex inline %}a^{xy}{% endkatex %} to decrypt any information that needs to be available to both of them.

In fact the standard cryptographic system is a small variation on this: Instead of a large prime, we choose a product {% katex inline %}q{% endkatex %} of two large primes in place of {% katex inline %}p{% endkatex %} and a number like {% katex inline %}a{% endkatex %} in place of {% katex inline %}p{% endkatex %}, and those two pieces of infomration combined are Alice's _public key_. This has the additional layer of security that the exponent we must raise a number to to get 1 (mod {% katex inline %}q{% endkatex %}) is hard to compute.