IEICE TRANSACTIONS on Fundamentals
Improving Width-3 Joint Sparse Form to Attain Asymptotically Optimal Complexity on Average Case
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E98-A No.6 pp.1216-1222
- Publication Date
- 2015/06/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E98.A.1216
- Type of Manuscript
- Special Section LETTER (Special Section on Discrete Mathematics and Its Applications)
- Category
Authors
Hiroshi IMAI
The University of Tokyo
Vorapong SUPPAKITPAISARN
National Institute of Informatics,JST
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Hiroshi IMAI, Vorapong SUPPAKITPAISARN, "Improving Width-3 Joint Sparse Form to Attain Asymptotically Optimal Complexity on Average Case" in IEICE TRANSACTIONS on Fundamentals,
vol. E98-A, no. 6, pp. 1216-1222, June 2015, doi: 10.1587/transfun.E98.A.1216.
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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E98.A.1216/_p
Copy
@ARTICLE{e98-a_6_1216,
author={Hiroshi IMAI, Vorapong SUPPAKITPAISARN, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Improving Width-3 Joint Sparse Form to Attain Asymptotically Optimal Complexity on Average Case},
year={2015},
volume={E98-A},
number={6},
pages={1216-1222},
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.},
keywords={},
doi={10.1587/transfun.E98.A.1216},
ISSN={1745-1337},
month={June},}
Copy
TY - JOUR
TI - Improving Width-3 Joint Sparse Form to Attain Asymptotically Optimal Complexity on Average Case
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1216
EP - 1222
AU - Hiroshi IMAI
AU - Vorapong SUPPAKITPAISARN
PY - 2015
DO - 10.1587/transfun.E98.A.1216
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E98-A
IS - 6
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - June 2015
AB - 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.
ER -
English
