蒋洪波，冯新宇，栾 兵，沈显庆

（1.黑龙江科技学院 黑龙江 哈尔滨 150027；2.东北农业大学 成栋学院，黑龙江 哈尔滨 150025）

椭圆曲线自引入密码学以来一直备受人们青睐，它的突出特点吸引着密码爱好者们对它的不断探索和研究，随着计算能力的增强对其实现速度也提出了更高的要求，关于实现速度的研究大部分集中在影响加密速度的几个关键点上，其中椭圆曲线上的点乘运算是研究热点之一，而研究点乘又主要集中在NAF标量乘[1]上，它们大都是将NAF算法与其他算法结合实现，没有从NAF算法本身出发提高速度，而本文则是立足NAF算法进行分析研究。在NAF算法中若NAF的长度为，那么算法中的移位运算就要进行次，该移位运算消耗了大部分的算法时间。本文提出的探测窗口法实现NAF则大大减少了算法中的移位次数，为所有基于NAF的算法提高了运算效率。该算法简单便于实现，实现效率高。

1 窗口宽度ω的AFω算法

假设实现平台的字长是W位，并且W是8的整数倍。则字U的W位，分别以W-1到0标记，且第W-1位为最高有效位。

设 f（z）是一个，次的二进制既约多项式，记做 f（z）=zm+r（z），则GF（2m）上的元素是次数最多为m-1的二进制多项式。

一个域元素a（z）=am-1zm-1+…+a2z2+a1z+a0与一个m维向量 a=（am-1，…，a2，a1，a0）相对应。 令 s=[m/W]，t=Ws-m。 软件实现时 k 用 s个 W 字的一个数组 K=（K[s-1]，…，K[1]，K[0]）来存储，最低有效位k0存储到K[0]中，并且K[s-1]的最左t位没有用（总是设置为0）。

因为域元素的移位是整体移位，因此总共只需要个s字的移位。

椭圆曲线点乘运算中，若允许利用额外的存储器和预计算，那么用加减法实现点乘可以获得更高效的点乘算法，把它叫做计算点乘的窗口方法[2]。……