Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have an elliptic curve $y^2 = x^3 + 2x + 2$ over $Z_{17}$. It has order $19$.

I've been given the equation $6\cdot(5, 1) + 6\cdot(0,6)$ and the answer as $(7, 11)$ and I'm unsure how to derive that answer.

I have $6\cdot(5, 1) = (16,13)$ and $6\cdot(0,6)=(0, 11)$ however when I use point addition to add them together I get $(16,13)+(0, 11)=(14,11)$ which isn't even a point on the curve...

Could someone help me identify where and why I've gone wrong?

For further information here's each of the points:

enter image description here

And here's the curve plotted out: enter image description here

share|improve this question

2 Answers 2

up vote 4 down vote accepted

Hints:

  • Your calculation of $6(5,1) = (16,13)$ is correct.
  • Your calculation of $6(0,6) = (0,11)$ is incorrect, you should get $6(0,6) = (3,1)$.

Maybe if you show how you did that calculation, I can spot the issue.

Once you fix that, I verified the author's result is correct, that is:

$$(16,13)+(3,1) = (7,11)$$

Update

Here are some additional hints to help you with intermediate calculations:

  • $P = (0,6)$
  • $2P = (9,1)$
  • $3P = (6,3)$
  • $4P = (7,6)$
share|improve this answer
    
Thanks for this, I'll redo my working for the second one and if I'm still struggling I'll get back to you, if not then I'll accept this. –  Peanut Jun 28 '13 at 15:39
    
@Peanut: Sounds great, I also added an update with some initial calculations, so you can verify as you are doing your calculations. Let me know if you still have issues. Regards –  Amzoti Jun 28 '13 at 15:47
    
Thanks for the hints, just done $2P$ and it's correct so I've got the method right, must have made a silly mistake somewhere. Is there a quick way to do these, or do you just have to work out $P$ then $2P$, then $3P, 4P$ etc or can you say for example point double $2P$ to get $4P$ and skip $3P$? I've just started looking at this topic and have a programming background so have relatively little mathematical knowledge. –  Peanut Jun 28 '13 at 15:59
    
@Peanut: In practice, you want to minimize the number of calculations you do, so yes, always minimize the number as much as is possible. Here, we can do (2P, 2.2P, 2P + 4P), or get to (3P = P + 2P, 2.3P). Clear? We are typically talking huge numbers in real life, so reductions are critical to speed. ALso, you are doing great! Regards –  Amzoti Jun 28 '13 at 16:11
1  
+ 1 for great hints, great follow-up, and great patience! –  amWhy Jun 29 '13 at 0:05

You can aid (read: double-check) your calculations with the computer, for instance using Sage or Magma. For example, you can use for free the Magma online calculator. The following code defines your curve $E$ over $\mathbb{Z}/17\mathbb{Z}$, and calculates $6\cdot (0,6)$.

g:=GF(17).1;

E:=EllipticCurve([0,0,0,2*g,2*g]);

P:=E![0,6];

6*P;

The output is $[3:1:1]$ which are projective coordinates for the point $(3,1)$, as it should be.

share|improve this answer
    
Thanks for this, I'll check it out. –  Peanut Jul 1 '13 at 12:16

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.