A Method of Fast Prime Number Generation

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.