What is the difference between Shor's algorithm for factoring and Shor's algorithm for logarithm

Question

There is a paper from Peter W. Shor from 1994: http://www.csee.wvu.edu/~xinl/library/papers/comp/shor_focs1994.pdf "Algorithms for Quantum Computation: Discrete Logarithms and Factoring", and I have a question about the paper and algorithms presented.

For integer factoring problem, Shor's algorithm is working as fast period finder for function f(x) = a^x mod N, where semiprime N is equal to p*q, a is fixed and all possible exponents x are quantumly computed. Then, Shor uses Simon's algorithm to find period r of f(x) such that f(x) = f(x+r) . With 0.5 probability, the output of quantum scheme r will be the even and a^(r/2) will be non-trivial square root of 1 mod N. Having such root we can easily crack N to p and q. (If there is something wrong in this description, please comment. Simple quantum circuit is here: http://www.nature.com/nature/journal/v414/n6866/fig_tab/414883a_F1.html )

But how Shor's algorithm for discrete logarithm problem works? There is only prime number P (and generator g), so we can't factor it to something having square root. I'm even not sure that there will be any nontrivial square root in mod p field.

Task for discrete logarithm is: given some x, equal to x = g^r mod p, with g and p known, find the r.

Answer 1

In fact, the basic idea of Shor's algorithm for the discrete logarithm problem is reasonably simple.

Assume (as in Section 4 Discrete Log: the easy case of Shor's paper) that you have an efficient quantum algorithm for the Fourier transform. Then, applying this Fourier transform twice (once for $a$ and once for $b$) on a quantum superposition of values $g^a\cdot x^{-b}$ and measuring yields a pair $(c,d)$ with $d\equiv -cr\pmod{p-1}$. Thus, you can recover $r$ (if the gcd of $c$ and $p-1$ is $1$) directly with a simple division modulo $p-1$. [If the gcd is a small number it is also easy to conclude]

Unfortunately, doing this Fourier transform directly is only easy when $p-1$ is smooth (which is an uninteresting case since dlogs are easy with a classical computer in that case) and technicalities arise because of this. These technicalities involve replacing the Fourier transform modulo $p-1$ by a Fourier transform modulo $q,$ where $q$ is smooth and not too far from $p-1$. A similar technique is used for factoring: it is simpler than the general discrete logarithm case because a single application of the Fourier transform is enough in that case.