Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question
1  
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. –  Gilles Sep 2 '13 at 16:01
    
Clearly, my problem is with doing basic arithmetic in my head sigh –  samoz Sep 2 '13 at 17:09
add comment

1 Answer 1

up vote 1 down vote accepted

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)$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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