6
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ i.sstatic.net/4S7ln.png Can't reproduce? Are you sure that x = 1980, y = 6928? For me it took multiple attempts to enter those numbers as typing one of them changes the other. $\endgroup$
    – MCCCS
    Commented Oct 4, 2020 at 8:24
  • $\begingroup$ @MCCCS I achieved those results on the online calculator by calculating 4P, where P is (0,1), rather than trying to point double (1980, 6928), which should yield the same results. $\endgroup$
    – S34NM68
    Commented Oct 4, 2020 at 10:03
  • $\begingroup$ I submitted a fix to the developer. If you can read code here is it: github.com/andreacorbellini/ecc/pull/7/… $\endgroup$
    – MCCCS
    Commented Oct 4, 2020 at 11:41
  • 1
    $\begingroup$ My fork of Corbellini's tool gives correct results, but I use half negatives, half positives, for modular results, so (x2, y2) = (-874, -2715) = (7045 - 7919, 5204 - 7919). $\endgroup$
    – enrique
    Commented Oct 4, 2020 at 17:01
  • $\begingroup$ The tool is fixed and works now. $\endgroup$
    – MCCCS
    Commented Oct 11, 2020 at 8:04

2 Answers 2

5
$\begingroup$

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
$\endgroup$
5
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .