Primality testing

The objective of primality testing is to take as input a positive integer, and return as output a verdict whether the number is prime or composite. Only as recently as 2002 was it shown that this age-old problem can be solved in polynomial time; the algorithm was discovered by Manindra Agarwal, Neeraj Kayal, and Nitin Saxena (professor and two graduate students) at the Indian Institute of Technology, Kanpur.

Euclid used the sieve of Eratosthenes to perform primality testing. In this method, one constructs a list of the integers from $2$ to $N$. From this list, we remove all of the multiples of 2 on the first step. Since 3 is the smalles remaining number, it must be prime. We next remove all multiples of 3. Now 5 is the smallest number remaining, so it is prime. Remove all its multiples.

Remark 3.1   In order to discover all primes less than $N$, it is necessary to continue this process for all primes less than $\sqrt{N}$ (why?). Therefore, if $X$ is a number with $n$ digits, $X\approx 10^n$, then it is necessary to sieve until $10^{n/2}$ - an exponentially long process.

If we know the primes up to $10^{n/2}$, then we need only $\pi(10^{n/2})=\char93 \{$primes $p<10^{N/2}\}$ trial divisions. How much of a savings is this? To estimate this, we need the celebrated

Theorem 3.2 (Prime Number Theorem)   $\pi(x)\sim x/\ln{x}$.

Remark 3.3   The error in this approximation is $\pi(x) = x/\ln{x}+O(\frac{x}{(\ln{x})^2})$.

Remark 3.4   A better approximation is $\pi(x)={\mathrm {li}}(x)+O(x^{1-\epsilon})$ for some constant $\epsilon>0$, where

$${\mathrm {li}}(x)=\int_{t=2}^x\frac{\text{d}{t}}{\ln{t}}\text{.}$$

This expression as a good approximation of $\pi(x)$ was conjectured by Gauss. ${\mathrm {li}}$ is called the logarithmic integral.

Remark 3.5   It is believed - and in fact is equivalent to the Riemann Hypothesis - that the error in the logarithmic integral expression is of the order of $\sqrt{x}$:      $\pi(x) = {\mathrm {li}}(x)+O(\sqrt{x})$.

Remark 3.6   With regard to the sieve of Eratosthenes, notice that

$$\pi(10^{n/2})\sim \frac{10^{n/2}}{\frac{n}{2}\ln{10}}$$,$$$$

which for large enough $n$, is larger than $9.9^{n/2}$. Thus we still have exponential complexity.

We shall present two randomized (``Monte Carlo'') algorithms. These algorithms have two possible outputs:

1. ``Composite'' with a proof of compositeness.
2. ``Prime.''

In case ``Composite'' is returned, we know that the number is composite, because a proof of compositeness is produced. However, in the case the output is ``Prime,'' this is only a guess. It is possible, although unlikely, that on composite input, the algorithm returns ``prime.'' The probability of this happening is less than a predetermined $\epsilon>0$, and it is not unreasonable to ask $\epsilon$ to be less than $1/2^{1500}$, which error is less than $1/($number of particles in the known universe$)$.

Remark 3.7   It is often said that a number $X$ deemed to be prime through this process is ``very likely prime.'' This statement, however, does not make sense. $X$ is not chosen at random, it is given explicitly. Therefore either $X$ is prime, or it is not, it cannot have a probability of being prime. Our verdict, however, is probabilistic; with certain probability we say ``$X$ is prime'' and otherwise we say ``$X$ is composite.'' If $X$ is prime, we shall always say so, so in this case the chance that we make an error is zero. If $X$ is composite, then we may accidentally declare that $X$ is prime, but the probability of this happening is $<\epsilon$. So overall, the probability that our verdict is in error is $<\epsilon$.

Our first tool is Fermat's little Theorem.

Theorem 3.8 (Fermat's little theorem)   If $p$ is a prime, and gcd$(p,a)=1$, then $a^{p-1}\equiv 1\mod p$.

Definition 3.9   A Fermat witness of compositeness of $x$ is a number $a$ such that $1\leq a\leq x-1$ such that

1. gcd$(a,x)\neq 1$, or
2. gcd$(a,x)= 1$ and $a^{x-1}\not\equiv 1\mod x$.

Remark 3.10   Notice that in the second case, we do not find any factor of $x$ though we do have a proof that it is composite using the contrapositve of Fermat's little theorem.

Unfortunately, this won't quite work as a basis for a primality test, because of the following:

Definition 3.11   $x$ is a Carmichael number if $x$ is odd, not prime, but for all $a$ with gcd$(a,x)= 1$, $a^{x-1}\equiv 1\mod x$.

Carmichael numbers are rare, but it has been proved recently that there are infinitely many of them (Alford, Granville, Pomerance, 1994).

Exercise 3.12   Show that if $x=pq$ is the product of two primes, then $x$ is not a Carmichael number.

Exercise 3.13   Prove that $x=pqr$ is a Carmichael number if and only if $(p-1){\,\mid\,}qr-1$, $(q-1){\,\mid\,}rp-1$, and $(r-1){\,\mid\,}pq-1$.

Exercise 3.14   Show that the following numbers are Carmichael: 561 ( $3\cdot 11\cdot 17$), 1105 ( $5\cdot 13\cdot 17$), 1729 ( $7\cdot 13\cdot 19$), 2465 ( $5\cdot 17\cdot 19$), 2821 ( $7\cdot 13\cdot 31$), 6601 ( $7\cdot 23\cdot 41$), 8911 ( $7\cdot 19\cdot 67$), 10585 ( $5\cdot 29\cdot 73$). (Note: these are the eight smallest Carmichael numbers.)

The next exercise shows how to find a witness of compositeness if the input number is not Carmichael.

Exercise 3.15   Prove that if $x$ is composite and not Carmichael, then the probability that a random $a$ is a Fermat witness is at least $1/2$.