Transforming Elliptic Curve to Hessian Form

Question

In the The Hessian Form of an Elliptic Curve, (NP Smart - ‎2001), they began with the elliptic curve

$$E': y^2 +xy = x^3 + x^2 + b$$ defined over the $\operatorname{GF}(2^{192})$ with the polynomial basis in $t$ over $\operatorname{GF}(2)$, where $$t^{191} + t^9 + 1 = 0.$$ with

$$b = \texttt{0x4DE3965E00F2A1C6C9750156A6FEFBE5EEF780BF3EF20E48}$$

The curve group order

$$ 6 \cdot q = 3138550867693340381917894711648254768837315541933943803842$$ with prime $q$. A point of order 3 on $E'$ is given by the point $(x_3,y_3)$;

$$x_3 = \texttt{0x4763CFBC4340674B749E57887850E92C9B6BEDF58EEDC3BF}$$ $$y_3 = \texttt{0x14A96A1E53DCC3E73CFB22B80E8658CE0D6D8E82ED2AEC7D}$$

Then proposed a change of variable

$$ X = x + x_3 \quad Y =y+sx+x^2$$ where $$s = \frac{x_3^2+y_3}{x_3},$$

then the elliptic form is obtained.

$$E:Y^2 + XY + x_3 Y = X^3$$

Then using the above the Hessian Form is obtained;

$$ x^3 + y^3 + z^3 = Dxyz$$ where

$$D = \texttt{ 0x16A4C7C2030FAD1380ABF8C2D47DC3E0C20AF62F6EDD06A7}$$

1. How does one find a point with order 3?
2. What is the intuition behind the change of variables?
3. How the Hessian form is obtained in the last step?

Answer 1

Since the situation in the OP is related to a special example, i will use this example to illustrate the steps. Computations are done in sage. Some ingredients in the OP differ from the one in the reference [Smart N.P., The Hessian form of an Elliptic Curve], these are marked in red. (Colors are also used to mark matching pieces in longer computations.) All computational details are given, if the computer support feels annoying for a community reader, please skip it, the remained part is still giving the frame of the structure.

We consider the field $$ F=\Bbb F_q=\Bbb F_2[T]/(T^{\color{red}{191}}+T^9+1) $$ with $q=2^{191}$ elements (migrated letter for the usual reason). Let $t$ be $T$ modulo the quotient ideal.

We associate the curve $E'$, given by the affine equation: $$ E': \ y^2 +xy = x^3 + x^2 + b\ . $$ The order of the curve is $6N$, with a big prime $N$. Let us initialize the curve in sage, and check the order.

R.<T> = PolynomialRing(GF(2))
F.<t> = GF(2^191, modulus=T^191 + T^9 + 1)

b = F.fetch_int(0x4DE3965E00F2A1C6C9750156A6FEFBE5EEF780BF3EF20E48)
x3 = F.fetch_int(0x4763CFBC4340674B749E57887850E92C9B6BEDF58EEDC3BF)
y3 = F.fetch_int(0x14A96A1E53DCC3E73CFB22B80E8658CE0D6D8E82ED2AEC7D)

E = EllipticCurve(F, [1, 1, 0, 0, b])
N = ZZ(3138550867693340381917894711648254768837315541933943803842 / 6)

Q = E( (x3, y3) )    # this is the given point. Is it a 3-torsion point?
print("For the given point Q do we have 3.Q = O? {}\n"
      .format(3*Q == E(0)))

# we check that multiplication with 6N maps a random point P to O.
P = E.random_point()
print("For some random point P, do we have 6N.P = O? {}\n"
      .format(6*N*P == E(0)))

We obtain so far:

For the given point Q do we have 3.Q = O? False

For some random point P, do we have 6N.P = O? True

---

So $Q$ is not a $3$-torsion point, it is rather a point of (prime) order $N$, useful for the usual cryptographic reasons.

sage: N*Q
(0 : 1 : 0)
sage: N * Q == E(0)
True

We will forget this point $Q$ in the following, thus also using the notations / the variables x3 and y3 for other purposes.

---

In order to construct a $3$-torsion point, we consider the $3$-torsion (or division) polynomial, which is $$ x^4+x^3+b\ . $$ Formally one can see this as follows. Let $(x{_0},y{_0})$ be a point on the curve. The formal differential of the given curve equation, computed in this point, is $2y_0\; dy+x_0\; dy+y_0\; dx+3x_0^2\; dx+2x_0^2\; dx=0$, i.e. $(x_0^2+y_0)\; dx +x_0\; dy=0$. We formally replace $dx$, $dy$ by $(x-x_0)$, $(y-y_0)$ getting the tangent/line equation $(x_0^2+y_0)(x-x_0)+x_0(y-y_0)=0$. Its slope is a function $s$ of/in $(x_0,y_0)$, formally obtained as $$s=s(x_0,y_0)=\frac1{x_0}(x_0^2+y_0)\ .$$ Now we would like to obtain an equation for the first component in the identity $-2T_3=T_3$ of a $3$-torsion point $T_3$. It is $s^2+s+1=x$. This leads to $x^4+x^3+b=0$.

---

Code computing this polynomial and using it:

pol = E.division_polynomial(3)
# or pol = E.torsion_polynomial(3)

roots = pol.roots(ring=F, multiplicities=False) 
print(f"The given polynomial has {len(roots)} roots over F")

# and we try to lift the roots one by one
three_torsion_points = []

print("\n...lifting found roots...")
for r in roots:
    try:
        U = E.lift_x(r)
        three_torsion_points.extend([U, -U])
        print(f"... OK: LIFTED ROOT {hex(r.integer_representation())}")

    except:
        print(f"... could *NOT* lift the root {hex(r.integer_representation())}")

print()
for U in three_torsion_points:
    Ux, Uy = U.xy()
    hexu = hex(Ux.integer_representation())
    hexv = hex(Uy.integer_representation())
    print(f"Computed 3-torsion point with components:\nx3 = {hexu}\ny3 = {hexv}")

This gives:

The given polynomial has 2 roots over F
...lifting found roots...
... OK: LIFTED ROOT 0x665dde483ee9b618357325c85666c1f9241d19d45e76d8e3
... could *NOT* lift the root 0x66b8ff1e96ee97559108d9e34fd7c48a372313924b5e81ea

Computed 3-torsion point (u, v) with:
u = 0x665dde483ee9b618357325c85666c1f9241d19d45e76d8e3
v = 0x38a4365e3388fc1094ba6755e471788805c9961f52054d79
Computed 3-torsion point (u, v) with:
u = 0x665dde483ee9b618357325c85666c1f9241d19d45e76d8e3
v = 0x5ef9e8160d614a08a1c9429db217b97121d48fcb0c73959a

To find all points of order three, we asked for the corresponding division polynomial, then for its roots in $F$, which correspond to the $x$-components of the $3$-torsion points. Then we tried to lift. Lifting needs the existence of a square root for the remained equation in $y$ (from $E'$), after plugging in the found $x$ value. We could lift one root of the $3$-torsion polynomial.

So the given point $Q$ is not a $3$-torsion point. But we have a good one. (There are two points sharing the same $x$-component, denoted above by u.)

Let us check that pol is in fact $x^4+x^3+b$:

sage: S = pol.parent()
sage: x, = S.gens()
sage: pol == x^4 + x^3 + b
True

This concludes (1).

---

Let $T_3(x_3,y_3)$ be the first $3$-torsion point from above. (The other one is $-T_3$.)

The second question. We are using a transformation of coordinates, which maps $T_3$ to the point $(0,0)$ of an other elliptic curve with equation in $X,Y$, obtained by passing from $(x,y)$ to $(X,Y)$ via $$ \begin{aligned} &\left\{ \begin{aligned} x &= X-x_3=X+x_3\ ,\\ y &= Y-sx-x^2_{\color{red}3}=Y+sx+x^2_{\color{red}3}\ , \end{aligned} \right. \\ &\qquad \qquad \text{ with }t=\frac{y_3}{x_3}\ ,\ s=x_3+t=x_3+\frac{y_3}{x_3} \\ &\left\{ \begin{aligned} X &= x+x_3\ ,\\ Y &=y+sx+x^2_{\color{red}3}\ , \end{aligned} \right. \\ &\qquad \qquad \text{ so that }T_3(x_3,y_3) \\ &\qquad \qquad \text{ goes to } (X_3,Y_3)=(x_3+x_3,y_3+sx_3+x_3^2)=(0,0)\ . \end{aligned} $$ We plug in $(x,y)$ from above in the equation $y^2 +xy = x^3 + x^2 + b$ of the given curve $E'$ and obtain (recalling that in our case $2=0$, so that for instance squaring is compatible with addition) an equation in $(X,Y)$: $$ \begin{aligned} y^2 &= (Y-sx-x^2_3)^2=(Y+sx+x^2_3)^2=Y^2+s^2x^2+x^4_3\\ &=Y^2+(x_3^2+t^2)(X^2+x_3^2) + x_3^4\ ,\\ &=Y^2+x_3^2X^2+t^2X^2+y_3^2\ ,\\ &=Y^2+s^2X^2+y_3^2\ , \\[2mm] xy &=(X+x_3)(Y+s(X+x_3)+x^2_3)\\ &=XY+x_3Y + (x_3+t)(X^2+x_3^2)+x_3^2X +x_3^3\ ,\\ &=XY+x_3Y + x_3X^2+tX^2+x_3^3+x_3y_3 +x_3^2X +x_3^3\\ &=XY+x_3Y + x_3X^2+tX^2+x_3y_3 +x_3^2X \ , \\[2mm] x^3+x^2+b &=(X^3+x_3X^2+x_3^2X+x_3^3)+(X^2+x_3^2)+b\ ,\\[2mm] &\text{ which implies}\\[2mm] 0 &=(y^2+xy)\pm(x^3+x^2+b)\\ &=Y^2 + \color{red}{s^2X^2} +\color{blue}{y_3^2}\\ &\qquad + XY + x_3Y + \color{red}{sX^2} + \color{blue}{x_3y_3} +x_3^2X \\ &\qquad\qquad + (X^3 + \color{red}{x_3X^2} + x_3^2X + \color{blue}{x_3^3}) + (\color{red}{X^2} + \color{blue}{x_3^2})+\color{blue}{b} \\ &=Y^2 + XY + x_3Y+X^3\\ &\qquad+ \color{red}{\underbrace{(s^2+s+x_3+1)}_{=0}}X^2 + \color{blue}{0} \\ &=Y^2 + XY + x_3Y+X^3\ . \end{aligned} $$ Note that the red term $s^2+s+x_3+1$ vanishes, since $x_3$ is a root of the $3$--torsion polynomial $x^4+x^3+b$: $$ \begin{aligned} x_3^2(s^2+s+x_3+1) &=x_3^2\left( x_3^2+\frac{y_3^2}{x_3^2} + x_3+\frac{y_3}{x_3} + x_3+1 \right) \\ &=x_3^4+\color{blue}{y_3^2+x_3y_3}+x_3^2\\ &=x_3^4+\color{blue}{x_3^3+x_3^2+b}+x_3^2\\ &=x_3^4+\color{blue}{x_3^3+b}\\ &=0\ . \end{aligned} $$ The sage code checking this vanishing is:

for U in three_torsion_points:
    x3, y3 = U.xy()
    s = x3 + y3/x3
    if s^2 + s + x3 + 1 != 0:
        continue
    hexu = hex(x3.integer_representation())
    hexv = hex(y3.integer_representation())
    print(f"ss + s + x3 + 1 = 0 for the values:\nx3 = {hexu}\ny3 = {hexv}")

It gives:

ss + s + x3 + 1 = 0 for the values:
x3 = 0x665dde483ee9b618357325c85666c1f9241d19d45e76d8e3
y3 = 0x38a4365e3388fc1094ba6755e471788805c9961f52054d79
ss + s + x3 + 1 = 0 for the values:
x3 = 0x665dde483ee9b618357325c85666c1f9241d19d45e76d8e3
y3 = 0x5ef9e8160d614a08a1c9429db217b97121d48fcb0c73959a

Note that the procedure of moving the torsion point $T_3(x_3,y_3)$ to the point $(0,0)$ of an other elliptic curve in long Weierstraß form in $X,Y$, while also moving the tangent in $(0,0)$ to $Y=0$ is a standard procedure. See e.g.

https://en.wikipedia.org/wiki/Hessian_form_of_an_elliptic_curve#Definition

in the proposition [ Conversely... ].
This answers the second question (structurally and programmatically).

---

To obtain the hessian form from the equation: $$ E''\ :\ Y^2 + XY + x_3Y = X^3\ , $$ we proceed as in loc. cit., page 120, [§3. The Hessian Form of an Elliptic Curve]. The values for $a_1$, $a_3$ are in our case explicitly $1$ and $x_3$, so for instance $\Delta =x_3^3(1-27x_3)=x_3^3(1+x_3)=b$, and $\delta = 1+x_3$. We compute a root of the polynomial in $T$ $$ T^3-\delta T^2+\frac 13 \delta^2T+x_3\delta^2 $$ and build $$ D=3\frac{\mu-\delta}\mu =1+\frac{\delta}\mu \ . $$ The hex value for this number is...

PF.<T> = PolynomialRing(F)
delta = x3 + 1
mu = (T^3 - delta*T^2 + delta^2*T + x3*delta^2).roots(multiplicities=False)[0]
D = 1 + delta/mu
print(f"D is {hex(D.integer_representation())}")

which gives:

D is 0x16a4c7c2030fad1380abf8c2d47dc3e0c20af62f6edd06a7

which is the same value as in loc. cit..