为什么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$

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

nyy

Gerbicz error checking
https://www.rieselprime.de/ziki/Gerbicz_error_checking
估计是为了防止造假

nyy

https://www.mersenneforum.org/node/16935?p=628562#post628562
这个没看懂

.·.·.

LL需要算两遍防止算错
然而有人开发了费马小定理专用的检测算法，可以生成一组provance，帮助你快速检验计算结果是否正确
大概是乘法结合律

假设你均匀地已知了a^2^1000, a^2^2000, ... a^2^1000000这一千个数，当你想计算a^1000000时，你有两种算法
一种是直接抄答案，a^2^1000000反正是已知的
另一种是将a^2^999000自乘1000次，得到a^2^1000000

类似地，计算a^(2^2000 + 2^4000 + ... + 2^1000000)也有两种算法
一个是按原样计算a^(2^2000 + 2^4000 + ... + 2^1000000)
另一个是计算a^(2^1000 + 2^3000 + ... + 2^999000)，之后将结果自乘1000次，即可得到a^(2^2000 + 2^4000 + ... + 2^1000000)

注意到两种算法用的是不同的数字，且有一种算法使用了自乘1000次，因此除非你专门针对这个算法做hack，否则，如果你计算出错，两次计算结果必不相同。

针对hack的情形，上面说的计算数字的算法可以随机，如果指数是随机选取的，那么你找不到一种可以同时hack所有计算结果的方法
这就保证了无论如何都算不错

---

BTW这个算法好像是18年的，当年读过
你问得太晚了，我都快忘干净了

nyy

.·.·. 发表于 2024-10-28 16:40
LL需要算两遍防止算错
然而有人开发了费马小定理专用的检测算法，可以生成一组provance，帮助你快速检验计 ...

LL为什么算两次？
要不是最近出了新的梅森素素，我也不会再回复这个问题

nyy

.·.·. 发表于 2024-10-28 16:40
LL需要算两遍防止算错
然而有人开发了费马小定理专用的检测算法，可以生成一组provance，帮助你快速检验计 ...

为什么会算错呢？

nyy

.·.·. 发表于 2024-10-28 16:40
LL需要算两遍防止算错
然而有人开发了费马小定理专用的检测算法，可以生成一组provance，帮助你快速检验计 ...

LL需要算两遍防止算错，难道数字大了就容易算错？