I am searching informations about the so called "Strauss-Shamir method" for scalar multiplication upon elliptic curves. It is a method to compute k1 · P + k2 · Q in around log2(k) additions and doublings, where k1, k2 < k.
Unfortunately, while this algorithm is cited left right and center, the actual algorithm (and, dare I hope, its analysis) is not cited anywhere. Is there someone that could explain it to me, or at least give me a link on pseudocode/analysis?
Many thanks in advance!
To multiply a number P by an n-bit scalar k, you can use doubling and addition according to the binary expansion of k. Let's say that k=9. In binary, that's 1001, and you can calculate 9P like this:
R=0
R=R*2+P //the most significant '1' bit
R=R*2 //next bit is 0
R=R*2 //next bit is 0
R=R*2+P //next bit is 1
The Strauss-Shamir trick is just calculating aP + bQ by doing the additions inside the chain instead of outside. Let's say that, in binary, a=1001 and b=0011`. Then we just do this:
R=0
R=R*2+P //bits from a,b = 1,0
R=R*2 //bits from a,b = 0,0
R=R*2+Q //bits from a,b = 0,1
R=R*2+P+Q //bits from a,b = 1,1
If you precompute P+Q, then this doesn't take much longer than a single multiplication.