Improved montgomery multiplication algorithm and its application

Computer Engineering and Applications ›› 2007, Vol. 43 ›› Issue (20): 52-55.

• 学术探讨 • Previous Articles Next Articles

Improved montgomery multiplication algorithm and its application

WANG Hong-xia¹，Wang Jin-rong^2,3，ZHAO Xian-sheng¹

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

Received:1900-01-01 Revised:1900-01-01 Online:2007-07-11 Published:2007-07-11
Contact: WANG Hong-xia

Montgomery模乘算法的改进及其应用

王红霞¹，王金荣^2,3，赵宪生¹

1.成都理工大学信息工程学院，成都610059
2.杭州师范学院信息工程学院，杭州 310018
3.浙江大学计算机科学与技术学院，杭州 310027

通讯作者: 王红霞

Abstract

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.

Key words: RSA, DSA, Montgomery multiplication algorithm

摘要： Montgomery算法是目前最适合于通用处理器软件实现的大整数模乘算法。1996年，Koc总结了该算法的五种实现方法：SOS、CIOS、FIOS、FIPS和CIHS，并指出CIOS方法综合性能较优。首先深入分析了FIOS实现方法，并通过消除进位传递和减少循环控制等手段，提出了一种改进方法IFIOS。然后将该方法应用于模幂计算，给出了基于滑动窗口技术的Montgomery模幂算法。最后理论分析和实验结果表明，该改进将FIOS的执行速度提高了约54%，与目前常用的CIOS方法相比，亦有较大的优势。

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

WANG Hong-xia¹，Wang Jin-rong^2,3，ZHAO Xian-sheng¹. Improved montgomery multiplication algorithm and its application[J]. Computer Engineering and Applications, 2007, 43(20): 52-55.

王红霞¹，王金荣^2,3，赵宪生¹. Montgomery模乘算法的改进及其应用[J]. 计算机工程与应用, 2007, 43(20): 52-55.

[1]	ZHANG Bo, XU Liming, HUANG Zhiwei, YAO Xiaopeng. Multi-objective GANs Pareto Optimality Algorithm Using Gradient Strategy [J]. Computer Engineering and Applications, 2021, 57(9): 89-95.
[2]	CHAI Xu, FANG Ming, FU Feiran, SHAO Zhen. Sight Estimation Algorithms for Examinee in Examination Room Environment [J]. Computer Engineering and Applications, 2021, 57(9): 199-206.
[3]	WU Wenlong, ZHOU Xi, WANG Yi, WANG Baoquan. WKAG：Fraud Detection Method for Imbalanced Medical Insurance Data [J]. Computer Engineering and Applications, 2021, 57(9): 247-254.
[4]	WANG Jinyu, YANG Haitao, LI Gaoyuan, ZHANG Changgong, FENG Bodi. Research Progress of Generative Adversarial Network and Its Application in Image Processing [J]. Computer Engineering and Applications, 2021, 57(8): 26-35.
[5]	ZHAI Zhengli, LI Penghui, FENG Shu. Research Overview of Adversarial Attacks on Graphs [J]. Computer Engineering and Applications, 2021, 57(7): 14-21.
[6]	LI Jian, SUN Dasong, ZHANG Beiwei. Image Restoration Using Dual-Encoder and Adversarial Training [J]. Computer Engineering and Applications, 2021, 57(7): 192-197.
[7]	WAN Mengxiang, YAO Hanbing. GAN Model for Malicious Web Training Data Generation [J]. Computer Engineering and Applications, 2021, 57(6): 124-130.
[8]	ZHANG Rui, WU Boxiong, ZHANG Liyuan, ZHANG Bo. Human Trajectory Prediction Method for Complex Scenes [J]. Computer Engineering and Applications, 2021, 57(6): 138-143.
[9]	XU Xiaochun, DONG Hongwei, WEI Chengfeng. Application of Improved CAGAN in Virtual Try-on [J]. Computer Engineering and Applications, 2021, 57(6): 152-158.
[10]	ZOU Chengming, HU Youpu. Monocular Depth Estimation in Outdoor Scene with Generative Adversarial Network [J]. Computer Engineering and Applications, 2021, 57(6): 176-183.
[11]	CHEN Renhe, LAI Zhenyi, QIAN Yurong. Improved Image Denoising Generative Adversarial Network Algorithm [J]. Computer Engineering and Applications, 2021, 57(5): 168-172.
[12]	ZHOU Huaqiang, CAO Lin, DU Kangning. Sketch Face Synthesis Based on Multi-discriminator Cyclic Generative Adversarial Network [J]. Computer Engineering and Applications, 2021, 57(3): 231-238.
[13]	XIA Hao, LYU Hongfeng, LUO Jun, CAI Nian. Survey on Deep Learning Based Image Super-Resolution [J]. Computer Engineering and Applications, 2021, 57(24): 51-60.
[14]	MA Zhihao, ZHU Xiangbin. Research on Quasi-hyperbolic Momentum Gradient for Adversarial Deep Reinforcement Learning [J]. Computer Engineering and Applications, 2021, 57(24): 90-99.
[15]	YANG Luyue, ZHANG Shumei, ZHAO Junli. Dynamic Expression Recognition with Partial Occlusion Based on Parallel Gan [J]. Computer Engineering and Applications, 2021, 57(24): 168-178.

Improved montgomery multiplication algorithm and its application

Montgomery模乘算法的改进及其应用

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics