2007 Reports :  Cryptology ePrint Archive Forum
Discussion forum for Cryptology ePrint Archive reports posted in 2007. Please put the report number in the subject.  
Goto Thread: PreviousNext
Goto: Forum ListMessage ListNew TopicSearchLog In
Report 2007/414, Optimizing double-base elliptic-curve single-scalar multiplication
Posted by: jamuir (IP Logged)
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 [22]).

When I look through [22] 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 [22], 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?


Please log in for posting a message. Only registered users may post in this forum.