Adding two points on a elliptic curve over $\operatorname{GF}(16)$ constructed using $p(x) = x^4+x+1$

Question

E is the elliptic curve over P(GF($16$)) satisfying
$$y^2 + xy = x^3+β^4x^2+1$$. $$\text{Let} \quad β= x\pmod {p(x)}.$$

I know that $(β^5,β^3)$ is a point on the curve. I want to find $13(β^5,β^3)$.
I am using the minimal addition chain for $13 (1,2,4,8,9,13)$ to find this.
But how do I add $(β^5,β^3)$ to itself to find $2(β^5,β^3)$?
I do not understand how to add two points on elliptic curve.

Answer 1

OK, let us do the computations explicitly, this is often a question when starting to use elliptic curves, without having the whole algebraic geometry needed for it in the blood.

I will use sage to illustrate and confirm the computations.

First of all, let us introduce the elliptic curve in sage.

R.<X> = PolynomialRing(GF(2))
F.<b> = GF(2^4, modulus=X^4+X+1)
E = EllipticCurve(F, [1, b^4, 0, 0, 1])
print(E)

The print explains E:

Elliptic Curve defined by y^2 + x*y = x^3 + (b+1)*x^2 + 1
    over Finite Field in b of size 2^4

---

Now let us consider the given point $P$, and ask for its multiples. It is not fair in an exam, but let us have them first, then we recover the values with bare hands. The sage interpreter gives:

sage: P = E.point( (b^5, b^3) )
sage: # this was also checking that P is a point on the curve
sage: for k in range(P.order()):
....:     print(f"{k:>2}P = {k*P}")
....: 
 0P = (0 : 1 : 0)
 1P = (b^2 + b : b^3 : 1)
 2P = (1 : b^3 + b^2 + 1 : 1)
 3P = (b^2 + b + 1 : b : 1)
 4P = (0 : 1 : 1)
 5P = (b^2 + b + 1 : b^2 + 1 : 1)
 6P = (1 : b^3 + b^2 : 1)
 7P = (b^2 + b : b^3 + b^2 + b : 1)
sage: P.order()
8

So $P$ is a point of order $8$, and thus $13P=5P$ with the above value.

---

Let us compute $2P$ explicitly. For this, consider the "line through $P$ and $P$", i.e. the tangent to the elliptic curve $E$ in $P$ in the ambient affine space parametrized with unknowns $x,y$. Formally: $$ \begin{aligned} &\text{Curve:} & 0 &=y^2 + xy + x^3 + b^4x^2 + 1 \ ,\\ &\text{Formal differential:} & 0 &= 0 + y\; dx+ x\; dy + x^2\; dx + 0 + 0 \ ,\\ &\text{Taken in $P=(x_0,y_0)=(b^5,b^3)$:} & 0 &= y_0(x-x_0)+x_0(y-y_0)+x_0^2(x-x_0) \ ,\\ &\text{Separate $(y-y_0)$ and $(x-x_0)$:} && (y_0+x_0^2)(x-x_0) = x_0(y-y_0) \ ,\\ &\text{So the slope in $(x_0,y_0)$ is:} & m &=\frac{y-y_0}{x-x_0} =\frac{y_0+x_0^2}{x_0}=\frac{y_0}{x_0}+x_0 \ ,\\ &\text{So using $(b^5,b^3)$ explicitly:} & m&=\frac{b^3}{b^5}+ b^5=\frac 1{b^2}+b^5=(b^3+b^2+1)+b^2+b\\&&&=b^3+b+1 \ . \end{aligned} $$ We have used $2=0$ in $F$. (So $3=1$, $-1=1$, et caetera.)

Now we "draw" the line with equation $(y-y_0)=m(x-x_0)$ in the ambient space, and intersect it with the elliptic curve. The theorem of Bezout predicts $3$ solutions for the system $$ \begin{aligned} 0 &=y^2 + xy + x^3 + b^4x^2 + 1 \ ,\\ y &= b^3 +m(x-b^5)\ , \end{aligned} $$ and we already know "two" of them (with multiplicity), corresponding to the double point $P$ in the intersection. The elimination of $y$ gives (note that in characteristic two squaring is simpler, $(A\pm B)^2=A^2+B^2$,) $$ 0 = b^6 + m^2(x^2+b^{10}) + xb^3 + mx(x+b^5) + x^3 + b^4x^2 + 1 \ . $$ From this equation we need only the part in $x^3$ and $x^2$, $$ x^3 + x^2(m^2+m+b^4) +\dots =0\ , $$ since Vieta gives the third point $x'$ of intersection, the point which satisfies $$ x'+x_0+x_0 =-(m^2+m+b^4)\ . $$ So $$x'=m^2+m+b^4=1\ .$$ The corresponding $y'$ is $$ y'=b^3+m(x'-b^5)=b^3 +(b^3+b+1)(1+b^5)=b^3+b^2\ . $$ To obtain $2P$, we have to compute the opposite of the obtained point $Q=(x',y')=(1,b^3+b^2)$. This point is $Q'=\ominus Q=\ominus(x', y')=(1,b^3+b^2+1)$, the only other point with the same $x=x'$ component. This confirms the sage computation for $2P$.

---

Similarly, one computes $4P=2(2P)$, $8P=2(4P)$, and so on. To get $4P$ start with the point $(x_0,y_0)=(1, b^3+b^2+1)=(1,b^{13})$, the slope in this point is $$ m = \frac{y_0}{x_0}+x_0=(b^3+b^2+1)+1=b^3+b^2\ , $$ we build again the same system of two equations, Bezout tells there are three solutions, we eliminate $y$ again, the solution $x$ is a solution for $$ x^3 + x^2(m^2+m+b^4)+\dots = 0\ , $$ so this solution is $$ x'' = m^2+m+b^2=0\ . $$ The corresponding $y$-value is $y''=y_0+m(x''-x_0)=(b^3+b^2+1)+(b^3+b^2)(0-1)=1$. So $4P=\ominus(0,1)=(0,1)$. Here, $\ominus(0,1)$ is the only "other point" with the same $x$-component, zero, where "other" means also considering the multiplicity. Indeed, setting $x=0$ in the equation of the curve we get $y^2=1$, i.e. $(y-1)^2=0$.

---

Since $4P$ already lives over $\Bbb F_2$, it is simple to compute $8P$. We start with $(x_0,y_0)=(0,1)$, corresponding to $4P$, while building the tangent in this point we obtain the line $x=0$. Two points of intersection of this line with the curve are known, $4P$ and $4P$, the third point is the infinity point, since the system with the two equations $$ \begin{aligned} 0 &=y^2 + xy + x^3 + b^4x^2 + 1 \ ,\\ 0 &= x\ , \end{aligned} $$ has no further solution in the affine $(x,y)$-plane.

---

We obtain $9P=8P+P=O+P=P$, and need to compute $13P=9P+4P=P+4P$. I will stop here....

(Once understood, the computation principle is simple. There is no reason to do this effort with bare hands in the present era, one should rather put the accent as a human on the structure.)

Answer 2

You can avoid adding points by making use of some coincidences.

If you replace $y$ by $y+\gamma x$, then the equation remains the same, except that $\beta^4$ is replaced by $\beta^4+\gamma+\gamma^2$. Since the trace of $\beta$ and hence of $\beta^4$ is zero, the equation $T^2+T=\beta^4$ has solutions in ${\bf F}_{16}$. Indeed, dividing the equation $\beta^4=\beta+1$ by $\beta^2$ and squaring gives $\beta^4 = 1/\beta^2 +1/\beta^4$.

Applying the change of variable $y\leftarrow y+x/\beta^2$, the curve becomes $y^2+xy=x^3+1$ and the point becomes $P=(\beta^5,0)$. So the curve is defined over ${\bf F}_2$! It is easy to see that it has $4$ points over ${\bf F}_2$, so that the Frobenius endomorphism $\phi$ of the curve 'is' $(-1+\sqrt{-7})/2$.

Since the $x$=coordinate $\beta^5=\beta\cdot\beta^4$ is a norm to the subfield ${\bf F}_4$, our point $P$ is defined over ${\bf F}_4$. Computing the trace of $\phi^2$, we find that the curve has $8$ points over ${\bf F}_4$. Since we are in characteristic $2$, the group $G$ of points over ${\bf F}_4$ is cyclic. Therefore $\phi$ acts on $G$ via multiplication by an element in $a\in ({\bf Z}/8{\bf Z})^*$. Since $\phi$ fixes the four ${\bf F}_2$-points, we have $a=5$.

Since $P$ is in $G$, we have $13P=5P=\phi(P)=(\beta^{10},0)$. Transforming this back into the original coordinates, we get $(\beta^{10},\beta^8)$. Since $\beta^8=\beta^2+1$, this is easily seen to be equal to be the point $(\beta^2+\beta+1,\beta^2+1)$, in agreement with the computation by dan_fulea