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