java - BigInteger.isProbablePrime 似乎比它说的要确定得多

Question

我了解 certainty参数表示:

certainty - a measure of the uncertainty that the caller is willing to tolerate: if the call returns true the probability that this BigInteger is prime exceeds (1 - 1/2^certainty)

从我的实验来看，它似乎超过了很多!下面的代码在 2 到 100 万之间找到“可能的素数”，并检查一组确定的素数，看看它是否是误报。

我使用的确定性参数为 2。因此，我预计只有 75% 的“可能素数”是实际素数。 (1 - 1/2² = 0.75 = 75%。)

实际上，它在 99.9% 的时间里都是正确的。

我对“确定性”含义的理解正确吗？我怀疑如果我通过实验看到的确定性远远超出了我的预期，那可能不会。

import java.math.BigInteger;
import java.util.BitSet;

import static java.lang.Math.sqrt;

public class PrimesCalculator {
    public final int max;
    private final BitSet sieve;  // Set of all non-primes from 2 to max.

    public PrimesCalculator(int max) {
        this.max = max;
        sieve = new BitSet(max+1);
        for (int n = 2, sqrtMax = (int) sqrt(max); n < sqrtMax; n++)
            for (int i = n * 2; i < max; i += n)
                sieve.set(i);
    }

    public boolean isPrime(int n) {
        return !sieve.get(n);
    }

    public static void main(String[] args) {
        PrimesCalculator calc = new PrimesCalculator(1_000_000);
        int numPrimes = 0;
        int numProbablePrimes = 0;
        for (int i = 2; i < calc.max; i++)
            if (BigInteger.valueOf(i).isProbablePrime(2)) {
                numProbablePrimes++;
                if (calc.isPrime(i))
                    numPrimes++;
            }
        System.out.printf("%s/%s (%s%%)%n", numPrimes, numProbablePrimes, numPrimes / (numProbablePrimes / 100.0));
    }
}

Answer 1

这些陈述经常引起混淆。我将尝试在这里更好地解释它。

Java 的 BigInteger.isProbablePrime()根本不包含对小整数的优化，除了 0、1 和 2 被视为特殊情况，并且除了 2 之外的所有偶数都立即声明为复合数。

使用 Miller-Rabin (MR) 素性检验检查所有其他奇数的素性。此外，如果整数为 100 位或更大，则还使用称为 Lucas-Lehmer 测试的方法对其进行检查。

MR 是一个复杂的素性测试，其解释和分析超出了 SO 答案的范围。关键是，就 MR 而言，并非所有复合 Material 都是平等的。非常非常小的一部分要发现它们的复合性要困难得多。举几个例子:在小的奇数复合 Material 中，91、703 和 1891 是困难的。 MR 通过尝试多次随机尝试来发现整数的复合性来克服这个问题。 Rabin 的分析表明，对于表现最差的复合 Material ，单次随机尝试仍有至少 75% (3/4) 的概率揭示其复合性。

certainty参数几乎等同于指定 MR 算法需要执行的随机尝试次数。在现实中，certainty 之间的关系论点和随机尝试的次数比较复杂，我自己也没有完全理解。

作为查看不同复合 Material 性能的实验，请将程序更改为只是重复尝试确认复合 Material ，例如 1891。您会看到成功率接近 75%。

相对较小的 MR 顽固复合 Material 列表是 here .