1
$\begingroup$

Consider the elliptic curve E1:y2=x3+7 over F17 with the base point G=(15,13)

I am trying to compute point double of (15,13) i.e (15,13)+ (15,13) Expected point is (2,10) , however I am not able to calcualate it. Could anyone point out where I am making mistake

s = 3 * (15*15) / 2 * 13 mod 17 = 375/26 mod 17 = 750 mod 17 = 2

x3 = (2*2) - 15 -15 mod 17 = -26 mod 17 = 8

y3 = 2(15-8) - 13 mod 17 = 1

however point x3,y3 = 8,1 does not lie on Elliptic curve Please help me understand this point doubling operation. Thanks in advance

$\endgroup$
5
  • $\begingroup$ I think something went wrong in your 2nd "equals". 3*15*15 is not 375 $\endgroup$
    – honzaik
    Dec 4, 2023 at 10:41
  • $\begingroup$ could you please be exact : i just did 3 * 125 /26 = 375/26 $\endgroup$ Dec 4, 2023 at 10:44
  • $\begingroup$ 3*15*15 = 3*(225) you calculate 3*(5^3) or something like that $\endgroup$
    – honzaik
    Dec 4, 2023 at 10:47
  • $\begingroup$ Yes , I am essentially trying to compute the same thing wrt to this point (15,13) on the said curve . I undertstand the my s calucation is incorrect ..but not sure how exactly.My explanation is inverse of 26 mod 17 is 2 ..hence 375 * 2 = 750.could you please correct ? $\endgroup$ Dec 4, 2023 at 10:54
  • $\begingroup$ The formulas to apply are in sec1v2 §2.2.1, case 5, which uses $\lambda$ where the question has $s$. The first issue in the question is that 3*(15*15) is 675, not 375. [reposted with correction] $\endgroup$
    – fgrieu
    Dec 4, 2023 at 10:57

1 Answer 1

0
$\begingroup$
s = 3 * (15*15) / 2 * 13 mod 17 = 375/26 mod 17 = 750 mod 17 = 2

This is not correct ($3\cdot 225 = 675 \neq 375$). The correct one is;

$s = \frac{3 (x_1^2)}{2 y_1 } = \frac{3 (15^2)}{2\cdot 13 }= \frac{3 (-2)^2}{2\cdot 13 }= \frac{3 \cdot 4}{2\cdot 13 }= 12 \cdot 26^{-1} = 12 \cdot 2 = 24 = 7\bmod 17$

Therefore;

$x_3 = s^2 - 2 \cdot x_1 = 49 - 2 \cdot 15 = -2 + 4 = 2\bmod 17$


We used the doubling formula on the affine formulas as with $a = 0$ with as in Secp256k1

Let $$y^2 = x^3 + b$$ be the curve equation then the doubling formula is

\begin{align} x_3 = & s^2 -2 x_1 & \mod p\\ y_3 = & s(x_1-x_3) -y_1 & \mod p \end{align}

$$ s = \frac{3 x_1^2}{2y_1} \bmod p $$

$\endgroup$
2
  • $\begingroup$ How thanks for your explantion . I understood your calculations and also my mistake. $\endgroup$ Dec 4, 2023 at 11:05
  • $\begingroup$ Using the negatives helps to reduce the calculations, like $15 = -2 \bmod 17$ so you don't need the large number and reduce it. $\endgroup$
    – kelalaka
    Dec 4, 2023 at 11:13

Your Answer

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

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