Double Base Number System and Elliptic Curve Cryptography
Christophe Doche (Macquarie University)
MSI Computational Mathematics Seminar SeriesDATE: 2008-04-28
TIME: 11:00:00 - 12:00:00
LOCATION: John Dedman G35
CONTACT: JavaScript must be enabled to display this email address.
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.
BIO:
http://www.ics.mq.edu.au/~doche/
