2
$\begingroup$

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$?

$\endgroup$
2
  • 4
    $\begingroup$ 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. $\endgroup$
    – Tosh
    Jan 6, 2020 at 17:46
  • 1
    $\begingroup$ Note: $(\frac{39}{2})^2 - 10$ is equal to $\frac{1481}{4}$ not $\frac{1361}{16}$ $\endgroup$
    – Tosh
    Jan 6, 2020 at 18:56

1 Answer 1

3
$\begingroup$

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}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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