数学研发网设为首页收藏本站
切换到窄版

 找回密码
 欢迎注册
数学研发论坛»论坛 › 【算法研发】 › 算法交流 › 大整数强伪素数测试实际概率统计
返回列表 发新帖
查看: 15808|回复: 9

[讨论] 大整数强伪素数测试实际概率统计

[复制链接]
无心人
发表于 2019-9-12 20:19:31 | 显示全部楼层 |阅读模式

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

您需要 登录 才可以下载或查看，没有账号？欢迎注册

×
从那个基2的2^64以内伪素数列表网站扒下来的统计数据做的概率计算

范围   伪素数 强伪素数  卡米切尔  伪素数比例     强伪素数比例  卡米切尔数比例
2^9           1         0               0   1.9531E-03    0.0000E+00      3.8147E-06
2^10          3         0              1   2.9297E-03    0.0000E+00      9.7656E-04
2^11          8         1              3   3.9063E-03    4.8828E-04      1.4648E-03
2^12         13       3              5   3.1738E-03    7.3242E-04      1.2207E-03
2^13         19       4             6   2.3193E-03    4.8828E-04      7.3242E-04
2^14         32       6             9   1.9531E-03    3.6621E-04      5.4932E-04
2^15         45       7            10   1.3733E-03    2.1362E-04      3.0518E-04
2^16         64      11          15   9.7656E-04    1.6785E-04      2.2888E-04
2^17         89      18          19   6.7902E-04    1.3733E-04      1.4496E-04
2^18        124      24          23   4.7302E-04    9.1553E-05      8.7738E-05
2^19        175      34          33   3.3379E-04    6.4850E-05      6.2943E-05
2^20        251      49          45   2.3937E-04    4.6730E-05      4.2915E-05
2^21        361      75          55   1.7214E-04    3.5763E-05      2.6226E-05
2^22        502     104          69   1.1969E-04    2.4796E-05      1.6451E-05
2^23        693     147        95   8.2612E-05    1.7524E-05      1.1325E-05
2^24        944     210     130   5.6267E-05    1.2517E-05      7.7486E-06
2^25       1264     296     162   3.7670E-05    8.8215E-06      4.8280E-06
2^26       1713     409     214   2.5526E-05    6.0946E-06      3.1888E-06
2^27       2361     552     290   1.7591E-05    4.1127E-06      2.1607E-06
2^28       3169     734     375   1.1805E-05    2.7344E-06      1.3970E-06
2^29       4232     981     483   7.8827E-06    1.8273E-06      8.9966E-07
2^30       5749    1311     656   5.3542E-06    1.2210E-06      6.1095E-07
2^31       7750    1736     864   3.6089E-06    8.0839E-07      4.0233E-07
2^32      10403    2314    1118   2.4221E-06    5.3877E-07      2.6030E-07
2^33      14011    3093    1446   1.6311E-06    3.6007E-07      1.6834E-07
2^34      18667    4139    1874   1.0866E-06    2.4092E-07      1.0908E-07
2^35      24958    5511    2437   7.2637E-07    1.6039E-07      7.0926E-08
2^36      33389    7396    3130   4.8587E-07    1.0763E-07      4.5547E-08
2^37      44540    9835    4058   3.2407E-07    7.1559E-08      2.9526E-08
2^38      59565   13106    5188   2.1670E-07    4.7679E-08      1.8874E-08
2^39      79343   17493    6642   1.4432E-07    3.1820E-08      1.2082E-08
2^40     105659   23270    8521   9.6096E-08    2.1164E-08      7.7498E-09
2^41     141147   31115   11002   6.4186E-08    1.4149E-08      5.0031E-09
2^42     188231   41664   14236   4.2799E-08    9.4733E-09      3.2369E-09
2^43     250568   55763   18400   2.8486E-08    6.3395E-09      2.0918E-09
2^44     333737   74739   23631   1.8971E-08    4.2484E-09      1.3433E-09
2^45     445316  100342   30521   1.2657E-08    2.8519E-09      8.6746E-10
2^46     593366  134559   39376   8.4322E-09    1.9122E-09      5.5957E-10
2^47     792172  180725   50685   5.6287E-09    1.2841E-09      3.6014E-10
2^48    1059097  243566   65590   3.7627E-09    8.6532E-10      2.3302E-10
2^49    1416055  327731   84817   2.5154E-09    5.8217E-10      1.5067E-10
2^50    1893726  441270  109857   1.6820E-09    3.9193E-10      9.7573E-11
2^51    2532703  594585  141892   1.1247E-09    2.6405E-10      6.3013E-11
2^52    3390284  803252  183507   7.5279E-10    1.7836E-10      4.0747E-11
2^53    4540673 1085426  237217   5.0412E-10    1.2051E-10      2.6336E-11
2^54    6086093 1468777  307278   3.3785E-10    8.1534E-11      1.7057E-11
2^55    8167163 1988905  398506   2.2668E-10    5.5203E-11      1.1061E-11
2^56   10964612 2697846  517446   1.5216E-10    3.7440E-11      7.1810E-12
2^57   14731767 3662239  672105   1.0222E-10    2.5412E-11      4.6637E-12
2^58   19806649 4976375  873109   6.8718E-11    1.7265E-11      3.0292E-12
2^59   26651383 6767707 1136472   4.6233E-11    1.1740E-11      1.9715E-12
2^60   35893886 9212942 1479525   3.1133E-11    7.9910E-12      1.2833E-12
2^61   48374139 12552513 1927138   2.0979E-11    5.4438E-12      8.3576E-13
2^62   65247459 17114780 2513234   1.4148E-11    3.7112E-12      5.4497E-13
2^63   88069251 23355139 3278553   9.5485E-12    2.5322E-12      3.5546E-13
2^64   118968379 31894014 4279356   6.4493E-12    1.7290E-12      2.3198E-13
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复

使用道具 举报

mathematica
发表于 2019-9-16 08:43:13 | 显示全部楼层
我觉得你可以搞一个统计公式出来，既然有这么多数据在这里，
搞个统计数据，然后证明它。
比如n以内有多少个以2为底的强伪素数！搞一个统计公式出来
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

无心人
 楼主| 发表于 2019-9-17 17:31:32 | 显示全部楼层
mathematica 发表于 2019-9-16 08:43
我觉得你可以搞一个统计公式出来，既然有这么多数据在这里，
搞个统计数据，然后证明它。
比如n以内有多 ...

很难，因为按我的估计，比如10^20，这么小的范围，是小于10^10个的2-spsp的，概率低于100亿分之一，很难统计出来，更大的数，概率更低，比如我找的10^67，概率低于10^(-34)，几乎找不到2-spsp
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

无心人
 楼主| 发表于 2020-12-24 11:47:09 | 显示全部楼层
粗略估计，假设spsp_c(n)表示n以下spsp(2)
spsp_c(2n) = k * spsp(n)
1.36 < k < 1.37
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

无心人
 楼主| 发表于 2020-12-29 09:31:05 | 显示全部楼层
n>2^32,  spsp(n) 约等于 1200 * 1.38^(log2(n) - 32)，远小于 sqrt(n)

所以理论上两次 米勒罗宾测试，即可保证错误概率小于1/n
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

mathematica
发表于 2020-12-29 09:35:51 | 显示全部楼层
无心人 发表于 2020-12-29 09:31
n>2^32,  spsp(n) 约等于 1200 * 1.37^(log2(n) - 32)

真正需要素数的时候，用baillie psw算法测试一下，然后走几次miller rabin就足够足够的了！
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

nyy
发表于 2022-9-19 11:22:11 | 显示全部楼层
你的数据，来自这个地方吗？
http://www.janfeitsma.nl/math/psp2/statistics
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

无心人
 楼主| 发表于 2022-9-23 10:57:16 | 显示全部楼层
nyy 发表于 2022-9-19 11:22
你的数据，来自这个地方吗？
http://www.janfeitsma.nl/math/psp2/statistics

是
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

nyy
发表于 2022-9-29 13:36:27 | 显示全部楼层
本帖最后由 nyy 于 2022-9-29 13:37 编辑

实在忍受不了你不对齐，我自己搞对齐了！
  1. 范围    伪素数       强伪素数    卡米切尔    伪素数比例    强伪素数比例    卡米切尔数比例
  2. 2^9     1            0           0           1.9531E-03    0.0000E+00      3.8147E-06
  3. 2^10    3            0           1           2.9297E-03    0.0000E+00      9.7656E-04
  4. 2^11    8            1           3           3.9063E-03    4.8828E-04      1.4648E-03
  5. 2^12    13           3           5           3.1738E-03    7.3242E-04      1.2207E-03
  6. 2^13    19           4           6           2.3193E-03    4.8828E-04      7.3242E-04
  7. 2^14    32           6           9           1.9531E-03    3.6621E-04      5.4932E-04
  8. 2^15    45           7           10          1.3733E-03    2.1362E-04      3.0518E-04
  9. 2^16    64           11          15          9.7656E-04    1.6785E-04      2.2888E-04
  10. 2^17    89           18          19          6.7902E-04    1.3733E-04      1.4496E-04
  11. 2^18    124          24          23          4.7302E-04    9.1553E-05      8.7738E-05
  12. 2^19    175          34          33          3.3379E-04    6.4850E-05      6.2943E-05
  13. 2^20    251          49          45          2.3937E-04    4.6730E-05      4.2915E-05
  14. 2^21    361          75          55          1.7214E-04    3.5763E-05      2.6226E-05
  15. 2^22    502          104         69          1.1969E-04    2.4796E-05      1.6451E-05
  16. 2^23    693          147         95          8.2612E-05    1.7524E-05      1.1325E-05
  17. 2^24    944          210         130         5.6267E-05    1.2517E-05      7.7486E-06
  18. 2^25    1264         296         162         3.7670E-05    8.8215E-06      4.8280E-06
  19. 2^26    1713         409         214         2.5526E-05    6.0946E-06      3.1888E-06
  20. 2^27    2361         552         290         1.7591E-05    4.1127E-06      2.1607E-06
  21. 2^28    3169         734         375         1.1805E-05    2.7344E-06      1.3970E-06
  22. 2^29    4232         981         483         7.8827E-06    1.8273E-06      8.9966E-07
  23. 2^30    5749         1311        656         5.3542E-06    1.2210E-06      6.1095E-07
  24. 2^31    7750         1736        864         3.6089E-06    8.0839E-07      4.0233E-07
  25. 2^32    10403        2314        1118        2.4221E-06    5.3877E-07      2.6030E-07
  26. 2^33    14011        3093        1446        1.6311E-06    3.6007E-07      1.6834E-07
  27. 2^34    18667        4139        1874        1.0866E-06    2.4092E-07      1.0908E-07
  28. 2^35    24958        5511        2437        7.2637E-07    1.6039E-07      7.0926E-08
  29. 2^36    33389        7396        3130        4.8587E-07    1.0763E-07      4.5547E-08
  30. 2^37    44540        9835        4058        3.2407E-07    7.1559E-08      2.9526E-08
  31. 2^38    59565        13106       5188        2.1670E-07    4.7679E-08      1.8874E-08
  32. 2^39    79343        17493       6642        1.4432E-07    3.1820E-08      1.2082E-08
  33. 2^40    105659       23270       8521        9.6096E-08    2.1164E-08      7.7498E-09
  34. 2^41    141147       31115       11002       6.4186E-08    1.4149E-08      5.0031E-09
  35. 2^42    188231       41664       14236       4.2799E-08    9.4733E-09      3.2369E-09
  36. 2^43    250568       55763       18400       2.8486E-08    6.3395E-09      2.0918E-09
  37. 2^44    333737       74739       23631       1.8971E-08    4.2484E-09      1.3433E-09
  38. 2^45    445316       100342      30521       1.2657E-08    2.8519E-09      8.6746E-10
  39. 2^46    593366       134559      39376       8.4322E-09    1.9122E-09      5.5957E-10
  40. 2^47    792172       180725      50685       5.6287E-09    1.2841E-09      3.6014E-10
  41. 2^48    1059097      243566      65590       3.7627E-09    8.6532E-10      2.3302E-10
  42. 2^49    1416055      327731      84817       2.5154E-09    5.8217E-10      1.5067E-10
  43. 2^50    1893726      441270      109857      1.6820E-09    3.9193E-10      9.7573E-11
  44. 2^51    2532703      594585      141892      1.1247E-09    2.6405E-10      6.3013E-11
  45. 2^52    3390284      803252      183507      7.5279E-10    1.7836E-10      4.0747E-11
  46. 2^53    4540673      1085426     237217      5.0412E-10    1.2051E-10      2.6336E-11
  47. 2^54    6086093      1468777     307278      3.3785E-10    8.1534E-11      1.7057E-11
  48. 2^55    8167163      1988905     398506      2.2668E-10    5.5203E-11      1.1061E-11
  49. 2^56    10964612     2697846     517446      1.5216E-10    3.7440E-11      7.1810E-12
  50. 2^57    14731767     3662239     672105      1.0222E-10    2.5412E-11      4.6637E-12
  51. 2^58    19806649     4976375     873109      6.8718E-11    1.7265E-11      3.0292E-12
  52. 2^59    26651383     6767707     1136472     4.6233E-11    1.1740E-11      1.9715E-12
  53. 2^60    35893886     9212942     1479525     3.1133E-11    7.9910E-12      1.2833E-12
  54. 2^61    48374139     12552513    1927138     2.0979E-11    5.4438E-12      8.3576E-13
  55. 2^62    65247459     17114780    2513234     1.4148E-11    3.7112E-12      5.4497E-13
  56. 2^63    88069251     23355139    3278553     9.5485E-12    2.5322E-12      3.5546E-13
  57. 2^64    118968379    31894014    4279356     6.4493E-12    1.7290E-12      2.3198E-13
复制代码

点评

nyy
论坛有问题，明明我在编辑器里搞的非常对齐，结果到论坛里就不对齐了！  发表于 2022-9-29 13:38
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2024-11-21 20:21 , Processed in 0.025668 second(s), 18 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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