Paper Info
Title
Width-3 joint sparse form
Abstract
The joint sparse form (JSF) is a representation of a pair of integers, which is famous for accelerating a multi-scalar multiplication in elliptic curve cryptosystems. Solinas’ original paper showed three unsolved problems on the enhancement of JSF. Whereas two of them have been solved, the other still remains to be done. The remaining unsolved problem is as follows: To design a representation of a pair of integers using a larger digit set such as a set involving ±3, while the original JSF utilizes the digit set that consists of 0, ±1 for representing a pair of integers. This paper puts an end to the problem; width-3 JSF. The proposed enhancement satisfies properties that are similar to that of the original. For example, the enhanced representation is defined as a representation that satisfies some rules. Some other properties are the existence, the uniqueness of such a representation, and the optimality of the Hamming weight. The non-zero density of the width-3 JSF is 563/1574(=0.3577) and this is ideal. The conversion algorithm to the enhanced representation takes O(logn) memory and O(n) computational cost, which is very efficient, where n stands for the bit length of the integers.
Year
DOI
Venue
2010
10.1007/978-3-642-12827-1_6
ISPEC
Keywords
Field
DocType
remaining unsolved problem,enhanced representation,proposed enhancement,original jsf,width-3 joint sparse form,unsolved problem,original paper,hamming weight,larger digit,digit set,width-3 jsf,scalar multiplication,satisfiability
Bit-length,Integer,Uniqueness,Discrete mathematics,Combinatorics,Elliptic curve cryptosystem,Multiplication,Elliptic curve cryptosystems,Hamming weight,Mathematics
Conference
Volume
ISSN
ISBN
6047
0302-9743
3-642-12826-2
Citations 
PageRank 
References 
2
0.46
9
Authors
3
Name
Order
Citations
PageRank
Katsuyuki Okeya144738.47
Hidehiro Kato2203.30
Yasuyuki Nogami314652.44