Elliptic Curve Group

Question

For $E_{11}(1, 7)$, compute the multiple of G from 2G through 13G.
$G = (3, 2)$

I have calculated the group with 15 points (including the point at infinity O)

$y^2 \pmod{11}$

y	0	1	2	3	4	5	6	7	8	9	10
Result	0	1	4	9	5	3	3	5	9	4	1

$y^2 = x^3 + x + 7 \pmod{11}$

x	0	1	2	3	4	5	6	7	8	9	10
Result	7	9	6	4	9	5	9	5	10	8	5
Points		3,8		2,9	3,8	4,7	3,8	4,7			4,7

There are 15 points(including infinity O) but I don't know how to compute the multiple of G(3, 2)

Answer 1

This is an easy computer exercise, so i will start by inserting the computations done (by computer) first. Then i will say something about how to get the results with bare hands. The given curve $E$ lives over the field $F=\Bbb F_{11}$ with eleven elements: $$ E/F\ :\ y^2 = x^3 + x + 7\ , $$ it has order $15$, i.e. there are $\#E(F)=15$ $F$-rational points. One of them is $G=(3,2)$, and its multiples are as in the following dialog with the sage interpreter...

sage: E = EllipticCurve(GF(11), (1, 7))
sage: E
Elliptic Curve defined by y^2 = x^3 + x + 7 over Finite Field of size 11
sage: E.order()
15


sage: for k in [0..15]:
....:     print(f"{k:2}G = {(k*G).xy() if k*G else 'ZERO'}")
....: 
 0G = ZERO
 1G = (3, 2)
 2G = (10, 4)
 3G = (1, 8)
 4G = (5, 4)
 5G = (4, 8)
 6G = (7, 7)
 7G = (6, 8)
 8G = (6, 3)
 9G = (7, 4)
10G = (4, 3)
11G = (5, 7)
12G = (1, 3)
13G = (10, 7)
14G = (3, 9)
15G = ZERO

OK, let us compute now $2G$ explicitly. Which is the tangent line to $E$ in $G=(3,2)$. We introduce $X,Y$ with $x=3+X$ and $y=2+Y$, write the equation of $E$ in terms of $X,Y$, $$ E\ :\ 0 = -(2+Y)^2 + (3+X)^3 +(3+X) + 7\ , $$ and consider formally the Taylor expansion of the polynomial on the R.H.S, thus neglecting monomials of degree $>1$, we get the equation of the line: $$ L\ :\ 0 = -4Y + 27X + X\ . $$ In other words, $Y=7X$, or $y-2=7(x-3)$, or $y=7x-19$, or $y=7x+3$. We substitute this in the equation of $E$, getting $0=-(7x+3)^2 + x^3+x+7$. Now we can factor, if we really want to, and this leads to $0=(X+1)(X-3)^2$. This confirms that $3$, the $x$-component of $G=(3,2)$ is a double root, so the computations are good so far. But it is easier to trust the computatios, and to use Vieta in the last equation, with roots $3$, $3$, and $(?)$. Vieta predicts that the sum of the roots is $7^2=49=5$ (since $-7^2$ is the coefficient in $x^2$), so that question mark third root is $x=-1$. The corresponding $y$-value is $y=7x+3=7\cdot(-1) +3=-4$.

So the tangent line $L$ to $E$ in $G$ hits $E$ in a third point, which is $(-1,-4)$.

So $2G$ is the "opposite" point of the above, (just take the opposite in the $y$-component, since the equation of $E$ has a clean $y^2$-term in short Weierstraß form,) it is $$ 2G = (-1,4)=(10,4)\ . $$

---

In a similar manner, all other points are computed. To get for instance $3G$ we write the equation of the line through $G$ and $2G$, it is $$ \frac{y-2}{4-2} =\frac{x-3}{10-3}\ , $$ so $y=2+\frac 27(x-3)=2 + 2\cdot8(x-3)=2 + 5(x-3)=5x-2$, the third root (counting multiplicities) of $-(5x-2)^2 +x^3 +x+ 7$, after excluding the known $3,10$, the $x$-components of $G,2G$, is $5^2-3-10=1$. The corresponding point is has $y= 5x-2=5\cdot 1-2=3$. We build the opposite of $(1,3)$ to get $$ 3G = (1,-3)=(1,8)\ . $$