In the elliptic curve: $y^2 = x^3 + 20x + 13 \bmod{2111}$. Using the point $P=(3, 10)$

I am wondering how to multiply this point by the scalar $57$?

I realize I can write $57*P$ as $2^5*P + 2^4*P + 2^3*P + P = 2(2(2(2(2P)))) + 2(2(2(2P))) +2(2(2P)) + P$.

My question is what is the best way to calculate these doubles and additions?

Some pseudo code or real code would be greatly appreciated although even a tutorial on how to do this by hand would help a lot!

  • $\begingroup$ Are you familiar with how to add points on an Elliptic curve? $\endgroup$ – figlesquidge Nov 14 '13 at 16:05

Basically, you keep a separate variable, which is initially $P$ and then double it again and again. Initialize the sum with 0 and add the according values of the other variable. Basically this method is described as "square and multiply" for exponentiation (which works just the same way with squaring instead of doubling and multiplying instead of adding).

In your example:

  • Let's transform your number $57$ into a binary number $F$ and address its digits as $F[i]$.
  • $T:= P; S:= 0$
  • for all $i$:
    • if $F[i] == 1: S+= T$
    • T := 2T
  • return $S$

The typical way to do this is the double and add method.

You start with the binary expansion of the scalar $57_{10}=111001_2$

Then scanning right from left, for each bit you double and if the bit is set to $1$ you add.

With elliptic curves it would look like this:

$Q\gets\infty$ (or the point at infinity since it is the identity element)
$P_{tmp}\gets P$
$bin\gets [1,0,0,1,1,1]$ (i.e., the binary expansion of the scalar reversed)
for $i$ in $bin$:
$\ \ $if $i==1$:
$\ \ \ \ \ Q\mathrel{+}=P_{tmp}$
$\ \ P_{tmp}=P_{tmp}+P_{tmp}$
return $Q$


Your Answer

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

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