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

Improve this question
$\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$ Commented 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$ Commented Jan 6, 2020 at 18:56

1 Answer 1

Reset to default
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}$.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.