1
$\begingroup$

Given E: (elliptical curve)

$y^2 = x_3+2x+2 \bmod 17$

Recall: $y^2 = x^3+ax+b$

point $P=(5,1)$

Compute:

$2P = P+P = (5,1)+(5,1)= (x_3,y_3)$

Now the formula used here is slope $m = \dfrac{3x_1^2 +a}{2y_1}$

and what they got is $s = (2 · 1)^{−1} (3 · 5^2 + 2) = 2^{−1} · 9 ≡ 9 · 9 ≡ 13 \bmod 17$

this is what confuses me.

should it not be $(2·1)^{-1}(3 · 5^2 + 2)= 38.5 \bmod 17$ which is 4.5?

Sorry if this may seem trivial, I'm doing a research for a high school project.

The next steps are:

$x_3 = m^2 − x_1 − x_2 = 13^2 − 5 − 5 = 159 ≡ 6 \bmod 17$ $y_3 = m(x_1−x_3) − y_1 = 13(5 − 6) − 1= −14 ≡ 3 \bmod 17$

$(x_3,y_3) = (6,3)$

which I don't understand as well

If someone could enlighten me on this I would be very happy!

$\endgroup$
1
  • $\begingroup$ Your $\;x_3\;$ must be, I think, $\;x^3\;$, otherwise this is not an elliptic curve... $\endgroup$ Commented Mar 30, 2014 at 3:52

1 Answer 1

Reset to default
0
$\begingroup$

$$2^{-1}=9\pmod{17}\;\;,\;\;3\cdot 5^2=3\cdot 8=7\pmod{17}\implies$$

$$(2\cdot 1)^{-1}(3\cdot 5^2+2)=9(7+2)=9^2=13\pmod{17}$$

BTW, this is exactly what you got, since

$$38.5=4.5=\frac92=9\cdot2^{-1}=9\cdot9=13\pmod{13}\ldots$$

$\endgroup$
3
  • $\begingroup$ thank you!!! But could you explain to me how does 38.5=4.5 and how does $9⋅2^{-1}=9⋅9$ $\endgroup$ Commented Mar 30, 2014 at 4:00
  • $\begingroup$ I see it now :D $\endgroup$ Commented Mar 30, 2014 at 4:02
  • $\begingroup$ Well, $\;38.5=4.5\pmod{17}\iff 38.5-4.5=34\;$ is a multiple of $\;17\;$ , which it is. As for $\;2^{-1}\;$: by definition, the inverse of two is an element s.t. when multiplied by two we get one, and indeed: $$2\cdot 9=18=1\pmod{17}\implies 2^{-1}=9$$ $\endgroup$ Commented Mar 30, 2014 at 4:03

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.