65 for (
int i=
E.max();
i >=
E.min();
i--)
156#if defined(HAVE_NTL) || defined(HAVE_FLINT)
168 for (
int j= 0;
j <
A.level() - 2;
j++)
183 if (factors.
length() == 1)
195#if defined(HAVE_NTL) || defined(HAVE_FLINT)
218 if (
result.getFirst().inCoeffDomain())
227 if (
buf.getFirst().inCoeffDomain())
244 if (
A.inCoeffDomain())
248 if (
i.getItem().inCoeffDomain())
252 lcmCont /=
i.getItem();
262 return contentAFactors;
272 if (
A.isUnivariate ())
278 append (factors, contentAFactors);
293 CFList biFactors, bufBiFactors;
295 int lift, bufLift, lengthAeval2=
A.level()-2;
299 int differentSecondVar= 0;
302 "time to preprocess poly and extract content over Q: ");
307 for (
int i= 0;
i < factorNums;
i++)
315 "time to find evaluation point over Q: ");
322 "time to eval wrt diff second vars over Q: ");
324 for (
int j= 0;
j < lengthAeval2;
j++)
326 if (!bufAeval2[
j].isEmpty())
335 "time for bivariate factorization: ");
338 if (bufBiFactors.
length() == 1)
353 biFactors= bufBiFactors;
355 for (
int j= 0;
j < lengthAeval2;
j++)
356 Aeval2 [
j]= bufAeval2 [
j];
357 differentSecondVar= counter;
363 counter > differentSecondVar)
367 biFactors= bufBiFactors;
369 for (
int j= 0;
j < lengthAeval2;
j++)
370 Aeval2 [
j]= bufAeval2 [
j];
371 differentSecondVar= counter;
376 evalPoly +=
j.getItem()*
power (
x,
k);
389 "time for bivariate factorization wrt diff second vars over Q: ");
392 "total time for eval and bivar factors over Q: ");
425 if (differentSecondVar == lengthAeval2)
427 bool zeroOccured=
false;
454 for (
int i= 0;
i < lengthAeval2;
i++)
455 oldAeval[
i]= Aeval2[
i];
461 biFactorsLCs.
append (
LC (
i.getItem(), 1));
473 CFList oldBiFactors= biFactors;
479 if (!LCmultiplierIsConst)
488 CFList bufLeadingCoeffs2= leadingCoeffs2[lengthAeval2-1];
489 bufBiFactors= biFactors;
492 if (!LCmultiplierIsConst)
495 for (
int i= 0;
i < lengthAeval2;
i++)
497 if (!oldAeval[
i].isEmpty())
502 "time to precompute LC over Q: ");
506 bool LCheuristic=
false;
512 CFList oldFactors= factors;
528 "time for successful LucksWang over Q: ");
531 else if (factors.
length() > 0)
540 for (
int j=1;
j <=
i-oneCount;
j++)
543 for (
int j= 0;
j < lengthAeval2;
j++)
545 l= leadingCoeffs2[
j];
547 for (
int k=1;
k <=
i-oneCount;
k++)
558 else if (!LCmultiplierIsConst && factors.
length() == 0)
563 bool foundTrueMultiplier=
false;
564 LCHeuristic2 (LCmultiplier, factors, leadingCoeffs2[lengthAeval2-1],
565 contents, LCs, foundTrueMultiplier);
566 if (foundTrueMultiplier)
569 leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
570 for (
int i= lengthAeval2-1;
i > -1;
i--)
577 bool foundMultiplier=
false;
578 LCHeuristic3 (LCmultiplier, factors, oldBiFactors, contents, oldAeval,
579 A, leadingCoeffs2, lengthAeval2, foundMultiplier);
583 foundMultiplier=
false;
584 LCHeuristic4 (oldBiFactors, oldAeval, contents, factors, testVars,
585 lengthAeval2, leadingCoeffs2,
A, LCmultiplier,
591 leadingCoeffs2[lengthAeval2-1], foundMultiplier);
594 LCHeuristic (
A, LCmultiplier, biFactors, leadingCoeffs2, oldAeval,
600 leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
601 for (
int i= lengthAeval2-1;
i > -1;
i--)
607 if (!
fdivides (
LC (oldA,1),
prod (leadingCoeffs2[lengthAeval2-1])))
611 biFactors= bufBiFactors;
612 leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
613 LCmultiplier= bufLCmultiplier;
623 if (!LCheuristic && !LCmultiplierIsConst && bufFactors.
isEmpty()
627 LCHeuristic (
A, LCmultiplier, biFactors, leadingCoeffs2, oldAeval,
630 leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
631 for (
int i= lengthAeval2-1;
i > -1;
i--)
636 if (!
fdivides (
LC (oldA,1),
prod (leadingCoeffs2[lengthAeval2-1])))
640 biFactors= bufBiFactors;
641 leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
642 LCmultiplier= bufLCmultiplier;
658 for (
int i= 0;
i < lengthAeval2-1;
i++)
663 for (
int i=
A.level() - 4;
i > -1;
i--)
665 if (
i + 1 == lengthAeval2-1)
672 "time to shift evaluation point to zero: ");
676 int* liftBounds=
new int [
A.level() - 1];
677 int liftBoundsLength=
A.level() - 1;
678 for (
int i= 0;
i < liftBoundsLength;
i++)
682 bool noOneToOne=
false;
685 CFList commonDenominators;
690 for (
int i= 0;
i < lengthAeval2;
i++)
692 iter2= commonDenominators;
710 multiplier= tmp3/
tmp1;
711 iter2= commonDenominators;
718 for (
int i= 0;
i < lengthAeval2;
i++)
720 iter2= commonDenominators;
728 Pi, liftBounds, liftBoundsLength, noOneToOne);
730 "time for non monic hensel lifting over Q: ");
739 "time to recover factors over Q: ");
743 factors=
Union (factors, bufFactors);
747 if (!LCmultiplierIsConst && LCheuristic)
750 biFactors= bufBiFactors;
751 leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
752 delete [] liftBounds;
754 goto tryAgainWithoutHeu;
759 biFactors= oldBiFactors;
768 for (;
i.hasItem();
i++)
776 for (;
i.hasItem();
i++)
778 LCA=
LC (
i.getItem(), 1);
779 extgcd (LCA, yToLift, LCA, dummy);
780 i.getItem()=
mod (
i.getItem()*LCA, yToLift);
783 liftBoundsLength= F.
level() - 1;
793 (
A, MOD, liftBounds, earlySuccess, earlyFactors,
800 "time for factor recombination: ");
803 factors=
Union (factors, earlyFactors);
810 if (
i.getItem().level() < kk)
812 i.getItem()=
i.getItem() (
Variable (kk) -
j.getItem(), kk);
823 append (factors, contentAFactors);
828 delete [] leadingCoeffs2;
const CanonicalForm CFMap CFMap & N
int myCompress(const CanonicalForm &F, const CanonicalForm &G, CFMap &M, CFMap &N, bool topLevel)
compressing two polynomials F and G, M is used for compressing, N to reverse the compression
CanonicalForm decompress(const CanonicalForm &F, const mpz_t *inverseM, const mpz_t *A)
decompress a bivariate poly
CanonicalForm extgcd(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &a, CanonicalForm &b)
CanonicalForm extgcd ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & a,...
univariate Gcd over finite fields and Z, extended GCD over finite fields and Q
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
declarations of higher level algorithms.
CFFList FACTORY_PUBLIC factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
static const int SW_RATIONAL
set to 1 for computations over Q
This file implements functions to map between extensions of finite fields.
generate random integers, random elements of finite fields
generate random evaluation points
class to evaluate a polynomial at points
ExtensionInfo contains information about extension.
void remove(int moveright)
class to generate random evaluation points
factory's class for variables
functions to print debug output
const CanonicalForm int const CFList & evaluation
const CanonicalForm int const CFList const Variable & y
CFFList append(const CFFList &Inputlist, const CFFactor &TheFactor)
CFList conv(const CFFList &L)
convert a CFFList to a CFList by dropping the multiplicity
CFList ratBiSqrfFactorize(const CanonicalForm &G, const Variable &v=Variable(1))
factorize a squarefree bivariate polynomial over .
const Variable & v
< [in] a sqrfree bivariate poly
CFList multiFactorize(const CanonicalForm &F, const Variable &v)
Factorization over Q (a)
void factorizationWRTDifferentSecondVars(const CanonicalForm &A, CFList *&Aeval, int &minFactorsLength, bool &irred, const Variable &w)
multivariate factorization over Q(a)
CFList int & minFactorsLength
[in,out] minimal length of bivariate factors
CFList *& Aeval
<[in] poly
CFList int bool & irred
[in,out] Is A irreducible?
void appendSwapDecompress(CFList &factors1, const CFList &factors2, const CFList &factors3, const bool swap1, const bool swap2, const CFMap &N)
first swap Variables in factors1 if necessary, then append factors2 and factors3 on factors1 and fina...
CFList henselLiftAndEarly(CanonicalForm &A, bool &earlySuccess, CFList &earlyFactors, DegreePattern °s, int &liftBound, const CFList &uniFactors, const ExtensionInfo &info, const CanonicalForm &eval, modpk &b, CanonicalForm &den)
hensel Lifting and early factor detection
CFList factorRecombination(CFList &factors, CanonicalForm &F, const CanonicalForm &N, DegreePattern °s, const CanonicalForm &eval, int s, int thres, const modpk &b, const CanonicalForm &den)
naive factor recombination as decribed in "Factoring multivariate polynomials over a finite field" by...
CFList recoverFactors(const CanonicalForm &F, const CFList &factors)
divides factors by their content wrt. Variable(1) and checks if these polys divide F
CanonicalForm shift2Zero(const CanonicalForm &F, CFList &Feval, const CFList &evaluation, int l)
shift evaluation point to zero
int * liftingBounds(const CanonicalForm &A, const int &bivarLiftBound)
compute lifting bounds
This file provides utility functions for multivariate factorization.
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,...
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,...
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...
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...
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 ...
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...
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 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...
CanonicalForm lcmContent(const CanonicalForm &A, CFList &contentAi)
compute the LCM of the contents of A wrt to each variable occuring in A.
void getLeadingCoeffs(const CanonicalForm &A, CFList *&Aeval)
extract leading coefficients wrt Variable(1) from bivariate factors obtained from factorizations of A...
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 ...
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...
void refineBiFactors(const CanonicalForm &A, CFList &biFactors, CFList *const &Aeval, const CFList &evaluation, int minFactorsLength)
refine a bivariate factorization of A with l factors to one with minFactorsLength if possible
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....
CFList buildUniFactors(const CFList &biFactors, const CanonicalForm &evalPoint, const Variable &y)
plug in evalPoint for y in a list of polys
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...
This file provides functions for factorizing a multivariate polynomial over , or GF.
CFList nonMonicHenselLift(const CFList &F, const CFList &factors, const CFList &LCs, CFList &diophant, CFArray &Pi, CFMatrix &M, int lOld, int &lNew, const CFList &MOD, bool &noOneToOne)
void sortList(CFList &list, const Variable &x)
sort a list of polynomials by their degree in x.
This file defines functions for Hensel lifting.
int LucksWangSparseHeuristic(const CanonicalForm &F, const CFList &factors, int level, const CFList &leadingCoeffs, CFList &result)
sparse heuristic lifting by Wang and Lucks
CFList sparseHeuristic(const CanonicalForm &A, const CFList &biFactors, CFList *&moreBiFactors, const CFList &evaluation, int minFactorsLength)
sparse heuristic which patches together bivariate factors of A wrt. different second variables by the...
This file provides functions for sparse heuristic Hensel lifting.
bool isZero(const CFArray &A)
checks if entries of A are zero
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
template CanonicalForm tmin(const CanonicalForm &, const CanonicalForm &)
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
ideal lift(const ideal J, const ring r, const ideal inI, const ring s)
int lcm(unsigned long *l, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
static int index(p_Length length, p_Ord ord)
int status int void * buf
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
#define TIMING_DEFINE_PRINT(t)
#define TIMING_END_AND_PRINT(t, msg)