1

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

以下是我遵循的规则：

  • 设 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 的素数列表。每当我输入这些数字中的任何一个时，我得到的不是“真”，而是“假”。

前 100,008 个素数

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

4

3 回答 3

1

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

对于较大的 a 或 n 值，您的计算将超过该限制。例如 Math.pow(3, 67)，将有一个值，9.270946314789783e31表示最后 3 之后的任何数字都将丢失。因此，在应用模运算后，您无法保证得到正确的结果（示例）。

这意味着您的代码实际上并没有测试您认为它所做的事情。这是浮点数工作方式所固有的，您必须更改保存值的方式才能解决此问题。您可以使用long，但随后您会遇到溢出问题（2^64 - 1如果您遇到另一个问题，long 不能再次保存大于此的值3^67。

一种解决方案是使用一个设计来保存任意大数字的类，例如Java SE APIBigInteger的一部分。

于 2012-12-27T23:00:31.837 回答
1

正如其他人所指出的，夺取权力会很快溢出。例如，如果您选择一个数字 n 来测试小到 30 的素数，而随机数 a 是 20，则 20^30 = 大约 10^39，即 >> 2^90。（我取了 10^39 的 ln）。

您想使用BigInteger，它甚至具有您想要的确切方法：

public BigInteger modPow(BigInteger exponent, BigInteger m)

“返回一个 BigInteger，其值为 (this^exponent mod m)”

另外，我认为测试 2 到 n-1 之间的单个随机数不会“证明”任何事情。您必须遍历 2 和 n-1 之间的所有整数。

于 2012-12-27T23:42:29.523 回答
1

@evthim 即使您使用了 BigInteger 类的 modPow 函数，您也无法获得正确选择的范围内的所有素数。为了进一步澄清问题，您将获得该范围内的所有质数，但您拥有的一些数字不是质数。如果您使用 BigInteger 类重新排列此代码。当您尝试所有 64 位数字时，一些非素数也会写入。这些数字如下；

341, 561, 645, 1105, 1387, 1729, 1905, 2047, 2465, 2701, 2821, 3277, 4033, 4369, 4371, 4681, 5461, 6601, 7957, 8321, 8481, 8911, 10261, 10585, 11305, 12801, 13741, 13747, 13981, 14491, 15709, 15841, 16705, 18705, 18721, 19951, 23001, 23377, 25761, 29341, ... https://oeis.org/a001567

161038, 215326, 2568226, 3020626, 7866046, 9115426, 49699666, 143742226, 161292286, 196116194, 209665666, 213388066, 293974066, 336408382, 376366, 666, 566, 566, 666 2001038066, 2138882626, 2952654706, 3220041826, ... https: //oeis.org/a006935

作为一种解决方案，通过从下面的链接获取这些数字的列表，确保您测试的数字不在此列表中。 http://www.cecm.sfu.ca/Pseudoprimes/index-2-to-64.html

C#的解决方案如下。

public static bool IsPrime(ulong number)
{
    return number == 2 
        ? true 
        : (BigInterger.ModPow(2, number, number) == 2 
            ? (number & 1 != 0 && BinarySearchInA001567(number) == false) 
            : false)
}

public static bool BinarySearchInA001567(ulong number)
{
    // Is number in list?
    // todo: Binary Search in A001567 (https://oeis.org/A001567) below 2 ^ 64
    // Only 2.35 Gigabytes as a text file http://www.cecm.sfu.ca/Pseudoprimes/index-2-to-64.html
}
于 2020-07-19T03:53:19.463 回答