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

An Improved wNAF Scalar-Multiplication Algorithm with Low Computational Complexity

作　　者：赵石磊 杨晓秋 刘志伟 于斌 黄海 ZHAO Shi-lei;YANG Xiao-qiu;LIU Zhi-wei;YU Bin;HUANG Hai(School of Computer Science and Technology,Harbin University of Science and Technology,Harbin,Heilongjiang 150080,China)

机构地区：[1]哈尔滨理工大学计算机科学与技术学院,黑龙江哈尔滨150080

出　　处：《电子学报》2022年第4期977-983,共7页Acta Electronica Sinica

基　　金：国家重点研发计划“光电子与微电子器件及集成”重点专项子课题(No.2018YFB2202100);黑龙江省自然科学基金优秀青年项目(No.YQ2019F010);黑龙江省普通高校基本科研业务费专项资金资助(No.2019KYYWF0214)。

摘　　要：在物联网等资源受限的环境中,低计算复杂度、存储空间占用少的标量乘算法尤为重要.为了降低标量乘的计算复杂度,本文采用有符号的窗口非相邻算法(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%.It is very important that scalar multiplication algorithm has low computational complexity and less storage space in the resource constrained environment such as the Internet of things.In order to reduce the complexity of scalar multiplication,wNAF is used to generate the wNAF chain of scalar k;it replaces odd number with power of 2,and makes up the difference between power of 2 and odd by building the addition chain.At the same time,the algorithm reduces the number of precomputed points,and solves the problem that wNAF scalar multiplication is not suitable for large window width.Compared the wNAF,swNAF,and precomputation algorithm based prime,only 12 are needed to store the precomputed points,and the number of precomputed points are optimized by 98.83%,96.49%,and 94.42%,and the scalar multiplication calculation stage are optimized by 78.23%,68.94%,and 43.63%when the window width is 11.

关 键 词：标量乘 窗口非相邻算法 加法链 

分 类 号：TN918.1[电子电信—通信与信息系统]