Package edu.jas.ufd
Class FactorInteger<MOD extends GcdRingElem<MOD> & Modular>
- 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 Summary
FieldsModifier and TypeFieldDescriptionprivate static final boolean
private static final org.apache.logging.log4j.Logger
protected final GreatestCommonDivisorAbstract
<MOD> Gcd engine for modular base coefficients.protected final FactorAbstract
<MOD> Factorization engine for modular base coefficients.Fields inherited from class edu.jas.ufd.FactorAbstract
engine, sengine
-
Constructor Summary
ConstructorsConstructorDescriptionNo argument constructor.FactorInteger
(RingFactory<BigInteger> cfac) Constructor. -
Method Summary
Modifier and TypeMethodDescriptionGenPolynomial base factorization of a squarefree polynomial.static <C extends RingElem<C>>
longdegreeSum
(List<GenPolynomial<C>> L) Sum of all degrees.factorDegrees
(List<ExpVector> E, int deg) BitSet for factor degree list.GenPolynomial factorization of a multivariate squarefree polynomial, using Hensel lifting if possible.GenPolynomial factorization of a multivariate squarefree polynomial, using Hensel lifting.factorsSquarefreeOptions
(GenPolynomial<BigInteger> P, boolean opti, boolean tlex) GenPolynomial factorization of a multivariate squarefree polynomial, using Hensel lifting if possible.boolean
GenPolynomial test if is irreducible.boolean
GenPolynomial test if is irreducible with Eisenstein criterion.(package private) boolean
(package private) List
<GenPolynomial<BigInteger>> searchFactorsMonic
(GenPolynomial<BigInteger> C, BigInteger M, List<GenPolynomial<MOD>> F, BitSet D) Factor search with modular Hensel lifting algorithm.(package private) List
<GenPolynomial<BigInteger>> searchFactorsNonMonic
(GenPolynomial<BigInteger> C, BigInteger M, List<GenPolynomial<MOD>> F, BitSet D) Factor search with modular Hensel lifting algorithm.(package private) boolean
testSeparate
(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 Details
-
logger
private static final org.apache.logging.log4j.Logger logger -
debug
private static final boolean debug -
mfactor
Factorization engine for modular base coefficients. -
mengine
Gcd engine for modular base coefficients.
-
-
Constructor Details
-
FactorInteger
public FactorInteger()No argument constructor. -
FactorInteger
Constructor.- Parameters:
cfac
- coefficient ring factory.
-
-
Method Details
-
isIrreducible
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
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
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
BitSet for factor degree list.- Parameters:
E
- exponent vector list.- Returns:
- {b_0,...,b_k} a BitSet of possible factor degrees.
-
degreeSum
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
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 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
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
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
-