Factorisation issues

[JASory]

I tried to build this library to benchmark the QS implementation : it failed due to incorrect typing. A trivial fix to a understandable error, but running it reveals many more issues.

1. BigUint's seem to be used for all arithmetic, this results in excessive overhead. Serious mathematical software heavily relies on the speed of hardware arithmetic, introducing multiprecision arrays needlessly can easily eliminate theoretical time complexity improvement
2. Due to 1. PollardRho is very slow. For instance, factoring 1125899906843507^2 takes 66s on my machine, my own pollard-rho implementation takes around 1s.
3. Quadratic sieve fails for many semiprimes. Infact it seems like it only works for small factors which pollardrho is faster for anyway.

[dlubarov]

Hey thanks for trying it. This is indeed a pretty immature/experimental library; for now I wouldn't recommend it unless someone needs a Rust implementation (so more mature libraries aren't available) and has modest performance requirements.

(1) I agree BigUint is slow, but it was just a requirement for our use case, where we didn't have any particular fixed bit width. Changing the allocator (e.g. with tikv-jemallocator) might help a bit on some platforms.

We could maybe generalize it to work with some generic number traits, which could include fixed-length bignums. The traits in num conceptually fit, but I don't think they have everything we need, like binary decomposition.

(3) I'm not sure why it would fail, that does seem unexpected. The slowness is somewhat expected - there seem to be many orders of magnitude between naive and serious qsieve implementations, and this one is somewhere in the middle currently, still far slower than the state of the art.