# 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?

• Not a full answer, but if you are asking because of the recent Defcon talk that claimed recent advances in the discrete log problem might break RSA, it was full of it. The advances were for groups of small characteristic which don't even apply to the groups we use for the discrete log problem, let alone RSA. Aug 17, 2013 at 2:35
• Yeah but their broader point about needing to begin the migration to other primitives is valid, imo. Why gamble on factoring and discrete log in prime fields when we can just as easily use elliptic curves? Aug 17, 2013 at 3:04

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