A Method of Fast Prime Number Generation

YE Wenwei; MA Changshe

doi:10.6054/j.jscnun.2023028

Journal of South China Normal University (Natural Science Edition) > 2023 > 55(2): 124-128. > DOI: 10.6054/j.jscnun.2023028

YE Wenwei, MA Changshe. A Method of Fast Prime Number Generation[J]. Journal of South China Normal University (Natural Science Edition), 2023, 55(2): 124-128. DOI: 10.6054/j.jscnun.2023028

Citation:

YE Wenwei, MA Changshe. A Method of Fast Prime Number Generation[J]. Journal of South China Normal University (Natural Science Edition), 2023, 55(2): 124-128. DOI: 10.6054/j.jscnun.2023028

Citation:

YE Wenwei, MA Changshe. A Method of Fast Prime Number Generation[J]. Journal of South China Normal University (Natural Science Edition), 2023, 55(2): 124-128. DOI: 10.6054/j.jscnun.2023028

PDF (611 KB)

A Method of Fast Prime Number Generation

YE Wenwei,
MA Changshe^,

School of Computer Science, South China Normal University, Guangzhou 510631, China

More Information

Received Date: August 31, 2021
Available Online: June 13, 2023

Graphical Abstract

Abstract

Abstract

Based on the Chinese remainder theorem, the improved incremental prime number generation algorithm is improved, and the threshold prime number generation algorithm (TCPG) based on the Chinese remainder theorem is designed to improve the efficiency of large prime number generation. Specifically, the TCPG algorithm uses the Chinese remainder theorem to randomly sample small prime arrays to solve the congruence equation; after the failure of the prime test, it is not necessary to resample the entire small prime array, but only to sample the threshold random numbers, reducing the number of random number sampling, thereby improving the efficiency of the prime number generation algorithm. Finally, the TCPG algorithm is compared with the original prime number genera-tion algorithm, the incremental prime number generation algorithm, the improved incremental algorithm, the M-J special case algorithm, the improved M-J algorithm and the Chinese remainder theorem prime number generation algorithm (CRT) to analyze the average time of prime number generation. The experimental results show that the average time of generating 512 bit primes by TCPG algorithm (7.80 ms) is slightly longer than that of the improved incremental algorithm (7.73 ms). However, the shortest average time is required to generate 1 024 bit and 2 048 bit primes. The average time of generating a 512 bit prime by TCPG algorithm under Miller-Rabiin prime test algorithm is 7.80 ms, which is 1.46 ms less than that of CRT algorithm. It takes 53.30 ms to generate a 1 024 bit prime, which is 5.50 ms and 4.30 ms less than that of the improved incremental prime generation algorithm and CRT algorithm respectively. It takes 505.78 ms to generate a 2 048 bit prime, which is 106.03 ms and 54.54 ms less than that of the improved incremental prime generation algorithm and CRT algorithm, respectively.
- fast prime number generation,
- RSA digital signature algorithm,
- public-key password,
- Chinese remainder theorem

FullText(HTML)

References (15)

References

[1]	KALISKI B, STADDON J. PKCS# 1: RSA cryptography specifications version 2.0: RFC 2437[S]. [S. l. ]: RFC Editor, 1998: 1-39.
[2]	李峰, 龚宗跃, 雷翻翻, 等. 快速素数生成方法综述[J]. 密码学报, 2018, 6(4): 463-476. https://www.cnki.com.cn/Article/CJFDTOTAL-MMXB201904005.htm LI F, GONG Z Y, LEI F F, et al. Overview of fast prime numbers generation[J]. Journal of Cryptography, 2018, 6(4): 463-476. https://www.cnki.com.cn/Article/CJFDTOTAL-MMXB201904005.htm
[3]	RABIN M O. Probabilistic algorithm for testing primality[J]. Journal of Number Theory, 1980, 12(1): 128-138. doi: 10.1016/0022-314X(80)90084-0
[4]	BEAUCHEMIN P, BRASSARD G, CRÉPEAU C, et al. The generation of random numbers that are probably prime[J]. Journal of Cryptology, 1988, 1(1): 53-64. doi: 10.1007/BF00206325
[5]	BRANDT J, DAMGARD I, LANDROCK P. Speeding up prime number generation[C]//Proceedings of the International Conference on the Theory and Application of Cryptology Fujiyosida. Berlin: Springer, 1991: 440-449.
[6]	BRANDT J, DAMGÅRD I. On generation of probable primes by incremental search[C]//Advances in Crypto-logy-CRYPTO'92. Berlin: Springer, 1992: 358-370.
[7]	JOYE M, PAILLIER P, VAUDENAY S. Efficient generation of prime numbers[C]//Cryptographic Hardware and Embedded Systems-CHES 2000. Berlin: Springer, 2000: 340-354.
[8]	JOYE M, PALIIER P. Fast generation of prime numbers on portable devices: an update[C]//Proceedings of the 8th International Conference on Cryptographic Hardware and Embedded Systems. Berlin: Springer, 2006: 160-173.
[9]	雷文, 邱玲, 张弘. 一种大素数快速生成算法设计与实现[J]. 四川理工学院学报(自然科学版), 2011, 24(3): 313-316. doi: 10.3969/j.issn.1673-1549.2011.03.020 LEI W, QIU L, ZHANG H. Design and implement of a fast big prime generation algorithm[J]. Journal of Sichuan University of Science and Technology(Natural Science Edition), 2011, 24(3): 313-316. doi: 10.3969/j.issn.1673-1549.2011.03.020
[10]	汤鹏志, 李彪. 基于频率的大素数高效生成算法[J]. 华东交通大学学报, 2011, 28(5): 52-56. https://www.cnki.com.cn/Article/CJFDTOTAL-HDJT201105013.htm TANG P Z, LI B. Efficient generation algorithm of big prime number based on frequency[J]. Journal of East China Jiaotong University, 2011, 28(5): 52-56. https://www.cnki.com.cn/Article/CJFDTOTAL-HDJT201105013.htm
[11]	郑朝霞, 吴旭峰, 季媛媛, 等. RSA中大素数生成算法优化及电路实现[J]. 华中科技大学学报(自然科学版), 2017, 45(6): 1-4. https://www.cnki.com.cn/Article/CJFDTOTAL-HZLG201706001.htm ZHENG C X, WU X F, JI Y Y, et al. Algorithm optimization and implementation of RSA big prime number genenration[J]. Journal of Huazhong University of Science and Technology(Natural Science Edition), 2017, 45(6): 1-4. https://www.cnki.com.cn/Article/CJFDTOTAL-HZLG201706001.htm
[12]	刘彦鑫. 基于中国剩余定理的素数搜索算法[J]. 网络安全技术与应用, 2019(6): 27-28. https://www.cnki.com.cn/Article/CJFDTOTAL-WLAQ201906017.htm
[13]	CLAVIER C, CORON J S. On the implementation of a fast prime generation algorithm[C]//Cryptographic Hardware and Embedded Systems-CHES 2007. Berlin: Springer, 2007: 443-449.
[14]	FINKE T, GEBHARDT M, SCHINDLER W. A new side-channel attack on RSA prime generation[C]//Cryptographic Hardware and Embedded Systems-CHES 2009. Berlin: Springer, 2009: 141-155.
[15]	游新娥, 田华娟. 一种快速的强素数生成方法[J]. 通信技术, 2009, 42(2): 323-325. doi: 10.3969/j.issn.1002-0802.2009.02.112 YOU X E, TIAN H J. A fast strong prime generation method[J]. Communications Technology, 2009, 42(2): 323-325. doi: 10.3969/j.issn.1002-0802.2009.02.112

Cited By

Cited by

Periodical cited type(0)

Other cited types(6)

Get Citation

PDF

XML

Article views (237) PDF downloads (51) Cited by(6)

Turn off MathJax

Article Contents

Abstract

References

A Method of Fast Prime Number Generation

Abstract

References

Cited by

Periodical cited type(0)

Other cited types(6)

Catalog

Export File

Citation

Format

Content