摘要： 分析Montgomery模乘算法的设计思想和模平方中乘法的计算过程，通过引入两种新的平方计算方法以及对Montgomery算法的优化，提出适合于通用32位处理器实现的Montgomery模平方算法。将该方法应用于模幂计算，给出基于滑动窗口技术的Montgomery模幂算法。实验结果表明，该算法能将模幂的计算速度提高9%~12%。

关键词: RSA公钥, DSA公钥, Montgomery模乘算法

Abstract: This paper analyzes the basic design principle of Montgomery algorithm and the computing produce of multiplication in computing modular squaring. By adopting two new methods of computing squaring and optimizing Montgomery algorithm for squaring, it proposes the Montgomery modular squaring algorithm which is best suited for standard 32-bit processors. It also applies this new method to modular exponentiation and gives a Montgomery modular exponentiation algorithm based on sliding window techniques. According to experimentation, the new algorithm improves its efficiency with 9%~12%.

Key words: RSA, DSA, Montgomery modular multiplication algorithm

中图分类号: 

• TP309