One thing that I've never quite understood is why computing discrete logarithms (in the multiplicative group mod p) and factoring seem to be so closely related. I don't think that there's a reduction in either direction, at least when p is prime (although a quick literature search tells me that there's a probabilistic reduction in one direction), but there are a huge number of nontrivial similarities:
- Neither of them are believed to have a classical polynomial-time algorithm, but essentially the same quantum algorithm works for both.
- Both of them serve as an easy basis for public-key cryptography, while other problems (for instance, lattice-based problems) are much more difficult to turn into working cryptosystems, and some (graph isomorphism, computing the permanent) seem to have no hope whatsoever of being useful in crypto.
- Many of the classical algorithms for one of them are closely related to a classical algorithm for the other — number field sieve and function field sieve, Pollard's rhos, baby-step giant-step vs. Fermat-type methods, and so on.
Is there a simple reason why, even though in theory they aren't reducible to each other, in practice they behave as though they were?
Edit: To clarify further, as Rune points out, both factoring and discrete log can be seen as versions of the hidden subgroup problem over an abelian group. I understand why there are quantum algorithms for this, and some of the obstacles to quantum algorithms for nonabelian HSP, and even to a degree why HSP is good to base a public-key system around. My question is essentially why "they share a much closer bond that isn't seen with other abelian HSPs."
Best Answer
Adding to Steve's answer: Both problems are special cases of the hidden subgroup problem over an abelian group. (Elliptic curve crypto also falls in the same category.)
We do have efficient quantum algorithms for solving the hidden subgroup problem over any abelian group. By "efficient" I mean it takes polynomially many queries AND has polynomial time complexity.
As for examples of non-abelian hidden subgroup problems: graph isomophism and certain lattice problems. We don't know how to solve these efficiently on a quantum computer. The WP article on quantum algorithms has more information and references.
Despite this similarity, factoring and discrete log share a much closer bond, which isn't seen with other abelian HSPs. I have no good explanation for that though.