Unbalanced digit sets and the closest choice strategy for minimal weight integer representations |
| |
Authors: | Clemens Heuberger James A Muir |
| |
Institution: | 1.Institut für Mathematik B,Technische Universit?t Graz,Graz,Austria;2.Cloakware Corporation,Ottawa,Canada |
| |
Abstract: | An algorithm is presented that produces an optimal radix-2 representation of an input integer n using digits from the set , where ℓ ≤ 0 and u ≥ 1. The algorithm works by scanning the digits of the binary representation of n from left-to-right (i.e., from most-significant to least-significant); further, the algorithm is of the online variety in
that it needs to scan only a bounded number of input digits before giving an output digit (i.e., the algorithm produces output
before scanning the entire input). The output representation is optimal in the sense that, of all radix-2 representations
of n with digits from D
ℓ,u
, it has as few nonzero digits as possible (i.e., it has minimal weight). Such representations are useful in the efficient implementation of elliptic curve cryptography. The strategy the algorithm
utilizes is to choose an integer of the form d 2
i
, where , that is closest to n with respect to a particular distance function. It is possible to choose values of ℓ and u so that the set D
ℓ,u
is unbalanced in the sense that it contains more negative digits than positive digits, or more positive digits than negative
digits. Our distance function takes the possible unbalanced nature of D
ℓ,u
into account.
|
| |
Keywords: | Elliptic curve cryptography Digital expansion Online algorithm Efficient implementation |
本文献已被 SpringerLink 等数据库收录! |
|