C＃中的MillerRabin素性測試＃

Question

歡迎。我正在嘗試實施MillerRabin測試來檢查大給定數是否爲素數。這裏是我的代碼：

public static bool MillerRabinTest(BigInteger number) 
     { 

      BigInteger d; 
      var n = number - 1; 
      var s = FindK(n, out d); 

      BigInteger a = 2; 
      BigInteger y = Calc(a, d, number); //a^d mod number 
      if (y != BigInteger.One && y != n) 
      { 
       for (var r = 1; r <= s - 1; r++) 
       { 
        y = Calc(y, 2, number); 
        if (y == 1) 
         return false; 
       } 

       if (y != n) 
        return false; 
      } 
      return true; //it is probably prime 
     } 

這對小的Bigintegers工作正常。但是如果我的程序需要評估包含16位以上的數字，程序就會凍結。例如，在成功檢查數字是否爲素數之後，程序突然不響應。我不明白這怎麼可能。如果它檢查了一個大號碼，再次檢查另一個號碼應該沒有問題。即使調試器也沒有幫助，因爲step options消失。如果需要，我可以共享更多功能代碼。以上功能對於小數字正常工作。

編輯。更改BigInteger.ModPow的模函數幫助。不幸的是，現在對於更大的數字，超過3000比特，它永遠不會返回素數，這是不可能的。或者真的數字很難找到？

Answer 1

嗯，這大概需要5秒在我的工作站（酷睿i5 3.2GHz的，IA64 .NET 4.5）來測試是對數字黃金等於2**3000：

public static class PrimeExtensions { 
    // Random generator (thread safe) 
    private static ThreadLocal<Random> s_Gen = new ThreadLocal<Random>(
    () => { 
     return new Random(); 
     } 
    ); 

    // Random generator (thread safe) 
    private static Random Gen { 
     get { 
     return s_Gen.Value; 
     } 
    } 

    public static Boolean IsProbablyPrime(this BigInteger value, int witnesses = 10) { 
     if (value <= 1) 
     return false; 

     if (witnesses <= 0) 
     witnesses = 10; 

     BigInteger d = value - 1; 
     int s = 0; 

     while (d % 2 == 0) { 
     d /= 2; 
     s += 1; 
     } 

     Byte[] bytes = new Byte[value.ToByteArray().LongLength]; 
     BigInteger a; 

     for (int i = 0; i < witnesses; i++) { 
     do { 
      Gen.NextBytes(bytes); 

      a = new BigInteger(bytes); 
     } 
     while (a < 2 || a >= value - 2); 

     BigInteger x = BigInteger.ModPow(a, d, value); 
     if (x == 1 || x == value - 1) 
      continue; 

     for (int r = 1; r < s; r++) { 
      x = BigInteger.ModPow(x, 2, value); 

      if (x == 1) 
      return false; 
      if (x == value - 1) 
      break; 
     } 

     if (x != value - 1) 
      return false; 
     } 

     return true; 
    } 
    } 

測試和基準

BigInteger value = BigInteger.Pow(2, 3217) - 1; // Mersenne prime number (2.5e968) 

    Stopwatch sw = new Stopwatch(); 

    sw.Start(); 

    Boolean isPrime = value.IsProbablyPrime(10); 

    sw.Stop(); 

    Console.Write(isPrime ? "probably prime" : "not prime"); 
    Console.WriteLine(); 
    Console.Write(sw.ElapsedMilliseconds);