Speaker: Christophe Doche Macquarie University
Time: 2008-05-28 16:00-2008-05-28 17:00
Venue: FIT Building 4-603, Tsinghua University
Download: Click!

Abstract:

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}.$$ Expansions of this form are usually very sparse and can be computed quite efficiently with a greedy approach. We present a new system called extended DBNS using nontrivial coefficients, whose number of terms is even smaller than the classical DBNS. We also discuss a new approach to approximate an integer $n$ by $d2^a3^b$ where $d$ belongs to a given digit set,leading to realistic implementations. Finally, a new tree-based algorithm, simpler and also more efficient than the greedy approach, is described and analyzed.

Short Bio:

Dr.Christophe Doche is a Senior Lecturer at Macquarie University and he is also a member of Centre for Advanced Computing-Algorithms and Cryptography. His areas of interest are Cryptography, Analytic Number Theory and Algorithmic Number Theory and efficiency aspects.