# Word-size primality test and factoring (Fredrik) Pari used to be much better than FLINT for primality testing and factoring word-size integers at least in some input ranges. After some recent optimizations I've made to FLINT, I expect that this should no longer be the case, and I've done some quick benchmarking to verify this. Average time in seconds for 100000 random inputs of each bit size: isprime factorint bits pari flint ratio pari flint ratio ----------------------------------------------------------- 2 1.27e-08 4.40e-09 2.89x 2.46e-08 5.42e-09 4.53x 3 1.33e-08 4.37e-09 3.04x 3.58e-08 6.71e-09 5.33x 4 1.43e-08 4.38e-09 3.26x 4.45e-08 8.45e-09 5.26x 5 1.43e-08 4.37e-09 3.28x 4.98e-08 9.16e-09 5.44x 6 1.51e-08 4.37e-09 3.47x 5.47e-08 1.04e-08 5.26x 7 1.60e-08 4.38e-09 3.66x 5.94e-08 1.22e-08 4.87x 8 1.68e-08 4.36e-09 3.84x 6.36e-08 1.37e-08 4.65x 9 1.72e-08 4.39e-09 3.92x 6.82e-08 1.47e-08 4.64x 10 1.87e-08 4.39e-09 4.25x 7.27e-08 1.58e-08 4.60x 11 1.93e-08 4.37e-09 4.41x 7.88e-08 1.68e-08 4.69x 12 2.03e-08 4.38e-09 4.63x 8.45e-08 1.79e-08 4.72x 13 2.14e-08 4.39e-09 4.89x 9.06e-08 1.88e-08 4.82x 14 2.29e-08 4.39e-09 5.22x 9.62e-08 1.96e-08 4.91x 15 2.48e-08 4.39e-09 5.65x 1.05e-07 2.05e-08 5.10x 16 2.90e-08 5.65e-09 5.13x 1.14e-07 2.30e-08 4.94x 17 2.62e-08 5.65e-09 4.64x 1.27e-07 2.65e-08 4.81x 18 2.39e-08 5.69e-09 4.19x 1.38e-07 2.83e-08 4.89x 19 2.51e-08 5.67e-09 4.43x 1.57e-07 3.04e-08 5.17x 20 2.72e-08 5.65e-09 4.81x 1.77e-07 3.29e-08 5.38x 21 2.80e-08 1.46e-08 1.91x 1.99e-07 4.09e-08 4.87x 22 2.88e-08 1.51e-08 1.91x 2.18e-07 4.79e-08 4.56x 23 2.93e-08 1.54e-08 1.90x 2.38e-07 5.52e-08 4.31x 24 3.05e-08 1.59e-08 1.92x 2.59e-07 6.31e-08 4.10x 25 3.07e-08 1.63e-08 1.88x 2.97e-07 7.18e-08 4.13x 26 3.15e-08 1.68e-08 1.87x 3.35e-07 8.13e-08 4.12x 27 3.22e-08 1.73e-08 1.86x 3.75e-07 9.15e-08 4.10x 28 3.26e-08 1.76e-08 1.85x 4.26e-07 1.03e-07 4.14x 29 3.34e-08 1.82e-08 1.84x 4.89e-07 1.17e-07 4.18x 30 3.41e-08 1.85e-08 1.84x 5.64e-07 1.31e-07 4.31x 31 3.80e-08 1.89e-08 2.01x 6.61e-07 1.48e-07 4.46x 32 4.02e-08 1.97e-08 2.04x 7.71e-07 1.69e-07 4.56x 33 5.11e-08 2.42e-08 2.11x 9.08e-07 1.99e-07 4.56x 34 5.78e-08 2.44e-08 2.37x 1.08e-06 2.37e-07 4.55x 35 6.19e-08 2.45e-08 2.53x 1.25e-06 2.75e-07 4.56x 36 6.34e-08 2.49e-08 2.55x 1.51e-06 3.32e-07 4.56x 37 6.45e-08 2.52e-08 2.56x 1.72e-06 3.92e-07 4.39x 38 6.62e-08 2.55e-08 2.60x 2.04e-06 4.62e-07 4.41x 39 6.48e-08 2.57e-08 2.52x 2.39e-06 5.47e-07 4.37x 40 6.37e-08 2.59e-08 2.46x 2.88e-06 6.38e-07 4.51x 41 6.42e-08 2.64e-08 2.43x 3.37e-06 7.53e-07 4.47x 42 6.43e-08 2.71e-08 2.37x 4.02e-06 8.73e-07 4.61x 43 6.44e-08 2.69e-08 2.39x 4.78e-06 1.03e-06 4.64x 44 6.48e-08 2.74e-08 2.37x 5.77e-06 1.20e-06 4.81x 45 6.63e-08 2.76e-08 2.40x 6.77e-06 1.35e-06 5.02x 46 6.73e-08 2.82e-08 2.39x 8.09e-06 1.54e-06 5.25x 47 6.76e-08 2.80e-08 2.41x 9.27e-06 1.74e-06 5.33x 48 6.98e-08 2.83e-08 2.47x 1.02e-05 1.94e-06 5.25x 49 7.00e-08 2.87e-08 2.44x 1.14e-05 2.17e-06 5.23x 50 7.09e-08 2.89e-08 2.45x 1.26e-05 2.45e-06 5.14x 51 7.22e-08 2.92e-08 2.47x 1.38e-05 2.72e-06 5.07x 52 7.26e-08 2.99e-08 2.43x 1.51e-05 3.05e-06 4.96x 53 7.30e-08 3.02e-08 2.42x 1.66e-05 3.40e-06 4.89x 54 7.48e-08 3.05e-08 2.45x 1.83e-05 3.78e-06 4.83x 55 7.59e-08 3.08e-08 2.46x 1.98e-05 4.22e-06 4.69x 56 7.66e-08 3.11e-08 2.46x 2.15e-05 4.70e-06 4.58x 57 7.75e-08 3.14e-08 2.47x 2.36e-05 5.19e-06 4.55x 58 7.86e-08 3.15e-08 2.50x 2.56e-05 5.83e-06 4.38x 59 8.04e-08 3.13e-08 2.57x 2.79e-05 6.52e-06 4.28x 60 8.00e-08 3.26e-08 2.45x 3.00e-05 7.36e-06 4.08x 61 8.11e-08 3.25e-08 2.49x 3.29e-05 8.28e-06 3.97x 62 8.25e-08 3.28e-08 2.51x 3.51e-05 9.25e-06 3.80x 63 8.50e-08 3.69e-08 2.30x 3.78e-05 1.07e-05 3.54x 64 8.54e-08 3.75e-08 2.28x 4.11e-05 1.23e-05 3.34x Here are the main tricks currently used in FLINT, some of which would make sense to implement in Pari too where they are not already used. Primality testing: * Static bitmap mod 2 up to 15 bits, mod 30 up to 20 bits * Trial division by a handful of small fixed primes * Between 21 and 32 bits, use a single base-2 test and catch all passing composites with a hash table * Modular arithmetic up to 32 bits uses Shoup modular reduction * Between 33 and 64 bits, use a base-2 test, then a single extra base strong probable prime test with a base chosen from a hash table to guarantee catching all remaining composites * Modular arithmetic up to 64 bits uses Montgomery reduction Factoring: * Trial division uses exactly the 16-bit primes. Divisibility testing is done by multiplying by precomputed inverses mod 2^64 * A primality test is done at a strategically chosen point in the middle of trial division * Between 33 and 38 bits, try Hart's one line factor algorithm with SQUFOF as a fallback (in practice SQUFOF is never needed) * Between 39 and 64 bits, try one run of Pollard-Brent (succeeds in 99.9% of cases), then one line factor, then SQUFOF as a fallback * Pollard-Brent uses Montgomery arithmetic * Primality testing (of the input as well as partial factors) skips trial division