Testing membership of elliptic curve points in subgroups of binary extension fields

Question

I come from an engineering background. Let a binary extension field $GF(2^{233})$ and a finite group $E$ made of points defined by a curve over Binary Fields i.e. $y^2 + xy = x^3 + x^2 + b$ with constructing polynomial $f(z)=z^{233}+z^{74}+1$ and let a subgroup $C \subset E$ only with elements that are created from doubling another point in $E$, i.e. $C(GF(2^m))=\{P+P:P \in E(GF(2^m)\}$.

Is there a way to test if a given element - point $a$ is a member of $C$ and what restrictions should apply on $E$ and $C$ for this test to be valid?

Thank you for your time,

Answer 1

Notations: The multiplication-by-two map $[2]$ is known algebraically, it is a map $$ [2]\ :\ E(F)\to E(F)\ , $$ mapping $P\in E(F)$ into the point $2P:=P+P\in E(F)$, where the addition $+$ is the structural addition on the elliptic curve w.r.t. the neutral infinity point $O$. Here, $F$ is the finite field with $2^{233}$ elements, constructed as $$ F = \Bbb F_2[X]\ \text{ modulo }\ \underbrace{z^{233}+z^{74}+1}_{f}\ , $$ and $E$ is the given elliptic curve over $F$ with affine equation $$ \tag{$E$} Y^2 + XY = X^3 + X^2 + b\ , $$ where $B$ is some a priori fixed parameter in $F$. The question regards

---

So let us get explicitly the formula for $2P$, starting from an affine point $P=(x,y)$, $P\ne O$. (For $O$ the situation is clear, $O=2O$ is in the image of $[2]$.) To compute the tangent in $(x,y)$ we write $X=x+\xi$, $Y=y+\eta$, and get the linear part in $\xi$ and $\eta$ after substitution in the affine $(X,Y)$-equation of the curve. So we get successively (formally): $$ \begin{aligned} Y^2 + XY &= X^3 + X^2 + b\ ,\\ (y+\eta)^2 + (x+\xi)(y+\eta) &= (x+\xi)^3 + (x+\xi)^2 + b\ ,\\ 2y\eta + x\eta+y\xi &= 3x^2\xi +2x\xi + O(\xi^2,\xi\eta,\eta^2)\ ,\\ x\eta+y\xi &= x^2\xi + O(\xi^2,\xi\eta,\eta^2)\ , \end{aligned} $$ (characteristic two case, so here and below $1=-1$ and $2=0$,) so the needed tangent has equation $ x\eta =(x^2-y)\xi $. Going back to $X,Y$ via $\xi = X-x$, $\eta=Y-y$, it is the affine line equation $$ \tag{$L$} Y=y+\frac 1x(x^2-y)(X-x)=mX+n\ ,\qquad m := \frac 1x(x^2-y) \ . $$ So we have to solve the system built from the two equations, $(E)$ and $(L)$.

Note: In case $x=0$, we cannot use $x$ as a denominator, so the tangent is $x(Y-y)=(x^2-y)(X-x)$, i.e. $0=(0-y)(X-0)$, i.e. the vertical line $X=0$, inserting this we get $Y^2=b=y^2$, i.e. $(Y-y)^2=0$, the affine point $P=(0,y)$ is a double solution, and the third intersection point is not an affine point, but the infinity point. Using this information, we see that $2P=P+P=O$, so $P=(0,y)$ is in $C$.

Consider the case $x\ne 0$. Then we substitute $Y$ from $(L)$ in $(E)$ getting, $$ (mX+n)^2 + X(mX+n) = X^3 +X^2+b\ , $$ and there are three solutions, the first two are known, $x$ and $x$, and the third one, $x'$ say, is wanted, so that their sum is (Vieta) obtained by isolating (minus) the coefficient of $X^2$: $$ \begin{aligned} x' &= x' + x + x = 1+m+m^2 \\ &= 1 + \frac 1x(x^2-y) + \frac 1{x^2}(x^2-y)^2 = 1 + \frac 1x(x^2+y) + \frac 1{x^2}(x^4+y^2) \\ &= 1 + x + \frac yx + x^2 +\frac {y^2}{x^2} = 1 + x + x^2 +\frac 1{x^2}(y^2+xy) \\ &= 1 + x + x^2 +\frac 1{x^2}(x^3 + x^2+b ) = 1 + x + x^2 + x + 1 +\frac bx \\ &=x^2 +\frac b{x^2} \ . \\[3mm] &\qquad\text{ For $y'$ we use the line equation, getting} \\[3mm] y' &= y+\frac 1x(x^2-y)(x'-x)\ . \end{aligned} $$ The point $2P$ is obtained from $(x',y')=-2P$ by intersecting $(E)$ with the "vertical line" $X=x'$ through $(x',y')$ and the infinity point $O$, getting the third intersection point $(x'',y'')$. Of course, $x''=x'$, and Vieta gives us for $y''$ the second solution with $Y^2+x'Y=\dots$ so $y'+y''=x'$.

---

We can, if we want so, get an explicit formula, but we do not need it in our case. We can now restate the problem: If a point $Q=(x'',y'')$ in $E(F)$ is given, does there exist a point $P=(x,y)$ with $2P=Q$ (i.e. equivalently $Q\in C$)?

This amounts to solving in the unknown $x$ first the equation $$ \begin{aligned} x' &= x^2 +\frac b{x^2}\ ,\qquad\text{i.e.}\\ 0 &=x^4 +x'\;x^2 +b\ , \end{aligned} $$ and if it has at least one solution in $F$, then $y',x'', y''$ are easily determined in a linear fashion. Solving involves to steps of getting the square roots in $F$, if both steps lead to at least one solution, then the starting point $Q$ is in $2C$.

---

---

Let us see this working in a special example.

The following sage code is giving an explicit example for the field $F=\Bbb F_2[u]=\Bbb F_2[U]/f(U)=\Bbb F_2[U]/(U^{233}+U^{74}+1)$. Here $u$ is the image of $U$ taken modulo $f(U)$.

We initialize some sample curve, taking $b=u^4 + u^2$. Then the point $Q=(u+1, u^2+1)$ is a point on the curve.

R.<U> = PolynomialRing(GF(2))
F.<u> = GF(2^233, modulus=U^233 + U^74 + 1)

b = u^4 + u^2
E = EllipticCurve(F, [1, 1, 0, 0, b])
Q = E.point( (u + 1, u^2 + 1, 1) )

So the question is if $Q$ is of the shape $2P$ for some $P=(x,y)$. We solve $$ x^4 + (u+1)x^2 + (u^4+u^2) = 0 $$ in $F$. Note that $(u+1)$ is a square in $F$, explicitly: $$ \underbrace{ (u^{228} + u^{191} + u^{154} + u^{117} + u^{69} + u^{32} + 1)}_{\text{Notation: }v}{}^2 =u+1\ . $$ So we deal with the equation $x^4+v^2\;x^2+ (uv)^2=0$. This is $$ (x^2+v\; x+ uv^2)^2=0\ , $$ and it turns out, that $x^2 +vx+uv^2$ it has two roots w.r.t. variable $x$ in $F$. To get them, we divide first by $v^2$, so the new (Artin-Schreier) equation is $$ W^2 + W + u=0\ ,\qquad W:=\frac xv\ . $$ It has a root $w$ in a quadratic extension of $F$, so $w^2+w=u$, and the question is if $w$ is already in $F$. This is indeed so, since $u$ has trace $0$ in $F$, leading to $$ \begin{aligned} 0 &=\operatorname{Trace}(u)\\ &=u + u^2 + u^4+ u^8+\dots+u^{2^{232}}\\ &=(w+w^2) + (w+w^2)^2 + (w+w^2)^4+ (w+w^2)^8+\dots+(w+w^2)^{2^{232}}\\ &=(w+w^2) + (w^2+w^4) + (w^4+w^8)+ (w^8+w^{16})+\dots+(w^{2^{232}}+w^{2^{233}})\\ &=w+w^{2^{233}}\ . \end{aligned} $$ So $w$ is fixed by the Frobenius of $F$, being thus in $F$. The trace-zero condition is necessary and sufficient in such cases.

The code computing the point $P$ with $2P=Q$ in this special case is then as follows:

v = sqrt(u + 1)
x = (U^2 + v*U + u*v^2).roots(ring=F, multiplicities=False)[0]
P = E.lift_x(x)
print(f'Is  2P = Q? {bool( 2*P == Q)}')
print(f'Is -2P = Q? {bool(-2*P == Q)}')

Results:

Is  2P = Q? False
Is -2P = Q? True

So one of the two lifts above is working.

Answer 2

Except for your mention of the “constructing polynomial” $f$, I’m pretty sure that I understand your question.

You consider an elliptic curve $E$ whose coefficients are in $\Bbb F_{2^m}$, the field with $2^m$ elements; I’ll just refer to this as $\Bbb F$, since you don’t seem to be changing $m$ throughout your question. And your elliptic curve has equation $Y^2+XY=X^3+X^2+b$, with $b\in\Bbb F$. (The parameter $b$ must be nonzero; otherwise you get a singularity at $(0,0)$, which would make your curve not elliptic.)

You are interested in the group of points $Q$ on $E$, and ask which are of form $P+_EP$, i.e. twice $P$ with respect to the addition on $E$. I’m sure you have seen that the addition on $E$ is by the chord-and-tangent process. That is, to get $P+_EQ=R$, you draw the line connecting $P$ and $Q$ (in $\Bbb F$-geometry, it’s understood) and see what is the third intersection of this line with $E$. This is not $R$, but rather $-_ER$, the inverse of $R$ with respect to the $E$-addition $+_E$. The fact to know is that $R$ and $-_ER$ lie on the same “vertical” line $X=c$. In case $P=Q$, you use the tangent to the curve at $P$ instead of a chord, and proceed.

I’ll use the (by now) standard notation $[n]_E(P)$ for what you get by adding $P$ to itself $n$ times. It’s $n\times P$ with respect to the $E$-addition.

Now, your curve, no matter what $b$ is, has the property that it’s “ordinary”: it has the maximum number of points $p$ with $[2]_E(Q)=\Bbb O$; that’s the neutral element (identity) of the group, and it’s not in the regular (affine) $\Bbb F$-plane, it’s at infinity vertically upwards in the projective plane, with (homogeneous) coordinates $(0:1:0)$. (The opposite of “ordinary” is “supersingular”, and supersingular curves have no points of order the characteristic ($2$ in our case) other than the identity. One such if $Y^2+Y=X^3$.)

Finally here’s the meat of what I can tell you: since the group of all points of $E(\Bbb F)$ is finite and abelian, and since the group $\{Q\in E(\Bbb F):[2]_E(Q)=\Bbb O\}$, that’s the kernel of $[2]$, has only the two elements $\Bbb O$ and $(0,\sqrt b\,)$ (that’s the unique element $\beta\in\Bbb F$ with $\beta^2=b$), the “cokernel” of $[2]$ also has order two, $\text{coker}([2])=E(\Bbb F)/\text{image}([2])$. The image of $[2]$ is just the set you’re worried about, the set of things writable as $[2]_E(P)$ for some element $P\in E(\Bbb F)$.

Discomplicating what I just wrote, this means that in all cases, exactly half of the points $Q\in E(\Bbb F)$ are of the form $[2](P)$, the points you’re interested in.

But now I have to disappoint you, because I’m not a specialist in this racket, and have no idea how you can tell that a given point $Q=(\xi,\eta)$ is in your good set. But let me give you an example.

In case $m=2$ and $b=1$, the points of $Y^2+XY=X^3+X^2+1$ are: $$ \Bbb O, (0,1),(1,\omega),(1,\omega^2),(\omega,1),(\omega,\omega^2),(\omega^2,1),(\omega^2,\omega)\,, $$ eight in all, and the first four make up the subgroup you’re interested in. Notation: $\omega$ is an element of $\Bbb F_4$ not in $\Bbb F_2$. For instance, $[2](\omega,1)=(1,\omega^2)$, if I haven’t slipped up in my pencil-work.