2
$\begingroup$

I am trying to do some elliptic curve calculations by hand, just to refresh myself on how the system works. I calculated some points and did some operations by hand. I am trying to double check my work with some web calculators, but I have tried several different calculators and each gives me a different result...

Is there a verified implementation or library somewhere that I could use, rather than pet projects that people have on their websites?

I am working with the curve

$y^2 \equiv x^3 - 2 \pmod 7$

I calculated the points to be

$(3,2),(3,5),(4,1),(4,6,),(5,2,),(5,5),(\infty, \infty)$

I calculated $(3,2) + (5,5) = (3,5)$ I'm fairly confident in this answer.

The problem I'm struggling with however is $(3,2) + (3,2) = (3,5)$. I have tried several times and have gotten the slope between the two points to be $27/4$. When I convert this to an integer $\mod 7$, I get the slope equal to either $3$ or $5$. When $m=3$, I get the point $(3,5)$. When $m=5$, I get the point $(5,1)$, which isn't on the curve, so I'm assuming I'm doing this step incorrectly.

$\endgroup$
  • 1
    $\begingroup$ The points $(4,1)$ and $(4,6)$ aren't on the curve. Only $1$ and $-1$ are cubes modulo 7, and they have three cube roots each, so there should be three values of $x$ for each $y$. Similarly for squares there should be two values of $y$ for each $x$. These points are $(6,2)$ and $(6,5)$ instead. $\endgroup$ – Gilles 'SO- stop being evil' Sep 2 '13 at 16:01
  • $\begingroup$ Clearly, my problem is with doing basic arithmetic in my head sigh $\endgroup$ – samoz Sep 2 '13 at 17:09
1
$\begingroup$

The slope is $5$: $$ \frac{27}{4} = 27 \cdot 4^{-1} = 27 \cdot 2 = 5 \mod 7 $$

$$ x = 5 \cdot 5 - 3 - 3 = 19 = 5 \mod 7 $$

$$ y = 5 \cdot (3 - 5) - 2 = 5 \cdot (-2) - 2 = 5 \cdot 5 + 5 = 30 = 2 \mod 7$$

So $(3,2) + (3,2) = (5,2)$. This matches with $(3,2) + (5,5) = (3,5)$, since this shows that $(3,2)$ and $(5,5)$ are on a line which is tangent to the curve at $(3,2)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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