Package edu.jas.ufd
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>
,java.io.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:
- Serialized Form
-
-
Field Summary
Fields Modifier and Type Field Description private static boolean
debug
private static org.apache.logging.log4j.Logger
logger
protected GreatestCommonDivisorAbstract<MOD>
mengine
Gcd engine for modular base coefficients.protected FactorAbstract<MOD>
mfactor
Factorization engine for modular base coefficients.-
Fields inherited from class edu.jas.ufd.FactorAbstract
engine, sengine
-
-
Constructor Summary
Constructors Constructor Description FactorInteger()
No argument constructor.FactorInteger(RingFactory<BigInteger> cfac)
Constructor.
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description java.util.List<GenPolynomial<BigInteger>>
baseFactorsSquarefree(GenPolynomial<BigInteger> P)
GenPolynomial base factorization of a squarefree polynomial.static <C extends RingElem<C>>
longdegreeSum(java.util.List<GenPolynomial<C>> L)
Sum of all degrees.java.util.BitSet
factorDegrees(java.util.List<ExpVector> E, int deg)
BitSet for factor degree list.java.util.List<GenPolynomial<BigInteger>>
factorsSquarefree(GenPolynomial<BigInteger> P)
GenPolynomial factorization of a multivariate squarefree polynomial, using Hensel lifting if possible.java.util.List<GenPolynomial<BigInteger>>
factorsSquarefreeHensel(GenPolynomial<BigInteger> P)
GenPolynomial factorization of a multivariate squarefree polynomial, using Hensel lifting.java.util.List<GenPolynomial<BigInteger>>
factorsSquarefreeOptions(GenPolynomial<BigInteger> P, boolean opti, boolean tlex)
GenPolynomial factorization of a multivariate squarefree polynomial, using Hensel lifting if possible.boolean
isIrreducible(GenPolynomial<BigInteger> P)
GenPolynomial test if is irreducible.boolean
isIrreducibleEisenstein(GenPolynomial<BigInteger> P)
GenPolynomial test if is irreducible with Eisenstein criterion.(package private) boolean
isNearlySquarefree(GenPolynomial<BigInteger> P)
(package private) java.util.List<GenPolynomial<BigInteger>>
searchFactorsMonic(GenPolynomial<BigInteger> C, BigInteger M, java.util.List<GenPolynomial<MOD>> F, java.util.BitSet D)
Factor search with modular Hensel lifting algorithm.(package private) java.util.List<GenPolynomial<BigInteger>>
searchFactorsNonMonic(GenPolynomial<BigInteger> C, BigInteger M, java.util.List<GenPolynomial<MOD>> F, java.util.BitSet D)
Factor search with modular Hensel lifting algorithm.(package private) boolean
testSeparate(java.util.List<BigInteger> A, BigInteger b)
Test if b has a prime factor different to the elements of A.-
Methods inherited from class edu.jas.ufd.FactorAbstract
baseFactors, baseFactorsRadical, basePrimitivePart, factors, factorsDegree, factorsRadical, factorsRadical, factorsSquarefreeKronecker, factorsSquarefreeOptimize, isFactorization, isFactorization, isRecursiveFactorization, isReducible, isSquarefree, normalizeFactorization, primitivePart, recursiveFactors, recursiveFactorsSquarefree, removeOnce, squarefreeFactors, squarefreePart, toString
-
-
-
-
Field Detail
-
logger
private static final org.apache.logging.log4j.Logger logger
-
debug
private static final boolean debug
-
mfactor
protected final FactorAbstract<MOD extends GcdRingElem<MOD> & Modular> mfactor
Factorization engine for modular base coefficients.
-
mengine
protected final GreatestCommonDivisorAbstract<MOD extends GcdRingElem<MOD> & Modular> mengine
Gcd engine for modular base coefficients.
-
-
Constructor Detail
-
FactorInteger
public FactorInteger()
No argument constructor.
-
FactorInteger
public FactorInteger(RingFactory<BigInteger> cfac)
Constructor.- Parameters:
cfac
- coefficient ring factory.
-
-
Method Detail
-
isIrreducible
public boolean isIrreducible(GenPolynomial<BigInteger> P)
GenPolynomial test if is irreducible.- Specified by:
isIrreducible
in interfaceFactorization<MOD extends GcdRingElem<MOD> & Modular>
- Overrides:
isIrreducible
in classFactorAbstract<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 java.util.List<GenPolynomial<BigInteger>> baseFactorsSquarefree(GenPolynomial<BigInteger> P)
GenPolynomial base factorization of a squarefree polynomial.- Specified by:
baseFactorsSquarefree
in classFactorAbstract<BigInteger>
- Parameters:
P
- squarefree and primitive! GenPolynomial.- Returns:
- [p_1,...,p_k] with P = prod_{i=1, ..., k} p_i.
-
factorDegrees
public java.util.BitSet factorDegrees(java.util.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(java.util.List<GenPolynomial<C>> L)
Sum of all degrees.- Parameters:
L
- univariate polynomial list.- Returns:
- sum deg(p) for p in L.
-
searchFactorsMonic
java.util.List<GenPolynomial<BigInteger>> searchFactorsMonic(GenPolynomial<BigInteger> C, BigInteger M, java.util.List<GenPolynomial<MOD>> F, java.util.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
java.util.List<GenPolynomial<BigInteger>> searchFactorsNonMonic(GenPolynomial<BigInteger> C, BigInteger M, java.util.List<GenPolynomial<MOD>> F, java.util.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 java.util.List<GenPolynomial<BigInteger>> factorsSquarefree(GenPolynomial<BigInteger> P)
GenPolynomial factorization of a multivariate squarefree polynomial, using Hensel lifting if possible.- Specified by:
factorsSquarefree
in interfaceFactorization<MOD extends GcdRingElem<MOD> & Modular>
- Overrides:
factorsSquarefree
in classFactorAbstract<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 java.util.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 java.util.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(java.util.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)
-
-