论坛 › 算法交流 › 大整数强伪素数测试实际概率统计

无心人 发表于 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   445316100342   30521   1.2657E-08    2.8519E-09      8.6746E-10
2^46   593366134559   39376   8.4322E-09    1.9122E-09      5.5957E-10
2^47   792172180725   50685   5.6287E-09    1.2841E-09      3.6014E-10
2^48    1059097243566   65590   3.7627E-09    8.6532E-10      2.3302E-10
2^49    1416055327731   84817   2.5154E-09    5.8217E-10      1.5067E-10
2^50    1893726441270109857   1.6820E-09    3.9193E-10      9.7573E-11
2^51    2532703594585141892   1.1247E-09    2.6405E-10      6.3013E-11
2^52    3390284803252183507   7.5279E-10    1.7836E-10      4.0747E-11
2^53    4540673 1085426237217   5.0412E-10    1.2051E-10      2.6336E-11
2^54    6086093 1468777307278   3.3785E-10    8.1534E-11      1.7057E-11
2^55    8167163 1988905398506   2.2668E-10    5.5203E-11      1.1061E-11
2^56   10964612 2697846517446   1.5216E-10    3.7440E-11      7.1810E-12
2^57   14731767 3662239672105   1.0222E-10    2.5412E-11      4.6637E-12
2^58   19806649 4976375873109   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 编辑

实在忍受不了你不对齐，我自己搞对齐了！
范围    伪素数       强伪素数    卡米切尔    伪素数比例    强伪素数比例    卡米切尔数比例
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

查看完整版本: 大整数强伪素数测试实际概率统计