Powering Algorithms and Primality Testing

note

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

The number $a^{k}(\bmod m)$ can be determined by $k-1$ multiplications of residue classes, but this is slow if $k$ is large. There is a much faster way: The values of $a, a^{2}, a^{4}, a^{8}, \ldots$, $a^{2^{i}}, \ldots, \quad(\bmod m)$ can be determined, by repeated squaring, in only $i$ multiplications. The binary expansion of $k$ provides a representation of $k$ as a sum of powers of 2 , and hence $a^{k}$ is a product of an appropriate collection of the numbers $a^{2^{i}}$. For example, $13=2^{3}+2^{2}+2^{0}$, and hence $a^{13}=a^{2^{3}} \cdot a^{2^{2}} \cdot a^{2^{0}}$. The exact number of multiplications required by this method varies irregularly with $k$, but it never exceeds $2 \log _{2} k$. The binary expansion of $k$ can be built from the bottom up, or from the top down. The former of these two methods is discussed on pages 76, 77 of §2.4 of NZM.

Problem 1

Apply the program PwrDem using its three different algorithm types to several values of $a, m$ until the process is clear to you. Apply the Left-to-Right and the Right-to-Left binary methods to the same $k$. How do the number of multiplications compare?

Problem 2

If $k$ has binary expansion $k=2^{i_{1}}+2^{i_{2}}+\cdots+2^{i_{r}}$ with $i_{1}<i_{2}<\cdots<i_{r}$, then our powering algorithm requires $i_{r}+r-1$ multiplications to calculate $a^{k}$. In particular, it takes 6 multiplications to calculate $a^{15}$. Show that $a^{15}$ can be obtained with only 5 multiplications.

Problem 3

The program Power evaluates $a^{k}(\bmod m)$. Use the program Power to evaluate $2^{m-1}(\bmod m)$ where $m=\left(10^{17}-1\right) / 9=$ 11111111111111111. Assuming Fermat's congruence, (Theorem 2.7 of NZM), this provides a quick (but indirect) proof that 11111111111111111 is composite. Apply the program Factor to 11111111111111111, and note how long it runs. With large numbers $m$ (of hundreds of digits), it is often the case that a quick proof that $m$ is composite can be given, even though we know of no way to obtain the factors of $m$ within a reasonable amount of time.

Problem 4

Is 91 prime? Evaluate $2^{90}(\bmod 91)$. Is 341 prime? Evaluate $2^{340}(\bmod 341)$. Now evaluate $3^{340}$ (mod 341). What do you conclude?

Problem 5

We have no quick method to find $k!(\bmod m)$ akin to our quick method for calculating powers. There are a few special cases (such as $(p-1)! \pmod{p}$), but in general the fastest method known involves simply performing the $k-1$ multiplications. If a quick method could be found, then it would have important applications (to factoring, for example). Suppose that you are in possession of a quick method for calculating $\binom{2 k}{k}(\bmod m)$.

Explain how this could be used to provide a quick method for calculating $k!(\bmod m)$. Suppose you have a quick method for calculating $k!(\bmod m)$. Explain how this could be used to provide a quick method for factoring $m$.

Discussion

If $0<a<m$ and $a^{m-1} \not \equiv 1(\bmod m)$ then $m$ is composite. Since it is easy to calculate powers modulo $m$, this provides a quick proof that $m$ is composite-when it works. Unfortunately, the converse is false, but the counterexamples seem to be rare, so we call $m$ a probable prime base $a$ if $m$ is odd and $a^{m-1} \equiv 1(\bmod m)$. If $m$ is a probable prime base $a$ but is nevertheless composite, then we call $m$ a pseudoprime base $a$, or, briefly, $m$ is a $\operatorname{PSP}(a)$. If $m$ is found to be a probable prime base 2 , then we might try base 3, and so on, but there exist composite $m$ that are probable primes to every base $a$ for which $(a, m)=1$. To see how this might happen, suppose that $m$ is a composite squarefree number with the peculiar property that $(p-1) \mid(m-1)$ for every prime number $p$ dividing $m$. (The least such $m$ is 561 .) Suppose that $(a, m)=1$. If $p \mid m$ then $(a, p)=1$, and hence $a^{p-1} \equiv 1(\bmod p)$. Since $(p-1) \mid(m-1)$, it follows that $a^{m-1} \equiv 1(\bmod p)$. Since this congruence holds for every $p$ dividing $m$, it holds modulo the product of all the primes dividing $m$. But we have assumed that $m$ is squarefree; hence $a^{m-1} \equiv 1(\bmod m)$. An odd composite number such that $a^{m-1} \equiv 1(\bmod m)$ whenever $(a, m)=1$ is called an absolute pseudoprime, or Carmichael number. The least Carmichael number is 561 ; indeed, it can be shown that if $m$ is a Carmichael number then $m$ is of the form we considered: $m$ is squarefree and $(p-1) \mid(m-1)$ whenever $p \mid m$. (This is called Korselt's criterion; see Problems 25-27 at the end of $\S 2.8$ of NZM.) It is not hard to show that there exist infinitely many pseudoprimes to any given base (see Problem 19 at the end of $\S 2.4$ of NZM), and it is easy to construct numerical examples of Carmichael numbers and to give arguments that suggest that Carmichael numbers form a fairly rich subset of the integers (by methods akin to the construction of Problem 20 of $\S 2.8$ of NZM). In particular, P. Erdős (On pseudoprimes and Carmichael numbers, Publ. Math. Debrecen 4 (1956), 201-206) formulated a heuristic argument that suggests that the number $C(x)$ of Carmichael numbers not exceeding $x$ is larger than $x^{1-\epsilon}$ for all sufficiently large $x$. Although Erdős's conjecture is presumably true, it seems that the $\epsilon$ tends to 0 slowly, since numerical studies have revealed that $C\left(10^{10}\right)=1547$, and that $C\left(10^{15}\right)=105212$. Nevertheless, it was finally proved that there do indeed exist infinitely many Carmichael numbers. W. R. Alford, A. Granville, and C. Pomerance, (There are infinitely many Carmichael numbers, Ann. of Math. (2) 139 (1994), 703-722) showed that $C(x)>x^{2 / 7}$ for all sufficiently large $x$.

Since the pseudoprime test fails to establish the compositeness of some composite numbers, we consider a slightly more elaborate test, which, however, involves no more calculation than before. If $m$ is odd, we repeatedly divide 2 into $m-1$, until we obtain a representation $m-1=2^{r} \cdot d$ with $d$ odd. Suppose that $a \not \equiv 0(\bmod m)$. Compute $a^{d}(\bmod$ $m)$. Next, repeatedly square, forming the sequence $a^{2 d}, a^{4 d}, \ldots, a^{(m-1) / 2}(\bmod m)$. Let $x$ denote this last residue class computed. If $x^{2} \not \equiv 1(\bmod m)$ then $a^{m-1} \not \equiv 1$ $(\bmod m)$, and hence $m$ is composite, by Fermat's congruence. Suppose now that $x^{2} \equiv 1$ $(\bmod m)$. If $x \not \equiv \pm 1(\bmod m)$ then $m$ is composite by virtue of Lemma 2.10 of NZM. More generally, if in the sequence of powers computed we find an entry $x \not \equiv \pm 1(\bmod m)$ followed by an entry 1 , then $x^{2} \equiv 1(\bmod m)$, and hence $m$ is composite. This test is more stringent than the previous one; if it is inconclusive then we call $m$ a strong probable prime base $a$. If in addition $m$ is composite then we call $m$ a strong pseudoprime base $a$, or $m$ is an $\operatorname{SPSP}(a)$. In practice, we abandon the repeated squaring if a value $\equiv \pm 1$ $(\bmod m)$ is encountered, since the conclusion is already clear. The exact sequence of steps performed is exhibited on p. 78 of NZM. It is known that if $m$ is composite then there are at least $m / 4$ bases $a$ such that the compositeness of $m$ is demonstrated by applying this strong pseudoprime test base $a$. Thus if $m$ survives this test for several values of $a$, we can be reasonably confident that $m$ is prime - such an $m$ might be called an "industrial grade prime".

Problem 6

By means of lengthy calculation (see C. Pomerance, J. L. Selfridge, and S. S. Wagstaff Jr., The pseudoprimes to $25 \cdot 10^{9}$, Math. Comp. 35 (1980), 1003-1026), it has been found that there are only 13 odd integers $m<25 \cdot 10^{9}$ that are $\operatorname{SPSP}(a)$ for $a=2, a=3$, and $a=5$. Of these, only one, namely $m=3215031751$ is also a $\operatorname{SPSP}(7)$. Apply the strong pseudoprime test to this $m$ with bases $a=2,3,5,7$, and 11. For example, try using the program SPsPDem with input $a=2$, $m = 3215031751$.

Problem 7

By appropriate use of the program Power, show that 4369 and 4371 are both probable primes base 2. Are either of these numbers strong probable primes base 2? Are either of these numbers prime? (Use the program SPsP to answer this question, not Factor.) Are either of these numbers Carmichael numbers?

Problem 8

Factor 561 using Factor, verify that 561 is squarefree, and that $p-1 \mid 560$ for every prime $p$ dividing 561. Hence deduce that 561 is a Carmichael number.

Problem 9

If $m$ is a $\operatorname{PSP}(a)$ but not a $\operatorname{SPSP}(a)$ then the strong pseudoprime test locates a number $x$ such that $x \not \equiv \pm 1(\bmod m)$, but $x^{2} \equiv 1(\bmod m)$. In such a situation not only is it established that $m$ is composite, but also a proper divisor of $m$ can be exhibited, namely $\gcd(x-1, m)$. Apply the program SPsPDem to $m=561$ with $a=2$.

Problem 10

Numerical evidence suggests that most pseudoprimes are squarefree. To explain this, show that if $m$ is a $\operatorname{PSP}(a)$, and if $p$ is a prime such that $p^{2} \mid m$, then

$$\begin{equation*} a^{p-1} \equiv 1 \quad\left(\bmod p^{2}\right) . \tag{1} \end{equation*}$$

(Hint: $a^{m} \equiv a(\bmod m)$, and hence $a^{p-1} \equiv\left(a^{m}\right)^{p-1} \equiv a^{m(p-1)}(\bmod m)$. But $\phi\left(p^{2}\right)$ divides $m(p-1)$.) Conversely, show that if $p$ is a prime such that (1) holds then $p^{2}$ is a $\operatorname{PSP}(a)$. Only a few primes have been found for which $2^{p-1} \equiv 1\left(\bmod p^{2}\right)$, although it is believed that infinitely many exist. The least such prime is 1093 . Use the program Factor to verify that 1093 is prime, and the program Power to verify that $2^{1092} \equiv 1$ $\left(\bmod 1093^{2}\right)$. Is 1093 a $\operatorname{SPSP}(2)$ ?

For an extensive account of primality testing see H. C. Williams, Primality testing on a computer, Ars Comb. 5 (1978), 127-185.