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;
430 if (
iter.getItem().isZero())
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++)
660 for (
iter= leadingCoeffs2[lengthAeval2-1];
iter.hasItem();
iter++)
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;
693 for (
iter= leadingCoeffs2[
i];
iter.hasItem();
iter++, iter2++)
710 multiplier= tmp3/
tmp1;
711 iter2= commonDenominators;
716 iter.getItem() *= tmp3*
power (multiplier, biFactors.
length() - 1)/denA;
718 for (
int i= 0;
i < lengthAeval2;
i++)
720 iter2= commonDenominators;
721 for (
iter= leadingCoeffs2[
i];
iter.hasItem();
iter++, iter2++)
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);
807 int kk=
Aeval.getLast().level();
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.
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
REvaluation E(1, terms.length(), IntRandom(25))
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 "Factoringmultivariate 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)