随机化算法素数测试问题

A. 求教用C++编写产生随机大素数程序，以及验证输入的数为素数的各种思路方法

以前我写过一个求打整数的程序，可以给你解释下大概的思路
先说说大整数怎么定义吧，我是用一个类来写的，支持1024位的大整数，整数是用数组来装的，长度可以自己设。然后定义了相关的成员函数，如四则运算，当然也包含了你所说的素性检测。这里用的素性检测的算法是拉宾米勒算法，这个算法可以判断大整数是否有可能是素数，函数名为Rab。如果你想得到大素数，可以看看素性检测相关的资料，拉宾米勒算法是最常用的算法。类里也写了个GetPrime函数用于获得大素数。类的定义如下：
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#define BI_MAXLEN 64

class CBigNumber
{
public:
//大数在0x100000000进制下的长度
unsigned m_nLength;
//用数组记录大数在0x100000000进制下每一位的值
unsigned long m_ulValue[BI_MAXLEN];

CBigNumber();
~CBigNumber();

/*****************************************************************
基本操作与运算
Mov，赋值运算，可赋值为大数或普通整数
Cmp，比较运算，比较两个大数或两个普通整数的大小
Add，加，求大数与大数或大数与普通整数的和
Sub，减，求大数与大数或大数与普通整数的差
Mul，乘，求大数与大数或大数与普通整数的积
Div，除，求大数与大数或大数与普通整数的商
Mod，模，求大数与大数或大数与普通整数的模
Pow，乘方，求大数与普通整数的乘方
*****************************************************************/
void Mov(unsigned __int64 A);
void Mov(CBigNumber A);
CBigNumber Add(CBigNumber A);
CBigNumber Sub(CBigNumber A);
CBigNumber Mul(CBigNumber A);
CBigNumber Div(CBigNumber A);
CBigNumber Mod(CBigNumber A);
CBigNumber Add(unsigned long A);
CBigNumber Sub(unsigned long A);
CBigNumber Mul(unsigned long A);
CBigNumber Div(unsigned long A);
unsigned long Mod(unsigned long A);
int Cmp(CBigNumber A);
CBigNumber Pow(unsigned long A);

/*****************************************************************
输入输出
Get，从字符串按10进制或16进制格式输入到大数
Put，将大数按10进制或16进制格式输出到字符串
*****************************************************************/
// void Get(unsigned char *str, UINT len);
CBigNumber Get(unsigned char *str, unsigned long len);
void Put10(CString &str);
void Put256(CString &str);
void Put16(CString &str);
void Putchar(CString &str);

/*****************************************************************
RSA相关运算
Rab，拉宾米勒算法进行素数测试
Euc，欧几里德算法求解同余方程
Mon，蒙格马利法进行幂模运算
GetPrime，产生指定长度的随机大素数
*****************************************************************/
int Rab();
CBigNumber Euc(CBigNumber A);

//CBigNumber RsaTrans(CBigNumber A, CBigNumber B);
CBigNumber Mon(CBigNumber A, CBigNumber B);
void GetPrime(int bits);
};

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
最后提醒楼主一点，大素数不是靠从1到那个数减1那样算的，因为那样真的很慢的
还有，这个只是一个类的定义，实现部分你可以按自己的想法定义，当然如果有不懂可以找我，我有它的实现部分

B. 素性测试的随机算法

费马测试 利用费马小定理来测试。 Miller-Rabin 质数测试 欧拉-雅科比测试 对于N，挑选任意的M，测试（M/N）≡M^[(N-1)/2]。如果不成立，则N为合数。否则N有一半的机率是质数。
上下素性判定法
首先，本文英文字母都表示整数，上半部B 》3N 》W，下半部B 》W 》3N。大于3的素数只有6N-1和6N+1两种形式，我们只需判定这两种数是素数还是合数即可。命题 1 对于B=36N+1 形数而言。若不定方程（3N）^2+N-（B-1）/36=W^2 有整数解，则 6（3N-W）+1 是小因子数；6（3N+W）+1 是大因子数。若不定方程 （3N）^2-N-（B-1）/36=W^2 有整数解，则 6（3N-W）-1 是小因子数；6（3N+W）-1 是大因子数。两式都无解，是素数。命题 2对于B=36N+7 形数而言。若不定方 （3N）^2+4N-（B-7）/36=W^2+W 有整数解，则 6（3N-W）+1 是小因子数，6（3N+W+1）+1 是大因子数。若不定方程 （3N+2）^2+2N+2-（B+29）/36=W^2+W 有整数解，则 6（3N+2-W）-1 是小因子数，6（3N+W+3）-1 是大因子数。两式都无解，是素数。命题 3对于B=36N+13 形数而言。若不定方程 （3N+1）^2+N-（B-13）/36=W^2 有整数解，则 6（3N+1-W）+1 是小因子数，6（3N+1+W）+1是大因子数。若不定方程 （3N+2）^2-N-（B+23）/36=W2 有整数解，则 6（3N+2-W）-1 是小因子数，6（3N+2+W）-1是大因子数。两式都无解，是素数。命题 4 对于B=36N+19 形数而言。若不定方程（3N+1）^2+4N+1-（B-19）/36=W^2 +W 有整数解，则 6（3N+1-W）+1 是小因子数；6（3N+2+W）+1 是大因子数。若不定方程 （3N+1）^2+2N+1-（B+17）/36=W^2 +W 有整数解，则 6（3N+1-W）-1 是小因子数；6（3N+2+W）-1 是大因子数。两式都无解，是素数。命题 5 对于B=36N+25 形数而言。若不定方 （3N+2）^2+N-（B-25）/36=W^2有整数解，则 6（3N+2-W）+1 是小因子数，6（3N+2+W）+1 是大因子数。若不定方程 （3N+1）^2-N-（B+11）/36=W^2有整数解，则 6（3N+1-W）-1 是小因子数，6（3N+1+W）-1 是大因子数。两式都无解，是素数。命题 6 对于B=36N+31 形数而言。若不定方程 （3N+2）^2+4N+2-（B-31）/36=W^2 +W 有整数解，则 6（3N+2-W）+1 是小因子数，6（3N+3+W）+1是大因子数。若不定方程 （3N+1）^2-4N-1-（B+5）/36=W^2+W有整数解，则 6（3N-W）-1 是小因子数，6（3N+1+W）-1是大因子数。两式都无解，是素数。命题 7对于B=36N-1 形数而言。若不定方程（3N）^2-N+（B-1）/36=W^2 有整数解，则 6（3N-W）+1 是小因子数；6（3N+W）-1 是大因子数。若不定方程 （3N）^2+N+（B-1）/36=W^2 有整数解，则 6（W-3N）-1 是小因子数；6（W+3N）+1 是大因子数。两式都无解，是素数。命题 8对于B=36N+5 形数而言。若不定方 （3N）^2+2N+（B-5）/36=W^2+W 有整数解，则 6（W-3N）+1 是小因子数，6（W+3N+1）-1 是大因子数。若不定方程 （3N+2）^2+4N+2+（B+31）/36=W^2+W 有整数解，则 6（W-3N-2）-1 是小因子数，6（W+3N+3）+1 是大因子数。两式都无解，是素数。命题 9对于B=36N+11 形数而言。若不定方程 （3N+1）^2-N+（B-11）/36=W^2 有整数解，则 6（W-3N-1）+1 是小因子数，6（W+3N+1）-1是大因子数。若不定方程 （3N+2）^2+N+(B+25）/36=W2 有整数解，则 6(W-3N-2）-1 是小因子数，6（W+3N+2）+1是大因子数。两式都无解，是素数。命题 10 对于B=36N+17 形数而言。若不定方程（3N+1）^2+2N+1+（B-17）/36=W^2 +W 有整数解，则 6（W-3N-1）+1 是小因子数；6（W+3N+2）-1 是大因子数。若不定方程 （3N+1）^2+4N+1+（B+19）/36=W^2 +W 有整数解，则 6（W-3N-1）-1 是小因子数；6（W+3N+2）+1 是大因子数。两式都无解，是素数。命题 11 对于B=36N+23 形数而言。若不定方 （3N+2）^2-N+（B-23）/36=W^2有整数解，则 6（W-3N-2）+1 是小因子数，6（W+3N+2）+1 是大因子数。若不定方程 （3N+1）^2+N+（B+13）/36=W^2有整数解，则 6（W-3N-1）-1 是小因子数，6（W+3N+1）+1 是大因子数。两式都无解，是素数。命题 12 对于B=36N+31 形数而言。若不定方程 （3N+2）^2+2N+2+（B-29）/36=W^2 +W 有整数解，则 6（W-3N-2）+1 是小因子数，6（W+3N+3）-1是大因子数。若不定方程 （3N）^2-4N+（B+7）/36=W^2+W有整数解，则 6（W-3N）-1 是小因子数，6（W+3N+1）+1是大因子数。两式都无解，是素数。

C. 如何用VC++随机生成一个大素数（满足RSA算法）

你需要的包含在这个程序中，生成一个大数然后做RM素数测试，通过的我们假设其为素数即可！

RSA算法
1978年就出现了这种算法，它是第一个既能用于数据加密也能用于数字签名的算法。它易于理解和操作，也很流行。算法的名字以发明者的名字命名：Ron Rivest, AdiShamir 和Leonard Adleman。但RSA的安全性一直未能得到理论上的证明。
RSA的安全性依赖于大数难于分解这一特点。公钥和私钥都是两个大素数（大于100个十进制位）的函数。据猜测，从一个密钥和密文推断出明文的难度等同于分解两个大素数的积。
密钥对的产生。选择两个大素数，p 和q 。计算：n = p * q 然后随机选择加密密钥e，要求 e 和 ( p - 1 ) * ( q - 1 )互质。最后，利用Euclid 算法计算解密密钥d, 满足e * d = 1 ( mod ( p - 1 ) * ( q - 1 ) )其中n和d也要互质。数e和n是公钥，d是私钥。两个素数p和q不再需要，应该丢弃，不要让任何人知道。加密信息 m（二进制表示）时，首先把m分成等长数据块 m1 ,m2,..., mi ，块长s，其中 2^s <= n, s 尽可能的大。对应的密文是：ci = mi^e ( mod n ) ( a ) 解密时作如下计算：mi = ci^d ( mod n ) ( b )
RSA 可用于数字签名，方案是用 ( a ) 式签名， ( b )式验证。具体操作时考虑到安全性和 m信息量较大等因素，一般是先作HASH 运算。RSA 的安全性。RSA的安全性依赖于大数分解，但是否等同于大数分解一直未能得到理论上的证明，因为没有证明破解RSA就一定需要作大数分解。假设存在一种无须分解大数的算法，那它肯定可以修改成为大数分解算法。目前，RSA的一些变种算法已被证明等价于大数分解。不管怎样，分解n是最显然的攻击方法。现在，人们已能分解140多个十进制位的大素数。因此，模数n必须选大一些，因具体适用情况而定。
由于进行的都是大数计算，使得RSA最快的情况也比DES慢上100倍，无论是软件还是硬件实现。速度一直是RSA的缺陷。一般来说只用于少量数据加密。
*/
#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;//RSA算法所需参数
typedef struct RSA_PARAM_Tag
{
unsigned __int64 p, q; //两个素数，不参与加密解密运算
unsigned __int64 f; //f=(p-1)*(q-1)，不参与加密解密运算
unsigned __int64 n, e; //公匙，n=p*q，gcd(e,f)=1
unsigned __int64 d; //私匙，e*d=1 (mod f)，gcd(n,d)=1
unsigned __int64 s; //块长，满足2^s<=n的最大的s，即log2(n)
} RSA_PARAM;//小素数表
const static long g_PrimeTable[]=
{
3,
5,
7,
11,
13,
17,
19,
23,
29,
31,
37,
41,
43,
47,
53,
59,
61,
67,
71,
73,
79,
83,
89,
97
};
const static long g_PrimeCount=sizeof(g_PrimeTable) / sizeof(long);const unsigned __int64 multiplier=12747293821;
const unsigned __int64 adder=1343545677842234541;//随机数类
class RandNumber
{

private:
unsigned __int64 randSeed;
public:
RandNumber(unsigned __int64 s=0);
unsigned __int64 Random(unsigned __int64 n);
};
RandNumber::RandNumber(unsigned __int64 s)
{
if(!s)
{
randSeed= (unsigned __int64)time(NULL);
}
else
{
randSeed=s;
}
}
unsigned __int64 RandNumber::Random(unsigned __int64 n)
{
randSeed=multiplier * randSeed + adder;
return randSeed % n;
}static RandNumber g_Rnd;
inline unsigned __int64 MulMod(unsigned __int64 a, unsigned __int64 b, unsigned __int64 n)
{
return a * b % n;
}
unsigned __int64 PowMod(unsigned __int64 &base, unsigned __int64 &pow, unsigned __int64 &n)
{
unsigned __int64 a=base, b=pow, c=1;
while(b)
{
while(!(b & 1))
{
b>>=1; //a=a * a % n; //函数看起来可以处理64位的整数，但由于这里a*a在a>=2^32时已经造成了溢出，因此实际处理范围没有64位
a=MulMod(a, a, n);
} b--; //c=a * c % n; //这里也会溢出，若把64位整数拆为两个32位整数不知是否可以解决这个问题。
c=MulMod(a, c, n);
} return c;
}
long RabinMillerKnl(unsigned __int64 &n)
{
unsigned __int64 b, m, j, v, i;
m=n - 1;
j=0; //0、先计算出m、j，使得n-1=m*2^j，其中m是正奇数，j是非负整数
while(!(m & 1))
{
++j;
m>>=1;
} //1、随机取一个b，2<=b<n-1
b=2 + g_Rnd.Random(n - 3); //2、计算v=b^m mod n
v=PowMod(b, m, n); //3、如果v==1，通过测试
if(v == 1)
{
return 1;
} //4、令i=1
i=1; //5、如果v=n-1，通过测试
while(v != n - 1)
{
//6、如果i==l，非素数，结束
if(i == j)
{
return 0;
} //7、v=v^2 mod n，i=i+1
unsigned __int64 tmp1 = 2;
v=PowMod(v,tmp1, n);
++i; //8、循环到5
} return 1;
}
long RabinMiller(unsigned __int64 &n, long loop)
{
//先用小素数筛选一次，提高效率
for(long i=0; i < g_PrimeCount; i++)
{
if(n % g_PrimeTable[i] == 0)
{
return 0;
}
} //循环调用Rabin-Miller测试loop次，使得非素数通过测试的概率降为(1/4)^loop
for(long i=0; i < loop; i++)
{
if(!RabinMillerKnl(n))
{
return 0;
}
} return 1;
}
unsigned __int64 RandomPrime(char bits)
{
unsigned __int64 base;
do
{
base= (unsigned long)1 << (bits - 1); //保证最高位是1
base+=g_Rnd.Random(base); //再加上一个随机数
base|=1; //保证最低位是1，即保证是奇数
} while(!RabinMiller(base, 30)); //进行拉宾－米勒测试30次
return base; //全部通过认为是素数
}
unsigned __int64 EuclidGcd(unsigned __int64 &p, unsigned __int64 &q)
{
unsigned __int64 a=p > q ? p : q;
unsigned __int64 b=p < q ? p : q;
unsigned __int64 t;
if(p == q)
{
return p; //两数相等，最大公约数就是本身
}
else
{
while(b) //辗转相除法，gcd(a,b)=gcd(b,a-qb)
{
a=a % b;
t=a;
a=b;
b=t;
} return a;
}
}
unsigned __int64 SteinGcd(unsigned __int64 &p, unsigned __int64 &q)
{
unsigned __int64 a=p > q ? p : q;
unsigned __int64 b=p < q ? p : q;
unsigned __int64 t, r=1;
if(p == q)
{
return p; //两数相等，最大公约数就是本身
}
else
{
while((!(a & 1)) && (!(b & 1)))
{
r<<=1; //a、b均为偶数时，gcd(a,b)=2*gcd(a/2,b/2)
a>>=1;
b>>=1;
} if(!(a & 1))
{
t=a; //如果a为偶数，交换a，b
a=b;
b=t;
} do
{
while(!(b & 1))
{
b>>=1; //b为偶数，a为奇数时，gcd(b,a)=gcd(b/2,a)
} if(b < a)
{
t=a; //如果b小于a，交换a，b
a=b;
b=t;
} b=(b - a) >> 1; //b、a都是奇数，gcd(b,a)=gcd((b-a)/2,a)
} while(b);
return r * a;
}
}
unsigned __int64 Euclid(unsigned __int64 &a, unsigned __int64 &b)
{
unsigned __int64 m, e, i, j, x, y;
long xx, yy;
m=b;
e=a;
x=0;
y=1;
xx=1;
yy=1;
while(e)
{
i=m / e;
j=m % e;
m=e;
e=j;
j=y;
y*=i;
if(xx == yy)
{
if(x > y)
{
y=x - y;
}
else
{
y-=x;
yy=0;
}
}
else
{
y+=x;
xx=1 - xx;
yy=1 - yy;
} x=j;
} if(xx == 0)
{
x=b - x;
} return x;
}
RSA_PARAM RsaGetParam(void)
{
RSA_PARAM Rsa={ 0 };
unsigned __int64 t;
Rsa.p=RandomPrime(16); //随机生成两个素数
Rsa.q=RandomPrime(16);
Rsa.n=Rsa.p * Rsa.q;
Rsa.f=(Rsa.p - 1) * (Rsa.q - 1);
do
{
Rsa.e=g_Rnd.Random(65536); //小于2^16，65536=2^16
Rsa.e|=1; //保证最低位是1，即保证是奇数，因f一定是偶数，要互素，只能是奇数
} while(SteinGcd(Rsa.e, Rsa.f) != 1); Rsa.d=Euclid(Rsa.e, Rsa.f);
Rsa.s=0;
t=Rsa.n >> 1;
while(t)
{
Rsa.s++; //s=log2(n)
t>>=1;
} return Rsa;
}
void TestRM(void)
{
unsigned long k=0;
cout << " - Rabin-Miller prime check.n" << endl;
for(unsigned __int64 i=4197900001; i < 4198000000; i+=2)
{
if(RabinMiller(i, 30))
{
k++;
cout << i << endl;
}
} cout << "Total: " << k << endl;
}
void TestRSA(void)
{
RSA_PARAM r;
char pSrc[]="abcdefghijklmnopqrstuvwxyz";
const unsigned long n=sizeof(pSrc);
unsigned char *q, pDec[n];
unsigned __int64 pEnc[n];
r=RsaGetParam();
cout << "p=" << r.p << endl;
cout << "q=" << r.q << endl;
cout << "f=(p-1)*(q-1)=" << r.f << endl;
cout << "n=p*q=" << r.n << endl;
cout << "e=" << r.e << endl;
cout << "d=" << r.d << endl;
cout << "s=" << r.s << endl;
cout << "Source:" << pSrc << endl;
q= (unsigned char *)pSrc;
cout << "Encode:";
for(unsigned long i=0; i < n; i++)
{
unsigned __int64 tmp2 = q[i];
pEnc[i]=PowMod(tmp2, r.e, r.n);
cout << hex << pEnc[i] << " ";
} cout << endl;
cout << "Decode:";
for(unsigned long i=0; i < n; i++)
{
pDec[i]=PowMod(pEnc[i], r.d, r.n);
cout << hex << (unsigned long)pDec[i] << " ";
} cout << endl;
cout << (char *)pDec << endl;
}
int main(void)
{
TestRSA();
return 0;
}

D. 讲解一下判素数的问题。.

首先，素数的概念
素数，也就是质数，除了1和自己本身，不能被其它数整除的自然数，称为素数。
然后为了找出这个数n是不是素数，基础算法就是从1测试到n，看看是不是存在一个数i 可以整除n // if(n%i==0)break;
那么，思考一下，就会发现，其实只要测试到k=sqrt(n)函数返回的值就可以了。这个函数是开根的意思。
然后，这个程序是为了找出101 --> 200之间的素数，至于步长为2，
当然是因为102，104，106等等根本就不可能是素数。

另，(float) 操作是把后面的数字转换成float格式。

E. 设计一个程序，判断一个十二位的整数是否为素数，也就是说判断一个很大的数是否为素数。

有一种办法是对大数的随机测试 准确率很高 （不保证100%）
你可以搜索 随机化算法（Monte Carlo）算法

还有一种是生成六位数以内的素数并保存
然后将你要测试的数作为long long或者__int64来除这些素数知道其平方根大，如果没有可以除尽的就是素数

F. 求解···java题目随机生成100个1000以内的整数，将这100个整数中的素数找出来并写到一个文本文件中。

import java.util.Random;
import java.io.*;
public class Test{
public static void main(String[] args) throws IOException
{
int[] arr = init();
PrintWriter bw = new PrintWriter(new FileOutputStream("text.txt"));
for(int i=0;i<arr.length;i++){
if(isPrime(arr[i])){
bw.print(arr[i] + ",");
}
}
bw.flush();
bw.close();

}
public static int[] init(){
int[] temp = new int[100];
for(int i=0;i<temp.length;i++){
temp[i] = new Random().nextInt(1000);
}
return temp;
}
public static boolean isPrime(int num) { //判断一个数是否为素数
for(int i = 2; i <= Math.sqrt(num); i++) {//程序默认2是素数，当j=2时，循环不执行
if(num % i == 0) {
return false;
}
}
return true;
}
}

G. C语言 设计并实现一种大素数随机生成方法； 实现一种快速判定任意一个大数是否是素数方法 跪求啊

Rabin -Miller算法是典型的验证一个数字是否为素数的方法。判断素数的方法是Rabin-Miller概率测试，那么他具体的流程是什么呢。假设我们要判断n是不是素数，首先我们必须保证n 是个奇数，那么我们就可以把n 表示为 n = (2^r)*s+1,注意s 也必须是一个奇数。然后我们就要选择一个随机的整数a (1<=a<=n-1)，接下来我们就是要判断 a^s=1 (mod n) 或a^((2^j)*s)= -1（mod n）(0<=j如果任意一式成立，我们就说n通过了测试，但是有可能不是素数也能通过测试。所以我们通常要做多次这样的测试，以确保我们得到的是一个素数。（DDS的标准是要经过50次测试）
采用Rabin-Miller算法进行验算
首先选择一个代测的随机数p，计算b，b是2整除p-1的次数。然后计算m，使得n=1+(2^b)m。
（1） 选择一个小于p的随机数a。
（2） 设j=0且z=a^m mod p
（3） 如果z=1或z=p-1，那麽p通过测试，可能使素数
（4） 如果j>0且z=1, 那麽p不是素数
（5） 设j=j+1。如果j且z<>p-1,设z=z^2 mod p，然后回到(4)。如果z=p-1，那麽p通过测试，可能为素数。
（6） 如果j=b 且z<>p-1，不是素数

#include<iostream.h>
#include<time.h>
#include<stdlib.h>

//随机数产生器
//产生m~n之间的一个随机数
unsigned long random(unsigned long m,unsigned long n)
{
srand((unsigned long)time(NULL));
return(unsigned long)(m+rand()%n);
}
//模幂函数
//返回X^YmodN
long PowMod(long x,long y,long n)
{
long s,t,u;

s=1;t=x;u=y;
while(u){
if(u&1)s=(s*t)%n;
u>>=1;
t=(t*t)%n;
}
return s;
}

//Rabin-Miller素数测试，通过测试返回1，否则返回0。
//n是待测素数。
//注意：通过测试并不一定就是素数，非素数通过测试的概率是1/4

int RabinMillerKnl(unsigned long n)
{
unsigned long b,m,j,v,i;
//先计算出m、j，使得n-1=m*2^j，其中m是正奇数，j是非负整数
m=n-1;
j=0;
while(!(m&1))
{
++j;
m>>=1;
}
//随机取一个b，2<=b<n-1
b=random(2,m);
//计算v=b^mmodn
v=PowMod(b,m,n);
//如果v==1，通过测试
if(v==1)
{
return 1;
}

i=1;
//如果v=n-1，通过测试
while(v!=n-1)
{
//如果i==l，非素数，结束
if(i==j)
{
return 0;
}
//v=v^2modn，i=i+1
v=PowMod(v,2,n);
i++;
}
return 1;
}
intmain()
{
unsigned long p;
int count=0;
cout<<"请输入一个数字"<<endl;
cin>>p;
for(int temp=0;temp<5;temp++)
{
if(RabinMillerKnl(p))
{
count++;
}
else
break;

}

if(count==5)
cout<<"一共通过5次测试，是素数！"<<endl;
else
cout<<"不是素数"<<endl;
return 0;
}

H. 如何快速检查一个素数的素性（算法）

算好,我以前也研究过素数问题.现在资料还保存着.. 拿来给你分享吧. (这个算法检测速度,还是很快的,你可以试试看哦~~)

一种适合32位机器数的确定性素数判定法

作者：

王浩（[email protected]）

此论文是为发布个人研究成果与大家分享交流而提交，本人教育背景如下：

计算机应用专业/管理工程专业双学士

天津大学

于1995年到1999年在校就读

日期________________2006-11-28___________________

摘要

一种适合32位机器数的确定性素数判定法

作者：王浩

本文通过对米勒-拉宾非确定性素数判定法如何转化为确定性素数判定法的研究，发现了与之相关的伪素数的一些性质，引入了伪素数的最小可判定底数的概念，并总结出了一些规律。通过这些规律找出了一种特别适合32位机器数的确定性素数判定法，该方法对于32位机器数进行素数判定最多只需要进行16log(n) 次乘/除法。该方法具有实现简单、速度快的优点，非常具有推广价值。

本文中总结出的一些规律如果能够得到证明和推广，则有可能彻底解决把米勒-拉宾非确定性素数判定法转化为确定性素数判定法的问题，从而对素数判定理论和实践产生一定的促进作用。

本文共有五章。分述如下：

第一章：讲述素数判定法的现状，列举了目前常用的一些素数判定法及其适用范围。

第二章：讲解伪素数表生成过程。

第三章：分析伪素数表，引入了伪素数的最小可判定底数的概念，并且总结出了一些规律。根据这些规律，找出了一种特别适合32位机器数的确定性素数判定法，并且进行了多种优化，给出了时间复杂度分析。

第四章：算法的C++语言实现和解释说明。

第五章：算法的可推广性分析和未来发展展望。

目录

第一章 素数判定法现状... 1

第二章 2-伪素数表的生成... 2

第三章 寻找2-伪素数的最小可判定底数... 3

第四章 算法实现和解释... 5

第五章 算法可推广性分析... 8

参考文献... 9

词汇表

素数判定法：判定一个自然数是否素数的方法。

确定性素数判定法：一个素数判定法判定某个自然数为素数的充要条件是该自然数确实是素数，该判定法就是确定性素数判定法。即该判定法不存在误判的可能性。

32位机器数：在计算机上用32个二进制位表示的无符号整数。

64位机器数：在计算机上用64个二进制位表示的无符号整数。

第一章 素数判定法现状

现在，确定性素数判定法已经有很多种，常用的有试除法、威廉斯方法、艾德利曼和鲁梅利法。它们的适用范围各不相同，威廉斯方法比较适合10^20到10^50之间的数，艾德利曼和鲁梅利法适合大于10^50的数，对于32位机器数，由于都小于10^10，所以一般都用试除法来判定。

也许有人会问：“你为什么没有提马宁德拉.阿格拉瓦法呢？不是有人说它是目前最快的素数判定法吗？” 其实这是一个很大的误解，阿格拉瓦法虽然是log(n)的多项式级算法，但目前只有理论上的意义，根本无法实用，因为它的时间复杂度是O(log(n)^12)，这个多项式的次数太高了。就拿最慢的试除法跟它来比吧，试除法的时间复杂度为O(n^(1/2)*log(n)^2)，当n = 16时，log(n)^12 = 16777216，而n^(1/2)*log(n)^2 = 64，你看相差有多么大！如果要让两者速度相当，即log(n)^12 = n^(1/2)*log(n)^2，得出n = 10^43.1214，此时需要进行的运算次数为log(n)^12 = 10^25.873（注意：本文中log（）函数缺省以2为底），这样的运算次数在一台主频3GHz的计算机上运行也要10^8.89707年才能运行完，看来我们这辈子是别指望看到阿格拉瓦法比试除法快的这一天啦！

除了这些确定性素数判定法外，还有基于概率的非确定性素数判定法，最常用的就是米勒-拉宾法。

对于32位机器数（四则运算均为常数时间完成），试除法的时间复杂度是O(n^(1/2))，而米勒-拉宾法的时间复杂度只有O(log(n))。所以后者要比前者快得多，但是由于米勒-拉宾法的非确定性，往往我们在需要确定解时仍然要依靠速度较慢的试除法。那是否可以通过扩展米勒-拉宾法，来找到一种更快的确定性素数判定法呢？结论是肯定的，本文就带你一起寻找这样一种方法。

第二章 2-伪素数表的生成

既然要扩展米勒-拉宾法，那首先我们应该知道为什么米勒-拉宾法是个非确定性素数判定法？答案很简单，由于伪素数的存在。由于米勒-拉宾法使用费尔马小定理的逆命题进行判断，而该逆命题对极少数合数并不成立，从而产生误判，这些使费尔马小定理的逆命题不成立的合数就是伪素数。为了研究伪素数，我们首先需要生成伪素数表，原理很简单，就是先用筛法得出一定范围内的所有素数，然后逐一判定该范围内所有合数是否使以2为底数的费尔马小定理的逆命题不成立，从而得出该范围内的2-伪素数表。我的程序运行了100分钟，得出了32位机器数范围内的2-伪素数表，如下：

341

561

645

1105

1387

1729

1905

2047

2465

2701

...

...

...

4286813749

4288664869

4289470021

4289641621

4289884201

4289906089

4293088801

4293329041

4294868509

4294901761

（共10403个，由于篇幅所限，中间部分省略。）

第三章 寻找2-伪素数的最小可判定底数

对于2-伪素数表的每一个伪素数，寻找最小的可以判定它们是合数的底数，我把这个底数称之为最小可判定底数。特别地，对于绝对伪素数，它的最小质因子即是它的最小可判定底数。由于已经证明了绝对伪素数至少有三个质因子，所以这个最小质因子一定不大于n^(1/3)。下面就是我找到的最小可判定底数列表：

341 3

561 3

645 3

1105 5

1387 3

1729 7

1905 3

2047 3

2465 5

2701 5

...

...

...

4286813749 3

4288664869 3

4289470021 5

4289641621 3

4289884201 3

4289906089 3

4293088801 3

4293329041 3

4294868509 7

4294901761 3

通过统计这个列表，我发现了一个规律，那就是所有的最小可判定底数都不大于n^(1/3)，由前述可知，对于绝对伪素数，这个结论显然成立。而对于非绝对伪素数，虽然直观上觉得它应该比绝对伪素数好判定出来，但是我无法证明出它的最小可判定底数都不大于n^(1/3)。不过没关系，这个问题就作为一个猜想留给数学家来解决吧，更重要的是我已经通过实验证明了在32位机器数范围内这个结论成立。

我们还有没有更好的方法来进一步减小最小可判定底数的范围呢？有的！我们可以在计算平方数时进行二次检测，下面是进行了二次检测后重新计算的最小可判定底数列表：

341 2

561 2

645 2

1105 2

1387 2

1729 2

1905 2

2047 3

2465 2

2701 2

...

...

...

4286813749 2

4288664869 2

4289470021 2

4289641621 2

4289884201 2

4289906089 2

4293088801 2

4293329041 2

4294868509 2

4294901761 3

很显然，二次检测是有效果的，经过统计，我发现了新的规律，那就是经过二次检测后所有的最小可判定底数都不大于n^(1/6)，真的是开了一个平方呀，哈哈！这个结论的数学证明仍然作为一个猜想留给数学家们吧。我把这两个猜想叫做费尔马小定理可判定上界猜想。而我已经完成了对32位机器数范围内的证明。

通过上面总结的规律，我们已经可以设计出一个对32位机器数进行素数判定的 O(n^(1/6)*log(n)) 的确定性方法。但是这还不够，我们还可以优化，因为此时的最小可判定底数列表去重后只剩下了5个数（都是素数）：{2,3,5,7,11}。天哪，就是前5个素数，这也太容易记忆了吧。

不过在实现算法时，需要注意这些结论都是在2-伪素数表基础上得来的，也就是说不管如何对2的判定步骤必不可少，即使当2>n^(1/6)时。

还有一些优化可以使用，经过实验，当n>=7^6时，可以不进行n^(1/6)上界限制，而固定地用{2,5,7,11}去判定，也是100%正确的。这样就可以把判定次数降为4次以下，而每次判定只需要进行4log(n)次乘除法（把取余运算也看作除法），所以总的计算次数不会超过16log(n)。经过实验，最大的计算次数在n=4294967291时出现，为496次。

第四章 算法实现和解释

算法实现如下：（使用C++语言）

#include <iostream>

#include <math.h>

using namespace std;

//定义跨平台的64位机器数类型

#ifndef _WIN32

typedef unsigned long long longlong_t;

#else

typedef unsigned __int64 longlong_t;

#endif

//使用费尔马小定理和二次检测针对一个底数进行判定

bool IsLikePrime(longlong_t n, longlong_t base)

{

longlong_t power = n-1;

longlong_t result = 1;

longlong_t x = result;

longlong_t bits = 0;

longlong_t power1 = power;

//统计二进制位数

while (power1 > 0)

{

power1 >>= 1;

bits++;

}

//从高位到低位依次处理power的二进制位

while(bits > 0)

{

bits--;

result = (x*x)%n;

//二次检测

if (result == 1 && x != 1 && x != n-1)

{

return false;

}

if ((power&((longlong_t)1<<bits)) != 0)

{

result = (result*base)%n;

}

x = result;

}

//费尔马小定理逆命题判定

return result == 1;

}

//前5个素数

const int primes[]={2,3,5,7,11};

//前5个素数的6次方，由后面的init对象初始化

int primes_six[sizeof(primes)/sizeof(primes[0])];

//静态初始化类

class CInit

{

public:

CInit()

{

int num = sizeof(primes)/sizeof(primes[0]);

for (int i = 0; i < num; i++)

{

primes_six[i] = primes[i]*primes[i]*primes[i];

primes_six[i] *= primes_six[i];

}

}

}init;

//王浩素数判定函数

bool JudgePrime(longlong_t n)

{

if (n < 2)

return false;

if (n == 2)

return true;

int num = sizeof(primes)/sizeof(int);

bool bIsLarge = (n >= primes_six[3]);

for (int i = 0; i < num; i++)

{

if (bIsLarge)

{

//当n >= 7^6时，不进行上界判断，固定地用{2,5,7,11}做判定。

if (primes[i] == 3)

continue;

}

else

{

//当n < 7^6时，进行上界判断，但是2例外。

if (primes[i] != 2 && n < primes_six[i])

break;

}

//做一次子判定

if (!IsLikePrime(n, primes[i]))

return false;

}

//所有子判定通过，则n必为素数！

return true;

}

//主程序

int main()

{

longlong_t n;

//对标准输入的每一个数进行素数判定

while (cin >> n)

{

if (JudgePrime(n))

{

//如果是素数，则输出到标准输出。

cout << n << endl;

}

//如果是合数，不输出。

}

return 0;

}

程序中已经加了足够的注释，应该不难理解。

需要说明的一点是，虽然我在输入时使用了longlong_t，那是为了类型一致性，有效的输入范围仍然是0 ~ 2^32-1 。

第五章 算法可推广性分析

如果前述的费尔马小定理可判定上界猜想可以被证明，那么该算法可以被推广到任意位数的n，此时的时间复杂度为O(n^(1/6)*log(n)^3)。这样我们就可以完成米勒-拉宾非确定性素数判定法向确定性素数判定法的转化，这对于数论理论是一个补充，对于实践中使用米勒-拉宾素数判定法具有指导意义。

本文所做的研究只是向米勒-拉宾非确定性素数判定法的确定化方向迈出了一小步，我相信，在不久的将来，米勒-拉宾非确定性素数判定法的确定化方向会有更大进展，从而对数论理论和实践产生深远影响。

参考文献

《计算机算法设计与分析（第2版）》，王晓东编着，电子工业出版社，2004年7月。

I. 关于求一个数是否为素数的问题

质数(又称为素数）
1.只有1和它本身这两个因数的自然数叫做质数。还可以说成质数只有1和它本身两个约数。
2.素数是这样的整数，它除了能表示为它自己和1的乘积以外，不能表示为任
何其它两个整数的乘积。
如果是if（n%d==0）就全都不是素数呀，因为除以本身的余数都是0

J. 对一个大于或等于3的正整数，判断它是不是一个素数。

如果按上述的算法，用C来作应该是下面程序！
main()
{
int i, n;
printf("please input the data:\n");
scanf("%d",&n);
for(i = 2; i < n; i++)
{
if(n % i == 0)
{
printf("this is not a prime number.\n");
break;
}
}
if(i == n)
printf("this is a prime number.\n");
getch();
}