Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer

up vote 3 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.