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.

Improve this question
$\endgroup$
2
  • 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'
    Commented Sep 2, 2013 at 16:01
  • $\begingroup$ Clearly, my problem is with doing basic arithmetic in my head sigh $\endgroup$
    – foobarfuzzbizz
    Commented Sep 2, 2013 at 17:09

1 Answer 1

Reset to default
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)$.

Improve this answer
$\endgroup$

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.