大整数强伪素数测试实际概率统计

cfan2021

从那个基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

isotaztiqotew

我觉得你可以搞一个统计公式出来，既然有这么多数据在这里，
搞个统计数据，然后证明它。
比如n以内有多少个以2为底的强伪素数！搞一个统计公式出来

ugetetip

很难，因为按我的估计，比如10^20，这么小的范围，是小于10^10个的2-spsp的，概率低于100亿分之一，很难统计出来，更大的数，概率更低，比如我找的10^67，概率低于10^(-34)，几乎找不到2-spsp

afijozaci

粗略估计，假设spsp_c(n)表示n以下spsp(2)
spsp_c(2n) = k * spsp(n)
1.36 < k < 1.37

ebirugerxos

n>2^32,  spsp(n) 约等于 1200 * 1.38^(log2(n) - 32)，远小于 sqrt(n)

所以理论上两次 米勒罗宾测试，即可保证错误概率小于1/n

esuruekinz

真正需要素数的时候，用baillie psw算法测试一下，然后走几次miller rabin就足够足够的了！

ukirhayexasi

你的数据，来自这个地方吗？
http://www.janfeitsma.nl/math/psp2/statistics

jnetoji

是

aecupeemow

实在忍受不了你不对齐，我自己搞对齐了！

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

复制代码