Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 105 down vote accepted

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.

share|cite|improve this answer
Hmm, I'm not sure if this is authoritative enough – chbaker0 Aug 15 '14 at 3:51
@mebob: Makes for a good Skeptics.SE post =P – Mehrdad Aug 17 '14 at 5:08
So... Shor's not sure? – OrangeDog Aug 18 '14 at 8:38
@PeterShor : $\:$ I figure I should mention this question, in case you hadn't seen it. $\hspace{.99 in}$ – Ricky Demer Jul 26 '15 at 0:48
@Ricky: that's number theory, and Andrew Odlyzko is an expert in that area. I forget how the proof goes. – Peter Shor Jul 26 '15 at 1:26

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.

share|cite|improve this answer
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. – Peter Shor Aug 13 '14 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. – Jeffrey Shallit Aug 13 '14 at 23:30
Heather Woll cites [1] 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) [1] LONG. D. (1981) “Random Equivalence of Factorization and Computation of Orders,” Technical Report 284, Princeton University, Department of Electrical Engineering and Computer Science, April. – Frédéric Grosshans Sep 18 '15 at 9:25
I have a copy and can send it to you if you send me your e-mail address. – Jeffrey Shallit Sep 19 '15 at 9:47

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.