Relationship between Elliptic Curve Discrete Log, Integer Discrete Log, and Integer Factorization I am trying to look into a relation between the following three problems which are widely used to build public crypto systems:


Integer Discrete log
Elliptic Curve Discrete log
Integer Factorization


Can any of these problems be reduced to another such that an efficient solution to one of them yields an efficient solution to the another?
Actually, there are two known reductions among these three problems:


If you can solve discrete logs in $Z^*_n$ for composite $n$, you can use that to efficiently factor $n$
If you can solve discrete logs in $GF(p^k)$, you can compute discrete logs in an Elliptic Curve over $GF(p)$.  That's because there is a known mapping of Elliptic Curves over $GF(p)$ into $GF(p^k)$ (for an integer $k$ that depends on the curve) that preserves the group operation; hence you can solve discrete logs over an Elliptic Curves by mapping the generator and the target into $GF(p^k)$, and solving the discrete log there.  Now, for curves used in practice, $k$ is large enough that, with the current discrete log algorithms, this method is actually slower than just using a generic discrete log algorithm in the elliptic curve.


Of course, neither of the above reductions would apply to the recently discovered algorithms for doing discrete logs over small characteristic fields; for the former, we're not talking about a field at all ($Z^*_n$ is a ring, not a field), and for prime elliptic curves (which is what we use in practice), $GF(p^k)$ has a very large characteristic.