Initial work on prime factorization.
Initial work on prime factorization.

This commit adds spire.math.primes.Factored, a data type representing
the prime factorization of an integer. It also adds three algorithms
for factoring an arbitrary SafeLong:

  1. Trial division (worst)
  2. Wheel division (about x1.5 faster than Trial division)
  3. Pollard Rho (fastest)

We cheat in Pollard Rho and use BigInt#isProbablePrime

None of these algorithms is state-of-the-art and they all do best when
some of the prime factors are small. So the worst-case is when you
have a composite number with two prime factors of roughly equal size.

On my machine using Pollard Rho a 20-digit composite with two 10-digit
prime factors took about 500ms to factor, but a 40-digit with two
20-digit prime factors didn't complete in the time I was willing to
wait.

adampingel/spire,rklaehn/spire,tixxit/spire,kevinmeredith/spire,siddhartha-gadgil/spire,codeaudit/spire,guersam/spire,guersam/spire,woparry/spire,non/spire,JackSullivan/spire,AlecZorab/spire,kevinmeredith/spire,adampingel/spire,JackSullivan/spire,non/spire,woparry/spire,tixxit/spire,rklaehn/spire,codeaudit/spire,siddhartha-gadgil/spire,AlecZorab/spire