0

How can we calculate the multiple of a point of an elliptic curve?

For example having the elliptic curve $y^2=x^3+x^2-25x+39$ over $\mathbb{Q}$ and the point $P=(21, 96)$.

To find the point $6P$ is the only way to calculate:

  1. the point $2P=P+P$,
  2. then $4P=2P+2P$
  3. and then finally the point $6P=4P+2P$ ?

Or is there also an other way of calculation?

EDIT:

$$P=(21, 96)$$

$$2P=P+P=\left ( \frac{13153}{2304}, \frac{1185553}{110592} \right )$$

$$4P= \left (-\frac{21456882568875649}{3238354750023936} , \frac{3395969291284125120479041}{122855718046564076691456} \right )$$

$$6P=\left (\frac{26455920935919644458805579323004114785}{14704264997379508491439452468204834816} , -\frac{1075150031960164636335160890473952630299280887362209417804659119}{66847620865553399763849555951358904102466015610213125405278208} \right )$$

Can someone check if the coordinates of the point is correctly calculated?

2 Answers2

3

Sure there are other ways. For example,

$2P=P+P$, $3P=2P+P$, $6P=3P+3P$

Also,

$2P=P+P$, $3P=2P+P$, $4P=3P+P$, $5P=4P+P$, $6P=5P+P$

and so on.

In general, the double and add method you describe is the fastest. It is akin to the square and multiply that you often see in multiplicative groups.

mikeazo
  • 412
  • 1
    The double-and-add method is not always the fastest. There may be addition chains that require fewer multiplications, but these are in general nontrivial to determine. Volume 2 of Knuth's The Art of Computer Programming contains a pretty detailed introduction. –  Jan 10 '15 at 19:25
  • I added the calculations I did in my post above. Could you check them? –  Jan 10 '15 at 19:36
  • @user159870 what is the field the curve is over? – mikeazo Jan 11 '15 at 16:03
  • The curve is over the field $\mathbb{Q}$ @mikeazo –  Jan 12 '15 at 17:02
  • @user159870 your math is wrong. You have $2P$ right, but $4P$ is wrong. – mikeazo Jan 12 '15 at 17:17
  • @mikeazo I tried it again... Is the point $4P$ now correct? –  Jan 13 '15 at 16:16
  • @user159870 using sage, I got 4P as (38872628026746241/12953419000095744, -128941101364716229828031/1474268616558768920297472) – mikeazo Jan 13 '15 at 16:59
  • If you want to use sage (online like 111 recommends below), I used it like this: E = EllipticCurve(QQ, [0,1,0,-25,39]) and then P = E([21,96]). Then you can do P+P+P+P or just 4*P. – mikeazo Jan 13 '15 at 17:01
  • @mikeazo Ok! Thank you! –  Jan 13 '15 at 17:09
0

Sage gives the following $2P=\left(\frac{13153}{2304} , \frac{1185553}{110592}\right),$ $6P=\big(\frac{17631797546863867480163645661711294049}{2834578067615933833996300908324147456} ,-\frac{60902529607177336000181399672827762453069546262535228527}{4772353810493036247904139120367622993558177805319376896} \big{)}$ $=(6.220254699738563,-12.761528592718786)$

111
  • 747
  • What is Sage? A program to calculate such points? –  Jan 11 '15 at 02:21
  • Not only. Is a mathematics, open source, software system. See http://www.sagemath.org/ – 111 Jan 11 '15 at 12:22
  • Can we solve a system of two equations using this tool @111 ? –  Jan 12 '15 at 19:15
  • sure. it is very easy to solve a system. You don't need to download it, there is also an online version. – 111 Jan 12 '15 at 21:01