# Trying to understand p-adic logarithm map in elliptic curves

Im following these slides from "An Introduction to the Theory of Elliptic Curves" http://www.math.brown.edu/johsilve/Presentations/WyomingEllipticCurve.pdf, but I'm having some difficulty understanding how the ECDLP can be solved in anomalous curves.

On the slides it says: "If #E(Fp) = p, then there is a “p-adic logarithm map” that gives an easily computed homomorphism logp-adic : E(Fp) -> Z/pZ. It is easy to solve the discrete logarithm problem in Z/pZ, so if #E(Fp) = p, then we can solve ECDLP in time O(log p)."

But I'm having trouble understanding some concepts. I understand that there exists an homomorphism between the elliptic curve E(Fp) and the ring of integers Z/pZ. I might be wrong but from what I understand this homomorphism is map phi that satisfies this properties

• phi(O) = 0
• phi(P + Q) = phi(P) + phi(Q)
• phi(kP) = k.phi(P)

What I don't understand is why is it easy to solve the discrete logarithm problem in Z/pZ. Isn't the Diffie Hellman key exchange based on the difficulty of computing discrete logarithms?

But even assuming that it is easy do solve the DLP in Z/pZ, how could I get to the solution to the ECDLP assuming I have the solution to the DLP?

• Mar 1 at 5:51
• The solution process is very simple as noted on slides 3 and 53, we can compute inverses mod $p$ using the extended Euclidean algorithm and then note that $k\equiv\phi(kP)\phi(P)^{-1}\pmod p$. My favourite introduction to anomalous curves is Elliptic Tales by Ash and Gross chapter 9 section 3. It provides a nice step-by-step example computation of the map. Mar 1 at 7:29

What I don't understand is why is it easy to solve the discrete logarithm problem in $$\mathbb{Z}/p\mathbb{Z}$$. Isn't the Diffie Hellman key exchange based on the difficulty of computing discrete logarithms?

In the additive group $$\mathbb{Z}/p\mathbb{Z}$$, DLOG is equivalent to computing a modular inverse, which is efficient. I highly suspect the target of the $$p$$-adic logarithm is this additive group, as

• the slides use different notation for multiplicative groups,
• you are right --- if it were a multiplicative group DLOG wouldn't be easy, and
• logarithms convert multiplication into addition, so the group operation in the codomain of a logarithm should really be addition.

But even assuming that it is easy do solve the DLP in $$\mathbb{Z}/p\mathbb{Z}$$, how could I get to the solution to the ECDLP assuming I have the solution to the DLP?

In general, given an efficiently computable injective homomorphism $$\phi: G\to G'$$, if DLOG is easy in $$G'$$, then it is easy in $$G$$. This is because, given $$t = g^a$$, one can

1. compute $$\phi(t) = \phi(g^a) = \phi(g)^a$$
2. compute the discrete logarithm of $$\phi(t)$$ to recover $$a$$.

If $$\phi$$ isn't an injection you might run into some issues/have to do some more work, but the existence of such a homomorphism is good for attackers generically. I think pairing-based cryptography has more examples of such things if you're interested in other examples, but don't know details myself.