Class FactorInteger<MOD extends GcdRingElem<MOD> & Modular>

java.lang.Object
edu.jas.ufd.FactorAbstract<BigInteger>
edu.jas.ufd.FactorInteger<MOD>
Type Parameters:
MOD -
All Implemented Interfaces:
Factorization<BigInteger>, Serializable
public class FactorInteger<MOD extends GcdRingElem<MOD> & Modular> extends FactorAbstract<BigInteger>
Integer coefficients factorization algorithms. This class implements factorization methods for polynomials over integers.
See Also:

  • Field Details

  • Constructor Details

    • FactorInteger

      public FactorInteger()
      No argument constructor.

    • FactorInteger

      public FactorInteger(RingFactory<BigInteger> cfac)
      Constructor.
      Parameters:
      cfac - coefficient ring factory.

  • Method Details

    • isIrreducible

      public boolean isIrreducible(GenPolynomial<BigInteger> P)
      GenPolynomial test if is irreducible.
      Specified by:
      isIrreducible in interface Factorization<MOD extends GcdRingElem<MOD> & Modular>
      Overrides:
      isIrreducible in class FactorAbstract<BigInteger>
      Parameters:
      P - GenPolynomial.
      Returns:
      true if P is irreducible, else false.

    • isIrreducibleEisenstein

      public boolean isIrreducibleEisenstein(GenPolynomial<BigInteger> P)
      GenPolynomial test if is irreducible with Eisenstein criterion.
      Parameters:
      P - univariate polynomial.
      Returns:
      true if P is irreducible, else false if it is unknown.

    • baseFactorsSquarefree

      public List<GenPolynomial<BigInteger>> baseFactorsSquarefree(GenPolynomial<BigInteger> P)
      GenPolynomial base factorization of a squarefree polynomial.
      Specified by:
      baseFactorsSquarefree in class FactorAbstract<BigInteger>
      Parameters:
      P - squarefree and primitive! GenPolynomial.
      Returns:
      [p_1,...,p_k] with P = prod_{i=1, ..., k} p_i.

    • factorDegrees

      public BitSet factorDegrees(List<ExpVector> E, int deg)
      BitSet for factor degree list.
      Parameters:
      E - exponent vector list.
      Returns:
      {b_0,...,b_k} a BitSet of possible factor degrees.

    • degreeSum

      public static <C extends RingElem<C>> long degreeSum(List<GenPolynomial<C>> L)
      Sum of all degrees.
      Parameters:
      L - univariate polynomial list.
      Returns:
      sum deg(p) for p in L.

    • searchFactorsMonic

      List<GenPolynomial<BigInteger>> searchFactorsMonic(GenPolynomial<BigInteger> C, BigInteger M, List<GenPolynomial<MOD>> F, BitSet D)
      Factor search with modular Hensel lifting algorithm. Let p = f_i.ring.coFac.modul() i = 0, ..., n-1 and assume C == prod_{0,...,n-1} f_i mod p with ggt(f_i,f_j) == 1 mod p for i != j
      Parameters:
      C - GenPolynomial.
      M - bound on the coefficients of g_i as factors of C.
      F - = [f_0,...,f_{n-1}] List<GenPolynomial>.
      D - bit set of possible factor degrees.
      Returns:
      [g_0,...,g_{n-1}] = lift(C,F), with C = prod_{0,...,n-1} g_i mod p**e. Note: does not work in all cases.

    • searchFactorsNonMonic

      List<GenPolynomial<BigInteger>> searchFactorsNonMonic(GenPolynomial<BigInteger> C, BigInteger M, List<GenPolynomial<MOD>> F, BitSet D)
      Factor search with modular Hensel lifting algorithm. Let p = f_i.ring.coFac.modul() i = 0, ..., n-1 and assume C == prod_{0,...,n-1} f_i mod p with ggt(f_i,f_j) == 1 mod p for i != j
      Parameters:
      C - GenPolynomial.
      M - bound on the coefficients of g_i as factors of C.
      F - = [f_0,...,f_{n-1}] List<GenPolynomial>.
      D - bit set of possible factor degrees.
      Returns:
      [g_0,...,g_{n-1}] = lift(C,F), with C = prod_{0,...,n-1} g_i mod p**e.

    • factorsSquarefree

      public List<GenPolynomial<BigInteger>> factorsSquarefree(GenPolynomial<BigInteger> P)
      GenPolynomial factorization of a multivariate squarefree polynomial, using Hensel lifting if possible.
      Specified by:
      factorsSquarefree in interface Factorization<MOD extends GcdRingElem<MOD> & Modular>
      Overrides:
      factorsSquarefree in class FactorAbstract<BigInteger>
      Parameters:
      P - squarefree and primitive! (respectively monic) multivariate GenPolynomial over the integers.
      Returns:
      [p_1,...,p_k] with P = prod_{i=1,...,r} p_i.

    • factorsSquarefreeOptions

      public List<GenPolynomial<BigInteger>> factorsSquarefreeOptions(GenPolynomial<BigInteger> P, boolean opti, boolean tlex)
      GenPolynomial factorization of a multivariate squarefree polynomial, using Hensel lifting if possible.
      Parameters:
      P - squarefree and primitive! (respectively monic) multivariate GenPolynomial over the integers.
      opti - true, if polynomial variables should be optimized, else false.
      tlex - true, if INVLEX term order should be forced, else false.
      Returns:
      [p_1,...,p_k] with P = prod_{i=1,...,r} p_i.

    • factorsSquarefreeHensel

      public List<GenPolynomial<BigInteger>> factorsSquarefreeHensel(GenPolynomial<BigInteger> P)
      GenPolynomial factorization of a multivariate squarefree polynomial, using Hensel lifting.
      Parameters:
      P - squarefree and primitive! (respectively monic) multivariate GenPolynomial over the integers.
      Returns:
      [p_1,...,p_k] with P = prod_{i=1,...,r} p_i.

    • testSeparate

      boolean testSeparate(List<BigInteger> A, BigInteger b)
      Test if b has a prime factor different to the elements of A.
      Parameters:
      A - list of integer with at least one different prime factor.
      b - integer to test with A.
      Returns:
      true, if b hase a prime factor different to elements of A

    • isNearlySquarefree

      boolean isNearlySquarefree(GenPolynomial<BigInteger> P)