Elliptic Curves with trace t = 1 [Practice]

So here comes the practical aspect of the previous post about elliptic curves with trace $1$.

I use SAGE for practical demonstration. You can use the online notebook functionality of it, e.g., under sagenb.org or nt.sagenb.org.

I use the curve $y^2 = x^3 + x + 4$, which has $19$ points over $\mathbb{F}_{19}$ and hence has trace equal to one.

--- Input
p = 19;
K = GF(19);
E = EllipticCurve(K,[1,4]); #y^2 = x^3 + x + 4
print "E is: ",E;
print "#E[K] = ",E.count_points();  
--- Output
E is:  Elliptic Curve defined by y^2 = x^3 + x + 4 over Finite Field of size 19
#E[GF(19)] =  19

 Lets create a discrete logarithm instance. Since the point $P =(1,5)$ is on the curve, we compute $[n]P = Q$ for some secrete integer $n$.

--- Input
n = 11; # our secret
P = E.point([1,5,1]); # P in projective coordinates
Q = n*P;
print "[n]P = Q = ",n*P;
 --- Output
[n]P = Q =  (8 : 7 : 1)

Now we lift these two points $P=(1,5)$ and $Q=(8,7)$ from $E[\mathbb{F}_{19}]$ to $E[\mathbb{Q}_{19}]$. W.l.o.g. we fix the $x$-coordinate and use Hensel-lifting to determine the correct $y$-coordinate.

Note that Hensel Lemma (Hensel-lifting) is:

Lemma [Hensel-lifting] Let $f$ be a integer polynomial with $f(r) \equiv 0\pmod{p^l}$ and $f'(r) \not\equiv 0\pmod{p^l}$, then for the integer $$t \equiv - \frac{f(r)}{p^lf'(r)} \pmod{p}$$it holds that for the integer $s = r + tp$ it is $f(s) \equiv 0\pmod{p^{l+1}}$.

In our case this means, that we have for the point $P$ the polynomial $f(y) = 1^3 + 1 + 4 - y^2$ and it is $f(5) \equiv 0 \pmod{p}$. Since $f'(y) = -2y$, we have $$t \equiv -\frac{f(5)}{19f'(y)} = -\frac{6-5^2}{19(-2\cdot 5)} \equiv -\frac{1}{10} \equiv 17 \pmod{19}$$ hence $s = 5 + 17\cdot 19 = 328$ and indeed $328^2 \equiv 1^3 + 1 + 4\pmod{19^2}$. The lift to $p^3$ is analogeous.  Doing this and the lifting for $Q$ in SAGE is:

--- Input
K   = pAdicField(p,2); # p-adic Field with cap = 2
EQp = EllipticCurve(K,[1,4]); #y^2 = x^3 + x + 4
print "EQp is: ",EQp;
Plift = EQp.lift_x(Integer(P[0]); # lift the point P
print "Plift = ",Plift;
--- Output
EpZ is:  Elliptic Curve defined by y^2 = x^3 + (1+O(19^2))*x + (4+O(19^2)) over 19-adic Field with capped relative precision 2
Plift =  (1 + O(19^2) : 5 + 17*19 + O(19^2) : 1 + O(19^2))

As you can see, the $y$ coordinate of the lifted point $P$ is indeed $5+17\cdot 19$ as calculated above. The $O(19^2)$ is due to the cap of $2$-$p$-adic precision. Now we lift $Q$ as well

--- Input
Plift = EQp.lift_x(Integer(Q[0]); # lift the point  
print "Plift = ",Plift;
--- Output
Qlift =  (8 + O(19^2) : 7 + 14*19 + O(19^2) : 1 + O(19^2))

Next, we compute $[p]P_{\text{lift}}$ and $[p]Q_{\text{lift}}$ on $E[\mathbb{Q}_p]$. As written in the theory post, this must have coordinates $x$ and $y$ with $v_p(x) = -2$ and $v_p(y) = -3$. And indeed it is:

--- Input
pPlift = p*Plift;
print "pPlift = ",pPlift;
pQlift = p*Qlift;
print "pQlift = ",pQlift; 
--- Output
pPlift =  (17*19^-2 + O(19^-1) : 7*19^-3 + O(19^-2) : 1 + O(19^2))
pQlift =  (16*19^-2 + O(19^-1) : 7*19^-3 + O(19^-2) : 1 + O(19^2))

These two points $P_{\text{lift}}$ and $Q_{\text{lift}}$ are from $E_1$, since they reduce to $\mathcal{O}$ modulo $19$.

Next, we bring these two points to $E[p\mathbb{Z}_p]$ via $z = -x/y$. Hence:

--- Input
z1 = (-pPlift[0])/(pPlift[1]);
z2 = (-pQlift[0])/(pQlift[1]);
 --- Output
z1 =  3*19 + O(19^2)
z2 =  14*19 + O(19^2)

Now we can execute the $\log_F$ function (which actually leaves $z_1$ and $z_2$ unchanged here) and $\log_F(z_2)/\log_F(z_1) = n$:

--- Input
FG = EQp.formal_group();
Flog = FG.log(2);
print "Flog = ",Flog;
print "Flog(z1) = ",Flog(z1);
print "Flog(z2) = ",Flog(z2);
print "n = ",Flog(z2)/Flog(z1);
 --- Output
Flog =  (1 + O(19^2))*t + O(t^2)
Flog(z1) =  3*19 + O(19^2)
Flog(z2) =  14*19 + O(19^2)
n =  11 + O(19)

And so we compute the discrete logarithm value $n = 11$.