Witness or liar? 🤥

Primes are of great theoretical and practical value in cryptography. A primality test is an algorithm for determining whether an input number is prime or not.

Naive but deterministic

The simplest primality test is trial division: given an input number, $n$, check whether it is divisible by any prime number between 2 and $\sqrt{n}$. If so, then $n$ is composite. Otherwise, it is prime.

The prime number theorem: the distribution of primes is $π(n) \sim n/\log(n)$ where $π(n)$ is the prime-counting function (the number of primes less than or equal to $n$) and $\log(n)$ is the natural logarithm of $n$.

1. By the prime number theorem, how many trial divisions one needs to perform?

Fast but probabilistic

The basic structure of probabilistic primality tests is as follows:

• Randomly pick a number $a$.
• Check some equality involving $a$ and the given number $n$. If the equality fails to hold true, then $n$ is a composite number and $a$ is a witness for the compositeness, and the test stops.
• Get back to the step one until the required accuracy is reached.

After one or more iterations, if $n$ is not found to be a composite number, then it can be declared probably prime.

The simplest probabilistic test is based on Fermat’s little theorem.

Fermat’s little theorem states that if $n$ is prime and $a$ is not divisible by $n$, then $a^{n-1} = 1 \pmod n$

Given an integer $n$, choose some integer $a$ coprime to $n$ and calculate $a^{n-1} \pmod n$. If the result is different from 1, then $n$ is composite. If it is 1, then $n$ may be prime.

2. Given that the time complexity of modular exponentiation is roughly $\mathcal{O}(\log^2 n)$, what is the complexity of this algorithm?
3. Apply this algorithm iteratively 3 times to determine if 17 is prime.
4. Now consider $n=221$. Apply the algorithm with $a=38$. Is $n$ probably a prime? Now use $a=24$. What do you conclude?
5. Now consider $n=561$. Apply the algorithm with any witness $a$ you want. What do you conclude?