数学研发论坛

 找回密码
 欢迎注册
查看: 175|回复: 5

[讨论] 这也许是别人敢用费马测试的原因

[复制链接]
发表于 2022-9-19 08:53:10 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
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软件用的就是费马测试!



点评

我不是写过嘛?卡米切尔数大于n的2/7次方,而强伪素数大于n的立方根,小于n的平方根,  发表于 2022-9-23 11:03
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2022-9-19 16:33:12 | 显示全部楼层
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.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2022-9-23 09:41:39 | 显示全部楼层
还有一个原因:费马测试比miller rabin测试快那么一点点,当n很大很大的时候,这种差别的相对值就比较可观了!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2022-9-23 11:29:59 | 显示全部楼层
我看了你引用的那个PGP的网页,你断章取义了,
那里面说了,PGP的老库,而且现在PGP也不怎么用了
在其他更新的库里,比如GMP,费马测试和米勒罗宾测试比,
既慢又出错概率大,没任何使用的价值


卡米切尔数并不是考虑的理由
在米勒罗宾测试下,不存在卡米切尔数能通过所有基的测试
这也是选择米勒罗宾测试而不是费马测试的一个理由,
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2022-9-23 11:37:38 | 显示全部楼层
无心人 发表于 2022-9-23 11:29
我看了你引用的那个PGP的网页,你断章取义了,
那里面说了,PGP的老库,而且现在PGP也不怎么用了
在其他 ...

费马测试和米勒罗宾测试比,既慢又出错概率大
你这就胡说八道了,我也用mathematica软件写过对比测试,费马测试快
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2022-10-3 06:51 , Processed in 0.094169 second(s), 20 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表