1
$\begingroup$

$E$ - elliptic curve on field $F_{2^4}$ with equetion $y^2 + y = x^3$.
I need to show, that for any $P \in E$, $3P = 0$.

Here is list of 16 field elements:
$0,1,t,t+1,$
$t^2,t^2+1,t^2+t,t^2+t+1,$
$t^3,t^3+1,t^3+t,t^3+t+1,t^3+t^2,t^3+t^2+1,t^3+t^2+t,t^3+t^2+t+1$

Let's define multiplication in the field as $a*b=c,$ where c is a remainder of division of $a*b$ by $t^4+t+1$
Now, we can clculate all elements of the field in cube:
$(0)^3 = 0$
$(1)^3 = 1$
$(t)^3 = t^3$
$(t+1)^3 = t^3+t^2+t+1$
$(t^2)^3 = t^3+t^2$
$(t^2+1)^3 = t^3+t$
$(t^2+t)^3 = 1$
$(t^2+t+1)^3 = 1$
$(t^3)^3 = t^3+t^2$
$(t^3+1)^3 = t^3+t^2+t+1$
$(t^3+t)^3 = t^3+t^2+t+1$
$(t^3+t+1)^3 = t^3+t^2$
$(t^3+t^2)^3 = t^3$
$(t^3+t^2+1)^3 = t^3+t$
$(t^3+t^2+t)^3 = t^3$
$(t^3+t^2+t+1)^3 = t^3+t^2$

We also can look at the curve equation like this: $y^2+y=y*(y+1)=x^3$.Thus, we can take any element from field, add $1$, multiply this two polynomials and check wheter it equals to any cube element or not.
$y=0 \Rightarrow 0*1=0$
$y=1 \Rightarrow 1*0=0$
$y=t \Rightarrow t*(t+1)=t^2+t$
$y=t+1 \Rightarrow (t+1)*t=t^2+t$
$y=t^2 \Rightarrow t^2*(t^2+1)=t^2+t+1$
$y=t^2+1 \Rightarrow (t^2+1)*t^2=t^2+t+1$
$y=t^2+t \Rightarrow (t^2+t)*(t^2+t+1)=1$
$y=t^2+t+1 \Rightarrow (t^2+t+1)*(t^2+t)=1$
$y=t^3 \Rightarrow t^3*(t^3+1)=t^2$
$y=t^3+1 \Rightarrow (t^3+1)*t^3=t^2$
$y=t^3+t \Rightarrow (t^3+t)*(t^3+t+1)=t$
$y=t^3+t+1 \Rightarrow (t^3+t+1)*(t^3+t)=t$
$y=t^3+t^2 \Rightarrow (t^3+t^2)*(t^3+t^2+1)=t+1$
$y=t^3+t^2+1 \Rightarrow (t^3+t^2+1)*(t^3+t^2)=t+1$
$y=t^3+t^2+t \Rightarrow (t^3+t^2+t)*(t^3+t^2+t+1)=t^2+1$
$y=t^3+t^2+t+1 \Rightarrow (t^3+t^2+t+1)*(t^3+t^2+t)=t^2+1$
That's how I found points from curve:
$(0,0),$
$(0,1),$
$(1,t^2+t),$
$(1,t^2+t+1)$
$(t^2+t,t^2+t),$
$(t^2+t,t^2+t+1)$
$(t^2+t+1,t^2+t),$
$(t^2+t+1,t^2+t+1)$

Now, I'm tpying to calculate $3P$ using formulas:
$P(x_1,y_1) + Q(x_2,y_2) = R(x_3,y_3)$
if $(x_1 = x_2)$
$x_3 = \left(\frac{x_1^2+y_1}{x_1}\right)^2 + \left(\frac{x_1^2+y_1}{x_1}\right)$
$y_3=(\left(\frac{x_1^2+y_1}{x_1}\right)+1)*x_3 + x_1^2$
if $(x_1 \ne x_2)$
$x_3 = \left(\frac{y_1+y_2}{x_1+x_2}\right)^2 + \left(\frac{y_1+y_2}{x_1+x_2}\right)+x_1+x_2$
$y_3=(\left(\frac{y_1+y_2}{x_1+x_2}\right)+1)*x_3 + \left(\frac{y_1*x_2+y_2*x_1}{x_1+x_2}\right)$
I understand that $3P = P+P+P$. But when I put actual numbers in them, I have, for example for point $(0,0)$ $x_3=\left(\frac{0}{0}\right)^2$. What is that? 0?

$\endgroup$
  • $\begingroup$ Since $2=0$ in the field, $3/2$ is not defined. $\endgroup$ – Dietrich Burde Jun 2 '18 at 11:25
  • $\begingroup$ First list all the elements of the field and then all the points of the curve. Have you done that? $\endgroup$ – Somos Jun 2 '18 at 14:09
  • $\begingroup$ @Somos, I've found points of the curve, but I'm not sure what you mean by elements of the field. Could you give me some help with that? $\endgroup$ – Daria Jun 2 '18 at 16:37
  • $\begingroup$ That is your problem. You are thinking of $\,\mathbb{Z}_{16}\,$ (integers modulo 16) which is only a ring. Please read Finite field article for some idea of what a finite field is, particularly in characteristic $2$. $\endgroup$ – Somos Jun 2 '18 at 16:43
  • $\begingroup$ Also read the MSE question 2777107 Addition and Multiplication in $F_4$. $\endgroup$ – Somos Jun 2 '18 at 16:51
1
$\begingroup$

The doubling formula on this curve is particularly simple. Indeed, if $(\xi,\eta)$ is a point on the curve, then $[2](\xi,\eta)=(\xi^4,\eta^4+1)$.

Here’s why: Take your point $(\xi,\eta)=P$ on the curve, so that $\xi^3=\eta^2+\eta$. The derivative there, as @Somos has pointed out, is $\xi^2$, so that the line through $P$ with this slope is $Y=\xi^2X+?$, where you adjust “?” for the line to pass through $P$. You get the equation of the line to be $Y=\xi^2X+\eta^2$. Call the line $\ell$.

Now, what is the third intersection of $\ell$ with our curve, beyond the double intersection at $P$? Substitute $Y=\xi^2X+\eta^2$ into $Y^2+Y=X^3$ to get a cubic in $X$ with a double root at $\xi$ and one other: $$ (\xi^2X+\eta^2)^2+\xi^2X+\eta^2+X^3=(X+\xi)^2(X+\xi^4)\,, $$ as you can check. Thus the other intersection of $\ell$ with our curve is $(\xi^4,\xi^6+\eta^2)=(\xi^4,\eta^4)=[-2](\xi,\eta)$. Now, in all cases, for a point $(a,b)$ on our curve, its negative is $(a,b+1)$: the other intersection of the curve with the vertical line through $(a,b)$.

Since $[-2](\xi,\eta)=(\xi^4,\eta^4)$, we have $[2](\xi,\eta)=(\xi^4,\eta^4+1)$.

Now, I say that for every point $(\xi,\eta)$ with coordinates in the field with four elements, we get $[3](\xi,\eta)=\Bbb O$, the neutral point at infinity, the one with projective coordinates $(0,1,0)$. That is, every one of the nine points with coordinates in $\Bbb F_4$ is a three-torsion point. Indeed, for $\xi,\eta\in\Bbb F_4$, $\xi^4=\xi$ and $\eta^4=\eta$. Thus for an $\Bbb F_4$-rational point $(\xi,\eta)$ on our curve, we have $[2](\xi,\eta)=(\xi,\eta+1)=[-1](\xi,\eta)$. Adding $(\xi,\eta)$ to both sides of this equation, we get $[3](\xi,\eta)=\Bbb O$.

It only remains to enumerate the nine points of the curve with $\Bbb F_4$-coordinates. Calling the elements of the field $0,1,\omega,\omega^2$, where $\omega^2+\omega+1=0$, we see that the only points on the curve are $$ \Bbb O,(0,0),(0,1)(1,\omega),(1,\omega^2),(\omega,\omega),(\omega,\omega^2),(\omega^2,\omega),(\omega^2,\omega^2)\,. $$ You can check that when you pass to the larger field $\Bbb F_{16}$, you don’t get any more points!

$\endgroup$
0
$\begingroup$

Okay, you have now almost all of the peices needed. There is one stumbling block. As the Wikipedia article Elliptic curve point multiplication states. For point doubling, you need to compute $\,\lambda = (3x_p^2+a)/(2y_p)\,$ but in characteristic $2$ you can't divide by two. We need a formula for point doubling that works for characteristic $2$. Our equation is $\, y^2 + y + x^3 = 0\,$ since $\, 1 = -1.\,$ Take the derivative WRT to $\,x\,$ to get $\, 2y\frac{dy}{dx} + \frac{dy}{dx} + 3x^2 = \frac{dy}{dx} + x^2 = 0.\,$ Thus, $\, m = x^2 \,$ is the slope of the tangent line at point $\,(x,y).\,$ Now suppose we have a point $\, P_0 = (x_0,y_0) \,$ on the curve. The equation of the line tangent at $\, P \,$ is $\, y = x_0^2(x + x_0) + y_0 . \,$ The other point of intersection $\, -2P_0 \,$ is a solution of $\, y^2 + y + x^3 = 0, \,$ thus $\, (x_0^2(x + x_0)+y_0)^2 + (x_0^2(x + x_0)+y_0) + x^3 = 0.\,$ In characteristic $2$, $\, (x+y)^2 = x + y, \,$ thus $\, x^2x_0^4 + x_0^6 + y_0^2 + x x_0^2 + x_0^3 + y_0 + x^3 = 0. \,$ Now $\, y_0^2 + y_0 + x_0^3 = 0, \,$ leaving $\, x^2x_0^4 + x_0^6 + x x_0^2 + x^3 = 0. \,$ But $\, x = x_0 \,$ is a double root and so the equation factors as $\, (x + x_0)^2(x + x_0^4) = 0. \,$ Now $\, x_1 := x_0^4 \,$ and $\, y1 := x_0^2(x_0^4 + x_0) + y_0 = y_0 \,$ give $\, P_1 = (x_1,y_1) = -2P_0. \,$ To prove that $\, P_1 = P_0 \,$ we need $\, x_0 = x_0^4 \,$ which has four roots, namely $\,0, 1\,$ and $\, t^2+t, t^2+t+1, \,$ two cube roots of unity.

The point at infinity $\,P=\mathcal{O}\,$ is the identity for point addition, thus $\,P\!+\!P = P\!+P\!+\!P \!=\! P.\,$

$\endgroup$
  • $\begingroup$ I didn't really get why $(0,y)+(0,y)=(0,y+1)$ because according to formulas this sum equals $(0,y)$ $\endgroup$ – Daria Jun 6 '18 at 14:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.