Study on QinJiuShao algorithm and its application in RSA

doi:10.3778/j.issn.1002-8331.2008.28.023

Computer Engineering and Applications ›› 2008, Vol. 44 ›› Issue (28): 65-66.DOI: 10.3778/j.issn.1002-8331.2008.28.023

• 理论研究 • Previous Articles Next Articles

Study on QinJiuShao algorithm and its application in RSA

DONG Fu-guo¹,LI Yu-rong^1,2

1.School of Information and Electronics Engineering，Shandong Institute of Business and Technology，Yantai，Shandong 264005，China
2.School of Computer Science and Technology，Shandong University，Jinan 250100，China

Received:2007-11-19 Revised:2008-02-01 Online:2008-10-01 Published:2008-10-01
Contact: DONG Fu-guo

秦九韶算法思想在RSA密码算法中的应用研究

董付国¹,厉玉蓉^1,2

1.山东工商学院信息与电子工程学院，山东烟台 264005
2.山东大学计算机科学与技术学院，济南 250100

通讯作者: 董付国

Abstract

Abstract: This paper studies QinJiuShao algorithm for fast computation of high-rank polynomial，analyses fast algorithm of modular exponentiation in RSA，and gives its implementation.Analysis and experiment results show that computation quantity of this algorithm does not get too larger with exponentiation getting larger very fast，and may reduce when exponentiation well-selected.Computation of modular exponentiation is very low because of big plain-text group and cipher-text group，so this algorithm is of great significance to design fast algorithm of RSA and select public-key and private-key of RSA.

Key words: QinJiuShao algorithm, RSA, fast algorithm, modular exponentiation

摘要： 介绍了用于快速计算高次多项式值的“秦九韶算法”，并用类似思路分析了RSA算法中方幂模快速实现算法，最后给出了该算法的具体实现。算法分析和实验结果证明，该算法的计算量不会随着指数的快速增大而增大，通过精心选择指数，还可以减少运算量。RSA算法中明文分组和密文分组都较大，方幂模运算消耗大量的运算时间。因此，简化方幂模计算减少计算次数对设计RSA快速算法和选择密钥具有重要的指导意义。

关键词: 秦九韶算法, RSA, 快速算法, 方幂模

DONG Fu-guo¹,LI Yu-rong^1,2. Study on QinJiuShao algorithm and its application in RSA[J]. Computer Engineering and Applications, 2008, 44(28): 65-66.

董付国¹,厉玉蓉^1,2. 秦九韶算法思想在RSA密码算法中的应用研究[J]. 计算机工程与应用, 2008, 44(28): 65-66.

[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]	LI Jian, SUN Dasong, ZHANG Beiwei. Image Restoration Using Dual-Encoder and Adversarial Training [J]. Computer Engineering and Applications, 2021, 57(7): 192-197.
[6]	ZHAI Zhengli, LI Penghui, FENG Shu. Research Overview of Adversarial Attacks on Graphs [J]. Computer Engineering and Applications, 2021, 57(7): 14-21.
[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.

Study on QinJiuShao algorithm and its application in RSA

秦九韶算法思想在RSA密码算法中的应用研究

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics