2005 | OriginalPaper | Chapter
A Note on Signed Binary Window Algorithm for Elliptic Curve Cryptosystems
Authors : Fanyu Kong, Daxing Li
Published in: Cryptology and Network Security
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
The window algorithms for various signed binary representations have been used to speed up point multiplication on elliptic curves. While there’s been extensive research on the non-adjacent form, little attention has been devoted to non-sparse optimal signed binary representations. In the paper, we prove some properties of non-sparse optimal signed binary representations and present a precise analysis of the non-sparse signed window algorithm. The main contributions are described as follows. Firstly, we attain the lower bound
k
+1/3 of the expected length of non-sparse optimal signed binary representations of
k
-bit positive integers. Secondly, we propose a new non-sparse signed window partitioning algorithm. Finally, we analyze Koyama-Tsuruoka’s non-sparse signed window algorithm and the proposed algorithm and compare them with other methods. The upper bound
$\frac{5}{6}\cdot 2^{w-1} -1+\frac{(-1)^{w}}{3}$
of the number of precomputed windows of the non-sparse signed window algorithms is attained.