一种基于交错的窗口标量乘算法  

A WINDOW ALGORITHM OF SCALAR MULTIPLICATION BASED ON INTERLEAVING

作　　者：殷新春[1] 朱虹[1] 赵荣[1] 

机构地区：[1]扬州大学信息工程学院,江苏扬州225009

出　　处：《计算机应用与软件》2010年第11期32-34,共3页Computer Applications and Software

基　　金：国家自然科学基金项目(60473012);国家高技术研究发展计划基金项目(2007AA012448);江苏省六大人才高峰项目(06-E-025)

摘　　要：从研究窗口标量乘法出发,通过将交错技术与Koblitz曲线上的窗口TNAF标量乘法相结合,给出一种新的标量乘算法,该算法不对标量乘进行预计算,只是在赋值阶段施加交错。由于Frobenius映射效率高,加之使用交错技术,本算法的效率比传统窗口NAF标量乘法要高。对新算法运行时间进行分析,新算法的时间复杂性比传统窗口NAF算法大约减少60%～75%,比Comb算法大约减少70%～79%。Proceeding from studying the sliding window algorithm of scalar multiplication,by applying interleaving to window algorithm of TNAF scalar multiplication on Koblitz curve,a new scalar multiplication is proposed in this paper.The algorithm performs no pre-computation on scalar multiplication but just exerts interleaving at the valuation stage.Because of high performance of Frobenius mapping,plus making use of interleaving,the efficiency of the new algorithm is higher than traditional window algorithm of NAF scalar multiplication.Analysis on runtime of the new algorithm indicates that the time complexity of the new algorithm reduces approximately 60%～75%than that of traditional NAF window algorithm,and 70%～79%than that of Comb algorithm.

关 键 词：标量乘法 交错 Koblitz曲线Frobenius映射 窗口算法 

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