| Montgomery模乘算法的改进及其应用 |
| |
| 引用本文： | 王红霞,王金荣,赵宪生.Montgomery模乘算法的改进及其应用[J].计算机工程与应用,2007,43(20):52-55. |
| |
| 作者姓名： | 王红霞 王金荣 赵宪生 |
| |
| 作者单位： | 成都理工大学信息工程学院，杭州师范学院信息工程学院，成都理工大学信息工程学院 成都610059，杭州310018 浙江大学计算机科学与技术学院，杭州310027，成都610059 |
| |
| 基金项目： | 浙江省自然科学基金
,
浙江省教育厅资助项目 |
| |
| 摘 要： | Montgomery算法是目前最适合于通用处理器软件实现的大整数模乘算法。1996年,Koc总结了该算法的五种实现方法:SOS、CIOS、FIOS、FIPS和CIHS,并指出CIOS方法综合性能较优。首先深入分析了FIOS实现方法,并通过消除进位传递和减少循环控制等手段,提出了一种改进方法IFIOS。然后将该方法应用于模幂计算,给出了基于滑动窗口技术的Montgomery模幂算法。最后理论分析和实验结果表明,该改进将FIOS的执行速度提高了约54%,与目前常用的CIOS方法相比,亦有较大的优势。
|
| 关 键 词： | RSA DSA Montgomery模乘算法 |
| 文章编号： | 1002-8331（2007）20-0052-04 |
| 修稿时间： | 2006-11 |
Improved montgomery multiplication algorithm and its application |
| |
| WANG Hong-xia,Wang Jin-rong,ZHAO Xian-sheng.Improved montgomery multiplication algorithm and its application[J].Computer Engineering and Applications,2007,43(20):52-55. |
| |
| Authors: | WANG Hong-xia Wang Jin-rong ZHAO Xian-sheng |
| |
| Affiliation: | 1.College of Information Engineering，Chengdu University of Technology，Chengdu 610059，China 2.College of Information Engineering，Hangzhou Teacher’s College，Hangzhou 310018，China 3.College of Computer Science，Zhejiang University，Hangzhou 310027，China |
| |
| Abstract: | Montgomery multiplication algorithm is best suited for fast software implementation on standard CPU architectures.In 1996,Koc 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. |
| |
| Keywords: | RSA DSA Montgomery multiplication algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《计算机工程与应用》浏览原始摘要信息 |
|
点击此处可从《计算机工程与应用》下载全文 |
|
