因?yàn)槲闹写嬖诠?#xff0c;只能用圖片方式上傳了！

?

以下為C語(yǔ)言源代碼：

#include <stdio.h>
typedef long long unsigned LLU;
typedef int BOOL;
#define TRUE 1
#define FALSE 0

BOOL isPrime(LLU n) {? //這是傳統(tǒng)的方法，用于與Miller-Rabin算法的結(jié)果進(jìn)行對(duì)比。
? ? if( (n&1)==0 || n%5==0)
? ? ? ? return FALSE;

? ? LLU i,bnd;
? ? bnd=sqrt(n);
? ? for(i=2; i<=bnd; i++)
? ? ? ? if(n%i==0)
? ? ? ? ? ? return FALSE;

? ? return TRUE;
}

//實(shí)現(xiàn)(a*b)%c,用類似快速冪的方式實(shí)現(xiàn)。
//將模運(yùn)算下的乘法用加法實(shí)現(xiàn)的思想是時(shí)間換空間。
//這可以作為典型的時(shí)間換空間的例子。
LLU quickMult(LLU a,LLU b,LLU c){
? ? LLU result=0;
? ? while(b>0) {
? ? ? ? if(b&1)
? ? ? ? ? ? result=(result+a)%c;
? ? ? ? a=(a+a)%c;
? ? ? ? b>>=1;
? ? }
? ? return result;
}

//請(qǐng)注意，計(jì)算快速冪時(shí)，因?yàn)樽兞康臄?shù)據(jù)類型為long long,是64bits長(zhǎng)度的整數(shù)。
//a的值不能大于(2的32次方-1)≈4000000000
//否則，計(jì)算a*a時(shí)會(huì)越界，超過64bits整數(shù)的表示范圍。
//例如a,b,c分別為：7087881096594 10000000000036 10000000000037時(shí)，
//正確結(jié)果 (a^b)%c=1，但是，在此計(jì)算的結(jié)果不為1。
//因此，可以改進(jìn)為用“快速乘”代替*乘法運(yùn)算符，能更加充分第利用64的long long unsigned型的存儲(chǔ)空間。
//這個(gè)例子可以作為算法改進(jìn)從O(n)到O(lg(n))的進(jìn)步的例子。
LLU quickPower(LLU a,LLU b,LLU c) {
? ? LLU result=1;
? ? while(b>0) {
? ? ? ? if(b&1)
? ? ? ? ? ? //result=result*a%c; //此為直接乘法
? ? ? ? ? ? result=quickMult(result,a,c);
? ? ? ? //a=a*a%c; //此為直接乘法
? ? ? ? a=quickMult(a,a,c);
? ? ? ? b>>=1;
? ? }
? ? return result;
}

//如果返回值為TRUE表示n為素?cái)?shù)，返回值為FALSE表示n為合數(shù)。
BOOL MillerRabinPrimeTest(LLU n) {
? ? LLU d,x,newX,a=1;
? ? int i;
? ? for (i=0; i<4; i++)
? ? ? ? a*=rand();
? ? a=a%(n-3)+2;//隨機(jī)第選取一個(gè)a∈[2,n-2]
? ? //printf("隨機(jī)選取的a=%lld\n",a);
? ? int s=0;//s為d中的因子2的冪次數(shù)。
? ? d=n-1; ?//d取初值n-1
? ? while( (d&1)==0) {//將d中因子2全部提取出來。
? ? ? ? s++;
? ? ? ? d>>=1;
? ? }

? ? x=quickPower(a,d,n);
? ? for(i=0; i<s; i++) { //進(jìn)行s次二次探測(cè)
? ? ? ? newX=quickPower(x,2,n);
? ? ? ? if(newX==1 && x!=1 && x!=n-1)
? ? ? ? ? ? return FALSE; //用二次定理的逆否命題，此時(shí)n確定為合數(shù)。
? ? ? ? x=newX;
? ? }
? ? if(x!=1)
? ? ? ? return FALSE; ? //用費(fèi)馬小定理的逆否命題判斷，此時(shí)x=a^(n-1) (mod n)，那么n確定為合數(shù)。

? ? return TRUE; //用費(fèi)馬小定理的逆命題判斷。能經(jīng)受住考驗(yàn)至此的數(shù)，大概率為素?cái)?shù)。
}

//經(jīng)過連續(xù)特定次數(shù)的Miller-Rabin測(cè)試后，
//如果返回值為TRUE表示n為素?cái)?shù)，返回值為FALSE表示n為合數(shù)。
BOOL isPrimeByMR(LLU n) {
? ? if((n&1)==0 || n%5==0)
? ? ? ? return FALSE;
? ? int i;
? ? for (i=0; i<100; i++)
? ? ? ? if(MillerRabinPrimeTest(n)==FALSE)
? ? ? ? ? ? return FALSE;
? ? return TRUE;
}

//對(duì)比傳統(tǒng)方法和Miller-Rabin算法的結(jié)果
void check(LLU n) {
? ? char isRight;
? ? BOOL resultA,resultB;
? ? resultA=isPrime(n);
? ? resultB=isPrimeByMR(n);
? ? if(resultA==resultB) {
? ? ? ? isRight='V';
? ? ? ? printf("%c,%llu %d %d\n",isRight,n,resultA,resultB);
? ? } else {
? ? ? ? isRight='X';
? ? ? ? printf("%c,%llu %d %d\n",isRight,n,resultA,resultB);
? ? }
}

//測(cè)試任務(wù)：在本人筆記本電腦上測(cè)試，N=10的18次方至N+10之間的質(zhì)數(shù)為：
//1000000000000000003
//1000000000000000009
//Miller-Rabin算法的速度：0.22秒
//常規(guī)算法：22秒
int main() {? ??
? ? srand(time(NULL));

? ? LLU i,n,N;
? ? N=1000000000000000000;
? ? BOOL result;
? ? for(i=N; i<N+10; i++) {
? ? ? ? n=i;
? ? ? ? //check(n);? ? ? ??
? ? ? ? //result=isPrime(n);
? ? ? ? result=isPrimeByMR(n);
? ? ? ? if(result==TRUE)
? ? ? ? ? ? printf("%llu\n",n);

? ? }
? ? return 0;
}

?

以下為Python語(yǔ)言源代碼：

import math import randomdef isPrime(n): #這是傳統(tǒng)的方法，用于與Miller-Rabin算法的結(jié)果進(jìn)行對(duì)比。if (n & 1) == 0 or n % 5 == 0:return Falsebnd = int(math.sqrt(n))for i in range(2, bnd + 1):if n % i == 0:return Falsereturn True# 實(shí)現(xiàn)(a*b)%c,用類似快速冪的方式實(shí)現(xiàn)。 # 將模運(yùn)算下的乘法用加法實(shí)現(xiàn)的思想是時(shí)間換空間。 # 這可以作為典型的時(shí)間換空間的例子。 def quickMult(a, b, c):result = 0while b > 0:if b & 1:result = (result + a) % ca = (a + a) % cb >>= 1return result#因?yàn)镻ython支持大整數(shù)運(yùn)算，所以在此也可以不用快速乘法，而直接使用乘法*。 def quickPower(a, b, c):result = 1while b > 0:if (b & 1):# result=result*a%c #此為直接乘法result = quickMult(result, a, c)# a=a*a%c #此為直接乘法a = quickMult(a, a, c)b >>= 1return result#如果返回值為TRUE表示n為素?cái)?shù)，返回值為FALSE表示n為合數(shù)。 def MillerRabinPrimeTest(n):a = random.randint(2,n-2) #隨機(jī)第選取一個(gè)a∈[2,n-2]# print("隨機(jī)選取的a=%lld\n"%a)s = 0 #s為d中的因子2的冪次數(shù)。d = n - 1while (d & 1) == 0: #將d中因子2全部提取出來。s += 1d >>= 1x = quickPower(a, d, n)for i in range(s): #進(jìn)行s次二次探測(cè)newX = quickPower(x, 2, n)if newX == 1 and x != 1 and x != n - 1:return False #用二次定理的逆否命題，此時(shí)n確定為合數(shù)。x = newXif x != 1: # 用費(fèi)馬小定理的逆否命題判斷，此時(shí)x=a^(n-1) (mod n)，那么n確定為合數(shù)。return Falsereturn True # 用費(fèi)馬小定理的逆命題判斷。能經(jīng)受住考驗(yàn)至此的數(shù)，大概率為素?cái)?shù)。# 經(jīng)過連續(xù)特定次數(shù)的Miller-Rabin測(cè)試后， # 如果返回值為TRUE表示n為素?cái)?shù)，返回值為FALSE表示n為合數(shù)。 def isPrimeByMR(n):if ((n & 1) == 0 or n % 5 == 0):return Falsefor i in range(100):if MillerRabinPrimeTest(n) == False:return Falsereturn True#對(duì)比傳統(tǒng)方法和Miller-Rabin算法的結(jié)果 def check(n):resultA = isPrime(n)resultB = isPrimeByMR(n)if resultA == resultB:isRight = 'V'print("%c,%u %d %d" % (isRight, n, resultA, resultB))else:isRight = 'X'print("%c,%u %d %d" % (isRight, n, resultA, resultB))# 測(cè)試任務(wù)：在本人筆記本電腦上測(cè)試，N=10的18次方至N+10之間的質(zhì)數(shù)為： # 1000000000000000003 # 1000000000000000009 # Miller-Rabin算法的速度：0.22秒 # 常規(guī)算法：22秒 # python的常規(guī)算法，耗時(shí)更長(zhǎng)。 def main():# freopen("result.txt","w",stdout)random.seed()# res=quickPower(2,10,7)# print("%u"%res)N = 1000000000000000000for i in range(N, N + 10):n = i#check(n)# n=int(input())#result=isPrime(n)result = isPrimeByMR(n)if result == True :print("%u" % n)return 0# print(isPrime(1000000000000000003)) # a, b, c = [int(e) for e in input().split(" ")] # print(quickPower(a,b,c)) # # 7087881096594 10000000000036 10000000000037 =1 main()

總結(jié)

以上是生活随笔為你收集整理的素性测试的Miller-Rabin算法完全解析 （C语言实现、Python实现）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。