# Finding subgroup in elliptic curve over finite field $\mathbb{F}_{11}$

For elliptic curve $$y^2 = x^3 +3x+7$$ I found the finite group $$E(\mathbb{F}_{11})= \left\{ \mathcal{O}, (1,0),(5,2),(5,9),(8,2),(8,9),(9,2),(9,9),(10,5),(10,6) \right\}$$.

I have to find a generator of a subgroup of $$E(\mathbb{F}_{11})$$, but for every point $$P$$ in $$E(\mathbb{F}_{11})$$ when I try to calculate $$[2]P$$ I get a rational number. Am I doing something wrong?

For example if $$P=(5,2)$$ then by the formula $$x([2]P)={(\frac{3x_1^2+a}{2y_1})}^2-2x_1$$, where $$a$$ is the coefficient next to $$x$$ in the elliptic curve, and $$x_1$$ is the first coordinate of $$P$$ and $$y_1$$ is the second. But here I get $$x([2]P) = (\frac{3*25+3}{2*2})^2-2*5 =(\frac{39}{2})^2-10$$. Should I just ignore the denominator and use $$(\frac{39}{2})^2-10 =\frac{1521-10*16}{16}=\frac{1361}{16}$$ and the answer for $$x$$ would be $$1361$$ mod 11$$= 8$$?

• In your case, divisions are done in $\mathbb{F}_{11}$. When you write $1361\over{16}$ it is $1361$ times the inverse of $16$ modulo $11$ (which is $9$ because $16*9 = 1$ modulo 11). You can use the extended euclidian algorithm to calculate this. – Tosh Jan 6 '20 at 17:46
• Note: $(\frac{39}{2})^2 - 10$ is equal to $\frac{1481}{4}$ not $\frac{1361}{16}$ – Tosh Jan 6 '20 at 18:56

In elliptic curve algebra, operations are computed over a field. In your case, the field is $$\mathbb{F}_{11}$$.

$$\mathbb{F}_{11}$$ is a finite field containing 11 elements ($$\{0,1,2,...,10\}$$), and like every field there is and addition and multiplicative law. Theses two laws work other the ring of integers modulo 11 (often noted $$\mathbb{Z}/11\mathbb{Z}$$).

In $$\mathbb{F}_{11}$$, when we write $${(\frac{39}{2})}^2 - 10 = \frac{1481}{4} = \frac{7}{4}$$ it is in fact 7 times the inverse of 4 modulo 11, which is 3 because $$3*4 = 1$$ modulo 11.

Calculating an inverse modulo an integer can be done with the Extended Euclidian Algorithm. The below is the inverse table;

$$\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|}\hline x \in \mathbb{F}_{11}&1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10\\\hline x^{-1} &1& 6 & 4 & 3 & 9 & 2 & 8 & 7 & 5 & 10\\\hline \end{array}$$

In your example, the x-coordinate of $$[2]P$$ is then $$7*3 = 10$$, an element of $$\mathbb{F}_{11}$$.