improve accuracy of integer factorization with primality testing.

[oscardssmith]

For numbers <2^64, not having factors <2^16 means that they have a roughly 1/2 chance of being prime. As such, it is worthwhile to perform a primality check. This can be done efficiently using Miller-Rabin with the bases (2, 325, 9375, 28178, 450775, 9780504, 1795265022) which have been proven to give the correct answer for all inputs <2^64. This can be done efficiently using Montgomery multiplication for the modular exponentiation, and runs in ~1us for prime inputs and ~350ns for composite inputs. This will have a somewhat notable affect on the time the algorithm takes, but makes it very easy to never give the wrong answer (which is somewhat messing with benchmarking since the cases where the current algorithm messes up tend to be the points that will take longer to factor anyway).

[cristaloleg]

This can be done efficiently using Miller-Rabin with the bases (2, 325, 9375, 28178, 450775, 9780504, 1795265022) which have been proven to give the correct answer for all inputs <2^64

~~According to Wikipedia for p < 2 ** 64 bases 2, 7, and 61 is enough.~~

~~See https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test#Testing_against_small_sets_of_bases~~

Sorry, I mixed 2^32 and 2^64.