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
.