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