费马素数检验
本文关键字:检验 马素数 | 更新日期: 2023-09-27 18:04:08
我试着写一个费马素数测试的代码,但显然失败了。如果我理解得好,如果p
是素数那么((a^p)-a)%p=0
其中p%a!=0
。我的代码看起来不错,因此很可能我误解了基本知识。我遗漏了什么?
private bool IsPrime(int candidate)
{
//checking if candidate = 0 || 1 || 2
int a = candidate + 1; //candidate can't be divisor of candidate+1
if ((Math.Pow(a, candidate) - a) % candidate == 0) return true;
return false;
}
阅读维基百科关于费马素数测试的文章,您必须选择小于您正在测试的候选的a
,而不是更多。
此外,正如MattW评论的那样,只测试单个a
不会给你一个关于候选是否是素数的结论性答案。你必须测试许多可能的a
,然后才能决定一个数可能是素数。即使这样,有些数字可能看起来是素数,但实际上是合数。
您的基本算法是正确的,但是如果您想要为非平凡数字执行此操作,则必须使用比int更大的数据类型。
你不应该像以前那样实现模求幂,因为中间结果是巨大的。下面是模幂的平方乘算法:
function powerMod(b, e, m)
x := 1
while e > 0
if e%2 == 1
x, e := (x*b)%m, e-1
else b, e := (b*b)%m, e//2
return x
例如,437^13 (mod 1741) = 819。如果使用上面所示的算法,中间结果不会大于1740 * 1740 = 3027600。但是如果你先执行幂运算,437^13的中间结果是21196232792890476235164446315006597,这可能是你想要避免的。
尽管如此,费马测试仍然是不完美的。有一些合数,卡迈克尔数,无论你选择什么见证,它都是质数。如果你想要更好的效果,可以试试米勒-拉宾测试。我在我的博客上推荐这篇关于素数编程的文章
您正在处理非常大的数字,并试图将它们存储为双精度,这只有64位。双精度体将尽其所能保存你的数字,但你会失去一些准确性。
另一种方法:
请记住,可以多次应用mod操作符,并且仍然给出相同的结果。因此,为了避免得到大量的数字,你可以在计算你的功率时应用mod运算符。
类似:
private bool IsPrime(int candidate)
{
//checking if candidate = 0 || 1 || 2
int a = candidate - 1; //candidate can't be divisor of candidate - 1
int result = 1;
for(int i = 0; i < candidate; i++)
{
result = result * a;
//Notice that without the following line,
//this method is essentially the same as your own.
//All this line does is keeps the numbers small and manageable.
result = result % candidate;
}
result -= a;
return result == 0;
}