# 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. 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)?

-
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

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. –  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