Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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!

share|improve this question
    
Are you familiar with how to add points on an Elliptic curve? –  figlesquidge Nov 14 '13 at 16:05
add comment

2 Answers 2

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$
share|improve this answer
add comment

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$

share|improve this answer
add comment

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.