The alternating greedy expansion and applications to computing digit expansions from left-to-right in cryptography
详细信息 查看全文
- 作者：Clemens Heuberger ; Rajendra Katti ; Helmut Prodinger and Xiaoyu Ruan
- 关键词：Signed digit expansion ; Left-to-right algorithm ; Joint expansion ; Public-key cryptography
- 刊名：Theoretical Computer Science
- 出版年：2005
- 出版时间：2005
- 年：2005
- 卷：341
- 期：1-3
- 页码：55-72
- 全文大小：270 K
文摘
The central topic of this paper is the alternating greedy expansion of integers, which is defined to be a binary expansion with digits {0,±1} with the property that the nonzero digits have alternating signs. We collect known results about this alternating greedy expansion and complement it with other useful properties and algorithms. In the second part, we apply it to give an algorithm for computing a joint expansion of d integers of minimal joint Hamming weight from left to right, i.e., from the column with the most significant bits towards the column with the least significant bits. Furthermore, we also compute an expansion equivalent to the so-called w-NAF from left to right using the alternating greedy expansion.