这也许是别人敢用费马测试的原因

nyy

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[10^11]/38975 // N
得到
1.01299*10^(5)

计算一下10^17以内的素数的个数，然后再除以伪素数的个数，
10^17/Log[10^17]/12604009 // N
得到：
2.02687*10^8

再计算一下10^19以内的素数的个数，然后再除以伪素数的个数，
10^19/Log[10^19]/91210364 // N
得到
2.50603*10^9

简单地估算，那就是10^n以内的素数的个数除以以2为底的伪素数的个数，
那么结果的数量级差不多就是10^((n-1)/2),

因此当被判定是随机奇数通过以2为底的费马测试，如果能达到10^101这个数量级，
那么你碰到是素数的概率，要远远远远远远大于是伪素数的概率，
这也许就是他们为什么敢用费马测试找素数的原因！

据说PGP软件用的就是费马测试！

nyy

Why does PGP still use the Fermat primality test? What if it hits one of the Carmichael numbers？
https://crypto.stackexchange.com ... 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.

nyy

还有一个原因：费马测试比miller rabin测试快那么一点点，当n很大很大的时候，这种差别的相对值就比较可观了！

无心人

我看了你引用的那个PGP的网页，你断章取义了，
那里面说了，PGP的老库，而且现在PGP也不怎么用了
在其他更新的库里，比如GMP，费马测试和米勒罗宾测试比，
既慢又出错概率大，没任何使用的价值


卡米切尔数并不是考虑的理由
在米勒罗宾测试下，不存在卡米切尔数能通过所有基的测试
这也是选择米勒罗宾测试而不是费马测试的一个理由，

nyy

无心人 发表于 2022-9-23 11:29
我看了你引用的那个PGP的网页，你断章取义了，
那里面说了，PGP的老库，而且现在PGP也不怎么用了
在其他 ...

费马测试和米勒罗宾测试比,既慢又出错概率大
你这就胡说八道了，我也用mathematica软件写过对比测试，费马测试快

nyy

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