【算法程式設計】基于Miller-Rabin的大素數測試

基本原理：

費爾馬小定理:如果p是一個素數,且0<a<p,則a^(p-1)%p=1.

       利用費爾馬小定理,對于給定的整數n,可以設計素數判定算法,通過計算d=a^(n-1)%n來判斷n的素性,當d!=1時,n肯定不是素數,當d=1時,n  很可能是素數.

二次探測定理:如果p是一個素數,且0<x<p,則方程x^2%p=1的解為:x=1或x=p-1.

       利用二次探測定理,可以再利用費爾馬小定理計算a^(n-1)%n的過程中增加對整數n的二次探測,一旦發現違背二次探測條件,即得出n不是素數的結論.

    如果n是素數,則(n-1)必是偶數,是以可令(n-1)=m*(2^q),其中m是正奇數(若n是偶數,則上面的m*(2^q)一定可以分解成一個正奇數乘以2的k次方的形式 ),q是非負整數,考察下面的測試:

    序列:

         a^m%n; a^(2m)%n; a^(4m)%n; ……;a^(m*2^q)%n

Miller-Rabin素性測試僞代碼描述：

1、找出整數k,q,其中k>0,q是奇數，使（n-1=2kq）。

2、随機選取整數a,1<a<n-1。

3、Ifaq mod n=1, printf("該數可能是素數!\n");

4、Forj=0 to k-1 , if a^(2^j*q) mod n = n – 1, printf("該數可能是素數!\n");如果步驟3、4都不成立，則printf("該數肯定不是素數!\n")

5、當該數可能是素數時，随機選取整數a,1<a<n-1。若多次都表明可能是素數，則我們有理由相信該數是素數。

具體代碼實作： 

1.、BigInt.h檔案

2. BigInt.c檔案：

運作結果如下：

作者：nineheadedbird