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$
  • 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 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 at 18:56
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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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