OK, I've uploaded a file is_likely_prime_1.c to the files section of mpir-devel.
It contains a self contained implementation of the BPSW test for single limbs. I already contacted the other author, Peter Shrimpton (who did the original implementation for FLINT), who has agreed to release his code under the LGPL v2+ (FLINT is GPL v2+). His only condition is that we list him as a developer of MPIR on our website and give him appropriate credit. As I am the only other author of that code it can be released under the LGPL. It should work as per FLINT-Lite. The only changes I made were: 1) powmod doesn't take negative exponents now as I don't think this is needed. 2) replaced round(x) with floor(x+0.5) as some machines don't provide round(). Two potential problems are that the is_square code uses the functions sqrt() and floor() from the math library, and the precomputed inverse stuff is probably not optimised on 32 bit machines (and possibly not on some 64 bit machines either). Bill. 2009/12/4 Bill Hart <[email protected]>: > I found Nicely's BPSW code on his website. Here are the times with > strong set to 0: > > 1) primes > > iBPSW: > bits = 1, min time is 64.532 cycles, max time is 64.889 cycles > bits = 2, min time is 551.978 cycles, max time is 40439.582 cycles > bits = 3, min time is 1481.438 cycles, max time is 1505.640 cycles > bits = 4, min time is 1690.125 cycles, max time is 1713.326 cycles > bits = 5, min time is 1634.273 cycles, max time is 1796.678 cycles > bits = 6, min time is 631.609 cycles, max time is 705.486 cycles > bits = 7, min time is 703.421 cycles, max time is 707.439 cycles > bits = 8, min time is 810.989 cycles, max time is 838.056 cycles > bits = 9, min time is 933.477 cycles, max time is 973.330 cycles > bits = 10, min time is 1065.187 cycles, max time is 1104.989 cycles > bits = 11, min time is 1176.622 cycles, max time is 1380.434 cycles > bits = 12, min time is 1451.705 cycles, max time is 1588.152 cycles > bits = 13, min time is 1646.486 cycles, max time is 1907.074 cycles > bits = 14, min time is 1618.428 cycles, max time is 1819.855 cycles > bits = 15, min time is 1901.565 cycles, max time is 2315.122 cycles > bits = 16, min time is 2366.067 cycles, max time is 2847.089 cycles > bits = 17, min time is 2927.263 cycles, max time is 3644.054 cycles > bits = 18, min time is 3919.337 cycles, max time is 4634.517 cycles > bits = 19, min time is 4812.206 cycles, max time is 6144.154 cycles > bits = 20, min time is 6320.959 cycles, max time is 7492.491 cycles > bits = 21, min time is 31685.071 cycles, max time is 34905.346 cycles > bits = 22, min time is 31976.952 cycles, max time is 38833.594 cycles > bits = 23, min time is 32019.867 cycles, max time is 38309.427 cycles > bits = 24, min time is 35487.123 cycles, max time is 37550.301 cycles > bits = 25, min time is 36391.670 cycles, max time is 38709.353 cycles > bits = 26, min time is 36915.411 cycles, max time is 42164.986 cycles > bits = 27, min time is 37576.214 cycles, max time is 42817.125 cycles > bits = 28, min time is 39723.566 cycles, max time is 44194.529 cycles > bits = 29, min time is 38939.314 cycles, max time is 45560.691 cycles > bits = 30, min time is 40318.145 cycles, max time is 44323.694 cycles > bits = 31, min time is 43281.631 cycles, max time is 47895.922 cycles > bits = 32, min time is 44575.454 cycles, max time is 48252.782 cycles > bits = 33, min time is 48133.982 cycles, max time is 54404.510 cycles > bits = 34, min time is 48407.671 cycles, max time is 54241.553 cycles > bits = 35, min time is 49240.155 cycles, max time is 56764.649 cycles > bits = 36, min time is 52645.502 cycles, max time is 59555.510 cycles > bits = 37, min time is 52719.569 cycles, max time is 61588.245 cycles > bits = 38, min time is 51457.227 cycles, max time is 56513.266 cycles > bits = 39, min time is 53113.515 cycles, max time is 60770.729 cycles > bits = 40, min time is 53863.574 cycles, max time is 62232.518 cycles > bits = 41, min time is 57386.088 cycles, max time is 61108.553 cycles > bits = 42, min time is 61287.490 cycles, max time is 64527.065 cycles > bits = 43, min time is 56022.034 cycles, max time is 64354.275 cycles > bits = 44, min time is 60824.650 cycles, max time is 63265.138 cycles > bits = 45, min time is 58838.873 cycles, max time is 66234.898 cycles > bits = 46, min time is 61500.422 cycles, max time is 73501.409 cycles > bits = 47, min time is 59894.513 cycles, max time is 73573.125 cycles > bits = 48, min time is 65192.246 cycles, max time is 68181.857 cycles > bits = 49, min time is 67262.901 cycles, max time is 70250.667 cycles > bits = 50, min time is 69266.914 cycles, max time is 71868.243 cycles > bits = 51, min time is 63088.183 cycles, max time is 77546.242 cycles > bits = 52, min time is 70646.928 cycles, max time is 77656.042 cycles > bits = 53, min time is 71909.400 cycles, max time is 78755.818 cycles > bits = 54, min time is 72077.205 cycles, max time is 83823.123 cycles > bits = 55, min time is 71176.173 cycles, max time is 78027.771 cycles > bits = 56, min time is 71257.162 cycles, max time is 82673.630 cycles > bits = 57, min time is 73694.239 cycles, max time is 80864.938 cycles > bits = 58, min time is 72710.235 cycles, max time is 84441.254 cycles > bits = 59, min time is 75244.255 cycles, max time is 84954.967 cycles > bits = 60, min time is 76106.530 cycles, max time is 83998.217 cycles > bits = 61, min time is 80983.282 cycles, max time is 85639.039 cycles > bits = 62, min time is 80526.974 cycles, max time is 87241.978 cycles > bits = 63, min time is 82530.775 cycles, max time is 91367.246 cycles > bits = 64, min time is 78548.883 cycles, max time is 92135.472 cycles > > 2) composites > > iBPSW: > bits = 1, min time is 64.553 cycles, max time is 67.764 cycles > bits = 2, min time is 1011.851 cycles, max time is 40690.097 cycles > bits = 3, min time is 638.529 cycles, max time is 1503.645 cycles > bits = 4, min time is 443.206 cycles, max time is 1609.022 cycles > bits = 5, min time is 409.343 cycles, max time is 1277.192 cycles > bits = 6, min time is 716.075 cycles, max time is 2030.554 cycles > bits = 7, min time is 633.776 cycles, max time is 1318.865 cycles > bits = 8, min time is 567.090 cycles, max time is 1285.251 cycles > bits = 9, min time is 811.867 cycles, max time is 1965.823 cycles > bits = 10, min time is 537.163 cycles, max time is 2105.794 cycles > bits = 11, min time is 449.905 cycles, max time is 2289.543 cycles > bits = 12, min time is 256.869 cycles, max time is 486.300 cycles > bits = 13, min time is 391.539 cycles, max time is 491.055 cycles > bits = 14, min time is 428.987 cycles, max time is 1038.708 cycles > bits = 15, min time is 508.797 cycles, max time is 1525.080 cycles > bits = 16, min time is 649.621 cycles, max time is 904.433 cycles > bits = 17, min time is 450.465 cycles, max time is 1769.604 cycles > bits = 18, min time is 248.959 cycles, max time is 1370.924 cycles > bits = 19, min time is 413.416 cycles, max time is 1849.894 cycles > bits = 20, min time is 446.925 cycles, max time is 1334.604 cycles > bits = 21, min time is 939.826 cycles, max time is 22480.760 cycles > bits = 22, min time is 408.566 cycles, max time is 13368.763 cycles > bits = 23, min time is 358.430 cycles, max time is 18654.210 cycles > bits = 24, min time is 352.884 cycles, max time is 36946.430 cycles > bits = 25, min time is 295.676 cycles, max time is 45451.965 cycles > bits = 26, min time is 440.507 cycles, max time is 11721.418 cycles > bits = 27, min time is 448.231 cycles, max time is 13541.857 cycles > bits = 28, min time is 371.660 cycles, max time is 7820.938 cycles > bits = 29, min time is 302.289 cycles, max time is 7028.093 cycles > bits = 30, min time is 315.861 cycles, max time is 1785.368 cycles > bits = 31, min time is 376.648 cycles, max time is 16127.045 cycles > bits = 32, min time is 454.480 cycles, max time is 24414.243 cycles > bits = 33, min time is 419.695 cycles, max time is 55610.177 cycles > bits = 34, min time is 403.621 cycles, max time is 36090.758 cycles > bits = 35, min time is 411.957 cycles, max time is 13874.008 cycles > bits = 36, min time is 365.711 cycles, max time is 28175.580 cycles > bits = 37, min time is 400.531 cycles, max time is 3188.391 cycles > bits = 38, min time is 391.644 cycles, max time is 2544.577 cycles > bits = 39, min time is 310.019 cycles, max time is 2459.853 cycles > bits = 40, min time is 310.157 cycles, max time is 20741.646 cycles > bits = 41, min time is 307.233 cycles, max time is 22037.581 cycles > bits = 42, min time is 433.873 cycles, max time is 13090.596 cycles > bits = 43, min time is 355.867 cycles, max time is 20756.806 cycles > bits = 44, min time is 546.488 cycles, max time is 17858.379 cycles > bits = 45, min time is 335.842 cycles, max time is 3048.902 cycles > bits = 46, min time is 174.362 cycles, max time is 865.052 cycles > bits = 47, min time is 308.729 cycles, max time is 2162.782 cycles > bits = 48, min time is 611.582 cycles, max time is 4489.002 cycles > bits = 49, min time is 620.193 cycles, max time is 27723.867 cycles > bits = 50, min time is 280.858 cycles, max time is 10345.271 cycles > bits = 51, min time is 404.822 cycles, max time is 35989.015 cycles > bits = 52, min time is 403.352 cycles, max time is 4333.535 cycles > bits = 53, min time is 241.694 cycles, max time is 72409.560 cycles > bits = 54, min time is 909.189 cycles, max time is 6285.180 cycles > bits = 55, min time is 459.143 cycles, max time is 2005.191 cycles > bits = 56, min time is 437.869 cycles, max time is 11339.705 cycles > bits = 57, min time is 268.852 cycles, max time is 13587.644 cycles > bits = 58, min time is 271.890 cycles, max time is 1128.425 cycles > bits = 59, min time is 412.058 cycles, max time is 22380.738 cycles > bits = 60, min time is 1034.295 cycles, max time is 4311.648 cycles > bits = 61, min time is 387.594 cycles, max time is 17555.115 cycles > bits = 62, min time is 672.620 cycles, max time is 18483.850 cycles > bits = 63, min time is 298.745 cycles, max time is 13494.847 cycles > bits = 64, min time is 252.986 cycles, max time is 23048.589 cycles > > Bill. > > 2009/12/4 Bill Hart <[email protected]>: >> Does anyone know how Nicely's code works. Does it actually contain a >> BPSW test? I see an extra strong Lucas test. Is that it or is it the >> strong Lucas-Selfridge test? >> >> Assuming it is the strong Lucas-Selfridge test, here are the times: >> >> 1) primes >> >> is_probabprime_BPSW: >> bits = 1, min time is 61.985 cycles, max time is 62.614 cycles >> bits = 2, min time is 527.511 cycles, max time is 5794.675 cycles >> bits = 3, min time is 3663.343 cycles, max time is 3687.511 cycles >> bits = 4, min time is 4294.546 cycles, max time is 4968.830 cycles >> bits = 5, min time is 3340.450 cycles, max time is 7610.115 cycles >> bits = 6, min time is 4843.608 cycles, max time is 8898.315 cycles >> bits = 7, min time is 4602.178 cycles, max time is 8144.019 cycles >> bits = 8, min time is 5991.857 cycles, max time is 10905.638 cycles >> bits = 9, min time is 9210.771 cycles, max time is 9667.430 cycles >> bits = 10, min time is 10746.994 cycles, max time is 12086.393 cycles >> bits = 11, min time is 11384.925 cycles, max time is 12423.267 cycles >> bits = 12, min time is 11719.608 cycles, max time is 14783.253 cycles >> bits = 13, min time is 12960.525 cycles, max time is 16329.370 cycles >> bits = 14, min time is 15416.198 cycles, max time is 19028.253 cycles >> bits = 15, min time is 15875.115 cycles, max time is 18912.795 cycles >> bits = 16, min time is 17351.400 cycles, max time is 19415.205 cycles >> bits = 17, min time is 14884.879 cycles, max time is 23171.126 cycles >> bits = 18, min time is 18249.552 cycles, max time is 24481.687 cycles >> bits = 19, min time is 16524.305 cycles, max time is 25484.811 cycles >> bits = 20, min time is 19145.499 cycles, max time is 25808.695 cycles >> bits = 21, min time is 21565.467 cycles, max time is 25776.237 cycles >> bits = 22, min time is 22635.634 cycles, max time is 28931.901 cycles >> bits = 23, min time is 23726.787 cycles, max time is 27372.267 cycles >> bits = 24, min time is 25403.599 cycles, max time is 31869.257 cycles >> bits = 25, min time is 26707.197 cycles, max time is 30901.039 cycles >> bits = 26, min time is 28002.360 cycles, max time is 34222.443 cycles >> bits = 27, min time is 26586.521 cycles, max time is 35404.423 cycles >> bits = 28, min time is 26935.495 cycles, max time is 32165.829 cycles >> bits = 29, min time is 28738.478 cycles, max time is 33661.467 cycles >> bits = 30, min time is 30764.129 cycles, max time is 38157.429 cycles >> bits = 31, min time is 31418.702 cycles, max time is 41914.745 cycles >> bits = 32, min time is 34986.466 cycles, max time is 40663.985 cycles >> bits = 33, min time is 33149.081 cycles, max time is 38600.911 cycles >> bits = 34, min time is 36955.474 cycles, max time is 44849.733 cycles >> bits = 35, min time is 38962.378 cycles, max time is 44244.165 cycles >> bits = 36, min time is 38973.405 cycles, max time is 50842.834 cycles >> bits = 37, min time is 40406.078 cycles, max time is 51502.526 cycles >> bits = 38, min time is 45536.006 cycles, max time is 52824.271 cycles >> bits = 39, min time is 43522.231 cycles, max time is 51041.969 cycles >> bits = 40, min time is 45643.077 cycles, max time is 52261.289 cycles >> bits = 41, min time is 46506.247 cycles, max time is 59813.040 cycles >> bits = 42, min time is 48651.298 cycles, max time is 55844.345 cycles >> bits = 43, min time is 47439.573 cycles, max time is 57396.933 cycles >> bits = 44, min time is 48550.958 cycles, max time is 57405.117 cycles >> bits = 45, min time is 49595.547 cycles, max time is 64121.119 cycles >> bits = 46, min time is 55459.707 cycles, max time is 62772.953 cycles >> bits = 47, min time is 54178.707 cycles, max time is 65096.654 cycles >> bits = 48, min time is 54454.526 cycles, max time is 62244.953 cycles >> bits = 49, min time is 54683.784 cycles, max time is 71340.881 cycles >> bits = 50, min time is 56204.393 cycles, max time is 65542.275 cycles >> bits = 51, min time is 52629.024 cycles, max time is 66244.498 cycles >> bits = 52, min time is 61295.839 cycles, max time is 65937.984 cycles >> bits = 53, min time is 59369.534 cycles, max time is 69865.293 cycles >> bits = 54, min time is 59775.480 cycles, max time is 67337.133 cycles >> bits = 55, min time is 63530.397 cycles, max time is 74050.306 cycles >> bits = 56, min time is 57579.288 cycles, max time is 70048.920 cycles >> bits = 57, min time is 64289.054 cycles, max time is 73008.003 cycles >> bits = 58, min time is 70346.503 cycles, max time is 74402.325 cycles >> bits = 59, min time is 61098.374 cycles, max time is 81539.259 cycles >> bits = 60, min time is 70055.465 cycles, max time is 76438.111 cycles >> bits = 61, min time is 72445.190 cycles, max time is 81103.286 cycles >> bits = 62, min time is 75068.187 cycles, max time is 82614.466 cycles >> bits = 63, min time is 72253.289 cycles, max time is 79274.808 cycles >> bits = 64, min time is 73485.597 cycles, max time is 84383.547 cycles >> >> 2) composites >> >> is_probabprime_BPSW: >> bits = 1, min time is 67.127 cycles, max time is 68.572 cycles >> bits = 2, min time is 5840.527 cycles, max time is 6012.120 cycles >> bits = 3, min time is 1716.754 cycles, max time is 6751.834 cycles >> bits = 4, min time is 363.321 cycles, max time is 5304.542 cycles >> bits = 5, min time is 527.223 cycles, max time is 3934.059 cycles >> bits = 6, min time is 2056.917 cycles, max time is 6729.626 cycles >> bits = 7, min time is 1399.546 cycles, max time is 5922.934 cycles >> bits = 8, min time is 6160.251 cycles, max time is 9922.790 cycles >> bits = 9, min time is 728.931 cycles, max time is 5263.279 cycles >> bits = 10, min time is 557.493 cycles, max time is 4596.654 cycles >> bits = 11, min time is 719.321 cycles, max time is 7177.680 cycles >> bits = 12, min time is 477.325 cycles, max time is 6349.264 cycles >> bits = 13, min time is 655.865 cycles, max time is 13961.245 cycles >> bits = 14, min time is 746.582 cycles, max time is 12047.142 cycles >> bits = 15, min time is 716.002 cycles, max time is 9826.946 cycles >> bits = 16, min time is 720.269 cycles, max time is 11631.801 cycles >> bits = 17, min time is 1020.101 cycles, max time is 19122.103 cycles >> bits = 18, min time is 961.358 cycles, max time is 13265.433 cycles >> bits = 19, min time is 473.537 cycles, max time is 21392.174 cycles >> bits = 20, min time is 10946.160 cycles, max time is 22015.622 cycles >> bits = 21, min time is 12148.591 cycles, max time is 26378.691 cycles >> bits = 22, min time is 8718.905 cycles, max time is 27389.578 cycles >> bits = 23, min time is 476.465 cycles, max time is 18610.256 cycles >> bits = 24, min time is 708.537 cycles, max time is 10990.865 cycles >> bits = 25, min time is 720.973 cycles, max time is 31767.435 cycles >> bits = 26, min time is 477.275 cycles, max time is 31715.201 cycles >> bits = 27, min time is 1391.393 cycles, max time is 27912.802 cycles >> bits = 28, min time is 10150.374 cycles, max time is 37506.648 cycles >> bits = 29, min time is 721.102 cycles, max time is 35302.515 cycles >> bits = 30, min time is 364.629 cycles, max time is 20789.167 cycles >> bits = 31, min time is 1097.990 cycles, max time is 39989.381 cycles >> bits = 32, min time is 552.910 cycles, max time is 38937.471 cycles >> bits = 33, min time is 901.282 cycles, max time is 31816.863 cycles >> bits = 34, min time is 13799.058 cycles, max time is 40163.921 cycles >> bits = 35, min time is 1162.162 cycles, max time is 20972.737 cycles >> bits = 36, min time is 14745.903 cycles, max time is 46513.869 cycles >> bits = 37, min time is 944.328 cycles, max time is 43435.270 cycles >> bits = 38, min time is 481.848 cycles, max time is 51622.586 cycles >> bits = 39, min time is 1402.947 cycles, max time is 23844.597 cycles >> bits = 40, min time is 1653.463 cycles, max time is 56029.587 cycles >> bits = 41, min time is 714.900 cycles, max time is 54112.584 cycles >> bits = 42, min time is 487.468 cycles, max time is 55815.712 cycles >> bits = 43, min time is 26897.830 cycles, max time is 54086.009 cycles >> bits = 44, min time is 2416.046 cycles, max time is 57456.274 cycles >> bits = 45, min time is 15769.202 cycles, max time is 55384.546 cycles >> bits = 46, min time is 1090.282 cycles, max time is 59227.625 cycles >> bits = 47, min time is 20467.273 cycles, max time is 59844.005 cycles >> bits = 48, min time is 20352.187 cycles, max time is 39489.627 cycles >> bits = 49, min time is 20038.603 cycles, max time is 22440.901 cycles >> bits = 50, min time is 31371.554 cycles, max time is 66357.717 cycles >> bits = 51, min time is 21082.753 cycles, max time is 67786.697 cycles >> bits = 52, min time is 718.490 cycles, max time is 65116.354 cycles >> bits = 53, min time is 22242.149 cycles, max time is 72314.181 cycles >> bits = 54, min time is 19225.343 cycles, max time is 74030.489 cycles >> bits = 55, min time is 1408.615 cycles, max time is 62320.858 cycles >> bits = 56, min time is 2011.250 cycles, max time is 71306.043 cycles >> bits = 57, min time is 715.596 cycles, max time is 48666.426 cycles >> bits = 58, min time is 1411.025 cycles, max time is 36619.221 cycles >> bits = 59, min time is 2130.261 cycles, max time is 79684.191 cycles >> bits = 60, min time is 1524.660 cycles, max time is 53533.928 cycles >> bits = 61, min time is 24257.240 cycles, max time is 78399.051 cycles >> bits = 62, min time is 23054.922 cycles, max time is 77868.319 cycles >> bits = 63, min time is 503.802 cycles, max time is 85392.977 cycles >> bits = 64, min time is 28290.290 cycles, max time is 55160.521 cycles >> >> This looks much worse, but then again, I have no idea whether I am >> supposed to be setting some #defines or what. >> >> Bill. >> >> >> 2009/12/4 Bill Hart <[email protected]>: >>> Whoops, I forgot to mention, being profiling code, it averages out >>> over lots of random values. So the min time there is not actually the >>> minimum time to check primality or otherwise of n, but the minimum >>> time the profile run takes. >>> >>> Each timing run works with sufficiently many *different* random values >>> n until a timing run takes a measurable amount of time, say 0.2s. But >>> for each n tried, the primality test is run on that same n 1000 times >>> and averaged over that 1000. >>> >>> For a higher number of bits there begins to be quite a lot of >>> difference in min and max because it needs to do very few timing runs >>> (i.e. use very few different values of n) to get a significant amount >>> of accumulated time. Thus it is only testing primality of relatively >>> few different values of n. Thus the values it chooses become >>> progressively more important in determining how long it takes, hence >>> the variability in timing. >>> >>> If I increase that 1000 to 1000000 then the composite min goes down to >>> 12 cycles for each bit size, because the minimum time is the time it >>> takes to check that an even number is not prime. If I decrease the >>> 1000 to about 3 then the max times become more accurate (but not >>> substantially different from what I reported). >>> >>> Bill. >>> >>> 2009/12/4 Bill Hart <[email protected]>: >>>> OK, I think I now have profiles for the BPSW test in FLINT-Lite for 1 >>>> to 64 bits: >>>> >>>> 1) n = n_randbits(bits); n = n_nextprime(n); - prime >>>> >>>> is_probabprime_BPSW: >>>> bits = 1, min time is 41.318 cycles, max time is 41.762 cycles >>>> bits = 2, min time is 157.077 cycles, max time is 211.797 cycles >>>> bits = 3, min time is 1521.374 cycles, max time is 1737.195 cycles >>>> bits = 4, min time is 1671.113 cycles, max time is 2991.291 cycles >>>> bits = 5, min time is 1837.207 cycles, max time is 3277.498 cycles >>>> bits = 6, min time is 2361.549 cycles, max time is 2907.369 cycles >>>> bits = 7, min time is 2688.065 cycles, max time is 4432.293 cycles >>>> bits = 8, min time is 3019.783 cycles, max time is 5556.871 cycles >>>> bits = 9, min time is 3405.127 cycles, max time is 5785.951 cycles >>>> bits = 10, min time is 1410.274 cycles, max time is 6117.360 cycles >>>> bits = 11, min time is 1367.475 cycles, max time is 1913.774 cycles >>>> bits = 12, min time is 1709.866 cycles, max time is 2046.679 cycles >>>> bits = 13, min time is 1445.799 cycles, max time is 2280.487 cycles >>>> bits = 14, min time is 1577.479 cycles, max time is 2475.494 cycles >>>> bits = 15, min time is 1622.289 cycles, max time is 1957.071 cycles >>>> bits = 16, min time is 1777.970 cycles, max time is 2261.688 cycles >>>> bits = 17, min time is 1819.906 cycles, max time is 2252.343 cycles >>>> bits = 18, min time is 1949.441 cycles, max time is 2763.886 cycles >>>> bits = 19, min time is 2052.178 cycles, max time is 2462.383 cycles >>>> bits = 20, min time is 2169.075 cycles, max time is 2770.822 cycles >>>> bits = 21, min time is 2307.915 cycles, max time is 3253.845 cycles >>>> bits = 22, min time is 2446.937 cycles, max time is 3018.096 cycles >>>> bits = 23, min time is 2471.630 cycles, max time is 3165.302 cycles >>>> bits = 24, min time is 2614.217 cycles, max time is 3080.465 cycles >>>> bits = 25, min time is 2748.463 cycles, max time is 3541.913 cycles >>>> bits = 26, min time is 2836.793 cycles, max time is 3259.786 cycles >>>> bits = 27, min time is 3006.309 cycles, max time is 3405.096 cycles >>>> bits = 28, min time is 3183.096 cycles, max time is 4558.008 cycles >>>> bits = 29, min time is 3315.902 cycles, max time is 4838.030 cycles >>>> bits = 30, min time is 3747.024 cycles, max time is 4762.286 cycles >>>> bits = 31, min time is 3831.069 cycles, max time is 5121.367 cycles >>>> bits = 32, min time is 3955.632 cycles, max time is 4833.267 cycles >>>> bits = 33, min time is 4003.467 cycles, max time is 4496.352 cycles >>>> bits = 34, min time is 4129.584 cycles, max time is 4987.810 cycles >>>> bits = 35, min time is 4202.160 cycles, max time is 4850.853 cycles >>>> bits = 36, min time is 4701.710 cycles, max time is 5708.133 cycles >>>> bits = 37, min time is 4661.753 cycles, max time is 5524.591 cycles >>>> bits = 38, min time is 4826.417 cycles, max time is 5515.176 cycles >>>> bits = 39, min time is 4928.194 cycles, max time is 5641.893 cycles >>>> bits = 40, min time is 5265.761 cycles, max time is 6197.842 cycles >>>> bits = 41, min time is 4956.504 cycles, max time is 6786.573 cycles >>>> bits = 42, min time is 4950.806 cycles, max time is 5951.421 cycles >>>> bits = 43, min time is 5412.518 cycles, max time is 5977.817 cycles >>>> bits = 44, min time is 5580.165 cycles, max time is 6455.061 cycles >>>> bits = 45, min time is 5759.976 cycles, max time is 6370.485 cycles >>>> bits = 46, min time is 5721.984 cycles, max time is 6381.789 cycles >>>> bits = 47, min time is 5907.189 cycles, max time is 6853.471 cycles >>>> bits = 48, min time is 6104.880 cycles, max time is 6870.645 cycles >>>> bits = 49, min time is 6088.687 cycles, max time is 6453.665 cycles >>>> bits = 50, min time is 6301.347 cycles, max time is 7475.510 cycles >>>> bits = 51, min time is 6440.674 cycles, max time is 6915.634 cycles >>>> bits = 52, min time is 6693.151 cycles, max time is 6843.871 cycles >>>> bits = 53, min time is 6810.957 cycles, max time is 8321.763 cycles >>>> bits = 54, min time is 7275.977 cycles, max time is 8676.069 cycles >>>> bits = 55, min time is 7425.243 cycles, max time is 8833.807 cycles >>>> bits = 56, min time is 7752.353 cycles, max time is 8618.054 cycles >>>> bits = 57, min time is 7959.816 cycles, max time is 9656.907 cycles >>>> bits = 58, min time is 7891.286 cycles, max time is 9424.985 cycles >>>> bits = 59, min time is 8092.786 cycles, max time is 8531.602 cycles >>>> bits = 60, min time is 8056.872 cycles, max time is 9400.306 cycles >>>> bits = 61, min time is 8154.384 cycles, max time is 8729.301 cycles >>>> bits = 62, min time is 8474.393 cycles, max time is 9675.010 cycles >>>> bits = 63, min time is 8511.110 cycles, max time is 8839.827 cycles >>>> bits = 64, min time is 8542.951 cycles, max time is 9547.522 cycles >>>> >>>> 2) n = n_randbits(bits) - likely composite >>>> >>>> is_probabprime_BPSW: >>>> bits = 1, min time is 12.060 cycles, max time is 44.057 cycles >>>> bits = 2, min time is 56.064 cycles, max time is 78.749 cycles >>>> bits = 3, min time is 262.825 cycles, max time is 443.345 cycles >>>> bits = 4, min time is 203.246 cycles, max time is 529.206 cycles >>>> bits = 5, min time is 353.365 cycles, max time is 597.048 cycles >>>> bits = 6, min time is 301.952 cycles, max time is 573.333 cycles >>>> bits = 7, min time is 330.889 cycles, max time is 781.560 cycles >>>> bits = 8, min time is 249.096 cycles, max time is 577.418 cycles >>>> bits = 9, min time is 369.734 cycles, max time is 537.382 cycles >>>> bits = 10, min time is 276.715 cycles, max time is 599.738 cycles >>>> bits = 11, min time is 327.437 cycles, max time is 1928.085 cycles >>>> bits = 12, min time is 373.757 cycles, max time is 681.569 cycles >>>> bits = 13, min time is 182.665 cycles, max time is 461.024 cycles >>>> bits = 14, min time is 502.922 cycles, max time is 1777.234 cycles >>>> bits = 15, min time is 520.193 cycles, max time is 1217.526 cycles >>>> bits = 16, min time is 403.329 cycles, max time is 2065.738 cycles >>>> bits = 17, min time is 313.534 cycles, max time is 1128.306 cycles >>>> bits = 18, min time is 262.136 cycles, max time is 1009.343 cycles >>>> bits = 19, min time is 485.613 cycles, max time is 2158.387 cycles >>>> bits = 20, min time is 492.557 cycles, max time is 1245.614 cycles >>>> bits = 21, min time is 532.513 cycles, max time is 1399.498 cycles >>>> bits = 22, min time is 535.313 cycles, max time is 1090.943 cycles >>>> bits = 23, min time is 245.650 cycles, max time is 1710.942 cycles >>>> bits = 24, min time is 589.800 cycles, max time is 1571.771 cycles >>>> bits = 25, min time is 432.478 cycles, max time is 1083.027 cycles >>>> bits = 26, min time is 278.344 cycles, max time is 2596.626 cycles >>>> bits = 27, min time is 349.594 cycles, max time is 918.408 cycles >>>> bits = 28, min time is 728.091 cycles, max time is 2080.855 cycles >>>> bits = 29, min time is 487.606 cycles, max time is 1466.496 cycles >>>> bits = 30, min time is 400.691 cycles, max time is 1680.162 cycles >>>> bits = 31, min time is 722.897 cycles, max time is 3292.601 cycles >>>> bits = 32, min time is 552.791 cycles, max time is 1608.576 cycles >>>> bits = 33, min time is 585.089 cycles, max time is 2224.639 cycles >>>> bits = 34, min time is 586.112 cycles, max time is 1634.890 cycles >>>> bits = 35, min time is 603.511 cycles, max time is 2306.277 cycles >>>> bits = 36, min time is 624.701 cycles, max time is 1864.858 cycles >>>> bits = 37, min time is 610.523 cycles, max time is 2245.095 cycles >>>> bits = 38, min time is 674.256 cycles, max time is 1864.166 cycles >>>> bits = 39, min time is 501.079 cycles, max time is 1884.893 cycles >>>> bits = 40, min time is 1078.399 cycles, max time is 1966.539 cycles >>>> bits = 41, min time is 537.093 cycles, max time is 2086.663 cycles >>>> bits = 42, min time is 736.394 cycles, max time is 2178.257 cycles >>>> bits = 43, min time is 1111.378 cycles, max time is 2823.583 cycles >>>> bits = 44, min time is 558.648 cycles, max time is 2281.134 cycles >>>> bits = 45, min time is 572.550 cycles, max time is 1543.973 cycles >>>> bits = 46, min time is 599.135 cycles, max time is 2606.099 cycles >>>> bits = 47, min time is 597.096 cycles, max time is 2440.546 cycles >>>> bits = 48, min time is 1186.891 cycles, max time is 4610.604 cycles >>>> bits = 49, min time is 855.699 cycles, max time is 3669.195 cycles >>>> bits = 50, min time is 669.112 cycles, max time is 2666.518 cycles >>>> bits = 51, min time is 1299.735 cycles, max time is 2758.073 cycles >>>> bits = 52, min time is 1332.624 cycles, max time is 3731.018 cycles >>>> bits = 53, min time is 1030.674 cycles, max time is 3372.115 cycles >>>> bits = 54, min time is 1466.748 cycles, max time is 3175.947 cycles >>>> bits = 55, min time is 1093.359 cycles, max time is 3165.907 cycles >>>> bits = 56, min time is 1501.320 cycles, max time is 7656.775 cycles >>>> bits = 57, min time is 1521.972 cycles, max time is 3303.411 cycles >>>> bits = 58, min time is 3246.638 cycles, max time is 3471.531 cycles >>>> bits = 59, min time is 1650.977 cycles, max time is 8608.049 cycles >>>> bits = 60, min time is 1619.892 cycles, max time is 3515.671 cycles >>>> bits = 61, min time is 1690.850 cycles, max time is 3546.489 cycles >>>> bits = 62, min time is 1686.543 cycles, max time is 3602.791 cycles >>>> bits = 63, min time is 1757.700 cycles, max time is 8525.469 cycles >>>> bits = 64, min time is 1867.281 cycles, max time is 3722.457 cycles >>>> >>>> Of course these "composite" times would be a lot lower if trial >>>> factoring were performed first (a factor of 2 is checked for already). >>>> >>>> In FLINT-Lite the likely_prime function first checks for perfect >>>> powers, which is super quick, then does a full primality test up to >>>> 10^16 using known combinations of bases for strong pseudoprimes. This >>>> is actually slower than doing a BPSW test as above, from about 24 bits >>>> up to 10^16 by a factor of up to 2, but the result is guaranteed up to >>>> that limit. From 10^16 it just runs a BPSW test from there on. >>>> >>>> For MPIR I guess we may as well just do trial division, then do BPSW, >>>> then over GMP_NUMB_BITS bits just do about 12 strong pseudo prime >>>> tests to random bases, i.e. just loop what we currently do about 12 >>>> times. >>>> >>>> I'm not sure I understand exactly what check you did up to 2^64. Did >>>> you take all the (composite) base 2 strong pseudoprimes and then test >>>> that BPSW eliminates them all? If you consider that to be a reliable >>>> result, I could use this in FLINT-Lite to give a guaranteed primality >>>> test up to 2^64 could I not? Was there some trial factoring done >>>> first? If so, what was the limit? >>>> >>>> Bill. >>>> >>>> 2009/12/4 Bill Hart <[email protected]>: >>>>> I've actually not done any timings of the BPSW code in FLINT. Using it >>>>> doesn't solve my problem, ha ha, but yeah we could use it in MPIR. I >>>>> consider it to be well tested by now. It is only for integers up to 64 >>>>> bits though (on a 64 bit machine). >>>>> >>>>> I'll run some timings on Selmer and post them. Perhaps we can get some >>>>> idea of how fast it is. The most optimised version is in FLINT Lite. >>>>> >>>>> Do we still have an optimised version of Nicely's code? I recall that >>>>> for the benchmark we were uninterested in all the optimisations, as >>>>> they weren't profiling MPIR itself, but Nicely's code. However I did >>>>> not keep track of whether we just benchmarked larger integers or >>>>> whether we hacked Nicely's code itself. >>>>> >>>>> Bill. >>>>> >>>>> 2009/12/4 Jeff Gilchrist <[email protected]>: >>>>>> On Fri, Dec 4, 2009 at 12:29 PM, Bill Hart <[email protected]> >>>>>> wrote: >>>>>>> Whoah, it just does trial division up to 1000 then uses a *single* >>>>>>> *random* base for a strong pseudoprime test! >>>>>>> >>>>>>> I have a definite problem with this. What is the probability of >>>>>>> returning a composite? Assuming the factors are bigger than 1000, it >>>>>>> is like 1/4. >>>>>> >>>>>> How fast is your BPSW code? From that project I have been working on >>>>>> I have confirmed there are no psp's up to 2^64 using BPSW so that >>>>>> should work quite well after the trial division assuming it doesn't >>>>>> take too long to run. >>>>>> >>>>>> Or we could even use the BPSW code from Thomas R. Nicely since he >>>>>> already gave us permission to use it for the benchmark code if it is >>>>>> faster than your implementation. >>>>>> >>>>>> Jeff. >>>>>> >>>>>> -- >>>>>> >>>>>> You received this message because you are subscribed to the Google >>>>>> Groups "mpir-devel" group. >>>>>> To post to this group, send email to [email protected]. >>>>>> To unsubscribe from this group, send email to >>>>>> [email protected]. >>>>>> For more options, visit this group at >>>>>> http://groups.google.com/group/mpir-devel?hl=en. >>>>>> >>>>>> >>>>>> >>>>> >>>> >>> >> > -- You received this message because you are subscribed to the Google Groups "mpir-devel" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/mpir-devel?hl=en.
