And a dilemma on making further use of it

Gary Miller is a Professor of Computer Science at Carnegie Mellon University. He is best known for the Miller-Rabin primality test, which was cited in awarding him the 2003 ACM Paris Kanellakis Award along with Michael Rabin, Robert Solovay, and Volker Strassen. He has, however, been active in many other areas. His publications page has the best database functionality of any I know, and needs it.

Today Ken and I wish to talk about a result that evolved from Gary’s classic 1975 primality-testing paper into Section 2 of an equally classic 1986 joint work with Eric Bach and Jeffrey Shallit on factoring. That paper also ascribes it to Douglas L. Long. We wonder if it can be evolved further.

I still recall the night I heard about Gary’s great result. This was before e-mail and of course the Internet. Social media meant phone calls or even letters. David Dobkin had heard about the result, and we were both at a party on a Saturday night when he grabbed me, and took me aside—the party was loud–and told me about Gary’s theorem on primality testing. I was immediately excited, a breakthrough? Certainly if one believes the Extended Riemann Hypothesis as used in the paper to get an ${\tilde{O}(m^4)}$ time algorithm, where ${m}$ is the number of digits in the number being tested, and the tilde ignores factors of ${\log m}$. The unconditional primality test of Manindra Agrawal, Neeraj Kayal, and Nitin Saxena, which was ${\tilde{O}(m^{12})}$ since improved to ${\tilde{O}(m^6)}$, was definitely hailed as one, including the 2006 Gödel prize.

Last year, Gary was hailed here for a “theoretical breakthrough…with enormous practical potential” on the solving of linear systems of equations from symmetric diagonally dominant matrices. The paper is joint with Ioannis Koutis and Richard Peng, and appeared at FOCS 2010. The CMU press release notes that Gaussian elimination “was first published by Chinese mathematicians 2,000 years ago”—a case of “everything being named after Gauss.”

## The Result

We will state the result only for the case ${M=pq}$ where ${p,q}$ are two distinct odd primes. This shows off the method, avoids messy notation, and is the most important case anyway. In crypto-systems that use factoring as a hardness assumption this is usually the case that they care about.

The related significance of the result is expressed by the title of the referenced paper by Long: “Random equivalence of factorization and computation of orders.” This is the equivalence used implicitly in Peter Shor’s famous paper on factoring by quantum computers. We have not been able to trace Long’s paper beyond the “to appear” citations. In any event, Shor cites the 1976 journal version of Miller’s paper for this equivalence.

Lemma 1 Suppose we are given integers ${M}$ and ${r}$ such that ${M = pq}$ where ${p}$ and ${q}$ are odd primes, and ${r}$ is a multiple of ${p-1}$. Then we can factor ${M}$ in randomized polynomial time.

The proof below is a slight simplification of the one in Section 2 of the 1986 paper, but still strikes us as not the proof from The Book. We thought you might like looking at it.

## Factoring Via GCD

There really is one theme that is used over and over in most methods of factoring: try to construct an integer ${x}$ so that ${p}$ divides ${x}$ and ${q}$ does not. Then the value of ${\gcd(x,M)}$ will equal ${p}$, and ${M}$ is factored. Of course the roles of ${p}$ and ${q}$ can be exchanged—the key is that only one prime divides ${x}$ and the other does not. Note that the ancient algorithm of Euclid computes ${\gcd(x,M)}$ in time that is a small power of the number of digits in ${x}$ and ${M}$, thus in polynomial time.

Let’s look at how this strategy factors ${M}$ provided we know a multiple ${r}$ of ${p-1}$.

Define ${A(r,p,q)}$ to be true when only one of ${p-1}$ and ${q-1}$ divides ${r}$. Also define ${B(r,p,q)}$ to be true when both

$\displaystyle \frac{r}{(p-1)}$

and

$\displaystyle \frac{r}{(q-1)}$

are odd numbers. The rationale for these definitions is the following two lemmas:

Lemma 2 There is a randomized algorithm ${A^{*}(r,M)}$ that factors ${M}$ with probability at least one-half, provided ${A(r,p,q)}$ is true.

Proof. Assume that ${A(r,p,q)}$ is true, and ${p-1}$ divides ${r}$. Pick a random ${a}$ in ${1,\dots,M-1}$, and compute ${\gcd(a^{r}-1,M)}$. We claim that at least half the time this is a factor of ${M}$. Picking ${a}$ by the Chinese Remainder Theorem (CRT) is equivalent to picking ${a}$ modulo each prime separately. Now ${a^{r} \equiv 1 \bmod p}$, since ${a^{p-1} \equiv 1 \bmod p}$ and ${p-1}$ divides ${r}$. So we need to show that

$\displaystyle a^{r} \equiv 1 \bmod q$

is true only at most half the time. Since ${q-1}$ does not divide ${r}$ there is some ${b}$ so that ${b^{r} \not\equiv 1 \bmod q}$. This uses that ${\mathbb{Z}_{q}^{*}}$ is a cyclic group of order ${q-1}$. But then the set of ${b}$ so that ${b^{r} \equiv 1 \bmod q}$ is a proper subgroup, and thus has at most half the elements modulo ${q}$. This proves the lemma. $\Box$

Lemma 3 There is a randomized algorithm ${B^{*}(r,M)}$ that factors ${M}$ with probability at least one-half, provided ${B(r,p,q)}$ is true.

Proof. Assume that ${B(r,p,q)}$ is true. Pick a random ${a}$ in ${1,\dots,M-1}$, and compute ${\gcd(a^{r/2}-1,M)}$. We claim that at least half the time this is a factor of ${M}$. Since ${B(r,p,q)}$ is true there is an ${\ell}$ so that ${(p-1)\ell = r}$ and ${\ell}$ is odd, and there is an ${m}$ so that ${(q-1)m = r}$ and ${m}$ is also odd. Now picking ${a}$ randomly means that at least half the time ${a}$ will be a quadratic residue modulo one of the primes and a non-residue modulo the other. So assume that ${a}$ is a quadratic residue modulo ${p}$ and a non-residue modulo ${q}$. Then,

$\displaystyle \begin{array}{rcl} a^{(p-1)/2} &\equiv& 1 \bmod p \\ a^{(q-1)/2} &\equiv& -1 \bmod q, \end{array}$

by the famous Euler criterion. The last step is to note that by definition of ${\ell}$ and ${m}$ this is the same as:

$\displaystyle \begin{array}{rcl} a^{(p-1)\ell/2} &\equiv& 1 \bmod p \\ a^{(q-1)m/2} &\equiv& -1 \bmod q. \end{array}$

$\Box$

## Putting This Together

Recall that we start with an ${r}$—any ${r}$—such that ${p-1}$ divides ${r}$. Note that we don’t yet know what ${p-1}$ is, we just know that it is among the divisors of the ${r}$ we have.

Our goal is to find ${r}$—possibly another ${r}$—so that ${A(r,p,q)}$ or ${B(r,p,q)}$ is true. Define ${r_{i} = r/2^{i}}$, and let ${k}$ be such that ${r_{k}}$ is an odd integer. We run ${A^{*}(r_{i},M)}$ and ${B^{*}(r_{i},M)}$ for all ${i=0,\dots,k-1}$. If any yields a factor we are done. Otherwise, we try the process again. The final point is that this process works at least one-half the time.

Let’s prove that. Initially ${p-1}$ divides ${r}$ by assumption. If ${q-1}$ does not divide ${r}$ then ${A(r,p,q)}$ is true and we are done. Note that since ${r_k}$ is odd, neither divides it. Hence there must exist a least ${i > 0}$ such that ${p-1}$ and ${q-1}$ both divide ${r_{i-1}}$ but do not both divide ${r_i}$. If exactly one divides ${r_i}$ then ${A(r_i,p,q)}$ holds and again we are done.

So suppose neither divides ${r_i}$. Then we have integers ${\ell}$ and ${m}$ such that

$\displaystyle (p-1)\ell = r_{i-1} = (q-1)m.$

Necessarily ${\ell}$ and ${m}$ are both odd, else one of ${p-1}$ or ${q-1}$ would divide ${r_i = r_{i-1}/2}$. Thus ${B(r_{i-1},p,q)}$ is true. This each run of the above process has at least a one-half chance to factor.

## Open Problems

Is there a way, given knowledge of ${M = pq}$, to improve the probability of hitting an ${r}$ such that one of ${p-1}$ or ${q-1}$ divides ${r}$? Of course this is equivalent to improving the heuristic odds on factoring.

[fixed AKS names, clarified last eqn in Lemma 3, fixed CMU link]

1. December 10, 2011 5:18 pm

The names should be Neeraj Kayal and Nitin Saxena.

• December 10, 2011 6:08 pm

Whoops! Tushar Saxena is someone I knew (of) while he was at Albany. Thanks. Meanwhile, I was occupied with Mac Firefox momentarily displaying the raw LaTeX code rather than rendering it, but it is now OK again.

December 10, 2011 8:32 pm

To me $a^{(p-1)/2l}$ and $a^{(q-1)/2m}$ may be ambiguous but most intuitively parses like $a^{(p-1)/(2l)}$ and $a^{(q-1)/(2m)}$. I assume you mean what would be clearer as $a^{(p-1)l/2}$ and $a^{(q-1)m/2}$.

December 11, 2011 9:22 am

Ørjan Johansen,

Good point. We should have fixed that. Of course it only divide by 2. Thanks.

• December 11, 2011 11:48 am

Fixed—thanks. Actually, here’s a weird “excuse” while tired: I was trying to work out whether only one evaluation of B^*(r_{k-1},M) might be needed in the algorithm as originally written, so mentally I was seeing powers of 2 in those denominators…

3. December 11, 2011 11:30 am

Very nice post.

But I can’t resist: Joel David Hamkins has, in my biased opinion, a slightly better publication page.

• December 11, 2011 11:31 am

By “better” I only mean the database functionality, of course.

December 13, 2011 5:32 pm

“But I can’t resist: Joel David Hamkins has, in my biased opinion, a slightly better publication page.”

Not bad. But nobody beats Neal Young:
http://www.cs.ucr.edu/~neal/publications

4. December 11, 2011 12:43 pm

“Last year, Gary was hailed here”

The link at the word “here” seems to be broken.

• December 11, 2011 1:05 pm

Fixed—the “http://” was missing. Thanks. Alternate, perhaps more permanent, link in the CMU archives here.

5. December 12, 2011 5:55 pm

When I was an undergrad in the 70s Miller was working on graph embedding, and had some nice papers on efficient ways to embed planar graphs. At the time, I got the impression he was moving in the direction of graph isomorphism, but apparently he changed course interestingly.