public class Hart_Fast2Mult
extends FactorAlgorithm
Pretty simple yet fast variant of Hart's one line factorizer.
This implementations introduces some improvements that make it the fastest factoring algorithm
for numbers with more then 20? and less then 50 bit.
It avoids the complexity of calculating the square root when factoring multiple numbers,
by storing the square roots of k in the main loop. This has the highest performance impact.
But there are some other improvements:
It uses an optimized trial division algorithm to factorize small numbers.
After calculating a number 'a' above sqrt(4*m*k) a will be adjusted to satisfy
some modulus a power of 2 argument.
It reuses the idea of rounding up by adding a well chosen constant (Warren D. Smith)
We choose k to be a multiple of 315 = 3*3*5*7 and 45 = 3*3*5 this causes that
a^2 - 4kn = b^2 mod 3*3*5*7 or 3*3*5 which increases the chance to find a solution a^2 - 4kn = b^2 pretty much.
We iterate over k1 = 315 * i and k2 = 45 * i in parallel, but make sure that k2 != k1.
General idea of this implementation:
It tires to find solutions for a^2 - 4*m*i*n = b^2 from fermat we then know that
gcd(a+b, n) and gcd(a-b, n) are divisors of n.
This is done by one simple loop over k were we generate numbers a = sqrt(4*m*k*n).
By storing sqrt(k) in an array this can be calculated fast.
Compared with the regular Lehman algorithm, the Hart algorithm does not
need a second loop to iterate over the numbers 'a' for a given 'k' in the equation a^2 - 4kn.
This means that the upper bound for this loop - which would be a expensive sqrt call - does not has to be calculated.
For each k the value sqrt(k) in order to determine a = ceil(sqrt(4kn))
the sqrt will be calculated only once and then stored in an array. This speeds up the sieving buy
a big factor since calculating the sqrt is expensive.
For any kind of test numbers except very hard semiprimes, Hart_TDiv_Race will be faster.