Research and Efficient Implementation of Miller-Rabin Algorithm

Abstract

Abstract: Miller-Rabin algorithm is the main stream probabilistic primality test algorithm, and is very important in constructing cryptography security system. When lots of primality test algorithms have been compared and Miller-Rabin algorithm has been researched in detail ,it is proved that Miller-Rabin algorithm is the best choice to be used in constructing cryptography security system to perform primality test. The performance of Miller-Rabin can be improved by optimizing the low level operations.

摘要： Miller-Rabin算法是目前主流的基于概率的素数测试算法，在构建密码安全体系中占有重要的地位。通过比较各种素数测试算法和对Miller-Rabin算法进行的仔细研究，证明在计算机中构建密码安全体系时，Miller-Rain算法是完成素数测试的最佳选择。通过对Miller-Rabin算法底层运算的优化，可以取得较以往实现更好的性能。

关键词: 素数, 算法, 时间复杂度, 误判概率, 密码学

CLC Number:

TP309

QIN Xiaodong，XIN Yunwei，LU Guizhang. Research and Efficient Implementation of Miller-Rabin Algorithm[J]. , 2002, 28(10): 63-65.

秦晓东,辛运帏,卢桂章. Miller-Rabin算法研究与优化实现[J]. , 2002, 28(10): 63-65.

/ Recommend / Download Citations

URL: https://www.ecice06.com/EN/Y2002/V28/I10/63

[1]	YUAN Huanyu, FU Jianming. Cryptographic Function Identification in Android Applications Based on Function Hooking [J]. Computer Engineering, 2026, 52(11): 250-259.
[2]	GUO Ziyun, TIAN Youliang, LI Mengqian. Adaptive Privacy-Preserving Federated Learning Scheme Based on Incentive Mechanism [J]. Computer Engineering, 2026, 52(11): 269-283.
[3]	XIE Qingqing, LIU Yuanyuan. Reference-Based Network Phishing Detection Scheme Using Large Language Model [J]. Computer Engineering, 2026, 52(11): 295-307.
[4]	SUN Tanbo, ZHONG Shuai, HU Xin'ao, WANG Liping. A Survey on Image Tampering Detection Technology Based on Tampering Features [J]. Computer Engineering, 2026, 52(11): 43-72.
[5]	LI Zaidong, CHEN Yuling, WANG Xuewei, LUO Yun. Interactive Ciphertext Expansion for Dynamic Multi-Key Fully Homomorphic Encryption [J]. Computer Engineering, 2026, 52(11): 284-294.
[6]	YANG Xiaodong, LI Muzi, MA Guozu, LI Songyu, WANG Caifen. Certificateless Anonymous Authentication Scheme Supporting Illegal Signatures Localization for Internet of Vehicles [J]. Computer Engineering, 2024, 50(6): 157-165.
[7]	WANG Dong, WANG Hejian, XUAN Jiaxing, ZHENG Shangzhuo, CHEN Bingcong. Blockchain Privacy-Traceable Deposit Scheme for Power-Dispatch Instructions [J]. Computer Engineering, 2024, 50(5): 158-166.
[8]	WANG Yiliang, ZHOU Peng, YE Wei, QI Weiqiang. Non-Intrusive Load Monitoring and Its Privacy-Preserving Scheme Based on Pyramid Network [J]. Computer Engineering, 2024, 50(5): 182-189.
[9]	XIONG Shiqiang, HE Daojing, WANG Zhendong, DU Runmeng. Review of Federated Learning and Its Security and Privacy Protection [J]. Computer Engineering, 2024, 50(5): 1-15.
[10]	DING Xiaohui, CAO Suzhen, WANG Caifen. Smart Contract-Assisted Dynamically Searchable Encryption Scheme with Forward and Backward Security [J]. Computer Engineering, 2022, 48(7): 141-150.
[11]	JIN Haibo, ZHAO Xinyue. High-Reliability Intrusion Detection Algorithm Under Conformal Prediction Framework [J]. Computer Engineering, 2022, 48(7): 130-140.
[12]	ZHANG Chao, PENG Changgen, DING Hongfa, XU Dequan. Searchable Encryption Scheme Based on China State Cryptography Standard SM9 [J]. Computer Engineering, 2022, 48(7): 159-167.
[13]	YE Qing, ZHAO Nannan, ZHAO Zongqu, QIN Panke, YAN Xixi, TANG Yongli. Efficient Fully Dynamic Group Signature Scheme from Lattice [J]. Computer Engineering, 2021, 47(2): 160-167,175.
[14]	JI Lusheng, ZHANG Guiling, YANG Jiarun. Off-Chain Personal Data Protection Scheme Based on Blockchain [J]. Computer Engineering, 2021, 47(2): 176-181,187.
[15]	ZHANG Jing, HE Zheng, GE Binghui, TANG Yongli, YE Qing. An Efficient Protocol for Millionaires' Problem and Its Application [J]. Computer Engineering, 2021, 47(2): 168-175.

Please choose a citation manager

Content to export