一种低复杂度的改进wNAF标量乘算法

作者：赵石磊; 杨晓秋; 刘志伟; 于斌; 黄海^*

来源：电子学报, 2022, 50(04): 977-983.

• 标量乘
• 窗口非相邻算法
• 加法链

在物联网等资源受限的环境中,低计算复杂度、存储空间占用少的标量乘算法尤为重要.为了降低标量乘的计算复杂度,本文采用有符号的窗口非相邻算法(window width-Non-Adjacent Form,wNAF)生成标量k的wNAF链;用2n替换wNAF链中的奇数,替换后的差值则通过构造微小的加法链进行弥补.该算法能降低预计算点的个数,解决wNAF标量乘不适用于窗口宽度较大的问题.相较于wNAF算法、swNAF算法和基于素数预计算的算法,当窗口宽度为11时,该算法只需要12个预计算点,预计算点分别减少了98.83%,96.49%和94.42%,标量乘计算复杂度优化了78.23%,68.94%和43.63%.

• 单位
  哈尔滨理工大学