Elliptic Curve Point Doubling

1.9k Views Asked by At

I understand that to double a point on an elliptic curve $y^2=x^3+ax+b$ you first calculate the slope of the tangent at the point $(x,y)$: $\lambda = \frac{3x^2+a}{2y}$ and then using the point addition formulae $x_2 = \lambda^2 - 2x_1$ and $y_2 = \lambda(x_1 - x_2) - y_1$ you can calculate the point multiplication.

When trying to calculate $4P$ with the point $P(0,1)$ on the elliptic curve $y^2 = x^3 + x + 1\mod(7919)$ an online calculator (https://andrea.corbellini.name/ecc/interactive/modk-mul.html) gives the value $(4860, 2511)$. I recognize that $4P = 2P + 2P = 2(2P)$ and so I can point double $P$ twice to get $4P$. When I double once I get the value $(1980, 6928)$ which is the same as the online calculator. However, when I double this point again I get the value $(7045, 5204)$ which is wrong. Here are my calculations:

$\lambda = \frac{3(1980^2)+1}{2(6928)} = 11761201 \cdot 4399 = 3739\mod(7919)$

Where $4399$ is the modular multiplicative inverse of $2(6928)$

$x_2 = 3739^2 - 2(1980) = 7045\mod(7919)$

$y_2 = 3739(1980 - 7045)-6928 = 5204\mod(7919)$

Why do I get an incorrect value for the point $4P$?

2

There are 2 best solutions below

0
On BEST ANSWER

Your calculations are correct. You can verify it on Sage.

Paste the following into this page and click "Evaluate" to see the result.

E = EllipticCurve(Integers(7919), [1, 1])
P = E([0, 1])

print(E)
print(P)

4*P
0
On

Your calculations are entirely correct. The online calculator is certainly incorrect, as $$2511^2\not\equiv4860^3+4860+1\pmod{7919}.$$ Why the online calculator gives this incorrect result, I cannot tell you. I can only suggest to use a more established computer tool such as PARI/GP or Sage.