89

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?

Kaveh
  • 21,577
  • 8
  • 82
  • 183

2 Answers2

155

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.

Peter Shor
  • 24,763
  • 4
  • 93
  • 133
  • 114
    Hmm, I'm not sure if this is authoritative enough – chbaker0 Aug 15 '14 at 03:51
  • 6
    @mebob: Makes for a good Skeptics.SE post =P – user541686 Aug 17 '14 at 05:08
  • 32
    So... Shor's not sure? – OrangeDog Aug 18 '14 at 08:38
  • @PeterShor : $:$ I figure I should mention this question, in case you hadn't seen it. $\hspace{.99 in}$ –  Jul 26 '15 at 00: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 01:26
  • @PeterShor : I’ve just reread one of your 1995 papers and page 15 contains the sentence “It is known that using randomization, factorization can be reduced to finding the order of an element [Miller 1976]; we now briefly give this reduction.” This is from the v2 (jan 96), the v1 (aug 95) was not kept by arXiv. Maybe this addition was suggested by a referee ? – Frédéric Grosshans Feb 16 '17 at 13:10
  • 2
    Actually, your original 1994 paper pdf contains the sentence “There is a randomized reduction from factoring to the order of an element [23]” where [23] 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 φ. – Frédéric Grosshans Feb 16 '17 at 13:33
  • 3
    @Frédéric Grosshans: Actually, I think it's quite likely that Andrew Odlyzko pointed that reference out to me. – Peter Shor Feb 16 '17 at 13:47
54

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.

Frédéric Grosshans
  • 815
  • 6
  • 15
Jeffrey Shallit
  • 6,986
  • 33
  • 38
  • 14
    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
  • 14
    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 09:25
  • 2
    I have a copy and can send it to you if you send me your e-mail address. – Jeffrey Shallit Sep 19 '15 at 09:47