Java语言中的Miller-Rabin素性检验
Java语言中的Miller-Rabin素性检验
提问于 2013-06-13 14:35:35
我目前正在从事Project Euler的工作，我想如果不强行解决所有的问题，它可能会更有趣(也是更好的学习体验)。在问题3中，它要求一个数的质数因子，我的解决方案是对该数进行因子分解(使用另一个因子分解算法)，然后测试这些因子的素性。我为Miller-Rabin素性测试(在彻底研究了素性测试之后)想出了这个代码，它对我输入的所有合成奇数都返回true。有人能帮我找出原因吗？我以为我已经正确地编码了算法。
public static boolean isPrime(long num)
{
if(num % 2 == 0)
return false;
else
{
double d;
int r=0;
while((num-1) % Math.pow(2,r+1) == 0)
r++;
d = (num-1) % Math.pow(2,r);
int[] a = {2,3,5,7,11,13,17,23,31,62,73,1662803};
boolean primality = true;
for(int k = 0; k < a.length; k++)
{
if((Math.pow(a[k],d)-1) % num != 0)
{
for(int s = 0; s < r-1; s++)
{
if((Math.pow(a[k],Math.pow(2,s)*d)+1) % num != 0)
primality = false;
}
}
}
return primality;
}回答 1
Stack Overflow用户
回答已采纳
发布于 2013-06-13 19:41:35
给定num > 3，您需要：d, r s.t. pow(2,r) * d = num - 1, where d is odd。
您可以有效地计算num - 1中的尾随零，以删除2的因子。然而，在该循环之后，您就知道pow(2,r)是num - 1的一个因素。因此：
d = (num-1) % Math.pow(2,r);总是会让步的：d = 0。我怀疑您在这里是想用/ (div)替换% (mod)；否则，Math.pow(a[k],d)-1将始终生成(0)，并且内部循环将永远不会被执行。
正如其他人指出的，一些简单的跟踪语句或断言可以发现这些错误。我认为你还有其他的问题，比如整数溢出。在我看来，针对a[]候选测试的循环( a-SPRP测试)是完全错误的。
也许你已经从Wikipedia得到了算法，我更喜欢The Handbook of Applied Cryptography中更详细的参考：4.2.3:米勒-拉宾测试，算法: 4.24。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/17080661
复制相关文章
相似问题
腾讯云开发者
