0
$\begingroup$

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?

$\endgroup$

migrated from crypto.stackexchange.com Jan 10 '15 at 17:25

This question came from our site for software developers, mathematicians and others interested in cryptography.

3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – user193271 Jan 10 '15 at 19:25
  • $\begingroup$ I added the calculations I did in my post above. Could you check them? $\endgroup$ – user175343 Jan 10 '15 at 19:36
  • $\begingroup$ @user159870 what is the field the curve is over? $\endgroup$ – mikeazo Jan 11 '15 at 16:03
  • $\begingroup$ The curve is over the field $\mathbb{Q}$ @mikeazo $\endgroup$ – user175343 Jan 12 '15 at 17:02
  • $\begingroup$ @user159870 your math is wrong. You have $2P$ right, but $4P$ is wrong. $\endgroup$ – mikeazo Jan 12 '15 at 17:17
0
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy