快速素数生成方法综述

Overview of Fast Prime Numbers Generation

很多非对称密码算法都使用素数,有些算法的安全性完全基于素数的质量和保密性.而生成大素数是非常耗时的,因此研究素数的快速生成是必要的.本文总结对比近年来提出的快速素数生成算法,将素数生成划分为生成与小素数乘积互素的数、素数生成主体和素数检测三个阶段,分别研究各阶段的算法.生成与小素数乘积互素的数中介绍了查表法、模搜索法和改进的模搜索法;素数生成主体部分包括原生算法、增量生成算法及其改进和M-J生成算法及其改进;然后研究了概率素数检测算法并给出提高其性能的一些技巧.并给出软件实现上述算法的性能对比结果,给算法的选取提供依据.最后给出了一个素数生成的应用场景.

Prime numbers are used in many asymmetric cryptographic algorithms.The security of some algorithms is based on the quality and the secrecy of the prime numbers.The generation of large prime numbers is time-consuming,so the study of fast generation of primes is necessary.This paper summarizes and compares the fast prime number generation algorithms proposed in recent years, and divides the generation of prime number into three stages:generating a number which is co-prime with the product of small primes,the main process of prime number generation,and primality test. The algorithm of each stage is studied separately.Table-based method,modular search method,and modified modular search method are studied in the section of generating a number co-prime with the product of small primes.The main process of prime number generation includes five methods,such as classical generation algorithm,incremental generation algorithm and its improvement,M-J generation algorithm and its improvement.Then probabilistic primality test algorithm is studied and some skills of improving its performance are given.The performance comparison result of these algorithms is given,which provides the basis for selecting a prime generation method.Finally,an application of the fast generation of prime numbers is presented.