Proving Primality

note

This is Lab 13 from Clint by Hugh Montgomery, edited by Codex and Elad Zelingher. All rights reserved to Hugh Montgomery.

We have seen that a composite number can be proved to be composite very quickly by means of the strong pseudoprime test. Finding the complete factorization of a composite number takes longer, but for large $n$ we have methods that are much faster than trial division. To complete the picture we need a fast method for proving the primality of a large prime number $p$. In this direction, we show that proving the primality of $p$ is no harder than factoring $p-1$. Suppose that $g^{p-1}\equiv1\pmod p$, and that $g^{(p-1)/q}\not\equiv1\pmod p$ for every prime factor $q$ of $p-1$. Then $g$ has order $p-1$ modulo $p$, and hence $p$ must be prime. In general, if $p$ is prime then such a $g$ is not hard to find; thus we have a means of proving that $p$ is prime provided that we can factor $p-1$.

Problem 1

Apply PrimRoot to 8675309. The machine quickly responds with a primitive root, because 8675308 is easily factored. Thus the primality of 8675309 has been rigorously established. (David Farmer proposes that this is the largest prime number ever mentioned in a popular song.)

The simple idea used above can be strengthened in several ways. First, suppose that $q$ is a prime factor of $p-1$, say $q^k\mathbin\Vert(p-1)$. Let $p'$ denote an arbitrary prime factor of $p$. Presumably the only such $p'$ is $p'=p$, but this remains to be proved. Suppose that we can find a number $a$ such that $a^{p-1}\equiv1\pmod p$ but such that $(a^{(p-1)/q}-1,p)=1$. Then $a^{p-1}\equiv1\pmod{p'}$ but $a^{(p-1)/q}\not\equiv1\pmod{p'}$. (Note that we can deduce this without knowing the value of $p'$.) Hence $q^k$ divides the order of $a$ modulo $p'$, and consequently $q^k\mid(p'-1)$. That is, every prime factor $p'$ of $p$ is $\equiv1\pmod{q^k}$. Suppose we repeat this for several different prime factors $q$ of $p-1$. (The value of $a$ that works is allowed to depend on $q$.) Let $s$ denote the product of the primepowers $q^k$ for which this calculation has succeeded. Then we can assert that every prime factor $p'$ of $p$ is $\equiv1\pmod s$. Since the product of two or more such primes must be $>s^2$, we see that if $s>\sqrt p$ then $p$ must be prime. Hence we can establish the primality of $p$, based only on an incomplete factorization of $p-1$, provided that we can factor $s$, $s\mid(p-1)$, and $s>\sqrt p$. (This analysis is related to Problems 38, 39 at the end of §2.8 of NZM.)

Problem 2

It is easy to confirm that $7^{16}+5^{16}=2\cdot16692759230113$. Use the program ProveP to demonstrate that this second factor is prime. That is, apply ProveP to 16692759230113, and note the results.

Problem 3

If, as the factorization of $p-1$ proceeds, a point is reached at which the factored portion $s$ of $p-1$ is so large that testing $p$ for divisors $d\equiv1\pmod s$, $d\leq\sqrt p$ will take less time than the time already spent trying to factor $p-1$, then the program ProveP automatically switches to the latter approach. To witness an instance of this, apply ProveP to the number $5\cdot10^{17}+21=500000000000000021$.

The method of proving primality being employed here can be made still more efficient. Suppose that as prime factors $q$ of $p-1$ are being found, we reach a point at which $p^{1/3}<s\leq p^{1/2}$. Then either $p$ is prime or $p$ is the product of two primes, $p=p'p''$, say. Write $p'=a's+1$ and $p''=a''s+1$, so that $p=a'a''s^2+(a'+a'')s+1$. With a little care with inequalities, it can be shown that $0<a'a''<s$ and that $0<a'+a''<s$. Thus the representation of $p$ that we have given here in terms of powers of $s$ coincides with the expansion of $p$ in base $s$. That is, by the division algorithm we may write $p=c_2s^2+c_1s+1$ with $0\leq c_i<s$, and $c_1=a'+a''$, $c_2=a'a''$. To determine whether such $a'$ and $a''$ exist, we have only to test whether $c_1^2-4c_2$ is a perfect square. This embellishment is due to H. C. Williams.

Problem 4

Apply the program ProveP to demonstrate that the number $1234567897531$ is prime. Also that $975312468097531$ is prime. If the program GetNextP is given an argument $x$ for which $10^9<x<10^{18}$, then the number $p$ returned is the least integer $>x$ that is a strong pseudoprime to bases 2, 3, 5, 7 and 11. It is incredibly likely that $p$ is prime, but to obtain a rigorous proof one should use the program ProveP. In this manner, find the least prime greater than 12345678987654321.

Problem 5

In most cases the method used by ProveP is reasonably quick. However, it can happen that $p-1=2q$ where $q$ is prime. In such a case, attention is focused on $q$. After a brief attempt to factor it by trial division fails, one should apply a strong pseudoprime test. If $q$ passes the test, then a rigorous proof that $q$ is prime may be obtained by applying the program ProveP to $q$. In attempting to factor $q-1$ one may encounter the same problem as with $p-1$. Nevertheless, by systematically employing the programs ProveP, SPsP, Factor and Rho, the needed factorizations can be rigorously established. For example, suppose that we apply the program ProveP to show that the number $p=987292984329259$ is prime. The machine quickly finds that $p-1$ is divisible by 2 and by 3, but then there is a pause. Touch any key to interrupt the program, and you find that it is trying to factor 164548830721543. Type q to quit, and then apply the program SPsP to this factor. In this way we discover that we are dealing with a composite number, so we apply the program Rho, which discloses that the factor may be written as $5378033\cdot30596471$. We apply the program Factor to the first of these numbers, to confirm that it is prime. Then we again apply ProveP to the original number $p$. Again the machine finds 2 and 3, but when it pauses, we interrupt it, type s to indicate that we wish to supply a prime factor, and enter 5378033. This time the program reaches a successful resolution without further intervention, and it is proved that $p$ is indeed prime. Show that $10^{18}-11=999999999999999989$ is prime. What intermediate numbers need to be factored? Give an account of the programs used, and the findings. (By applying GetNextP to this number you may confirm that this is the largest prime not exceeding $10^{18}$. Similarly, show that $(10^{18}-7)/3=333333333333333331$ is prime. Indicate what numbers are encountered, and how they are dealt with.

Problem 6

Show that $10^{17}+19$ and $10^{17}+21$ are both prime.

Problem 7

What is the first composite number in the sequence 31, 331, 3331, 33331, $\ldots$? Apply ProveP until the first composite element is encountered. Here the $k$-th term is $u_k=(10^k-7)/3$. Show that for every $k$, the least prime factor dividing $u_k$ is $\geq17$. Show that $17\mid u_k$ precisely when $k$ lies in a certain residue class (mod 16). (Suggestion: Use the program PowerTab to display $10^k\pmod m$ for appropriate $m$.)

Problem 8

For the programmer. When attempting to prove that $p$ is prime, we factor $p-1$. After removing the factor 2, this leaves $p_1=(p-1)/2$ to be factored—but this may be prime. In such a case we would confirm that $p_1$ is prime by applying ProveP. However, it may happen that $p_1=2p_2+1$ with $p_2$ prime. Perhaps also $p_2=2p_3+1$ with $p_3$ prime. It is in such a case that our procedure for establishing primality will require the most work. How long can a chain of primes be, with $p_i=2p_{i+1}+1$? Construct a program to explore this. Apply the SPSP test to odd integers until a probable prime $p$ is found. Then apply SPSP to $2p+1$, and so on, until a chain of $k$ probable primes has been constructed. If this chain is of record-breaking length, print out $p$ and $k$, so that the program ProveP can be applied to the members of the chain. The first chain you will find is $3$, $7$; the next one is $5$, $11$, $23$, $47$. Show that if $p$ begins a chain of length at least 4, with $p>5$, then necessarily $p\equiv29\pmod{30}$. For more on such chains, see D. H. Lehmer, On certain chains of primes, Proc. London Math. Soc. (3) 14a (1965), 183–186.

By the method of primality proof employed here, we see that proving that $p$ is prime is no harder than factoring $p-1$. Other methods of proving primality have been proposed, and some of these are significantly more efficient than our best factoring algorithms. Thus a prime of 1000 digits can be proved to be prime, but the record for factoring hard composite numbers stands below 200 digits. One of the methods currently in wide use is that of Adleman, Pomerance and Rumely (the APR method); it depends on Gauss sums. A method depending on elliptic curves, devised by Atkin and Morain, has achieved some striking successes lately. For more information concerning proofs of primality, consult the following papers.

L. M. Adleman, C. Pomerance, and R. S. Rumely, On distinguishing prime numbers from composite numbers, Ann. of Math. (2) 117 (1983), 173–206.

A. O. L. Atkin and F. Morain, Elliptic curves and primality proving, Math. Comp. 61 (1993), 29–68.

J. D. Dixon, Factorization and primality tests, Amer. Math. Monthly. 91 (1984), 333–352.