Class TDiv31Inverse

java.lang.Object
de.tilman_neumann.jml.factor.FactorAlgorithm
de.tilman_neumann.jml.factor.tdiv.TDiv31Inverse

public class TDiv31Inverse
extends FactorAlgorithm
Trial division factor algorithm using double-valued Barrett reduction, thus replacing division by multiplications. Instead of dividing N by consecutive primes, we store the reciprocals of those primes, too, and multiply N by those reciprocals. Only if such a result is near to an integer we need to do a division. This variant abstains from testing N%primes[i] when the discriminator test indicates a neat division, and unrolls the loop in findSingleFactor().
  • Field Summary

    Fields inherited from class de.tilman_neumann.jml.factor.FactorAlgorithm

    NUM_PRIMES_FOR_31_BIT_TDIV, tdivLimit
  • Constructor Summary

    Constructors
    Constructor Description
    TDiv31Inverse()  
  • Method Summary

    Modifier and Type Method Description
    void factor​(java.math.BigInteger Nbig, int Nexp, SortedMultiset<java.math.BigInteger> primeFactors)
    Find all factor of NBig, which must have less than 32 bit.
    void factor​(java.math.BigInteger Nbig, SortedMultiset<java.math.BigInteger> primeFactors)
    Decomposes the argument N into prime factors.
    int findSingleFactor​(int 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()  

    Methods inherited from class de.tilman_neumann.jml.factor.FactorAlgorithm

    factor, getDefault, searchFactors

    Methods inherited from class java.lang.Object

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

    • TDiv31Inverse

      public TDiv31Inverse()
  • Method Details

    • getName

      public java.lang.String getName()
      Specified by:
      getName in class FactorAlgorithm
      Returns:
      The name of the algorithm, possibly including important parameters.
    • factor

      public void factor​(java.math.BigInteger Nbig, SortedMultiset<java.math.BigInteger> primeFactors)
      Description copied from class: FactorAlgorithm
      Decomposes the argument N into prime factors.
      Overrides:
      factor in class FactorAlgorithm
      Parameters:
      Nbig - Number to factor.
      primeFactors - a map to which found factors are added
    • factor

      public void factor​(java.math.BigInteger Nbig, int Nexp, SortedMultiset<java.math.BigInteger> primeFactors)
      Find all factor of NBig, which must have less than 32 bit.
      Parameters:
      Nbig -
      Nexp - the exponent which with found factors are added to primeFactors
      primeFactors -
    • 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 int findSingleFactor​(int N)