Class Hart_Fast
java.lang.Object
de.tilman_neumann.jml.factor.FactorAlgorithm
de.tilman_neumann.jml.factor.hart.Hart_Fast
public class Hart_Fast extends FactorAlgorithm
Pretty simple yet fast variant of Hart's one line factorizer.
The main problem with this implementation is that we need to know to nature of test numbers.
With doTDivFirst=false it is the fastest algorithm for hard semiprimes,
but if the test numbers contain factors < cbrt(N), it will fail to find some of them.
With doTDivFirst=true it will find all factors of any kind of numbers, but not extraordinarily fast.
Hart_TDiv_Race fixes that problem and is faster for test numbers that contain factors < cbrt(N).
-
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_Fast(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_Fast
public Hart_Fast(boolean doTDivFirst)Full constructor.- Parameters:
doTDivFirst
- If true then trial division is done before the Lehman loop. This is recommended if arguments N are known to have factors < cbrt(N) frequently.
-
-
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
-