A new minimal average weight representation for left-to-right point multiplication methods

TitleA new minimal average weight representation for left-to-right point multiplication methods
Publication TypeJournal Article
Year of Publication2005
AuthorsKhabbazian, M., T. A. Gulliver, and V. K. Bhargava
JournalComputers, IEEE Transactions on
Volume54
Pagination1454 - 1459
Date Publishednov.
ISSN0018-9340
Keywordscomputational complexity, cryptography, digital arithmetic, elliptic curve cryptosystems, integer representation, left-to-right point multiplication, memory-constrained devices, minimal average weight representation, multiplying circuits, nonzero digit, radix-2 representation
Abstract

This paper introduces a new radix-2 representation with the same average weight as the width-w nonadjacent form (w-NAF). In both w-NAF and the proposed representations, each nonzero digit is an odd integer with absolute value less than M. However, for w-NAF, M is of the form 2w-1, while, for the proposed representation, it can be any positive integer. Therefore, using the proposed integer representation, we can use the available memory efficiently, which is attractive for devices with limited memory. Another advantage of the proposed representation over-w-NAF is that it can be obtained by scanning the bits from left-to-right. This property is also useful for memory-constrained devices because it can reduce both the time and space complexity of fast point multiplication techniques.

URLhttp://dx.doi.org/10.1109/TC.2005.173
DOI10.1109/TC.2005.173

a place of mind, The University of British Columbia

Electrical and Computer Engineering
2332 Main Mall
Vancouver, BC Canada V6T 1Z4
Tel +1.604.822.2872
Fax +1.604.822.5949
Email:

Emergency Procedures | Accessibility | Contact UBC | © Copyright 2020 The University of British Columbia