MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

2 added 460 characters in body

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

1

# Discrete logs vs. factoring

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?