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

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 works as a fast period finder for the function $$f(x) = a^x \bmod N$$, where semiprime $$N$$ is equal to $$p \times q$$, $$a$$ is fixed and all possible exponents $$x$$ are quantumly computed. Then, Shor uses Simon's algorithm to find the period $$r$$ of $$f(x)$$ such that $$f(x) = f(x+r)$$. With $$0.5$$ probability, the output of quantum scheme $$r$$ will be even, and $$a^{r/2}$$ will be the non-trivial square root of $$1 \bmod N$$. Having such a 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 a prime number $$p$$ (and generator $$g$$), so we can't factor it into something having a square root. I'm not even sure that there will be any nontrivial square root in the $$\bmod p$$ field.

The task for discrete logarithm is: given some $$x$$, equal to $$x = g^r \bmod p$$, with $$g$$ and $$p$$ known, find the $$r$$.

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.