Miller Rabin Primality test

Question

我在C sharp中編寫了一個Miller Rabin素數測試，但它在每個輸入上都返回false。

下面的代碼：

static Boolean MilRab(UInt64 n) 
    { 
     UInt64[] ar = new UInt64[] { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 }; 
     for (int i = 0; i < 10; i++) 
     { 
      if (Tanu(ar[i], n) == true) return false; 
     } 
     return true; 
    }//MilRab 

    static Boolean Tanu(UInt64 a, UInt64 n) 
    { 
     UInt64 b = n - 1; 
     UInt64 d = 1; 
     UInt64 x; 
     Int16 i; 
     for (i = 63; i >= 0; i--) if (((b >> i) & 1) == 1) break; 

     for (;i>=0;i--) 
     { 
      x = d; 
      d = ((d * d) % n); 
      if (d == 1 && x != 1 && x != n - 1) return true; 
      if (b>>i == 1) d = (d * a) % n; 
     } 
     if (d != 1) return true; 
     return false; 
    }//Tanu 

你覺得有什麼問題，可以嗎？我花了一天的時間進行調試，讓我瘋狂。謝謝。

Answer 1

選中此實施int和BigInteger的

http://rosettacode.org/wiki/Miller-Rabin_primality_test#C.23

Answer 2

正如阿米爾說，

http://rosettacode.org/wiki/Miller-Rabin_primality_test#C.23

有解決方案。但是，我嘗試了它，即使是像79這樣的非常小的輸入值，它也會給出錯誤的結果（79是質數，但是會反覆出現，因爲不是質數）。原因是功率溢出（例如，11^78就像1E + 81，它不能用32或64位整數表示）。

所以這裏

public static class RabinMiller 
{ 
    public static bool IsPrime(int n, int k) 
    { 
     if(n < 2) 
     { 
      return false; 
     } 
     if(n != 2 && n % 2 == 0) 
     { 
      return false; 
     } 
     int s = n - 1; 
     while(s % 2 == 0) 
     { 
      s >>= 1; 
     } 
     Random r = new Random(); 
     for (int i = 0; i < k; i++) 
     { 
      double a = r.Next((int)n - 1) + 1; 
      int temp = s; 
      int mod = (int)Math.Pow(a, (double)temp) % n; 
      while(temp != n - 1 && mod != 1 && mod != n - 1) 
      { 
       mod = (mod * mod) % n; 
       temp = temp * 2; 
      } 
      if(mod != n - 1 && temp % 2 == 0) 
      { 
       return false; 
      } 
     } 
     return true; 
    } 
} 

你應該添加一個功能

static int ModuloPower(int a, int b, int n) 
    { 
     // return (a^b)%n 
     int res = 1; 
     for (int i = 0; i < b; ++i) 
      res = (res * a) % n; 
     return res; 
    } 

並更改開機/模線

int mod = ModuloPower(a, temp, n); // (int)Math.Pow(a, (double)temp) % n; 

這當然可以再優化..見rosettacode網站上其他語言的代碼示例，用於更快捷地計算功率/模數的更巧妙方法。

（我試過編輯代碼有，但必須註冊，所以我張貼在這裏。）