Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
I am trying to look into a relation between the following three problems which are widely used to build public crypto systems:
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.
