这也许是别人敢用费马测试的原因
http://www.janfeitsma.nl/math/psp2/statistics伪素数统计表（base 2）
10^11 38975
10^17 12604009
10^18 33763684
10^19 91210364
利用素数定理，计算一下10^11以内的素数的个数，然后再除以伪素数的个数，
10^11/Log/38975 // N
得到
1.01299*10^(5)
计算一下10^17以内的素数的个数，然后再除以伪素数的个数，
10^17/Log/12604009 // N
得到：
2.02687*10^8
再计算一下10^19以内的素数的个数，然后再除以伪素数的个数，
10^19/Log/91210364 // N
得到
2.50603*10^9
简单地估算，那就是10^n以内的素数的个数除以以2为底的伪素数的个数，
那么结果的数量级差不多就是10^((n-1)/2),
因此当被判定是随机奇数通过以2为底的费马测试，如果能达到10^101这个数量级，
那么你碰到是素数的概率，要远远远远远远大于是伪素数的概率，
这也许就是他们为什么敢用费马测试找素数的原因！
据说PGP软件用的就是费马测试！
Why does PGP still use the Fermat primality test? What if it hits one of the Carmichael numbers？
https://crypto.stackexchange.com/questions/88307/why-does-pgp-still-use-the-fermat-primality-test-what-if-it-hits-one-of-the-car
The quote from the last;
The Carmichael Numbers
Unfortunately, there are some numbers which are not prime and which do satisfy the equation bn−1modn
. These integers are known as the Carmichael Numbers, and they are quite rare. The reason for this is that a Carmichael Number must not be divisable by the square of any prime and must be the product of at least three primes). The first three Carmichael Numbers are: 561, 1105, and 1729. They are so rare, in fact, there are only 255 of them less than 109. The chance of PGP generating a Carmichael Number is less than 1 in 1050
.
So, even there are other alternatives to Fermat Test, they still use it. 还有一个原因：费马测试比miller rabin测试快那么一点点，当n很大很大的时候，这种差别的相对值就比较可观了！ 我看了你引用的那个PGP的网页，你断章取义了，
那里面说了，PGP的老库，而且现在PGP也不怎么用了
在其他更新的库里，比如GMP，费马测试和米勒罗宾测试比，
既慢又出错概率大，没任何使用的价值
卡米切尔数并不是考虑的理由
在米勒罗宾测试下，不存在卡米切尔数能通过所有基的测试
这也是选择米勒罗宾测试而不是费马测试的一个理由，
无心人 发表于 2022-9-23 11:29
我看了你引用的那个PGP的网页，你断章取义了，
那里面说了，PGP的老库，而且现在PGP也不怎么用了
在其他 ...
费马测试和米勒罗宾测试比,既慢又出错概率大
你这就胡说八道了，我也用mathematica软件写过对比测试，费马测试快 Probable-primes: How Probable?
https://primes.utm.edu/notes/prp_prob.html
Digits
in x Upper bound
for p(x) Digits
in x Upper bound
for p(x) Digits
in x Upper bound
for p(x)
60 0.0716 80 0.0000846 100 0.0000000277
120 5.28*10-12 150 1.49*10-17 200 3.85*10-27
300 5.8*10-29 400 5.7*10-42 500 2.3*10-55
700 1.8*10-82 1000 1.2*10-123 2000 8.6*10-262
5000 7.6*10-680 10000 1.6*10-1331 100000 1.3*10-10584
KP89
S. H. Kim and C. Pomerance, "The probability that a random probable prime is composite," Math. Comp., 53 (1989) 721-741.MR 90e:11190
The Probability that a Random Probable Prime is Composite
https://www.docin.com/p-1431695926.html
页:
[1]