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?