14 #ifndef FAC_FQ_FACTORIZE_H 15 #define FAC_FQ_FACTORIZE_H 86 "GF as base field expected");
102 bool substCheck=
true 111 bool foundOne=
false;
112 int * substDegree=
new int [F.
level()];
118 if (substDegree [
i-1] > 1)
125 substDegree[
i-1]= -1;
136 tmp2=
i.getItem().factor();
139 if (substDegree[
j-1] > 1)
146 j.getItem().exp()*
i.getItem().exp()));
148 delete [] substDegree;
151 delete [] substDegree;
160 "time for squarefree factorization over Fq: ");
170 "time to factorize sqrfree factor over Fq: ");
171 for (i= bufResult; i.
hasItem(); i++)
186 bool substCheck=
true 195 bool foundOne=
false;
196 int * substDegree=
new int [F.
level()];
202 if (substDegree [
i-1] > 1)
209 substDegree[
i-1]= -1;
220 tmp2=
i.getItem().factor();
223 if (substDegree[
j-1] > 1)
230 j.getItem().exp()*
i.getItem().exp()));
232 delete [] substDegree;
235 delete [] substDegree;
243 "time for squarefree factorization over Fq: ");
253 "time to factorize sqrfree factor over Fq: ");
254 for (i= bufResult; i.
hasItem(); i++)
268 bool substCheck=
true 272 "GF as base field expected");
279 bool foundOne=
false;
280 int * substDegree=
new int [F.
level()];
286 if (substDegree [
i-1] > 1)
293 substDegree[
i-1]= -1;
304 tmp2=
i.getItem().factor();
307 if (substDegree[
j-1] > 1)
314 j.getItem().exp()*
i.getItem().exp()));
316 delete [] substDegree;
319 delete [] substDegree;
333 for (i= bufResult; i.
hasItem(); i++)
438 int& adaptedLiftBound,
461 int& adaptedLiftBound,
619 const CFList& leadingCoeffs,
647 const CFList* differentSecondVarFactors,
678 CFList* & differentSecondVarLCs,
725 const CFList& oldBiFactors
738 bool& foundTrueMultiplier
755 bool& foundTrueMultiplier
764 const CFList& oldBiFactors,
773 bool& foundMultiplier
794 bool& foundMultiplier
TIMING_END_AND_PRINT(fac_alg_resultant, "time to compute resultant0: ")
const CanonicalForm int s
const CanonicalForm int const CFList const Variable & y
CanonicalForm lcmContent(const CanonicalForm &A, CFList &contentAi)
compute the LCM of the contents of A wrt to each variable occuring in A.
void gcdFreeBasis(CFFList &factors1, CFFList &factors2)
gcd free basis of two lists of factors
static CanonicalForm bound(const CFMatrix &M)
CFList buildUniFactors(const CFList &biFactors, const CanonicalForm &evalPoint, const Variable &y)
plug in evalPoint for y in a list of polys
CFList precomputeLeadingCoeff(const CanonicalForm &LCF, const CFList &LCFFactors, const Variable &alpha, const CFList &evaluation, CFList *&differentSecondVarLCs, int lSecondVarLCs, Variable &y)
computes a list l of length length(LCFFactors)+1 of polynomials such that prod (l)=LCF, note that the first entry of l may be non constant. Intended to be used to precompute coefficients of a polynomial f from its bivariate factorizations.
CFFList FpSqrf(const CanonicalForm &F, bool sort=true)
squarefree factorization over . If input is not monic, the leading coefficient is dropped ...
TIMING_START(fac_alg_resultant)
factory's class for variables
CFFList GFBiFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a bivariate polynomial over GF
CFList *& Aeval
<[in] poly
CFList distributeContent(const CFList &L, const CFList *differentSecondVarFactors, int length)
distribute content
void sortByUniFactors(CFList *&Aeval, int AevalLength, CFList &uniFactors, CFList &biFactors, const CFList &evaluation)
sort bivariate factors in Aeval such that their corresponding univariate factors coincide with uniFac...
void LCHeuristic4(const CFList &oldBiFactors, const CFList *oldAeval, const CFList &contents, const CFList &factors, const CanonicalForm &testVars, int lengthAeval, CFList *&leadingCoeffs, CanonicalForm &A, CanonicalForm &LCmultiplier, bool &foundMultiplier)
heuristic to remove factors of LCmultiplier from factors. More precisely checks if elements of conten...
CFList int & minFactorsLength
[in,out] minimal length of bivariate factors
CFList GFBiSqrfFactorize(const CanonicalForm &G)
factorize a squarefree bivariate polynomial over GF
CFFList FqSqrf(const CanonicalForm &F, const Variable &alpha, bool sort=true)
squarefree factorization over . If input is not monic, the leading coefficient is dropped ...
CFList henselLiftAndEarly(CanonicalForm &A, CFList &MOD, int *&liftBounds, bool &earlySuccess, CFList &earlyFactors, const CFList &Aeval, const CFList &biFactors, const CFList &evaluation, const ExtensionInfo &info)
hensel Lifting and early factor detection
CFList FpSqrfFactorize(const CanonicalForm &F)
factorize a squarefree multivariate polynomial over
const CanonicalForm int const CFList & evaluation
CFList FqBiSqrfFactorize(const CanonicalForm &G, const Variable &alpha)
factorize a squarefree bivariate polynomial over .
void distributeLCmultiplier(CanonicalForm &A, CFList &leadingCoeffs, CFList &biFactors, const CFList &evaluation, const CanonicalForm &LCmultipler)
distributes a divisor LCmultiplier of LC(A,1) on the bivariate factors and the precomputed leading co...
CFList GFSqrfFactorize(const CanonicalForm &F)
factorize a squarefree multivariate polynomial over GF
CFList evalPoints(const CanonicalForm &F, CFList &eval, const Variable &alpha, CFList &list, const bool &GF, bool &fail)
evaluation point search for multivariate factorization, looks for a (F.level() - 1)-tuple such that t...
CanonicalForm subst(const CanonicalForm &f, const CFList &a, const CFList &b, const CanonicalForm &Rstar, bool isFunctionField)
CFFList FpFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a multivariate polynomial over
void getLeadingCoeffs(const CanonicalForm &A, CFList *&Aeval)
extract leading coefficients wrt Variable(1) from bivariate factors obtained from factorizations of A...
CFList extFactorize(const CanonicalForm &F, const ExtensionInfo &info)
Factorization over an extension of initial field.
This file provides functions for squarefrees factorizing over , or GF.
ExtensionInfo contains information about extension.
CFFList GFSqrf(const CanonicalForm &F, bool sort=true)
squarefree factorization over GF. If input is not monic, the leading coefficient is dropped ...
int liftBoundAdaption(const CanonicalForm &F, const CFList &factors, bool &success, const int deg, const CFList &MOD, const int bound)
Lift bound adaption. Essentially an early factor detection but only the lift bound is adapted...
int extLiftBoundAdaption(const CanonicalForm &F, const CFList &factors, bool &success, const ExtensionInfo &info, const CFList &eval, const int deg, const CFList &MOD, const int bound)
Lift bound adaption over an extension of the initial field. Essentially an early factor detection but...
const CanonicalForm CFMap CFMap & N
CFList multiFactorize(const CanonicalForm &F, const Variable &v)
Factorization over Q (a)
void prepareLeadingCoeffs(CFList *&LCs, CanonicalForm &A, CFList &Aeval, int n, const CFList &leadingCoeffs, const CFList &biFactors, const CFList &evaluation)
normalize precomputed leading coefficients such that leading coefficients evaluated at evaluation in ...
const ExtensionInfo & info
< [in] sqrfree poly
CFFList FqFactorize(const CanonicalForm &G, const Variable &alpha, bool substCheck=true)
factorize a multivariate polynomial over
CFFList FpBiFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a bivariate polynomial over
void changeSecondVariable(CanonicalForm &A, CFList &biFactors, CFList &evaluation, CFList *&oldAeval, int lengthAeval2, const CFList &uniFactors, const Variable &w)
changes the second variable to be w and updates all relevant data
void evaluationWRTDifferentSecondVars(CFList *&Aeval, const CFList &evaluation, const CanonicalForm &A)
evaluate a poly A with main variable at level 1 at an evaluation point in K^(n-1) wrt different secon...
int substituteCheck(const CanonicalForm &F, const Variable &x)
check if a substitution x^n->x is possible
CFList FpBiSqrfFactorize(const CanonicalForm &G)
factorize a squarefree bivariate polynomial over .
CFList FqSqrfFactorize(const CanonicalForm &F, const Variable &alpha)
factorize a squarefree multivariate polynomial over
CFFList FqBiFactorize(const CanonicalForm &G, const Variable &alpha, bool substCheck=true)
factorize a bivariate polynomial over
CFFList GFFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a multivariate polynomial over GF
void refineBiFactors(const CanonicalForm &A, CFList &biFactors, CFList *const &factors, const CFList &evaluation, int minFactorsLength)
refine a bivariate factorization of A with l factors to one with minFactorsLength if possible ...
void LCHeuristicCheck(const CFList &LCs, const CFList &contents, CanonicalForm &A, const CanonicalForm &oldA, CFList &leadingCoeffs, bool &foundTrueMultiplier)
checks if prod(LCs)==LC (oldA,1) and if so divides elements of leadingCoeffs by elements in contents...
CFList leadingCoeffReconstruction(const CanonicalForm &F, const CFList &factors, const CFList &M)
obtain factors of F by reconstructing their leading coeffs
This file provides utility functions for bivariate factorization.
CFList factorRecombination(const CanonicalForm &F, const CFList &factors, const CFList &M)
Naive factor recombination for multivariate factorization. No precomputed is used to exclude combinat...
CFList extFactorRecombination(const CFList &factors, const CanonicalForm &F, const CFList &M, const ExtensionInfo &info, const CFList &evaluation)
Naive factor recombination for multivariate factorization over an extension of the initial field...
void LCHeuristic3(const CanonicalForm &LCmultiplier, const CFList &factors, const CFList &oldBiFactors, const CFList &contents, const CFList *oldAeval, CanonicalForm &A, CFList *&leadingCoeffs, int lengthAeval, bool &foundMultiplier)
heuristic to remove LCmultiplier from a factor based on the contents of factors. factors are assumed ...
TIMING_DEFINE_PRINT(fac_fq_squarefree) TIMING_DEFINE_PRINT(fac_fq_factor_squarefree) CFList multiFactorize(const CanonicalForm &F
Factorization over a finite field.
#define GaloisFieldDomain
CFList extEarlyFactorDetect(CanonicalForm &F, CFList &factors, int &adaptedLiftBound, bool &success, const ExtensionInfo &info, const CFList &eval, const int deg, const CFList &MOD, const int bound)
detects factors of F at stage deg of Hensel lifting. No combinations of more than one factor are test...
This file provides a class to handle degree patterns.
CanonicalForm reverseSubst(const CanonicalForm &F, const int d, const Variable &x)
reverse a substitution x^d->x
void LCHeuristic2(const CanonicalForm &LCmultiplier, const CFList &factors, CFList &leadingCoeffs, CFList &contents, CFList &LCs, bool &foundTrueMultiplier)
heuristic to distribute LCmultiplier onto factors based on the contents of factors. factors are assumed to come from LucksWangSparseHeuristic. If not successful contents will contain the content of each element of factors and LCs will contain the LC of each element of factors divided by its content
CFList recombination(const CFList &factors1, const CFList &factors2, int s, int thres, const CanonicalForm &evalPoint, const Variable &x)
recombination of bivariate factors factors1 s. t. the result evaluated at evalPoint coincides with fa...
CanonicalForm myCompress(const CanonicalForm &F, CFMap &N)
compress a polynomial s.t. and no gaps between the variables occur
#define ASSERT(expression, message)
This file provides functions for factorizing a bivariate polynomial over , or GF.
CFList earlyFactorDetect(CanonicalForm &F, CFList &factors, int &adaptedLiftBound, bool &success, const int deg, const CFList &MOD, const int bound)
detects factors of F at stage deg of Hensel lifting. No combinations of more than one factor are test...
void LCHeuristic(CanonicalForm &A, const CanonicalForm &LCmultiplier, CFList &biFactors, CFList *&leadingCoeffs, const CFList *oldAeval, int lengthAeval, const CFList &evaluation, const CFList &oldBiFactors)
heuristic to distribute LCmultiplier onto factors based on the variables that occur in LCmultiplier a...
static void evalPoint(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &FEval, CanonicalForm &GEval, CFGenerator &evalPoint)
This file provides a class to store information about finite fields and extensions thereof...