欢迎。我正在尝试实施 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
}
对于小大整数来说它工作得很好。但如果我的程序需要计算包含超过 16 位的数字,程序就会冻结。例如,在成功检查数字是否为素数后,程序突然没有响应。我不明白这怎么可能。如果它检查了一个大数字,那么再次检查另一个数字应该没有问题。即使调试器也没有帮助,因为step options
消失。如果需要,我可以分享更多功能代码。对于小数字,上述函数可以正常工作。
编辑。更改 BigInteger.ModPow 的模函数有帮助。不幸的是,现在对于更大的数字,超过 3000 位,它永远不会返回质数,这是相当不可能的。或者说真正重要的数字很难找到?
嗯,大约需要5秒在我的工作站(Core 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);
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)