隨機化演算法素數測試問題

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();
}