C＃中的MillerRabin素性测试

欢迎。 我正在尝试实施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消失了。 如果需要，我可以分享更多function代码。 以上function适用于小数字。

编辑。 更改BigInteger.ModPow的模数函数有帮助。 不幸的是，现在对于更大的数字，超过3000位，它永远不会返回素数，这是不可能的。 或者真正的prme数字很难找到？

Answer 1

好吧，我的工作站（Core i5 3.2GHz，IA64 .Net 4.5）需要大约5秒来测试数字等于2**3000素数：

  public static class PrimeExtensions { // Random generator (thread safe) private static ThreadLocal s_Gen = new ThreadLocal( () => { 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); 

Answer 2

这是我的代码，你可以检查从0到十进制的素数.MaxValue = 79228162514264337593543950335

UPDATE

我做了一些调整，以使程序更快

在一个：
英特尔（R）Atom（TM）@ 1.60GHz
2.00GB RAM
32位操作系统

结果：
1. UInt32.MaxValue = 4294967295
UInt32.MaxValue下面的最大素数是4294967291
经过的时间是0.015600秒
2. ulong.MaxValue = UInt64.MaxValue = 18446744073709551615
ulong下面的最大素数.MaxValue是18446744073709551533
经过的时间是3分钟和57.6059176秒
3. decimal.MaxValue = 79228162514264337593543950335
十进制以下的最大数字.MaxValue测试的是79228162514264337593543950319，但不知道79228162514264337593543950319是素数，因为我在经过时间为3小时40分钟后中断了程序的运行（需要使用高规格笔记本电脑进行测试）

 using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace PrimalityTest { class Program { static void Main(string[] args) { Console.Write("Enter a number: "); decimal decimal_number = Convert.ToDecimal(Console.ReadLine()); DateTime date = DateTime.Now; ulong ulong_a; ulong ulong_b; if (decimal_number <= ulong.MaxValue) { ulong ulong_number = Convert.ToUInt64(decimal_number); if (ulong_number < 2) { Console.WriteLine(ulong_number + " is not a prime number"); } else if (ulong_number == 2 || ulong_number == 3) { Console.WriteLine(ulong_number + " is a prime number"); } else if (ulong_number % 2 == 0) { Console.WriteLine(ulong_number + " is not a prime number and is divisible by 2"); } else { ulong_a = Convert.ToUInt64(Math.Ceiling(Math.Sqrt(ulong_number))); for (ulong_b = 3; ulong_b <= ulong_a; ulong_b += 2) { if (ulong_number % ulong_b == 0) { Console.WriteLine(ulong_number + " is not a prime number and is divisible by " + ulong_b); goto terminate_ulong_primality_test; } } Console.WriteLine(ulong_number + " is a prime number"); } terminate_ulong_primality_test: { } } else { if (decimal_number % 2 == 0) { Console.WriteLine(decimal_number + " is not a prime number and is divisible by 2"); } else { ulong_a = Convert.ToUInt64(Math.Ceiling(Math.Sqrt(ulong.MaxValue) * Math.Sqrt(Convert.ToDouble(decimal_number / ulong.MaxValue)))); for (ulong_b = 3; ulong_b <= ulong_a; ulong_b += 2) { if (decimal_number % ulong_b == 0) { Console.WriteLine(decimal_number + " is not a prime number and is divisible by " + ulong_b); goto terminate_decimal_primality_test; } } Console.WriteLine(decimal_number + " is a prime number"); } terminate_decimal_primality_test: { } } Console.WriteLine("elapsed time: " + (DateTime.Now - date)); Console.ReadKey(); } } }