摘要
Montgomery算法是目前最适合于通用处理器软件实现的大整数模乘算法。1996年,Koc总结了该算法的五种实现方法:SOS、CIOS、FIOS、FIPS和CIHS,并指出CIOS方法综合性能较优。首先深入分析了FIOS实现方法,并通过消除进位传递和减少循环控制等手段,提出了一种改进方法IFIOS。然后将该方法应用于模幂计算,给出了基于滑动窗口技术的Montgomery模幂算法。最后理论分析和实验结果表明,该改进将FIOS的执行速度提高了约54%,与目前常用的CIOS方法相比,亦有较大的优势。
Montgomery multiplication algorithm is best suited for fast software implementation on standard CPU architectures.In 1996,Koe has summarized its five implementations,such as SOS,CIOS,FIOS,FIPS,CIHS,and points out that the CIOS has the most efficient of all methods.Firstly,this article analyzes the FIOS method in-depth and provides an improved method of FIOS by eliminating carry propagation and decreasing the number of iteration.Second,it also puts this new method to compute modular exponentiation and gives a Montgomery modular exponentiation algorithm based on slidsing window techniques.According to this analysis and experimentation,the new method improves in its efficiency with about 54% by comparison with FIOS,and it also exceeds the CIOS which is common used method of Montgomery multiplication algorithm.
出处
《计算机工程与应用》
CSCD
北大核心
2007年第20期52-55,共4页
Computer Engineering and Applications
基金
浙江省自然科学基金(the Natural Science Foundation of Zhejiang Province of China under Grant No.Y105067)
浙江省教育厅高校科研计划项目(No.20050718)
