What is p-adic logarithmic map of an elliptic curve? How to compute it?

Question

I was reading about elliptic curves in this pdf. Page 55 of the pdf states that if number of points on elliptic curve #$E(F_p) = p$, then there exists a p-adic logarithmic map that homomorphically maps points in $E(F_p)$ to $F_p$. Now, solving for discrete logarithm on $E(F_p)$ reduces to solving for discrete logarithm in $F_p$.

Can anyone please explain what is p-adic logarithmic map and how to compute it? Does the technique extend to $E(F_{p^k})$?

Answer 1

Such curves are known as anomalous curves, which should help you find more information about this, by searching anomalous discrete logarithm problem or something.

In particular exercise 7.13 of Silverman's "Arithmetic of elliptic curves" book goes through this. The basic idea is that it is the logarithm map associated to the formal group of the elliptic curve.

Nigel Smart also has an article "The Discrete Logarithm Problem on Elliptic Curves of Trace One" which goes through an example of this, but doesn't explain too much about the actual computation of the logarithm unfortunately. http://www.hpl.hp.com/techreports/97/HPL-97-128.pdf

http://www.monnerat.info/publications/anomalous.pdf also explains everything in detail if you don't want to do the exercise.

As for your second question, I think it should extend fine to $\mathbf F_{p^k}$ though I didn't check to be completely sure. You will have to take the logarithm map to an unramified extension of $\mathbf Q_p$ instead though.

Let me know if you want I can try and add some more detail on some part of this.

Example

I apologise for the spammy long example, this probably isn't the most helpful first example. Rather this is an example of me trying to convince myself something like this works over $\mathbf F_{25}$. I didn't (yet) get around to adding an explanation of the theory, as requested either.

But here is an (extended) explicit example I just did in Sage, much of this could be done by hand I'm sure but computers make less typos than me.

The short version is, I took an elliptic curve $F$ over $\mathbf F_{25}$ with 25 points (hence the group structure is $C_{25}$), picked a random generator $\bar P$ and multiplied it by 7 to get a second point $\bar Q$, I took lifts of both the curve and the points to $\mathbf Q_{25}$ the unramified extension of $\mathbf Q_5$ of degree 2, and multiplied both lifted points by 25 to ensure they lie in the residue disk around $\infty$. Then I used the formal group logarithm, an isomorphism from this disk to $\mathbf Z_{25}$ to find a $q$-adic number that one is multiplied by to get the other and reduced mod $25$ to (magically) get a number in $\mathbf Z/25\mathbf Z$ even though the $q$-adic did not lie in $\mathbf Q_5\subseteq \mathbf Q_{25}$.

sage: L = GF(25)
sage: b = L.gen() # So L = F_5 (b)
sage: b.minpoly() # So L = F_5 [x] / (x^2 + 4x + 2)
x^2 + 4*x + 2
sage: F = EllipticCurve([3,b+1])
sage: F
Elliptic Curve defined by y^2 = x^3 + 3*x + (z2+1) over Finite Field in z2 of size 5^2
sage: F.points() # z2 is the generator I called b above, its possible to make this display nicer by doing L.<b> = GF(25) from the start, oh well
[(0 : 1 : 0), (0 : 2*z2 + 3 : 1), (0 : 3*z2 + 2 : 1), (z2 : z2 + 1 : 1), (z2 : 4*z2 + 4 : 1), (z2 + 1 : 2*z2 : 1), (z2 + 1 : 3*z2 : 1), (z2 + 2 : 2*z2 + 3 : 1), (z2 + 2 : 3*z2 + 2 : 1), (z2 + 3 : 2*z2 : 1), (z2 + 3 : 3*z2 : 1), (2*z2 + 2 : 2*z2 + 2 : 1), (2*z2 + 2 : 3*z2 + 3 : 1), (2*z2 + 3 : z2 + 4 : 1), (2*z2 + 3 : 4*z2 + 1 : 1), (3*z2 + 1 : 2*z2 : 1), (3*z2 + 1 : 3*z2 : 1), (3*z2 + 2 : 2*z2 + 1 : 1), (3*z2 + 2 : 3*z2 + 4 : 1), (3*z2 + 3 : 1 : 1), (3*z2 + 3 : 4 : 1), (3*z2 + 4 : z2 + 2 : 1), (3*z2 + 4 : 4*z2 + 3 : 1), (4*z2 + 3 : 2*z2 + 3 : 1), (4*z2 + 3 : 3*z2 + 2 : 1)]

We need 25 points to be in business for the attack (fortunately I picked this curve to have this property!)

sage: len(F.points())
25
sage: rP = F.points()[3]
sage: rP,rP.order()
((z2 : z2 + 1 : 1), 25)

So we have a generator of $F(\mathbf F_{25})$

sage: rQ = 7*rP # multiply by our _secret_ 7, from this point we "forget" where rQ came from
sage: rQ
(z2 + 1 : 2*z2 : 1)
sage: K.<a> = Qq(25) # The unramified extension of Q_5 of degree 2
sage: a^2 + 4*a + 2 # check a is a lift of b
O(5^20)
sage: Fq = EllipticCurve([3,a+1]) # A lift of our elliptic curve from before (we can check if we want to be sure that minpoly of b is minpoly of the lift a)
sage: Fq.lift_x(a, all=True) # points where x = a, so potentially lifting rP
[(a + O(5^20) : (a + 1) + (4*a + 4)*5 + (a + 1)*5^2 + (4*a + 4)*5^3 + (4*a + 4)*5^4 + (3*a + 3)*5^5 + (3*a + 3)*5^6 + (2*a + 2)*5^8 + (4*a + 4)*5^9 + (2*a + 2)*5^10 + (2*a + 2)*5^11 + (a + 1)*5^12 + (2*a + 2)*5^13 + (3*a + 3)*5^16 + (3*a + 3)*5^17 + (2*a + 2)*5^18 + (2*a + 2)*5^19 + O(5^20) : 1 + O(5^20)),
 (a + O(5^20) : (4*a + 4) + (3*a + 3)*5^2 + (a + 1)*5^5 + (a + 1)*5^6 + (4*a + 4)*5^7 + (2*a + 2)*5^8 + (2*a + 2)*5^10 + (2*a + 2)*5^11 + (3*a + 3)*5^12 + (2*a + 2)*5^13 + (4*a + 4)*5^14 + (4*a + 4)*5^15 + (a + 1)*5^16 + (a + 1)*5^17 + (2*a + 2)*5^18 + (2*a + 2)*5^19 + O(5^20) : 1 + O(5^20))]
sage: P = Fq.lift_x(a, all=True)[0] # point above rP is the first one (look at y-coeff)
sage: Fq.lift_x(a+1, all=True) # points where x = a + 1, potentially lifting Q
[((a + 1) + O(5^20) : 3*a + 4*5 + 2*5^2 + 2*a*5^3 + (4*a + 4)*5^4 + (4*a + 4)*5^5 + 2*5^6 + (a + 4)*5^7 + (3*a + 4)*5^8 + (a + 2)*5^9 + 4*a*5^10 + 3*a*5^11 + 3*a*5^12 + (2*a + 2)*5^13 + 3*5^14 + 4*a*5^15 + (4*a + 2)*5^16 + a*5^17 + 3*5^18 + a*5^19 + O(5^20) : 1 + O(5^20)),
 ((a + 1) + O(5^20) : 2*a + (4*a + 1)*5 + (4*a + 2)*5^2 + (2*a + 4)*5^3 + (4*a + 2)*5^6 + 3*a*5^7 + a*5^8 + (3*a + 2)*5^9 + 4*5^10 + (a + 4)*5^11 + (a + 4)*5^12 + (2*a + 2)*5^13 + (4*a + 1)*5^14 + 4*5^15 + 2*5^16 + (3*a + 4)*5^17 + (4*a + 1)*5^18 + (3*a + 4)*5^19 + O(5^20) : 1 + O(5^20))]
sage: Q = Fq.lift_x(a + 1, all=True)[1] # point above rQ is the second one

Now the goal is to find what the multiplier is that takes $P$ to $Q$, first we need to be near $\infty$ $p$-adically, so using the fact that 25 is the order of the $\mathbf F_{25}$ points:

sage: pP = 25*P
sage: pQ = 25*Q
sage: pP,pQ # points near infinity we can take log of
(((4*a + 4)*5^-2 + (a + 1) + (2*a + 2)*5 + (a + 1)*5^2 + (2*a + 3)*5^3 + (2*a + 2)*5^4 + (3*a + 3)*5^5 + (4*a + 1)*5^6 + (a + 2)*5^7 + (a + 1)*5^8 + 4*a*5^9 + (3*a + 4)*5^10 + 3*a*5^11 + (a + 4)*5^12 + a*5^13 + (4*a + 3)*5^14 + (a + 2)*5^15 + O(5^17) : (4*a + 3)*5^-3 + (4*a + 2)*5^-2 + (a + 2)*5^-1 + (4*a + 4) + 2*a*5 + (a + 1)*5^2 + 5^3 + 5^4 + (2*a + 2)*5^5 + (4*a + 1)*5^6 + (a + 3)*5^7 + 3*5^8 + (4*a + 1)*5^9 + 2*5^10 + (2*a + 2)*5^11 + (a + 1)*5^12 + (3*a + 3)*5^13 + 2*a*5^14 + O(5^16) : 1 + O(5^20)),
 ((a + 1)*5^-2 + (4*a + 4)*5^-1 + (4*a + 4) + a*5 + (4*a + 1)*5^2 + (2*a + 3)*5^4 + (2*a + 3)*5^5 + (3*a + 2)*5^6 + (3*a + 3)*5^7 + (3*a + 4)*5^8 + 3*a*5^9 + (4*a + 3)*5^10 + (3*a + 1)*5^11 + (a + 4)*5^12 + (3*a + 4)*5^13 + (3*a + 3)*5^14 + (4*a + 2)*5^15 + (a + 1)*5^16 + O(5^17) : (3*a + 1)*5^-3 + (3*a + 3)*5^-2 + (3*a + 2)*5^-1 + (2*a + 1) + 4*5 + (4*a + 3)*5^2 + (3*a + 2)*5^3 + (2*a + 1)*5^4 + (4*a + 3)*5^5 + (4*a + 4)*5^6 + (a + 3)*5^7 + (3*a + 3)*5^9 + 3*5^11 + 2*a*5^13 + a*5^14 + (4*a + 2)*5^15 + O(5^16) : 1 + O(5^20)))

Now we come to taking logarithms, we express $25P,25Q$ in terms of a formal parameter $t = -x/y$ near $\infty$:

sage: tP = -pP[0]/pP[1] # the formal parameters for 25P,25Q
sage: tQ = -pQ[0]/pQ[1]
sage: tP,tQ # we can see they are valuation 1
(3*a*5 + 5^2 + (a + 2)*5^3 + (4*a + 1)*5^4 + (a + 3)*5^5 + (a + 1)*5^6 + (2*a + 4)*5^7 + 3*5^8 + (2*a + 4)*5^9 + 2*5^10 + (3*a + 4)*5^11 + (2*a + 4)*5^12 + 3*a*5^13 + (3*a + 3)*5^14 + (2*a + 1)*5^15 + (a + 3)*5^16 + 3*a*5^17 + 3*5^18 + (a + 4)*5^19 + O(5^20),
 a*5 + (4*a + 2)*5^2 + a*5^4 + (2*a + 3)*5^5 + 4*a*5^6 + (a + 2)*5^7 + (3*a + 3)*5^8 + (2*a + 1)*5^9 + (2*a + 3)*5^10 + 5^11 + (4*a + 2)*5^12 + (2*a + 1)*5^13 + (2*a + 4)*5^14 + (a + 2)*5^15 + (a + 3)*5^16 + a*5^17 + 4*5^18 + 5^19 + O(5^20))
sage: Fq.formal_group().x()(tP) == pP[0] # check we made no mistake with the parameter
True
sage: Fq.formal_group().y()(tP) == pP[1]
True
sage: Fq.formal_group().x()(tQ) == pQ[0]
True
sage: Fq.formal_group().y()(tQ) == pQ[1]
True
sage: Fq.formal_group().log()(tP) # take log of 25P
3*a*5 + 5^2 + (a + 2)*5^3 + (a + 4)*5^4 + (4*a + 1)*5^5 + (2*a + 2)*5^6 + 2*5^7 + (3*a + 4)*5^8 + (2*a + 2)*5^9 + (3*a + 3)*5^10 + (4*a + 4)*5^11 + (4*a + 2)*5^12 + (2*a + 3)*5^13 + (4*a + 1)*5^14 + (2*a + 2)*5^15 + (4*a + 3)*5^16 + (4*a + 3)*5^17 + 3*5^19 + O(5^20)
sage: Fq.formal_group().log()(tQ) # and of 25 Q
a*5 + (4*a + 2)*5^2 + 5^4 + (4*a + 3)*5^5 + (3*a + 1)*5^6 + (a + 4)*5^7 + (4*a + 1)*5^9 + (4*a + 4)*5^10 + a*5^11 + (a + 4)*5^12 + (2*a + 2)*5^13 + 4*5^14 + (2*a + 4)*5^15 + 4*a*5^16 + (2*a + 4)*5^17 + (4*a + 2)*5^19 + O(5^20)

Now divide the logs to find the multiplier in the additive group

sage: Fq.formal_group().log()(tQ)/Fq.formal_group().log()(tP)
2 + 5 + 5^2 + (a + 1)*5^3 + (2*a + 1)*5^4 + (3*a + 4)*5^5 + 5^6 + (4*a + 2)*5^7 + (3*a + 1)*5^8 + (2*a + 1)*5^9 + (a + 2)*5^10 + (4*a + 3)*5^11 + (a + 3)*5^12 + 2*a*5^13 + 3*a*5^15 + 3*5^16 + (2*a + 1)*5^18 + O(5^19)

So we have recovered the secret key 7 it seems by reducing this mod $25$ (the first two coefficients), I checked this example with 8 also and succeeded.

I think I have convinced myself at least that this works, but Lubin is of course the expert on these things, so I would appreciate any remarks/criticism on the above if it is incorrect. Or maybe I just didn't make it clear what I was thinking of originally?

I have no idea how efficient this is in practice!