程序怎样才能快速地产生一个大素数

来源：互联网 2023-03-20 14:41:31 108

现在许多的安全加密算法都要涉及到大素数的运算，比如RSA算法的实现需要两个随机的大素数作为秘钥的“种子”。在我们实际程序编写时，也常常需要用大素数对数据进行处理。但是，如今并没有可以产生任意大素数的有效技术。然而概率性检验素性方面的许多方法已经比较成熟。下面介绍Miller—Rabin算法进行素性检测。

程序怎样才能快速地产生一个大素数？

方法/步骤

使用伪随机数产生器产生一个奇数p

程序怎样才能快速地产生一个大素数？

用概率性算法Miller-Rabin算法对p做一次素性检验。

程序怎样才能快速地产生一个大素数？

算法如下：Miller-Rabin（p）/*p大于3且为奇数，算法输出p进行素性检验的结果*/{ 把p-1写成m*2^k的形式，其中m是一个奇数; 随机选取集合{2，…，p-1}中的一个整数n;a=n^m mod p;if(a=1) return TRUE; for(i=0;ik;i ){ if(a=p-1) return TRUE; else a=a*a mod p; } return FALSE;}。这里的格式不好读算法，可以参照下图。

程序怎样才能快速地产生一个大素数？