1

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!

1 Answers1

0

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

DonAntonio
  • 211,718
  • 17
  • 136
  • 287
  • thank you!!! But could you explain to me how does 38.5=4.5 and how does $9⋅2^{-1}=9⋅9$ – user3170899 Mar 30 '14 at 04:00
  • I see it now :D – user3170899 Mar 30 '14 at 04:02
  • 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$$ – DonAntonio Mar 30 '14 at 04:03