Take the 2-minute tour ×
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.

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|improve this question

2 Answers 2

up vote 84 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. 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)?

share|improve this answer
30  
Hmm, I'm not sure if this is authoritative enough –  mebob Aug 15 at 3:51
2  
@mebob: Makes for a good Skeptics.SE post =P –  Mehrdad Aug 17 at 5:08
6  
So... Shor's not sure? –  OrangeDog Aug 18 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.

share|improve this answer
12  
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 at 23:23
13  
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 at 23:30

Your Answer

 
discard

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.