素数确定性算法分析

Prime Number Determinacy Algorithm Analysis

在计算机技术以及密码学高速发展的阶段,提升生成大素数的效率,构建素数库已成为行业趋向。为了探索素数确定性算法的效率和稳定性,提出用算法执行时间和时间曲线斜率的分析方法。通过改进素数确定性算法,计算10个n(n106)以内所有的素数,各类算法所需的执行时间,得出算法执行时间曲线来判断算法的效率和稳定性。在结果中,算法执行时间越短算法的效率越高,时间曲线切点斜率越小算法的稳定性越高,得出筛法的执行效率和稳定性远高于试除法、6k±1法优于奇偶过滤法。

With rapid development of computer technology and cryptology,improving the efficiency of generating of large prime number and constructing the prime number library have become the trend of computer industry.To explore the efficiency and stability of the algorithm,propose the algorithm execution time method and slope analysis of time curve method.With the improved prime number determinacy algorithm,calculate the time it needs to obtain all the prime numbers within nn≥106 and do it ten times,in order to get the algorithm execution time and time curve to prove the efficiency and stability of the algorithm.The results prove that efficiency is higher while the algorithm execution time shorter,at the same time stability is higher while time curve slope smaller.The execution efficiency and stability of the algorithm is much better than trial division,and 6k±1 method is superior to parity filtering.