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 class FactorAlgorithm
      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 class FactorAlgorithm
      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