Group law on Elliptic Curves over $\mathbb F_5$

Question

I want to find the group table of the elliptic curve $\mathcal C : y^2 = x^3-x$, defined over $\mathbb F_5$.

I get the points on $\mathcal C$ to be the identity ${\bf o}$, together with $(0,0)$, $(1,0)$, $(2,1)$, $(2,4)$, $(3,2)$, $(3,3)$ and $(4,0)$.

To compose elements, say $(1,0)$ and $(2,1)$, I found the equation of the line through the two points and then looked for integer points on that line which, modulo five, also lie on $\mathcal C$. For example the line $y=x-1$ passes through $(1,0)$ and $(2,1)$, but also $(3,2)$. Reflecting in the $x$-axis and reducing modulo five gives $(1,0) \oplus (2,1) = (3,3)$.

I have two problems that are stopping me from completing the group table.

1. In the case $\mathcal C/\mathbb R$, to compose an element with itself, say $P \oplus P$, we find the tangent line to $\mathcal C$ at $P$ and then find the intersection of this line with $\mathcal C$. But how do we compose elements with themselves in my case? What is the tangent line to $\mathcal C/\mathbb F_5$? These points are coloured peach on my group table. (I managed to fill in two peach boxes with simple properties of groups, but without the other entries I wouldn't have known how to find these.)

2. When trying to compose $(0,0)$ with other points, I can't seem to find a third point of the line for most points. These are marked as ? in my group table.

EDIT: My updated group table thanks to Jyrki Lahtonen (original table below).

My original group table

Answer 1

You get the slope of the tangent line by the usual method of implicit differentiation (works also in $\Bbb{F}_5$ and other fields). So, if the equation of your curve is $$ y^2=x^3-x $$ you get by implicit differentiation $$ 2y\,dy=(3x^2-1)\,dx, $$ and therefore $$ \frac{dy}{dx}=\frac{3x^2-1}{2y}. $$ So for example at the point $P=(2,1)$ you get the slope $$ m=\frac{dy}{dx}=\frac{3\cdot2^2-1}{2}=\frac{11}2=\frac12=3. $$ So the equation of the tangent at $P$ is $$ y-1=3(x-2)\Leftrightarrow y=3x. $$ Therefore the origin $(0,0)$ is the third point of $C$ on the tangent, and you can calculate that $$ P+P=-(0,0)=(0,0). $$ Observe that at the points where $y=0$ the above formula for the slope leads to division by zero. This poses no problem whatsoever, because at such a point we have a vertical tangent. When the curve is in short Weierstrass form (such as here) those points are always of order two, because the neutral element, the point at infinity, is the third point on all vertical lines.

---

Your other unfilled entries are also related to tangency. We just saw that the line $y=3x$ connecting $(0,0)$ and $(2,1)$ is tangent to the curve at $(2,1)$. Therefore $(2,1)$ is also the third point of intersection (it's a doubled point of intersection). So you should follow the usual recipe and negate the $y$-coordinate to arrive at $$ (0,0)+(2,1)=-(2,1)=(2,4). $$ An algebraic explanation for that doubled intersection comes also from the equations. We are looking for points where the line $y=3x$ intersects the curve $y^2=x^3-x$. If we plug-in $y=3x$ to the latter equation we get $$ x^3-x=y^2=(3x)^2=9x^2=-x^2. $$ So to find the third point we need to solve the cubic $$ x^3+x^2-x=0. $$ Because we know in advance that $x=0$ and $x=2$ are solutions of this cubic (the points $(0,0)$ and $(2,1)$ are points of intersection by design!), the third solution can be found easily by factoring out $x-0$ and $x-2$. This gives $$ x^3+x^2-x=x(x^2+x-1)=x(x-2)(x-2) $$ confirming the original observation that $x=2$ is a double solution, and $(2,1)$ a doubled point of intersection (tangency!).

If you don't want to factor cubics even though you already know two of the factors you can use the well known fact (aka Vieta relations) that when $$ x^3+ax^2+bx+c=(x-x_1)(x-x_2)(x-x_3) $$ then $$ -a=x_1+x_2+x_3.\qquad(*) $$ Here you know $a=1$, $x_1=0$, $x_2=2$ and can solve from $(*)$ that $x_3=2$.

Answer 2

Since $\;0=-0\;$ , we get that $\;2(0,0)=(0,0)+(0,0)=\mathcal O\;$

With the rest (with second coordinate diffrerent from zero) it is easier, for example:

$$(x_1,y_1):=(2,1):\;\;m=\frac{3\cdot2^2+1}2=3\cdot2^{-1}=4=-1\implies$$

$$\begin{cases}x_3=m^2-2x_1=1-4=2\\{}\\y_3=y_1+m(x_3-x_1)=1-(2-2)=1\end{cases}\;\;\implies 2(2,1)=2(x_1,y_1)=(x_3,-y_3)=(2,4)$$

Read for example page 12 here .