n_is_semiprime_k is basically one-line factoring
7 views
Skip to first unread message
David Sparks
Mar 22, 2026, 5:51:27 AM (4 days ago) Mar 22
to flint-devel
I was talking to Viorel Wegner about the utility of adding k = 3/2
to the semiprime tests. After some discussion about how to
implement it, I realized that the test is basically equivalent to
Hart's one-line factoring algorithm. But more limited; HOLF with
i=24 catches both the k=6 and k=3/2 cases.
The downside of HOLF is that you have to do a more expensive
is_square test on the residue s^2 - i*n, or do one comparison
per k value.
The upside is that it can cope with numbers with more than two
factors, like Carmichael numbers, which can also be strong
pseudoprimes to a large fraction of bases.
These numbers also tend to have simple integer ratios between
the p_i - 1, but guessing all of them leads to a combinatorial
explosion, while guessing just one requires a division to check.
HOLF uses an is_square test instead. A *successful* is_square
test requires a square root, but there are pre-tests which can
obviate this in the majority of failed cases.
It's nice to have a test which works against almost all strong
pseudoprimes.
For each SPSP(2) between 2^32 and 2^64, I computed a score which
is the negative logarithm of the fraction of witnesses to its
compositeness. When finding a witness to a set of pseudoprimes,
the expected number of steps to search is the exp(sum(score[i])).
If they're scattered among an N-entry hash table, then the score is
distributed across the buckets, but the total size of the buckets
remains the same.
Anyway, the total score for all SPSP(2) in the range is 1387819.564778,
and the score of the numbers caught by HOLF rt semiprime_k tests
is given in the following table.
Notes about this first table:
- I searched semiprime-k values for 1 < k/60 <= 36.
In these cases, a number's score is attributed to the
first k which finds a factor. Few numbers are factored
by more than one k, so the order of tests shouldn't
matter significantly.
- I did HOLF tests up to 480. In this case, a number's score
is added to *each* multiplier which leads to a factor.
For a realistic search, I'll have to pick a first test,
then find the most effective multiplier for the remainder,
and so on.
k Count Score Avg fraction liars
HOLF(144): 3764474 360728.052681 (0.091376 liars)
HOLF(288): 2427881 347107.928168 (0.133218 liars)
HOLF(128): 2160152 342238.694633 (0.146520 liars)
HOLF(32): 2098957 341375.526026 (0.150103 liars)
HOLF(256): 3175154 329739.084645 (0.098639 liars)
HOLF(64): 3124755 329384.281018 (0.100046 liars)
HOLF(400): 2973644 321174.578404 (0.102379 liars)
HOLF(16): 2677709 316743.833308 (0.111561 liars)
4/1: 2677623 316743.251183 (0.111564 liars)
HOLF(72): 1787018 314003.470635 (0.161142 liars)
HOLF(200): 1566030 308984.245718 (0.179059 liars)
HOLF(392): 1540322 308755.781029 (0.181637 liars)
HOLF(8): 1529302 308713.887428 (0.182795 liars)
2/1: 1529234 308713.615214 (0.182803 liars)
HOLF(192): 2888485 258784.072215 (0.085696 liars)
HOLF(432): 2859000 258595.251174 (0.086480 liars)
HOLF(48): 2751608 257505.806906 (0.089338 liars)
HOLF(243): 1734671 217265.871277 (0.117723 liars)
HOLF(27): 1732140 217261.700122 (0.117882 liars)
HOLF(108): 1732123 217261.642298 (0.117883 liars)
HOLF(75): 1702667 216525.236515 (0.119415 liars)
HOLF(300): 1702646 216525.183503 (0.119416 liars)
HOLF(147): 1676475 216368.152867 (0.121080 liars)
HOLF(363): 1667302 216340.626798 (0.121689 liars)
HOLF(3): 1664443 216337.744878 (0.121884 liars)
HOLF(12): 1664426 216337.703804 (0.121885 liars)
3/1: 1664383 216337.514816 (0.121888 liars)
HOLF(320): 1647997 126958.372304 (0.074145 liars)
HOLF(80): 1605657 126720.411869 (0.075887 liars)
HOLF(405): 1484045 121298.499668 (0.078484 liars)
HOLF(45): 1476779 121290.370670 (0.078849 liars)
HOLF(180): 1476755 121290.292711 (0.078851 liars)
HOLF(125): 1287328 119337.467998 (0.088535 liars)
HOLF(245): 1286171 119315.540227 (0.088595 liars)
HOLF(5): 1276492 119297.580354 (0.089223 liars)
HOLF(20): 1276470 119297.571034 (0.089225 liars)
5/1: 1276442 119297.503834 (0.089226 liars)
HOLF(384): 1865108 94836.297344 (0.049577 liars)
HOLF(96): 1808819 94572.294552 (0.050941 liars)
HOLF(216): 1426648 86787.978796 (0.059020 liars)
HOLF(24): 1374873 86435.389112 (0.060932 liars)
6/1: 786176 49427.156185 (0.060935 liars)
HOLF(225): 1042387 44503.935165 (0.041796 liars)
HOLF(441): 877742 41035.918520 (0.045676 liars)
HOLF(81): 833398 40551.864438 (0.047494 liars)
HOLF(324): 833376 40551.748932 (0.047495 liars)
HOLF(9): 793915 40333.620129 (0.049535 liars)
HOLF(36): 793887 40333.302185 (0.049536 liars)
9/1: 793832 40333.001927 (0.049539 liars)
3/2: 588623 37007.808078 (0.060936 liars)
HOLF(448): 952574 35856.470027 (0.036942 liars)
HOLF(112): 908797 35680.585480 (0.038501 liars)
8/1: 569648 32661.674867 (0.055724 liars)
HOLF(63): 603789 30351.435731 (0.049026 liars)
HOLF(252): 603760 30351.414149 (0.049028 liars)
HOLF(175): 573475 30129.462433 (0.051182 liars)
HOLF(343): 563026 30105.597604 (0.052067 liars)
HOLF(7): 561304 30103.702112 (0.052219 liars)
HOLF(28): 561291 30103.594525 (0.052220 liars)
7/1: 561262 30103.432875 (0.052222 liars)
HOLF(160): 968024 29900.174378 (0.030416 liars)
HOLF(360): 787646 27473.365542 (0.034279 liars)
HOLF(40): 731530 27244.810839 (0.036559 liars)
12/1: 573049 21699.785103 (0.037159 liars)
4/3: 514084 19468.176839 (0.037162 liars)
HOLF(208): 629369 18581.399448 (0.029092 liars)
HOLF(117): 537976 17612.610741 (0.032209 liars)
HOLF(468): 537955 17612.605043 (0.032210 liars)
HOLF(325): 511433 17484.284878 (0.033609 liars)
HOLF(13): 500462 17468.804354 (0.034303 liars)
HOLF(52): 500449 17468.768116 (0.034304 liars)
13/1: 500421 17468.730789 (0.034306 liars)
HOLF(336): 783563 14253.679825 (0.018026 liars)
5/2: 365774 13623.517263 (0.036561 liars)
10/1: 365690 13621.013294 (0.036562 liars)
HOLF(189): 648696 13463.450221 (0.020541 liars)
HOLF(21): 625007 13407.338881 (0.021223 liars)
HOLF(84): 624989 13407.236280 (0.021223 liars)
HOLF(240): 708379 12814.543954 (0.017927 liars)
16/1: 447049 12640.539859 (0.027880 liars)
HOLF(135): 453339 10836.451536 (0.023620 liars)
HOLF(375): 441050 10796.577196 (0.024182 liars)
HOLF(15): 437454 10792.915429 (0.024370 liars)
HOLF(60): 437432 10792.809499 (0.024371 liars)
21/1: 357313 7667.337582 (0.021230 liars)
HOLF(224): 317091 6984.020208 (0.021785 liars)
HOLF(176): 267676 6900.711231 (0.025451 liars)
HOLF(56): 240860 6372.167936 (0.026109 liars)
HOLF(99): 198313 6051.126152 (0.030052 liars)
HOLF(396): 198292 6051.071069 (0.030055 liars)
HOLF(275): 179819 5975.253036 (0.032683 liars)
HOLF(11): 176632 5970.557031 (0.033237 liars)
HOLF(44): 176625 5970.555016 (0.033239 liars)
11/1: 176597 5970.374357 (0.033243 liars)
15/1: 238551 5886.697178 (0.024375 liars)
7/3: 267618 5739.775463 (0.021219 liars)
5/3: 198831 4905.941151 (0.024372 liars)
HOLF(272): 205883 4614.137034 (0.022162 liars)
8/3: 242370 4544.994744 (0.018578 liars)
HOLF(153): 188165 4404.251459 (0.023135 liars)
HOLF(425): 166706 4334.618061 (0.025666 liars)
HOLF(17): 163070 4330.634866 (0.026207 liars)
HOLF(68): 163063 4330.623653 (0.026208 liars)
17/1: 163044 4330.583358 (0.026211 liars)
HOLF(25): 229664 4132.960814 (0.017835 liars)
HOLF(100): 229638 4132.900895 (0.017836 liars)
25/1: 229590 4132.639065 (0.017839 liars)
HOLF(480): 403743 4100.244664 (0.010104 liars)
20/1: 169514 3824.090950 (0.022307 liars)
HOLF(352): 264892 3750.053785 (0.014057 liars)
HOLF(120): 304086 3728.865094 (0.012188 liars)
5/4: 159632 3598.667566 (0.022291 liars)
24/1: 191568 3591.962331 (0.018576 liars)
7/2: 132424 3502.936603 (0.026106 liars)
HOLF(88): 205710 3447.951428 (0.016622 liars)
HOLF(297): 261193 3438.837490 (0.013080 liars)
HOLF(33): 251790 3424.378165 (0.013508 liars)
HOLF(132): 251769 3424.366585 (0.013509 liars)
14/1: 108384 2869.117014 (0.026124 liars)
9/2: 136547 2801.906214 (0.020311 liars)
28/1: 174249 2798.703345 (0.015933 liars)
7/4: 173235 2778.234519 (0.015909 liars)
HOLF(304): 202773 2700.064876 (0.013227 liars)
18/1: 121150 2487.656836 (0.020324 liars)
HOLF(171): 122446 2183.868137 (0.017677 liars)
HOLF(475): 113588 2161.274622 (0.018847 liars)
HOLF(19): 111136 2159.314630 (0.019242 liars)
HOLF(76): 111124 2159.294257 (0.019244 liars)
19/1: 111104 2159.111484 (0.019246 liars)
36/1: 160269 1998.949084 (0.012395 liars)
22/1: 111839 1875.736052 (0.016632 liars)
33/1: 126271 1717.597913 (0.013510 liars)
11/3: 125457 1706.633131 (0.013511 liars)
9/4: 132648 1652.313910 (0.012379 liars)
11/2: 93830 1572.038341 (0.016615 liars)
HOLF(464): 110480 1426.816676 (0.012832 liars)
HOLF(168): 160587 1404.581919 (0.008708 liars)
HOLF(261): 100865 1357.165132 (0.013365 liars)
HOLF(416): 113609 1356.579368 (0.011870 liars)
HOLF(29): 85926 1331.207969 (0.015373 liars)
HOLF(116): 85918 1331.150953 (0.015374 liars)
29/1: 85902 1331.111502 (0.015376 liars)
8/5: 112946 1265.778912 (0.011144 liars)
HOLF(104): 87774 1244.452702 (0.014078 liars)
HOLF(136): 113904 1232.677172 (0.010764 liars)
HOLF(333): 105973 1198.601649 (0.011247 liars)
HOLF(37): 97867 1187.368627 (0.012059 liars)
HOLF(148): 97860 1187.331086 (0.012060 liars)
10/3: 84223 1032.834131 (0.012188 liars)
15/2: 76716 941.084842 (0.012192 liars)
9/5: 94336 937.937426 (0.009893 liars)
27/1: 67699 923.969444 (0.013555 liars)
HOLF(57): 116621 916.844267 (0.007831 liars)
HOLF(228): 116603 916.727363 (0.007831 liars)
30/1: 72791 892.991408 (0.012193 liars)
HOLF(368): 76061 883.729162 (0.011551 liars)
HOLF(351): 96691 876.731659 (0.009026 liars)
HOLF(39): 92584 872.323934 (0.009378 liars)
HOLF(156): 92568 872.275088 (0.009379 liars)
32/1: 61200 863.205225 (0.014006 liars)
6/5: 70279 861.671300 (0.012186 liars)
HOLF(279): 74142 836.964140 (0.011225 liars)
HOLF(31): 70023 831.146427 (0.011799 liars)
HOLF(124): 70018 831.145126 (0.011800 liars)
31/1: 70006 831.118888 (0.011802 liars)
HOLF(207): 52504 745.792470 (0.014104 liars)
HOLF(315): 80040 744.257124 (0.009255 liars)
HOLF(23): 45750 733.684204 (0.015909 liars)
HOLF(92): 45743 733.675366 (0.015911 liars)
23/1: 45725 733.658023 (0.015917 liars)
HOLF(35): 69635 731.717492 (0.010453 liars)
HOLF(140): 69623 731.691255 (0.010454 liars)
HOLF(49): 75898 694.589979 (0.009110 liars)
HOLF(196): 75884 694.505366 (0.009110 liars)
26/1: 47760 678.445300 (0.014105 liars)
17/2: 61914 669.301167 (0.010752 liars)
16/3: 70548 658.627378 (0.009292 liars)
HOLF(369): 62412 622.575993 (0.009926 liars)
HOLF(69): 94946 616.021192 (0.006467 liars)
HOLF(276): 94931 616.019124 (0.006468 liars)
HOLF(41): 55976 614.444836 (0.010917 liars)
HOLF(164): 55968 614.418703 (0.010918 liars)
HOLF(184): 74052 591.970086 (0.007962 liars)
13/2: 39969 565.900959 (0.014059 liars)
34/1: 51946 563.274861 (0.010785 liars)
HOLF(105): 130935 557.846898 (0.004251 liars)
HOLF(420): 130908 557.791373 (0.004252 liars)
12/5: 73114 545.533699 (0.007434 liars)
13/4: 62083 534.496962 (0.008572 liars)
HOLF(280): 98986 519.290153 (0.005232 liars)
15/4: 68596 512.099309 (0.007438 liars)
11/4: 48720 495.825509 (0.010125 liars)
20/3: 65943 492.150738 (0.007435 liars)
HOLF(264): 88177 490.586272 (0.005548 liars)
13/3: 51460 484.464201 (0.009370 liars)
HOLF(459): 66699 466.483380 (0.006969 liars)
HOLF(51): 64514 464.707563 (0.007177 liars)
HOLF(204): 64503 464.690369 (0.007178 liars)
HOLF(85): 85905 452.113326 (0.005249 liars)
HOLF(340): 85885 452.028262 (0.005249 liars)
HOLF(61): 61266 450.491172 (0.007326 liars)
HOLF(244): 61259 450.476483 (0.007327 liars)
HOLF(55): 63010 420.542887 (0.006652 liars)
HOLF(220): 63000 420.540889 (0.006653 liars)
19/3: 52899 415.369378 (0.007821 liars)
HOLF(65): 59918 412.729985 (0.006865 liars)
HOLF(260): 59908 412.724608 (0.006866 liars)
HOLF(152): 41584 402.784571 (0.009639 liars)
35/1: 35881 377.766316 (0.010473 liars)
14/3: 42387 370.536843 (0.008704 liars)
7/5: 33712 353.752632 (0.010439 liars)
21/2: 40239 351.938503 (0.008708 liars)
23/3: 52371 339.533867 (0.006462 liars)
7/6: 38410 335.521202 (0.008697 liars)
HOLF(387): 40331 326.841391 (0.008071 liars)
HOLF(43): 37927 324.368039 (0.008516 liars)
HOLF(172): 37918 324.360853 (0.008518 liars)
(table truncated at score=300)
Expanding the HOLF multiplier search to 1335 (this is the first
1000, skipping values == 2 mod 4 which are useless for odd inputs),
repeatedly taking the highest-scoring multiplier, and then
re-scoring the rest on the remaining inputs, we get
HOLF(576): 4241422 373462.532635 (0.084286 liars)
HOLF(1152): 2499129 347987.036977 (0.129984 liars)
4/1: 2677623 316743.251183 (0.111564 liars)
2/1: 1529234 308713.615214 (0.182803 liars)
HOLF(768): 2904915 258822.446660 (0.085244 liars)
3/1: 1664383 216337.514816 (0.121888 liars)
HOLF(720): 1855468 128836.802295 (0.067080 liars)
5/1: 1276442 119297.503834 (0.089226 liars)
HOLF(864): 1877119 94959.831439 (0.049330 liars)
6/1: 786176 49427.156185 (0.060935 liars)
9/1: 793832 40333.001927 (0.049539 liars)
3/2: 588623 37007.808078 (0.060936 liars)
HOLF(1008): 977962 35975.964752 (0.036118 liars)
8/1: 569648 32661.674867 (0.055724 liars)
7/1: 561262 30103.432875 (0.052222 liars)
HOLF(640): 996840 29982.270516 (0.029629 liars)
12/1: 573049 21699.785103 (0.037159 liars)
4/3: 514084 19468.176839 (0.037162 liars)
HOLF(832): 645379 18616.746055 (0.028434 liars)
13/1: 500421 17468.730789 (0.034306 liars)
HOLF(336): 783561 14253.674071 (0.018026 liars)
5/2: 365774 13623.517263 (0.036561 liars)
10/1: 365690 13621.013294 (0.036562 liars)
HOLF(960): 742157 12877.768869 (0.017202 liars)
16/1: 447049 12640.539859 (0.027880 liars)
21/1: 357313 7667.337582 (0.021230 liars)
HOLF(896): 326156 7002.709359 (0.021242 liars)
HOLF(704): 282655 6939.992847 (0.024254 liars)
11/1: 176597 5970.374357 (0.033243 liars)
15/1: 238551 5886.697178 (0.024375 liars)
7/3: 267618 5739.775463 (0.021219 liars)
5/3: 198831 4905.941151 (0.024372 liars)
HOLF(1225): 307211 4827.670972 (0.015592 liars)
HOLF(1088): 211110 4623.590343 (0.021663 liars)
8/3: 242370 4544.994744 (0.018578 liars)
17/1: 163044 4330.583358 (0.026211 liars)
25/1: 229590 4132.639065 (0.017839 liars)
HOLF(480): 403741 4100.244165 (0.010104 liars)
20/1: 169514 3824.090950 (0.022307 liars)
HOLF(352): 264889 3750.036383 (0.014057 liars)
HOLF(528): 316368 3643.938503 (0.011452 liars)
5/4: 159632 3598.667566 (0.022291 liars)
24/1: 191568 3591.962331 (0.018576 liars)
7/2: 132424 3502.936603 (0.026106 liars)
14/1: 108384 2869.117014 (0.026124 liars)
9/2: 136547 2801.906214 (0.020311 liars)
28/1: 174249 2798.703345 (0.015933 liars)
7/4: 173235 2778.234519 (0.015909 liars)
HOLF(1216): 211574 2713.626481 (0.012744 liars)
18/1: 121150 2487.656836 (0.020324 liars)
19/1: 111104 2159.111484 (0.019246 liars)
36/1: 160269 1998.949084 (0.012395 liars)
22/1: 111839 1875.736052 (0.016632 liars)
33/1: 126271 1717.597913 (0.013510 liars)
11/3: 125457 1706.633131 (0.013511 liars)
9/4: 132648 1652.313910 (0.012379 liars)
11/2: 93830 1572.038341 (0.016615 liars)
HOLF(672): 210223 1536.799660 (0.007284 liars)
HOLF(464): 110480 1426.816676 (0.012832 liars)
HOLF(416): 113609 1356.579368 (0.011870 liars)
HOLF(544): 147180 1342.874803 (0.009083 liars)
29/1: 85902 1331.111502 (0.015376 liars)
HOLF(592): 126155 1274.405224 (0.010051 liars)
8/5: 112946 1265.778912 (0.011144 liars)
HOLF(675): 107322 1112.297578 (0.010311 liars)
HOLF(624): 155538 1053.577364 (0.006751 liars)
10/3: 84223 1032.834131 (0.012188 liars)
HOLF(912): 144209 971.291365 (0.006713 liars)
HOLF(496): 102796 949.590462 (0.009195 liars)
15/2: 76716 941.084842 (0.012192 liars)
9/5: 94336 937.937426 (0.009893 liars)
27/1: 67699 923.969444 (0.013555 liars)
30/1: 72791 892.991408 (0.012193 liars)
HOLF(368): 76058 883.692588 (0.011551 liars)
HOLF(560): 113386 872.312912 (0.007664 liars)
32/1: 61200 863.205225 (0.014006 liars)
6/5: 70279 861.671300 (0.012186 liars)
31/1: 70006 831.118888 (0.011802 liars)
23/1: 45725 733.658023 (0.015917 liars)
26/1: 47760 678.445300 (0.014105 liars)
17/2: 61914 669.301167 (0.010752 liars)
16/3: 70548 658.627378 (0.009292 liars)
HOLF(1104): 119998 657.464113 (0.005464 liars)
HOLF(736): 95329 646.015832 (0.006754 liars)
HOLF(656): 66715 644.134607 (0.009609 liars)
HOLF(1120): 129977 569.797553 (0.004374 liars)
13/2: 39969 565.900959 (0.014059 liars)
34/1: 51946 563.274861 (0.010785 liars)
HOLF(945): 135716 560.286618 (0.004120 liars)
HOLF(816): 104353 552.810874 (0.005284 liars)
12/5: 73114 545.533699 (0.007434 liars)
HOLF(1056): 115113 536.314948 (0.004648 liars)
13/4: 62083 534.496962 (0.008572 liars)
15/4: 68596 512.099309 (0.007438 liars)
HOLF(880): 103661 503.740154 (0.004848 liars)
11/4: 48720 495.825509 (0.010125 liars)
20/3: 65943 492.150738 (0.007435 liars)
13/3: 51460 484.464201 (0.009370 liars)
HOLF(976): 73171 472.948026 (0.006443 liars)
HOLF(765): 92197 455.817478 (0.004932 liars)
HOLF(1040): 76884 443.975083 (0.005758 liars)
HOLF(608): 54565 441.823060 (0.008064 liars)
19/3: 52899 415.369378 (0.007821 liars)
HOLF(688): 58920 380.361521 (0.006435 liars)
35/1: 35881 377.766316 (0.010473 liars)
14/3: 42387 370.536843 (0.008704 liars)
HOLF(1024): 57876 368.400994 (0.006345 liars)
7/5: 33712 353.752632 (0.010439 liars)
21/2: 40239 351.938503 (0.008708 liars)
23/3: 52371 339.533867 (0.006462 liars)
7/6: 38410 335.521202 (0.008697 liars)
HOLF(1248): 81599 325.374042 (0.003980 liars)
HOLF(928): 58654 301.450125 (0.005126 liars)
HOLF(400): 66389 298.363240 (0.004484 liars)
The semiprime-k and HOLF lists are computed independently, and
then interleaved to make them easier to compare.
From the second list, we can derive cumulative scores.
The 45 HOLF entries up to HOLF(928) sum to 1374316.2, while the
68 Semiprime-k entries up to k=7/6 sum to 1352620.6.
The total score for all SPSP(2) is 1387819.6, so the residuals
are 13503.365 and 35198.945. These roughly correspond (after
multiplying by 1.4427 = log2(e)) to the number of bits required
to store the secondary M-R witness table.
Using a cumulative score as the cutoff instead of a per-test score,
it takes 22 k values to leave a residual score less than 100K, while
it takes 8 HOLF tests to achieve the same thing.
The current nine semiprime-k tests leave a residue of 252502.6;
adding k=3/2 takes that to 215494.8. Five HOLF multipliers
leave 183750.9.
I'm not suggesting any particular change to the current 64-bit
prime test code, just exploring the parameter space.
to the semiprime tests. After some discussion about how to
implement it, I realized that the test is basically equivalent to
Hart's one-line factoring algorithm. But more limited; HOLF with
i=24 catches both the k=6 and k=3/2 cases.
The downside of HOLF is that you have to do a more expensive
is_square test on the residue s^2 - i*n, or do one comparison
per k value.
The upside is that it can cope with numbers with more than two
factors, like Carmichael numbers, which can also be strong
pseudoprimes to a large fraction of bases.
These numbers also tend to have simple integer ratios between
the p_i - 1, but guessing all of them leads to a combinatorial
explosion, while guessing just one requires a division to check.
HOLF uses an is_square test instead. A *successful* is_square
test requires a square root, but there are pre-tests which can
obviate this in the majority of failed cases.
It's nice to have a test which works against almost all strong
pseudoprimes.
For each SPSP(2) between 2^32 and 2^64, I computed a score which
is the negative logarithm of the fraction of witnesses to its
compositeness. When finding a witness to a set of pseudoprimes,
the expected number of steps to search is the exp(sum(score[i])).
If they're scattered among an N-entry hash table, then the score is
distributed across the buckets, but the total size of the buckets
remains the same.
Anyway, the total score for all SPSP(2) in the range is 1387819.564778,
and the score of the numbers caught by HOLF rt semiprime_k tests
is given in the following table.
Notes about this first table:
- I searched semiprime-k values for 1 < k/60 <= 36.
In these cases, a number's score is attributed to the
first k which finds a factor. Few numbers are factored
by more than one k, so the order of tests shouldn't
matter significantly.
- I did HOLF tests up to 480. In this case, a number's score
is added to *each* multiplier which leads to a factor.
For a realistic search, I'll have to pick a first test,
then find the most effective multiplier for the remainder,
and so on.
k Count Score Avg fraction liars
HOLF(144): 3764474 360728.052681 (0.091376 liars)
HOLF(288): 2427881 347107.928168 (0.133218 liars)
HOLF(128): 2160152 342238.694633 (0.146520 liars)
HOLF(32): 2098957 341375.526026 (0.150103 liars)
HOLF(256): 3175154 329739.084645 (0.098639 liars)
HOLF(64): 3124755 329384.281018 (0.100046 liars)
HOLF(400): 2973644 321174.578404 (0.102379 liars)
HOLF(16): 2677709 316743.833308 (0.111561 liars)
4/1: 2677623 316743.251183 (0.111564 liars)
HOLF(72): 1787018 314003.470635 (0.161142 liars)
HOLF(200): 1566030 308984.245718 (0.179059 liars)
HOLF(392): 1540322 308755.781029 (0.181637 liars)
HOLF(8): 1529302 308713.887428 (0.182795 liars)
2/1: 1529234 308713.615214 (0.182803 liars)
HOLF(192): 2888485 258784.072215 (0.085696 liars)
HOLF(432): 2859000 258595.251174 (0.086480 liars)
HOLF(48): 2751608 257505.806906 (0.089338 liars)
HOLF(243): 1734671 217265.871277 (0.117723 liars)
HOLF(27): 1732140 217261.700122 (0.117882 liars)
HOLF(108): 1732123 217261.642298 (0.117883 liars)
HOLF(75): 1702667 216525.236515 (0.119415 liars)
HOLF(300): 1702646 216525.183503 (0.119416 liars)
HOLF(147): 1676475 216368.152867 (0.121080 liars)
HOLF(363): 1667302 216340.626798 (0.121689 liars)
HOLF(3): 1664443 216337.744878 (0.121884 liars)
HOLF(12): 1664426 216337.703804 (0.121885 liars)
3/1: 1664383 216337.514816 (0.121888 liars)
HOLF(320): 1647997 126958.372304 (0.074145 liars)
HOLF(80): 1605657 126720.411869 (0.075887 liars)
HOLF(405): 1484045 121298.499668 (0.078484 liars)
HOLF(45): 1476779 121290.370670 (0.078849 liars)
HOLF(180): 1476755 121290.292711 (0.078851 liars)
HOLF(125): 1287328 119337.467998 (0.088535 liars)
HOLF(245): 1286171 119315.540227 (0.088595 liars)
HOLF(5): 1276492 119297.580354 (0.089223 liars)
HOLF(20): 1276470 119297.571034 (0.089225 liars)
5/1: 1276442 119297.503834 (0.089226 liars)
HOLF(384): 1865108 94836.297344 (0.049577 liars)
HOLF(96): 1808819 94572.294552 (0.050941 liars)
HOLF(216): 1426648 86787.978796 (0.059020 liars)
HOLF(24): 1374873 86435.389112 (0.060932 liars)
6/1: 786176 49427.156185 (0.060935 liars)
HOLF(225): 1042387 44503.935165 (0.041796 liars)
HOLF(441): 877742 41035.918520 (0.045676 liars)
HOLF(81): 833398 40551.864438 (0.047494 liars)
HOLF(324): 833376 40551.748932 (0.047495 liars)
HOLF(9): 793915 40333.620129 (0.049535 liars)
HOLF(36): 793887 40333.302185 (0.049536 liars)
9/1: 793832 40333.001927 (0.049539 liars)
3/2: 588623 37007.808078 (0.060936 liars)
HOLF(448): 952574 35856.470027 (0.036942 liars)
HOLF(112): 908797 35680.585480 (0.038501 liars)
8/1: 569648 32661.674867 (0.055724 liars)
HOLF(63): 603789 30351.435731 (0.049026 liars)
HOLF(252): 603760 30351.414149 (0.049028 liars)
HOLF(175): 573475 30129.462433 (0.051182 liars)
HOLF(343): 563026 30105.597604 (0.052067 liars)
HOLF(7): 561304 30103.702112 (0.052219 liars)
HOLF(28): 561291 30103.594525 (0.052220 liars)
7/1: 561262 30103.432875 (0.052222 liars)
HOLF(160): 968024 29900.174378 (0.030416 liars)
HOLF(360): 787646 27473.365542 (0.034279 liars)
HOLF(40): 731530 27244.810839 (0.036559 liars)
12/1: 573049 21699.785103 (0.037159 liars)
4/3: 514084 19468.176839 (0.037162 liars)
HOLF(208): 629369 18581.399448 (0.029092 liars)
HOLF(117): 537976 17612.610741 (0.032209 liars)
HOLF(468): 537955 17612.605043 (0.032210 liars)
HOLF(325): 511433 17484.284878 (0.033609 liars)
HOLF(13): 500462 17468.804354 (0.034303 liars)
HOLF(52): 500449 17468.768116 (0.034304 liars)
13/1: 500421 17468.730789 (0.034306 liars)
HOLF(336): 783563 14253.679825 (0.018026 liars)
5/2: 365774 13623.517263 (0.036561 liars)
10/1: 365690 13621.013294 (0.036562 liars)
HOLF(189): 648696 13463.450221 (0.020541 liars)
HOLF(21): 625007 13407.338881 (0.021223 liars)
HOLF(84): 624989 13407.236280 (0.021223 liars)
HOLF(240): 708379 12814.543954 (0.017927 liars)
16/1: 447049 12640.539859 (0.027880 liars)
HOLF(135): 453339 10836.451536 (0.023620 liars)
HOLF(375): 441050 10796.577196 (0.024182 liars)
HOLF(15): 437454 10792.915429 (0.024370 liars)
HOLF(60): 437432 10792.809499 (0.024371 liars)
21/1: 357313 7667.337582 (0.021230 liars)
HOLF(224): 317091 6984.020208 (0.021785 liars)
HOLF(176): 267676 6900.711231 (0.025451 liars)
HOLF(56): 240860 6372.167936 (0.026109 liars)
HOLF(99): 198313 6051.126152 (0.030052 liars)
HOLF(396): 198292 6051.071069 (0.030055 liars)
HOLF(275): 179819 5975.253036 (0.032683 liars)
HOLF(11): 176632 5970.557031 (0.033237 liars)
HOLF(44): 176625 5970.555016 (0.033239 liars)
11/1: 176597 5970.374357 (0.033243 liars)
15/1: 238551 5886.697178 (0.024375 liars)
7/3: 267618 5739.775463 (0.021219 liars)
5/3: 198831 4905.941151 (0.024372 liars)
HOLF(272): 205883 4614.137034 (0.022162 liars)
8/3: 242370 4544.994744 (0.018578 liars)
HOLF(153): 188165 4404.251459 (0.023135 liars)
HOLF(425): 166706 4334.618061 (0.025666 liars)
HOLF(17): 163070 4330.634866 (0.026207 liars)
HOLF(68): 163063 4330.623653 (0.026208 liars)
17/1: 163044 4330.583358 (0.026211 liars)
HOLF(25): 229664 4132.960814 (0.017835 liars)
HOLF(100): 229638 4132.900895 (0.017836 liars)
25/1: 229590 4132.639065 (0.017839 liars)
HOLF(480): 403743 4100.244664 (0.010104 liars)
20/1: 169514 3824.090950 (0.022307 liars)
HOLF(352): 264892 3750.053785 (0.014057 liars)
HOLF(120): 304086 3728.865094 (0.012188 liars)
5/4: 159632 3598.667566 (0.022291 liars)
24/1: 191568 3591.962331 (0.018576 liars)
7/2: 132424 3502.936603 (0.026106 liars)
HOLF(88): 205710 3447.951428 (0.016622 liars)
HOLF(297): 261193 3438.837490 (0.013080 liars)
HOLF(33): 251790 3424.378165 (0.013508 liars)
HOLF(132): 251769 3424.366585 (0.013509 liars)
14/1: 108384 2869.117014 (0.026124 liars)
9/2: 136547 2801.906214 (0.020311 liars)
28/1: 174249 2798.703345 (0.015933 liars)
7/4: 173235 2778.234519 (0.015909 liars)
HOLF(304): 202773 2700.064876 (0.013227 liars)
18/1: 121150 2487.656836 (0.020324 liars)
HOLF(171): 122446 2183.868137 (0.017677 liars)
HOLF(475): 113588 2161.274622 (0.018847 liars)
HOLF(19): 111136 2159.314630 (0.019242 liars)
HOLF(76): 111124 2159.294257 (0.019244 liars)
19/1: 111104 2159.111484 (0.019246 liars)
36/1: 160269 1998.949084 (0.012395 liars)
22/1: 111839 1875.736052 (0.016632 liars)
33/1: 126271 1717.597913 (0.013510 liars)
11/3: 125457 1706.633131 (0.013511 liars)
9/4: 132648 1652.313910 (0.012379 liars)
11/2: 93830 1572.038341 (0.016615 liars)
HOLF(464): 110480 1426.816676 (0.012832 liars)
HOLF(168): 160587 1404.581919 (0.008708 liars)
HOLF(261): 100865 1357.165132 (0.013365 liars)
HOLF(416): 113609 1356.579368 (0.011870 liars)
HOLF(29): 85926 1331.207969 (0.015373 liars)
HOLF(116): 85918 1331.150953 (0.015374 liars)
29/1: 85902 1331.111502 (0.015376 liars)
8/5: 112946 1265.778912 (0.011144 liars)
HOLF(104): 87774 1244.452702 (0.014078 liars)
HOLF(136): 113904 1232.677172 (0.010764 liars)
HOLF(333): 105973 1198.601649 (0.011247 liars)
HOLF(37): 97867 1187.368627 (0.012059 liars)
HOLF(148): 97860 1187.331086 (0.012060 liars)
10/3: 84223 1032.834131 (0.012188 liars)
15/2: 76716 941.084842 (0.012192 liars)
9/5: 94336 937.937426 (0.009893 liars)
27/1: 67699 923.969444 (0.013555 liars)
HOLF(57): 116621 916.844267 (0.007831 liars)
HOLF(228): 116603 916.727363 (0.007831 liars)
30/1: 72791 892.991408 (0.012193 liars)
HOLF(368): 76061 883.729162 (0.011551 liars)
HOLF(351): 96691 876.731659 (0.009026 liars)
HOLF(39): 92584 872.323934 (0.009378 liars)
HOLF(156): 92568 872.275088 (0.009379 liars)
32/1: 61200 863.205225 (0.014006 liars)
6/5: 70279 861.671300 (0.012186 liars)
HOLF(279): 74142 836.964140 (0.011225 liars)
HOLF(31): 70023 831.146427 (0.011799 liars)
HOLF(124): 70018 831.145126 (0.011800 liars)
31/1: 70006 831.118888 (0.011802 liars)
HOLF(207): 52504 745.792470 (0.014104 liars)
HOLF(315): 80040 744.257124 (0.009255 liars)
HOLF(23): 45750 733.684204 (0.015909 liars)
HOLF(92): 45743 733.675366 (0.015911 liars)
23/1: 45725 733.658023 (0.015917 liars)
HOLF(35): 69635 731.717492 (0.010453 liars)
HOLF(140): 69623 731.691255 (0.010454 liars)
HOLF(49): 75898 694.589979 (0.009110 liars)
HOLF(196): 75884 694.505366 (0.009110 liars)
26/1: 47760 678.445300 (0.014105 liars)
17/2: 61914 669.301167 (0.010752 liars)
16/3: 70548 658.627378 (0.009292 liars)
HOLF(369): 62412 622.575993 (0.009926 liars)
HOLF(69): 94946 616.021192 (0.006467 liars)
HOLF(276): 94931 616.019124 (0.006468 liars)
HOLF(41): 55976 614.444836 (0.010917 liars)
HOLF(164): 55968 614.418703 (0.010918 liars)
HOLF(184): 74052 591.970086 (0.007962 liars)
13/2: 39969 565.900959 (0.014059 liars)
34/1: 51946 563.274861 (0.010785 liars)
HOLF(105): 130935 557.846898 (0.004251 liars)
HOLF(420): 130908 557.791373 (0.004252 liars)
12/5: 73114 545.533699 (0.007434 liars)
13/4: 62083 534.496962 (0.008572 liars)
HOLF(280): 98986 519.290153 (0.005232 liars)
15/4: 68596 512.099309 (0.007438 liars)
11/4: 48720 495.825509 (0.010125 liars)
20/3: 65943 492.150738 (0.007435 liars)
HOLF(264): 88177 490.586272 (0.005548 liars)
13/3: 51460 484.464201 (0.009370 liars)
HOLF(459): 66699 466.483380 (0.006969 liars)
HOLF(51): 64514 464.707563 (0.007177 liars)
HOLF(204): 64503 464.690369 (0.007178 liars)
HOLF(85): 85905 452.113326 (0.005249 liars)
HOLF(340): 85885 452.028262 (0.005249 liars)
HOLF(61): 61266 450.491172 (0.007326 liars)
HOLF(244): 61259 450.476483 (0.007327 liars)
HOLF(55): 63010 420.542887 (0.006652 liars)
HOLF(220): 63000 420.540889 (0.006653 liars)
19/3: 52899 415.369378 (0.007821 liars)
HOLF(65): 59918 412.729985 (0.006865 liars)
HOLF(260): 59908 412.724608 (0.006866 liars)
HOLF(152): 41584 402.784571 (0.009639 liars)
35/1: 35881 377.766316 (0.010473 liars)
14/3: 42387 370.536843 (0.008704 liars)
7/5: 33712 353.752632 (0.010439 liars)
21/2: 40239 351.938503 (0.008708 liars)
23/3: 52371 339.533867 (0.006462 liars)
7/6: 38410 335.521202 (0.008697 liars)
HOLF(387): 40331 326.841391 (0.008071 liars)
HOLF(43): 37927 324.368039 (0.008516 liars)
HOLF(172): 37918 324.360853 (0.008518 liars)
(table truncated at score=300)
Expanding the HOLF multiplier search to 1335 (this is the first
1000, skipping values == 2 mod 4 which are useless for odd inputs),
repeatedly taking the highest-scoring multiplier, and then
re-scoring the rest on the remaining inputs, we get
HOLF(576): 4241422 373462.532635 (0.084286 liars)
HOLF(1152): 2499129 347987.036977 (0.129984 liars)
4/1: 2677623 316743.251183 (0.111564 liars)
2/1: 1529234 308713.615214 (0.182803 liars)
HOLF(768): 2904915 258822.446660 (0.085244 liars)
3/1: 1664383 216337.514816 (0.121888 liars)
HOLF(720): 1855468 128836.802295 (0.067080 liars)
5/1: 1276442 119297.503834 (0.089226 liars)
HOLF(864): 1877119 94959.831439 (0.049330 liars)
6/1: 786176 49427.156185 (0.060935 liars)
9/1: 793832 40333.001927 (0.049539 liars)
3/2: 588623 37007.808078 (0.060936 liars)
HOLF(1008): 977962 35975.964752 (0.036118 liars)
8/1: 569648 32661.674867 (0.055724 liars)
7/1: 561262 30103.432875 (0.052222 liars)
HOLF(640): 996840 29982.270516 (0.029629 liars)
12/1: 573049 21699.785103 (0.037159 liars)
4/3: 514084 19468.176839 (0.037162 liars)
HOLF(832): 645379 18616.746055 (0.028434 liars)
13/1: 500421 17468.730789 (0.034306 liars)
HOLF(336): 783561 14253.674071 (0.018026 liars)
5/2: 365774 13623.517263 (0.036561 liars)
10/1: 365690 13621.013294 (0.036562 liars)
HOLF(960): 742157 12877.768869 (0.017202 liars)
16/1: 447049 12640.539859 (0.027880 liars)
21/1: 357313 7667.337582 (0.021230 liars)
HOLF(896): 326156 7002.709359 (0.021242 liars)
HOLF(704): 282655 6939.992847 (0.024254 liars)
11/1: 176597 5970.374357 (0.033243 liars)
15/1: 238551 5886.697178 (0.024375 liars)
7/3: 267618 5739.775463 (0.021219 liars)
5/3: 198831 4905.941151 (0.024372 liars)
HOLF(1225): 307211 4827.670972 (0.015592 liars)
HOLF(1088): 211110 4623.590343 (0.021663 liars)
8/3: 242370 4544.994744 (0.018578 liars)
17/1: 163044 4330.583358 (0.026211 liars)
25/1: 229590 4132.639065 (0.017839 liars)
HOLF(480): 403741 4100.244165 (0.010104 liars)
20/1: 169514 3824.090950 (0.022307 liars)
HOLF(352): 264889 3750.036383 (0.014057 liars)
HOLF(528): 316368 3643.938503 (0.011452 liars)
5/4: 159632 3598.667566 (0.022291 liars)
24/1: 191568 3591.962331 (0.018576 liars)
7/2: 132424 3502.936603 (0.026106 liars)
14/1: 108384 2869.117014 (0.026124 liars)
9/2: 136547 2801.906214 (0.020311 liars)
28/1: 174249 2798.703345 (0.015933 liars)
7/4: 173235 2778.234519 (0.015909 liars)
HOLF(1216): 211574 2713.626481 (0.012744 liars)
18/1: 121150 2487.656836 (0.020324 liars)
19/1: 111104 2159.111484 (0.019246 liars)
36/1: 160269 1998.949084 (0.012395 liars)
22/1: 111839 1875.736052 (0.016632 liars)
33/1: 126271 1717.597913 (0.013510 liars)
11/3: 125457 1706.633131 (0.013511 liars)
9/4: 132648 1652.313910 (0.012379 liars)
11/2: 93830 1572.038341 (0.016615 liars)
HOLF(672): 210223 1536.799660 (0.007284 liars)
HOLF(464): 110480 1426.816676 (0.012832 liars)
HOLF(416): 113609 1356.579368 (0.011870 liars)
HOLF(544): 147180 1342.874803 (0.009083 liars)
29/1: 85902 1331.111502 (0.015376 liars)
HOLF(592): 126155 1274.405224 (0.010051 liars)
8/5: 112946 1265.778912 (0.011144 liars)
HOLF(675): 107322 1112.297578 (0.010311 liars)
HOLF(624): 155538 1053.577364 (0.006751 liars)
10/3: 84223 1032.834131 (0.012188 liars)
HOLF(912): 144209 971.291365 (0.006713 liars)
HOLF(496): 102796 949.590462 (0.009195 liars)
15/2: 76716 941.084842 (0.012192 liars)
9/5: 94336 937.937426 (0.009893 liars)
27/1: 67699 923.969444 (0.013555 liars)
30/1: 72791 892.991408 (0.012193 liars)
HOLF(368): 76058 883.692588 (0.011551 liars)
HOLF(560): 113386 872.312912 (0.007664 liars)
32/1: 61200 863.205225 (0.014006 liars)
6/5: 70279 861.671300 (0.012186 liars)
31/1: 70006 831.118888 (0.011802 liars)
23/1: 45725 733.658023 (0.015917 liars)
26/1: 47760 678.445300 (0.014105 liars)
17/2: 61914 669.301167 (0.010752 liars)
16/3: 70548 658.627378 (0.009292 liars)
HOLF(1104): 119998 657.464113 (0.005464 liars)
HOLF(736): 95329 646.015832 (0.006754 liars)
HOLF(656): 66715 644.134607 (0.009609 liars)
HOLF(1120): 129977 569.797553 (0.004374 liars)
13/2: 39969 565.900959 (0.014059 liars)
34/1: 51946 563.274861 (0.010785 liars)
HOLF(945): 135716 560.286618 (0.004120 liars)
HOLF(816): 104353 552.810874 (0.005284 liars)
12/5: 73114 545.533699 (0.007434 liars)
HOLF(1056): 115113 536.314948 (0.004648 liars)
13/4: 62083 534.496962 (0.008572 liars)
15/4: 68596 512.099309 (0.007438 liars)
HOLF(880): 103661 503.740154 (0.004848 liars)
11/4: 48720 495.825509 (0.010125 liars)
20/3: 65943 492.150738 (0.007435 liars)
13/3: 51460 484.464201 (0.009370 liars)
HOLF(976): 73171 472.948026 (0.006443 liars)
HOLF(765): 92197 455.817478 (0.004932 liars)
HOLF(1040): 76884 443.975083 (0.005758 liars)
HOLF(608): 54565 441.823060 (0.008064 liars)
19/3: 52899 415.369378 (0.007821 liars)
HOLF(688): 58920 380.361521 (0.006435 liars)
35/1: 35881 377.766316 (0.010473 liars)
14/3: 42387 370.536843 (0.008704 liars)
HOLF(1024): 57876 368.400994 (0.006345 liars)
7/5: 33712 353.752632 (0.010439 liars)
21/2: 40239 351.938503 (0.008708 liars)
23/3: 52371 339.533867 (0.006462 liars)
7/6: 38410 335.521202 (0.008697 liars)
HOLF(1248): 81599 325.374042 (0.003980 liars)
HOLF(928): 58654 301.450125 (0.005126 liars)
HOLF(400): 66389 298.363240 (0.004484 liars)
The semiprime-k and HOLF lists are computed independently, and
then interleaved to make them easier to compare.
From the second list, we can derive cumulative scores.
The 45 HOLF entries up to HOLF(928) sum to 1374316.2, while the
68 Semiprime-k entries up to k=7/6 sum to 1352620.6.
The total score for all SPSP(2) is 1387819.6, so the residuals
are 13503.365 and 35198.945. These roughly correspond (after
multiplying by 1.4427 = log2(e)) to the number of bits required
to store the secondary M-R witness table.
Using a cumulative score as the cutoff instead of a per-test score,
it takes 22 k values to leave a residual score less than 100K, while
it takes 8 HOLF tests to achieve the same thing.
The current nine semiprime-k tests leave a residue of 252502.6;
adding k=3/2 takes that to 215494.8. Five HOLF multipliers
leave 183750.9.
I'm not suggesting any particular change to the current 64-bit
prime test code, just exploring the parameter space.
Reply all
Reply to author
Forward
0 new messages