# Was the reduction in Shor's algorithm originally discovered by Shor?

This is a "historical question" more than it is a research question, but was the classical reduction to order-finding in Shor's algorithm for factorization initially discovered by Peter Shor, or was it previously known? Is there a paper that describes the reduction that pre-dates Shor, or is it simply a so-called "folk result?" Or was it simply another breakthrough in the same paper?

I have to admit (surprising as it sounds) that I don't know really the answer. I either discovered or rediscovered this reduction myself.

I discovered the discrete log algorithm first, and the factoring algorithm second, so I knew from discrete log that periodicity was useful. I knew that factoring was equivalent to finding two unequal numbers with equal squares (mod N) — this is the basis for the quadratic sieve algorithm. I had also seen the reduction of factoring to finding the Euler $\phi$ function, which is quite similar.

While I came up with the reduction of this question to order-finding, it's not hard, so I wouldn't be surprised if there was another paper describing this reduction that predates mine. However, I don't think this could be a widely known "folk result". Even if somebody had discovered it, before quantum computing why would anybody care about reducing factoring to the question of order-finding (provably exponential on a classical computer)?

EDIT: Note that order-finding is provably exponential only in an oracle setting; order finding modulo $N$ is equivalent to factoring $N$, and this had been proved earlier by Heather Woll, as the other answer points out.

• Hmm, I'm not sure if this is authoritative enough Aug 15, 2014 at 3:51
• @mebob: Makes for a good Skeptics.SE post =P Aug 17, 2014 at 5:08
• So... Shor's not sure? Aug 18, 2014 at 8:38
• Actually, your original 1994 paper pdf contains the sentence “There is a randomized reduction from factoring to the order of an element ” where  is again a reference to Miller 1976 pdf. However, a quick glance at this paper didn’t allow me to find the corresponding reduction, but the reduction to φ. Feb 16, 2017 at 13:33
• @Frédéric Grosshans: Actually, I think it's quite likely that Andrew Odlyzko pointed that reference out to me. Feb 16, 2017 at 13:47

The random reduction from factorization to order-finding (mod N) was very well known to people working in number theory algorithms in the late 1970's and early 1980's. Indeed, it appears in a paper of Heather Woll, Reductions among number theoretic problems, Information and Computation 72 (1987) 167-179, and Eric Bach and I knew it before then.

I am mystified why Peter Shor says that order-finding is "provably exponential on a classical computer". If one knows the factorization of N and also $\varphi(N)$ (both computable in sub exponential time) and one works modulo each prime power, one can find orders.

• Order-finding for an oracle function for which all you can do is: given $k, n$, find $f^k(n)$ is provably exponential. This is all you need to use on a quantum computer. Aug 13, 2014 at 23:23
• I suspected you had a much more restricted model of computation in mind. But -- as I'm sure you know -- the particular problem of order-finding mod N is quite different. So in fact, it's quite plausible people would have been thinking about the reduction of this specific problem to and from factoring. Aug 13, 2014 at 23:30
• Heather Woll cites  as source for the reduction from factorization to order finding, but neither the Princeton engineering library nor Princeton Computer Science departement has a copy. (I’d be interested to find one, btw)  LONG. D. (1981) “Random Equivalence of Factorization and Computation of Orders,” Technical Report 284, Princeton University, Department of Electrical Engineering and Computer Science, April. Sep 18, 2015 at 9:25
• I have a copy and can send it to you if you send me your e-mail address. Sep 19, 2015 at 9:47