java - 费马小定理的实现问题

Question

这是我对费马小定理的实现。有谁知道为什么它不起作用？

以下是我遵循的规则:

• 设 n 为要测试素数的数字。
• 选择 2 到 n-1 之间的任意整数 a。
• 计算 a^n mod n。
• 检查 a^n 是否 = a mod n。

我的代码:

int low = 2;
int high = n -1;
Random rand = new Random();

//Pick any integer a between 2 and n-1.
Double a = (double) (rand.nextInt(high-low) + low);

//compute:a^n = a mod n
Double val = Math.pow(a,n) % n;

//check whether a^n = a mod n   
if(a.equals(val)){
return "True";
}else{
return "False";
}

这是一个小于 100000 的素数列表。每当我输入这些数字中的任何一个时，我得到的不是“真”，而是“假”。

The First 100,008 Primes

这就是我认为代码不起作用的原因。

Answer 1

在 java 中， double 的精度有限，约为 15 到 17 位数字。这意味着虽然您可以计算 Math.pow(a,n) 的值，对于非常大的数字，一旦该值超过 15 位，您就无法保证获得准确的结果。

如果 a 或 n 的值较大，您的计算将超出该限制。例如 Math.pow(3, 67)值为 9.270946314789783e31这意味着最后 3 位之后的任何数字都会丢失。因此，在应用模运算后，您无法保证获得正确的结果( example )。

这意味着您的代码实际上并没有测试您认为它所做的事情。这是 float 工作方式所固有的，您必须改变保存值的方式来解决这个问题。您可以使用 long但是这样你就会遇到溢出问题(long 不能容纳大于 2^64 - 1 的值，所以同样，在 3^67 的情况下，你还会遇到另一个问题。

一种解决方案是使用一个旨在保存任意大数字的类，例如 BigInteger这是 Java SE API 的一部分.