为什么GIMPS用费马测试？

nyy

https://www.mersenne.org/various/math.php#prp
Starting in 2018, GIMPS started using a Fermat probable prime test rather than a Lucas-Lehmer test to search for new Mersenne primes. Robert Gerbicz devised a way to almost completely eliminate the chance of a hardware error corrupting the primality test. Even though results are 99.999+% reliable double-checking is still necessary to guard against program error or forged results. Gerbicz error checking does mean that GIMPS is extremely unlikely to miss a new Mersenne prime on the first test -- a big improvement over the previous 1 or 2% chance of missing a new Mersenne prime on the first test.

Another breakthrough lets GIMPS completely avoid the double-checking process! Krzysztof Pietrzak showed how to create a PRP proof that cannot be faked and can be verified over 100 times faster than a standard double-check. In 2020 proofs were added to the GIMPS software and PRP with proofs became the preferred way to search for new Mersenne primes.

为什么他们会用费马测试呢？我感觉很奇怪！
谁能说清楚其中的道理，梅森数不是有现成的 Lucas-Lehmer test 吗？而且这个测试还是确定的！
为什么他们会改变呢？

无心人

因为$n=2^p-1$在执行MR测试时候
$n-1=2^p-2=2(2^{p-1}-1)$，只有一个$2$

所以，测试时候只需要测试 $b^{(n-1)/2} = ±1 (mod n)$ 是否成立就行

nyy

无心人 发表于 2022-9-24 20:48
因为$n=2^p-1$在执行MR测试时候
$n-1=2^p-2=2(2^{p-1}-1)$，只有一个$2$

上面的英文我不大懂，但是很明显与你这个没关系！