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.