
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Improving Width3 Joint Sparse Form to Attain Asymptotically Optimal Complexity on Average Case
Hiroshi IMAI Vorapong SUPPAKITPAISARN
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E98A
No.6
pp.12161222 Publication Date: 2015/06/01 Online ISSN: 17451337
DOI: 10.1587/transfun.E98.A.1216 Type of Manuscript: Special Section LETTER (Special Section on Discrete Mathematics and Its Applications) Category: Keyword: analysis of algorithms, number representation, elliptic curve cryptography, multiscalar multiplication, width3 joint sparse form,
Full Text: PDF>>
Summary:
In this paper, we improve a width3 joint sparse form proposed by Okeya, Katoh, and Nogami. After the improvement, the representation can attain an asymtotically optimal complexity found in our previous work. Although claimed as optimal by the authors, the average computation time of multiscalar multiplication obtained by the representation is 563/1574n+o(n)≈0.3577n+o(n). That number is larger than the optimal complexity 281/786n+o(n)≈0.3575n+o(n) found in our previous work. To optimize the width3 joint sparse form, we add more cases to the representation. After the addition, we can show that the complexity is updated to 281/786n+o(n)≈0.3575n+o(n), which implies that the modified representation is asymptotically optimal. Compared to our optimal algorithm in the previous work, the modified width3 joint sparse form uses less dynamic memory, but it consumes more static memory.

