2007 Reports : Cryptology ePrint Archive Forum

Discussion forum for Cryptology ePrint Archive reports posted in 2007.
Please put the report number in the subject.

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?

-James

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?

-James

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