Improving Width-3 Joint Sparse Form to Attain Asymptotically Optimal Complexity on Average Case
-
- IMAI Hiroshi
- Graduate School of Information Science and Technology, The University of Tokyo
-
- SUPPAKITPAISARN Vorapong
- Global Research Center for Big Data Mathematics, National Institute of Informatics ERATO Kawarabayashi Large Graph Project, JST
Abstract
In this paper, we improve a width-3 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 multi-scalar 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 width-3 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 width-3 joint sparse form uses less dynamic memory, but it consumes more static memory.
Journal
-
- IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
-
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E98.A (6), 1216-1222, 2015
The Institute of Electronics, Information and Communication Engineers
- Tweet
Keywords
Details 詳細情報について
-
- CRID
- 1390001206310821376
-
- NII Article ID
- 130005071824
- 120006904160
-
- ISSN
- 17451337
- 09168508
-
- HANDLE
- 2261/00074088
-
- Text Lang
- en
-
- Data Source
-
- JaLC
- IRDB
- Crossref
- CiNii Articles
- KAKEN
-
- Abstract License Flag
- Disallowed