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) &mdash; 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.