Class FactorAlgorithm

java.lang.Object
de.tilman_neumann.jml.factor.FactorAlgorithm
Direct Known Subclasses:
CFrac, CFrac63, CombinedFactorAlgorithm, EllipticCurveMethod, Hart_Fast, Hart_Fast2Mult, Hart_Fast2Mult_FMA, Hart_Fast2Mult2, Hart_Simple, Hart_Squarefree, Hart_TDiv_Race, Hart_TDiv_Race2, Lehman_CustomKOrder, Lehman_Fast, Lehman_Simple, Lehman_Smith, PollardRho, PollardRho_ProductGcd, PollardRho31, PollardRhoBrent, PollardRhoBrent31, PollardRhoBrentMontgomery64, PollardRhoBrentMontgomery64_MH, PollardRhoBrentMontgomery64_MHInlined, PollardRhoBrentMontgomeryR64Mul63, PSIQSBase, SIQS, SIQS_Small, SquFoF31, SquFoF31Preload, SquFoF63, TDiv, TDiv31, TDiv31Barrett, TDiv31Inverse, TDiv63, TDiv63Inverse, TinyEcm64, TinyEcm64_MH, TinyEcm64_MHInlined

public abstract class FactorAlgorithm
extends java.lang.Object
Abstraction of integer factorization algorithms. This class provides a framework to find the complete prime factorization of N, requiring only to implement the method findSingleFactor(BigInteger).
  • Field Summary

    Fields
    Modifier and Type Field Description
    protected static int NUM_PRIMES_FOR_31_BIT_TDIV
    the number of primes needed to factor any int <= 2^31 - 1 using trial division
    protected java.lang.Integer tdivLimit  
  • Constructor Summary

    Constructors
    Constructor Description
    FactorAlgorithm()  
    FactorAlgorithm​(java.lang.Integer tdivLimit)  
  • Method Summary

    Modifier and Type Method Description
    SortedMultiset<java.math.BigInteger> factor​(java.math.BigInteger N)
    Decomposes the argument N into prime factors.
    void factor​(java.math.BigInteger N, SortedMultiset<java.math.BigInteger> primeFactors)
    Decomposes the argument N into prime factors.
    abstract java.math.BigInteger findSingleFactor​(java.math.BigInteger N)
    Find a single factor of the given N, which is composite and odd.
    static FactorAlgorithm getDefault()  
    abstract java.lang.String getName()  
    void searchFactors​(FactorArguments args, FactorResult result)
    Try to find at least one factor of the given args.N, which is composite and odd.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
  • Field Details

    • NUM_PRIMES_FOR_31_BIT_TDIV

      protected static final int NUM_PRIMES_FOR_31_BIT_TDIV
      the number of primes needed to factor any int <= 2^31 - 1 using trial division
      See Also:
      Constant Field Values
    • tdivLimit

      protected java.lang.Integer tdivLimit
  • Constructor Details

    • FactorAlgorithm

      public FactorAlgorithm()
    • FactorAlgorithm

      public FactorAlgorithm​(java.lang.Integer tdivLimit)
  • Method Details

    • getDefault

      public static FactorAlgorithm getDefault()
      Returns:
      The best available single-threaded factor algorithm. (multi-threading may not always be wanted)
    • getName

      public abstract java.lang.String getName()
      Returns:
      The name of the algorithm, possibly including important parameters.
    • factor

      public SortedMultiset<java.math.BigInteger> factor​(java.math.BigInteger N)
      Decomposes the argument N into prime factors. The result is a multiset of BigIntegers, sorted bottom-up.
      Parameters:
      N - Number to factor.
      Returns:
      The prime factorization of N
    • factor

      public void factor​(java.math.BigInteger N, SortedMultiset<java.math.BigInteger> primeFactors)
      Decomposes the argument N into prime factors.
      Parameters:
      N - Number to factor.
      primeFactors - a map to which found factors are added
    • searchFactors

      public void searchFactors​(FactorArguments args, FactorResult result)
      Try to find at least one factor of the given args.N, which is composite and odd. This is a default implementation for algorithms that will only find a single factor or none at all. For sub-algorithms that may find more factors at once this method should be overwritten appropriately.
      Parameters:
      args -
      result - the result of the factoring attempt. Should be initialized only once by the caller to reduce overhead.
    • findSingleFactor

      public abstract java.math.BigInteger findSingleFactor​(java.math.BigInteger N)
      Find a single factor of the given N, which is composite and odd.
      Parameters:
      N - number to be factored.
      Returns:
      factor