Class Hart_Fast2Mult
java.lang.Object
de.tilman_neumann.jml.factor.FactorAlgorithm
de.tilman_neumann.jml.factor.hart.Hart_Fast2Mult
public class Hart_Fast2Mult extends FactorAlgorithm
Pretty simple yet fast variant of Hart's one line factorizer.
This implementation introduces some improvements that make it our fastest factoring algorithm
in a range somewhere between 25 and 48 bit.
General idea of this implementation:
For some n to factor, it tries to find solutions for a^2 - 4*k*n = b^2 from Fermat, with k = i*K_MULT, i=1,2,3,... ;
we then know that gcd(a+b, n) and gcd(a-b, n) are divisors of n.
In contrast to Lehman's algorithm, this is done in a single loop over k where we generate numbers a = sqrt(4*k*n).
This implies that the upper bound for Lehman's 'a'-loop - which would be an expensive sqrt() call - does not need to be calculated.
For each k, the sqrt(k) required to determine a = ceil(sqrt(4kn)) will be calculated only once and then stored in an array.
This speeds up the sieving by a big factor since calculating the sqrt is expensive.
After calculating a number 'a' above sqrt(4*k*n), 'a' will be adjusted to satisfy some conditions modulo powers of 2.
These adjustments have been slightly improved compared to those used by Lehman.
The implementation reuses Warren D. Smith's idea of rounding up by adding a well chosen constant.
Instead of a single multiplier for k we use two of them, which means another small speedup although we do not fully understand why.
The implementation uses an optimized trial division algorithm to factorize small numbers.
-
Field Summary
Fields inherited from class de.tilman_neumann.jml.factor.FactorAlgorithm
NUM_PRIMES_FOR_31_BIT_TDIV, tdivLimit
-
Constructor Summary
Constructors Constructor Description Hart_Fast2Mult(boolean doTDivFirst)
Full constructor. -
Method Summary
Modifier and Type Method Description long
findSingleFactor(long N)
Find a factor of long N.java.math.BigInteger
findSingleFactor(java.math.BigInteger N)
Find a single factor of the given N, which is composite and odd.java.lang.String
getName()
static void
main(java.lang.String[] args)
Test.Methods inherited from class de.tilman_neumann.jml.factor.FactorAlgorithm
factor, factor, getDefault, searchFactors
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
-
Constructor Details
-
Hart_Fast2Mult
public Hart_Fast2Mult(boolean doTDivFirst)Full constructor.- Parameters:
doTDivFirst
- If true then trial division is done before the Hart loop. This is recommended if arguments N are known to have factors < cbrt(N) frequently. With doTDivFirst=false, this implementation is pretty fast for hard semiprimes. But the smaller possible factors get, it will become slower and slower.
-
-
Method Details
-
getName
public java.lang.String getName()- Specified by:
getName
in classFactorAlgorithm
- Returns:
- The name of the algorithm, possibly including important parameters.
-
findSingleFactor
public java.math.BigInteger findSingleFactor(java.math.BigInteger N)Description copied from class:FactorAlgorithm
Find a single factor of the given N, which is composite and odd.- Specified by:
findSingleFactor
in classFactorAlgorithm
- Parameters:
N
- number to be factored.- Returns:
- factor
-
findSingleFactor
public long findSingleFactor(long N)Find a factor of long N.- Parameters:
N
-- Returns:
- factor of N
-
main
public static void main(java.lang.String[] args)Test.- Parameters:
args
- ignored
-