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

Question

There is a paper from Peter W. Shor from 1994: Algorithms for Quantum Computation: Discrete Logarithms and Factoring, and I have a question about it and the algorithms presented.

For integer factoring problem, Shor's algorithm is working as a 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 the 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 with this description, please comment. The simple quantum circuit is here.

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

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