Miller-Rabin實施中的錯誤

Question

我正在實施Wikipedia's Miller-Rabin algorithm，但似乎沒有得到模糊的結果。據報道，7,11,19,23等組合。事實上，當k> 12時，甚至5顯示覆合。我讀過Miller-Rabin背後的數學知識，但對此並不十分理解，盲目依賴於算法。任何暗示我要去哪裏的錯誤？

這裏是我的代碼：

#include<stdio.h> 
#include<math.h> 

int modpow(int b, int e, int m) { 
    long result = 1; 

    while (e > 0) { 
     if ((e & 1) == 1) { 
      result = (result * b) % m; 
     } 
     b = (b * b) % m; 
     e >>= 1; 
    } 

    return result; 
} 

int isPrime(long n,int k){ 
     int a,s,d,r,i,x,loop; 
     if(n<2)return 0; 
     if(n==2||n==3)return 1; 
     if(n%2==0)return 0; 

     d=n-1; 
     s=0; 
     while(d&1==0){ 
       d>>=1; 
       s++; 
     } 


     for(i=0;i<k;i++){ 
       loop=0; 
       a=(int)(rand()*(n-1))+1; 
       x=modpow(a,d,n); 
       if(x==1 || x==n-1){ 
         continue; 

       } 
       for(r=1;r<=s;r++){ 
         x=modpow(x,2,n); 
         if(x==1)return 0; 
         if(x==n-1){ 
           loop=1; 
           break; 
         } 
       } 
       if(!loop)return 0; 

     } 
     return 1; 

} 

int main(){ 
     int i,k; 
     scanf("%d",&k); 
     for(i=5;i<100;i+=2){ 
       printf("%d : %d\n",i,isPrime(i,k)); 
     } 
     return 0; 
} 

Answer 1

如果基礎不互質的候選人，強費爾馬檢查總是返回「不是一個可能的總理」。

有了自己的錯誤

a=(int)(rand()*(n-1))+1; 

的主要p，基本不會互質p（的p的倍數），當且僅當rand()結果的形式

k*p + 1 

對於小素數，實際上保證即使迭代次數很少也會發生。

基地應在2個ANS n/2之間說謊（選擇基地比n/2大是沒有必要的，因爲a是compositeness證人當且僅當n - a就是其中之一），所以你要像

a = rand() % (n/2 - 2) + 2; 

如果如果你想在整個可能範圍分佈偏向你不介意在隨機數生成適合小余模偏置，或

a = rand() /(RAND_MAX + 1.0) * (n/2 - 2) + 2; 

。