Report 2007/414, Optimizing double-base elliptic-curve single-scalar multiplication
Posted by: jamuir
Date: 23 November 2007 18:08
Report 2007/414 is "Optimizing double-base elliptic-curve single-scalar multiplication" by Bernstein, Birkner, Lange and Peters. I think it is a very nice paper, but I wondered if someone might be able to help me track down the origins of one of the ideas mentioned in it.
In the discussion in the section "Computing a chain", which starts at the bottom of page 8, the first two paragraphs mention what I call closest-choice decompositions of the integer 314159. It is mentioned that these decompositions correspond to an addition chain method by Thurber. Specifically, "Thurber's base-2 sliding window chain" is mentioned. I assume that this a reference to Thurber's DMJ paper (cited as ).
When I look through  I don't find any discussion there about closest-choice decompositions. Moreover, Thurber treats only addition chains rather than addition-subtraction chains. Does anyone know if there is some other work by Thurber where this can be found?
In , Thurber does, however, present an example (page 912) where he uses the binary representation of n to identify what he calls critical numbers. His strategy seems to differ from the close-choice strategy because he selects the first critical number to be larger than the others.
Can anyone help me track down the origins of closest choice representations?