-2

How do I compute 2P, 3P etc?

ex: $y^2=x^3+4xmod7$

and I have to compute the order of (2,3)=P

and my example says 2P =(0,0) 3P=(2,4) but I don't know how to get these answers?

Math Major
  • 2,234

1 Answers1

1

You should let a computer try all possibilities for nP, until nP=O. Then n* is the order of P.

EDIT: To do this using a computer or by hand, use the formulae found on wikipedia: http://en.m.wikipedia.org/wiki/Elliptic_curve_point_multiplication

Instead of division, you should multiply by the modular multiplicative inverse, since we are working in a finite field. The modular multiplicative inverse can be found by using the extended Euclidean algorithm.

Dasherman
  • 4,206
  • unfortunately it's an exam question...so I have to do it without a computer – Math Major Dec 09 '14 at 16:49
  • So I am asking how can I compute for example 2P and 3P? – Math Major Dec 09 '14 at 16:49
  • Use the formulae on wikipedia: http://en.m.wikipedia.org/wiki/Elliptic_curve_point_multiplication. Use the doubling one to calculate 2P, then use addition to calculate 3P, 4P, etc. – Dasherman Dec 09 '14 at 16:54
  • I might show you the calculation without a computer later, if nobody else does so before me. I can't do so now, however, since I'm busy. – Dasherman Dec 09 '14 at 17:01
  • Yes, you should not divide by 6. Instead multiply by the modular multiplicative inverse of 6. This is the integer, n, with the following property: n*6=1 (mod 7). – Dasherman Dec 09 '14 at 17:13
  • Got it! Does lambda stay constant throughout my calculations? – Math Major Dec 09 '14 at 17:21
  • No, it is dependent on the two points you are adding (for example P+2P: lambda=(3-0)/(2-0)=3/2=3*4=12=5 mod7) – Dasherman Dec 09 '14 at 17:27
  • does the order matter when I add points? So let's say I calculat P and 2P, should I add P+2P in this order? – Math Major Dec 09 '14 at 17:42
  • 1
    No, addition is still commutative, since elliptic curve points form an abelian group under addition (a line through P and 2P is the same as a line through 2P and P). So for all points P and Q, P+Q=Q+P – Dasherman Dec 09 '14 at 17:44
  • Thanks for all your help! Last question about this: how can I determine the order of a point P and what does that tell me about the structure? Specifically in this practice exam, 7Q was calculated for a point Q=(3,2) and this is mod 7, so the example concluded that Q has order 8 and the structure is Z/8. If I hadn't tested this point would I just need to test all the points and if I couldn't compute up to 7P then it has structure Z/4*Z/2? – Math Major Dec 09 '14 at 18:15
  • I'm sorry, I don't know enough about structures to answer the second part. The first part: I would try all multiples until the result is O. However, this is not very efficient. Do you have more info on the curve? – Dasherman Dec 09 '14 at 18:21
  • Oh ok, that's fine then~ Sadly I don't – Math Major Dec 09 '14 at 18:25