Primality Testing

Theorem 2.4 (Pseudoprimality)   An integer $p>1$ is prime if and only if for every $a\not\equiv 0\pmod{p}$ ,

$$a^{p-1}\equiv 1\pmod{p}.$$

Proof. If $p$ is prime, then the statement follows from Proposition 2.1.21. If $p$ is composite, then there is a divisor $a$ of $p$ with $2 \leq a < p$ . If $a^{p-1}\equiv 1\pmod{p}$ , then $p\mid a^{p-1} -1$ . Since $a\mid p$ , we have $a \mid a^{p-1} -1$ hence there exists an integer $k$ such that $ak = a^{p-1}-1$ . Subtracting we see that $a^{p-1} - ak = 1$ , so $a(a^{p-2} - k) = 1$ . This implies that $a\mid 1$ , which is a contradiction since $a \geq 2$ . $\qedsymbol$

Suppose $n\in\mathbb{N}$ . Using Theorem 2.4.1 and Algorithm 2.3.13, we can either quickly prove that $n$ is not prime, or convince ourselves that $n$ is likely prime (but not quickly prove that $n$ is prime). For example, if $2^{n-1}\not\equiv 1\pmod{n}$ , then we have proved that $n$ is not prime. On the other hand, if $a^{n-1}\equiv 1\pmod{n}$ for a few $a$ , it ``seems likely'' that $n$ is prime, and we loosely refer to such a number that seems prime for several bases as a pseudoprime.

There are composite numbers $n$ (called Carmichael numbers) with the amazing property that $a^{n-1}\equiv 1\pmod{n}$ for all $a$ with $\gcd(a,n)=1$ . The first Carmichael number is $561$ , and it is a theorem that there are infinitely many such numbers ([#!carmichael!#]).

Example 2.4   Is $p=323$ prime? We compute $2^{322}\pmod{323}$ . Making a table as above, we have

$i$	$m$	$\varepsilon _i$	$2^{2^i}$ mod 323
0	322	0	2
1	161	1	4
2	80	0	16
3	40	0	256
4	20	0	290
5	10	0	120
6	5	1	188
7	2	0	137
8	1	1	35

<>

Thus

$$2^{322} \equiv 4\cdot 188\cdot 35 \equiv 157\pmod{323},$$

so $323$ is not prime, though this computation gives no information about how $323$ factors as a product of primes. In fact, one finds that $323 = 17\cdot 19$ .

SAGE Example 2.4   It's possible to easily prove that a large number is composite, but the proof does not easily yield a factorization. For example if

$$n = 95468093486093450983409583409850934850938459083,$$

then $2^{n-1}\not\equiv 1\pmod{n}$ , so $n$ is composite.

sage: n = 95468093486093450983409583409850934850938459083
sage: Mod(2,n)^(n-1)
34173444139265553870830266378598407069248687241

Note that factoring $n$ actually takes much longer than the above computation (which was essentially instant).

sage: factor(n)                # takes up to a few seconds.
1610302526747 * 59285812386415488446397191791023889

Another practical primality test is the Miller-Rabin test, which has the property that each time it is run on a number $n$ it either correctly asserts that the number is definitely not prime, or that it is probably prime, and the probability of correctness goes up with each successive call. If Miller-Rabin is called $m$ times on $n$ and in each case claims that $n$ is probably prime, then one can in a precise sense bound the probability that $n$ is composite in terms of $m$ .

We state the Miller-Rabin algorithm precisely, but do not prove anything about the probability that it will succeed.

Algorithm 2.4 (Miller-Rabin Primality Test)   Given an integer $n\geq 5$ this algorithm outputs either true or false. If it outputs true, then $n$ is ``probably prime'', and if it outputs false, then $n$ is definitely composite.

1. [Split Off Power of $2$ ] Compute the unique integers $m$ and $k$ such that $m$ is odd and $n-1=2^k \cdot m$ .
2. [Random Base] Choose a random integer $a$ with $1<a<n$ .
3. [Odd Power] Set $b=a^m\pmod{n}$ . If $b\equiv \pm 1\pmod{n}$ output true and terminate.
4. [Even Powers] If $b^{2^r}\equiv -1 \pmod{n}$ for any $r$ with $1\leq r\leq k-1$ , output true and terminate. Otherwise output false.

If Miller-Rabin outputs true for $n$ , we can call it again with $n$ and if it again outputs true then the probability that $n$ is prime increases.

Proof. We will prove that the algorithm is correct, but will prove nothing about how likely the algorithm is to assert that a composite is prime. We must prove that if the algorithm pronounces an integer $n$ composite, then $n$ really is composite. Thus suppose $n$ is prime, yet the algorithm pronounces $n$ composite. Then $a^m\not\equiv \pm 1\pmod{n}$ , and for all $r$ with $1\leq r\leq k-1$ we have $a^{2^r m} \not \equiv -1\pmod{n}$ . Since $n$ is prime and $2^{k-1}m = (n-1)/2$ , Proposition 4.2.1 implies that $a^{2^{k-1}m}\equiv \pm 1\pmod{n}$ , so by our hypothesis $a^{2^{k-1}m}\equiv 1\pmod{n}$ . But then $(a^{2^{k-2}m})^2 \equiv 1\pmod{n}$ , so by Proposition 2.5.3 (which is proved below, and whose proof does not depend on this argument), we have $a^{2^{k-2}m}\equiv \pm 1\pmod{n}$ . Again, by our hypothesis, this implies $a^{2^{k-2}}\equiv 1\pmod{n}$ . Repeating this argument inductively we see that $a^m\equiv \pm 1\pmod{n}$ , which contradicts our hypothesis on $a$ . $\qedsymbol$

Until recently it was an open problem to give an algorithm (with proof) that decides whether or not any integer is prime in time bounded by a polynomial in the number of digits of the integer. Agrawal, Kayal, and Saxena recently found the first polynomial-time primality test (see [#!agrawal:primes!#]). We will not discuss their algorithm further, because for our applications to cryptography Miller-Rabin or pseudoprimality tests will be sufficient.

SAGE Example 2.4   The SAGE command is_prime uses a combination of techniques to determines (provably correctly!) whether or not an integer is prime.

sage: is_prime(95468093486093450983409583409850934850938459083)
False

We use the is_prime function to make a small table of the first few Mersenne primes (see Section 1.2.3).

sage: for p in primes(100):
...   if is_prime(2^p - 1):
...       print p, 2^p - 1
2 3
3 7
5 31
7 127
13 8191
17 131071
19 524287
31 2147483647
61 2305843009213693951
89 618970019642690137449562111

There is a specialized tests for primality of Mersenne numbers called the Lucas-Lehmer test. This remarkably simple algorithm determines provably correctly whether or not a number $2^p-1$ is prime. We implement it in a few lines of code and use the Lucas-Lehmer test to check for primality of two Mersenne numbers:

sage: def is_prime_lucas_lehmer(p):
...    s = Mod(4, 2^p - 1)
...    for i in range(3, p+1): 
...        s = s^2 - 2
...    return s == 0
sage: is_prime_lucas_lehmer(next_prime(1000))
False
sage: is_prime_lucas_lehmer(9941)
True

For more on searching for Mersenne primes, see the Great Internet Mersenne Prime Search (GIMPS) project at http://www.mersenne.org/.