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.
