我理解确定性论点的意思是:
certainty - 衡量调用者愿意容忍的不确定性:如果调用返回 true,则此 BigInteger 为素数的概率超过 (1 - 1/2certainty)
从我的实验来看,它似乎超过了它不少!下面的代码找到 2 到 100 万之间的“可能素数”,并检查一组确定的素数以查看它是否是误报。
我使用的确定性参数为 2。因此,我预计只有 75% 的“可能素数”将是实际素数。 (1 - 1/22 = 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));
}
}
这些陈述经常引起混淆。我会尝试在这里更好地解释它。
Java 的
BigInteger.isProbablePrime()
根本不包含对小整数的优化,除了 0、1 和 2 被视为特殊情况并且除 2 之外的所有偶数整数都立即声明为复合。在撰写本文时,这将是真实的。
使用 Miller-Rabin (MR) 素数测试检查所有其他奇数的素数。此外,如果整数是 100 位或更大,它也会使用称为 Lucas-Lehmer 测试的东西进行检查。
MR 是一个复杂的素数测试,其解释和分析超出了 SO 答案的范围。关键是,就 MR 而言,并非所有复合材料都生而平等。非常非常小的一部分是 stubborn,这意味着要发现它们的复合性要困难得多。举几个例子:在小奇数组合中,91、703 和 1891 是顽固的。 MR 通过尝试多次随机尝试来发现整数的复合性来克服这个问题。 Rabin 的分析表明,对于最顽固的复合材料,单次随机尝试仍有至少 75% (3/4) 的概率揭示其复合材料。
算法无法知道哪些复合材料是顽固的。对于密码学,得到一个你被告知是素数但实际上是复合数的数字可能是灾难性的。因此,为了安全起见,
certainty
的公式假设 all 它测试素数的数字都是顽固的复合数或实素数。 certainty
参数几乎等同于指定 MR 算法需要执行的随机尝试次数。实际上,Java 实现中certainty
参数与随机尝试次数之间的关系似乎更复杂,仅通过阅读源代码我自己并没有完全理解它。
但请记住我说过顽固的复合材料的比例非常非常小。您测试的几乎每个复合材料都不是顽固的,并且随着质数变大,仅在一次随机尝试后就会使 MR 失败。这就是为什么您的成功率似乎是 99.9%。
作为查看不同复合材料性能的实验,将您的程序更改为只是反复尝试确认 1891 年的复合材料。您会看到接近 75% 的成功率。
一个相对较小的 MR-stubborn 复合材料列表是这里.
您引用的文档是正确的。
certainty - 衡量调用者愿意容忍的不确定性:如果调用返回 true,则此 BigInteger 为素数的概率超过 (1 - 1/2certainty)
99.9% 确实超过 1 - 1/(22) = 3/4,所以您向我们展示的内容没有任何问题。
实现不保证这就是 exactly 概率,它只是提供了一个实现,其错误是 definitely bounded by that certainty.
大多数质量素性测试器都会对小素数进行大量优化,或者更确切地说,对除数是小合数的数进行优化。这些可能会在算法的随机方面之前启动,从而导致小素数的准确性高于平常。