1、使用伪随机数产生器产生一个奇数p
2、用概率性算法Miller-Rabin算法对p做一次素性检验。
3、算法如下：Mil盟敢势袂ler-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;i<k;i++){ if(a=p-1) return TRUE; else a=a*a mod p; } return FALSE;}。这里的格式不好读算法，可以参照下图。
4、如果p算法返回值为FALSE，表明p没有通过检验，p一定不是素数，返回步骤1；如果返回值为TRUE，表明p通过本次检验，p不是素数的概率不会多于1/4
5、重复步骤2足够多次（例如S次），如果p全都通过了检测，可判定p是素数的概率至少有（1-1/4^S）。当此概率高于可接受的阈值，则可认为p是一个素数
6、这个检验只是概率性的，并不能完全确定p是素数，因此可能会产生错误的结果。但是通过提高阈值，也就是增加检验的次数，可使p不是素数的概率接近于0
