ACAC Seminar Abstract

ACAC Seminar Abstract

ACAC Seminars

ACAC Seminar Abstract

A New Approach to Find Short Double-Base Chains

Speaker: Christophe Doche
Date, Time: Fri, 13 Jun 2008 15:00

In this work, we investigate the use of Double Base Number System (DBNS) to perform scalar multiplications on elliptic curves. In DBNS, an integer is represented as $$sum_i=0^ell pm 2^{a_i}3^{b_i}.$$ Double-Base chains are similar but have the additional requirement that the sequences of exponents (a_i) and (b_i) are simultaneously decreasing. Expansions of this form are usually very sparse and can be computed quite efficiently with a greedy approach. We present a new algorithm based on a tree-exploration, that is simpler and also more efficient than the greedy approach. We conclude with a complexity analysis of the average length returned by this algorithm.

Back to the top of this page