75 if (!allZero && foundZero)
139 if (
degree (contentx) > 0)
167 for (
int j= 0;
j < A.
level() - 2;
j++)
169 if (!Aeval[
j].isEmpty())
174 if (factors.
getFirst().inCoeffDomain())
177 if (minFactorsLength == 0)
178 minFactorsLength= factors.
length();
180 minFactorsLength=
tmin (minFactorsLength, factors.
length());
182 if (factors.
length() == 1)
214 if (result.
getFirst().inCoeffDomain())
244 if (
i.getItem().inCoeffDomain())
248 lcmCont /=
i.getItem();
258 return contentAFactors;
274 append (factors, contentAFactors);
289 CFList biFactors, bufBiFactors;
291 int lift, bufLift, lengthAeval2= A.
level()-2;
295 int differentSecondVar= 0;
298 "time to preprocess poly and extract content over Q: ");
303 for (
int i= 0;
i < factorNums;
i++)
309 bufEvaluation=
evalPoints (bufA, bufAeval, E);
311 "time to find evaluation point over Q: ");
318 "time to eval wrt diff second vars over Q: ");
320 for (
int j= 0;
j < lengthAeval2;
j++)
322 if (!bufAeval2[
j].isEmpty())
331 "time for bivariate factorization: ");
334 if (bufBiFactors.
length() == 1)
348 evaluation= bufEvaluation;
349 biFactors= bufBiFactors;
351 for (
int j= 0;
j < lengthAeval2;
j++)
352 Aeval2 [
j]= bufAeval2 [
j];
353 differentSecondVar= counter;
359 counter > differentSecondVar)
362 evaluation= bufEvaluation;
363 biFactors= bufBiFactors;
365 for (
int j= 0;
j < lengthAeval2;
j++)
366 Aeval2 [
j]= bufAeval2 [
j];
367 differentSecondVar= counter;
372 evalPoly +=
j.getItem()*
power (x, k);
385 "time for bivariate factorization wrt diff second vars over Q: ");
388 "total time for eval and bivar factors over Q: ");
399 if (minFactorsLength == 0)
400 minFactorsLength= biFactors.
length();
403 minFactorsLength=
tmin (minFactorsLength, biFactors.
length());
409 minFactorsLength=
tmin (minFactorsLength, biFactors.
length());
411 if (minFactorsLength == 1)
421 if (differentSecondVar == lengthAeval2)
423 bool zeroOccured=
false;
450 for (
int i= 0;
i < lengthAeval2;
i++)
451 oldAeval[
i]= Aeval2[
i];
457 biFactorsLCs.
append (
LC (
i.getItem(), 1));
462 evaluation, Aeval2, lengthAeval2, w);
469 CFList oldBiFactors= biFactors;
475 if (!LCmultiplierIsConst)
484 CFList bufLeadingCoeffs2= leadingCoeffs2[lengthAeval2-1];
485 bufBiFactors= biFactors;
488 if (!LCmultiplierIsConst)
491 for (
int i= 0;
i < lengthAeval2;
i++)
493 if (!oldAeval[
i].isEmpty())
494 testVars *= oldAeval[
i].
getFirst().mvar();
498 "time to precompute LC over Q: ");
502 bool LCheuristic=
false;
506 int check= biFactors.length();
508 CFList oldFactors= factors;
511 if (check == factors.
length())
515 for (iter= factors; iter.hasItem(); iter++)
516 iter.getItem()=
swapvar (iter.getItem(),
w,
y);
524 "time for successful LucksWang over Q: ");
527 else if (factors.
length() > 0)
536 for (
int j=1;
j <=
i-oneCount;
j++)
539 for (
int j= 0;
j < lengthAeval2;
j++)
541 l= leadingCoeffs2[
j];
543 for (
int k=1;
k <=
i-oneCount;
k++)
554 else if (!LCmultiplierIsConst && factors.
length() == 0)
559 bool foundTrueMultiplier=
false;
560 LCHeuristic2 (LCmultiplier, factors, leadingCoeffs2[lengthAeval2-1],
561 contents, LCs, foundTrueMultiplier);
562 if (foundTrueMultiplier)
565 leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
566 for (
int i= lengthAeval2-1;
i > -1;
i--)
573 bool foundMultiplier=
false;
574 LCHeuristic3 (LCmultiplier, factors, oldBiFactors, contents, oldAeval,
575 A, leadingCoeffs2, lengthAeval2, foundMultiplier);
579 foundMultiplier=
false;
580 LCHeuristic4 (oldBiFactors, oldAeval, contents, factors, testVars,
581 lengthAeval2, leadingCoeffs2, A, LCmultiplier,
587 leadingCoeffs2[lengthAeval2-1], foundMultiplier);
590 LCHeuristic (A, LCmultiplier, biFactors, leadingCoeffs2, oldAeval,
591 lengthAeval2, evaluation, oldBiFactors);
596 leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
597 for (
int i= lengthAeval2-1;
i > -1;
i--)
603 if (!
fdivides (
LC (oldA,1),
prod (leadingCoeffs2[lengthAeval2-1])))
607 biFactors= bufBiFactors;
608 leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
609 LCmultiplier= bufLCmultiplier;
619 if (!LCheuristic && !LCmultiplierIsConst && bufFactors.
isEmpty()
623 LCHeuristic (A, LCmultiplier, biFactors, leadingCoeffs2, oldAeval,
624 lengthAeval2, evaluation, oldBiFactors);
626 leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
627 for (
int i= lengthAeval2-1;
i > -1;
i--)
632 if (!
fdivides (
LC (oldA,1),
prod (leadingCoeffs2[lengthAeval2-1])))
636 biFactors= bufBiFactors;
637 leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
638 LCmultiplier= bufLCmultiplier;
651 for (iter= biFactors; iter.hasItem(); iter++)
652 iter.getItem()= iter.getItem () (y + evaluation.
getLast(),
y);
654 for (
int i= 0;
i < lengthAeval2-1;
i++)
656 for (iter= leadingCoeffs2[lengthAeval2-1]; iter.hasItem(); iter++)
659 for (
int i= A.
level() - 4;
i > -1;
i--)
661 if (
i + 1 == lengthAeval2-1)
662 leadingCoeffs2[
i].
append (iter.getItem() (0,
i + 4));
668 "time to shift evaluation point to zero: ");
672 int* liftBounds=
new int [A.
level() - 1];
673 int liftBoundsLength= A.
level() - 1;
674 for (
int i= 0;
i < liftBoundsLength;
i++)
675 liftBounds [
i]=
degree (A,
i + 2) + 1;
678 bool noOneToOne=
false;
681 CFList commonDenominators;
682 for (iter=biFactors; iter.hasItem(); iter++)
686 for (
int i= 0;
i < lengthAeval2;
i++)
688 iter2= commonDenominators;
689 for (iter= leadingCoeffs2[
i]; iter.hasItem(); iter++, iter2++)
697 tmp1=
prod (commonDenominators);
698 for (iter= Aeval; iter.hasItem(); iter++)
702 tmp3=
lcm (tmp2,tmp3);
706 multiplier= tmp3/
tmp1;
707 iter2= commonDenominators;
708 for (iter=biFactors; iter.hasItem(); iter++, iter2++)
709 iter.getItem() *= iter2.
getItem()*multiplier;
711 for (iter= Aeval; iter.hasItem(); iter++)
712 iter.getItem() *= tmp3*
power (multiplier, biFactors.length() - 1)/denA;
714 for (
int i= 0;
i < lengthAeval2;
i++)
716 iter2= commonDenominators;
717 for (iter= leadingCoeffs2[
i]; iter.hasItem(); iter++, iter2++)
718 iter.getItem() *= iter2.
getItem()*multiplier;
724 Pi, liftBounds, liftBoundsLength, noOneToOne);
726 "time for non monic hensel lifting over Q: ");
735 "time to recover factors over Q: ");
736 if (check != factors.
length())
739 factors=
Union (factors, bufFactors);
743 if (!LCmultiplierIsConst && LCheuristic)
746 biFactors= bufBiFactors;
747 leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
748 delete [] liftBounds;
750 goto tryAgainWithoutHeu;
755 biFactors= oldBiFactors;
756 for (iter= biFactors; iter.hasItem(); iter++)
757 iter.getItem()= iter.getItem () (y + evaluation.
getLast(),
y);
770 yToLift=
power (y, lift);
775 extgcd (LCA, yToLift, LCA, dummy);
779 liftBoundsLength= F.
level() - 1;
789 (A, MOD, liftBounds, earlySuccess, earlyFactors,
790 Aeval, biFactors, evaluation, info);
796 "time for factor recombination: ");
799 factors=
Union (factors, earlyFactors);
803 int kk= Aeval.
getLast().level();
816 iter.getItem()=
swapvar (iter.getItem(),
w,
y);
819 append (factors, contentAFactors);
824 delete [] leadingCoeffs2;
TIMING_END_AND_PRINT(fac_alg_resultant, "time to compute resultant0: ")
CanonicalForm shift2Zero(const CanonicalForm &F, CFList &Feval, const CFList &evaluation, int l)
shift evaluation point to zero
CFFList append(const CFFList &Inputlist, const CFFactor &TheFactor)
const CanonicalForm int const CFList const Variable & y
CFList recoverFactors(const CanonicalForm &F, const CFList &factors)
divides factors by their content wrt. Variable(1) and checks if these polys divide F ...
This file defines functions for Hensel lifting.
This file provides utility functions for multivariate factorization.
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
int lcm(unsigned long *l, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
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
functions to print debug output
CanonicalForm extgcd(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &a, CanonicalForm &b)
CanonicalForm extgcd ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & a...
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
TIMING_START(fac_alg_resultant)
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...
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...
factory's class for variables
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 *& Aeval
<[in] poly
generate random evaluation points
CFList int & minFactorsLength
[in,out] minimal length of < bivariate factors
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...
class to generate random evaluation points
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 ...
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...
const CanonicalForm int const CFList & evaluation
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...
int LucksWangSparseHeuristic(const CanonicalForm &F, const CFList &factors, int level, const CFList &leadingCoeffs, CFList &result)
sparse heuristic lifting by Wang and Lucks
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)
TIMING_DEFINE_PRINT(fac_bi_factorizer) TIMING_DEFINE_PRINT(fac_hensel_lift) TIMING_DEFINE_PRINT(fac_factor_recombination) TIMING_DEFINE_PRINT(fac_shift_to_zero) TIMING_DEFINE_PRINT(fac_precompute_leadcoeff) TIMING_DEFINE_PRINT(fac_evaluation) TIMING_DEFINE_PRINT(fac_recover_factors) TIMING_DEFINE_PRINT(fac_preprocess_and_content) TIMING_DEFINE_PRINT(fac_bifactor_total) TIMING_DEFINE_PRINT(fac_luckswang) TIMING_DEFINE_PRINT(fac_lcheuristic) TIMING_DEFINE_PRINT(fac_cleardenom) TIMING_DEFINE_PRINT(fac_content) TIMING_DEFINE_PRINT(fac_compress) CFList evalPoints(const CanonicalForm &F
void sortList(CFList &list, const Variable &x)
sort a list of polynomials by their degree in x.
This file implements functions to map between extensions of finite fields.
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...
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
CFList conv(const CFFList &L)
convert a CFFList to a CFList by dropping the multiplicity
ideal lift(const ideal J, const ring r, const ideal inI, const ring s)
CFFList factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
This file provides functions for sparse heuristic Hensel lifting.
ExtensionInfo contains information about extension.
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 ...
const CanonicalForm CFMap CFMap & N
univariate Gcd over finite fields and Z, extended GCD over finite fields and Q
CanonicalForm decompress(const CanonicalForm &F, const mpz_t *inverseM, const mpz_t *A)
decompress a bivariate poly
CFList multiFactorize(const CanonicalForm &F, const Variable &v)
Factorization over Q (a)
int status int void * buf
const ExtensionInfo & info
< [in] sqrfree poly
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...
static const int SW_RATIONAL
set to 1 for computations over Q
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.
multivariate factorization over Q(a)
generate random integers, random elements of finite fields
declarations of higher level algorithms.
void factorizationWRTDifferentSecondVars(const CanonicalForm &A, CFList *&Aeval, int &minFactorsLength, bool &irred, const Variable &w)
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
static int index(p_Length length, p_Ord ord)
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
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...
const Variable & v
< [in] a sqrfree bivariate poly
CFList buildUniFactors(const CFList &biFactors, const CanonicalForm &evalPoint, const Variable &y)
plug in evalPoint for y in a list of polys
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...
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 ...
CFList ratBiSqrfFactorize(const CanonicalForm &G, const Variable &v=Variable(1))
factorize a squarefree bivariate polynomial over .
class to evaluate a polynomial at points
CanonicalForm lcmContent(const CanonicalForm &A, CFList &contentAi)
compute the LCM of the contents of A wrt to each variable occuring in A.
bool isZero(const CFArray &A)
checks if entries of A are zero
CFList int bool & irred
[in,out] Is A irreducible?
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 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 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
void getLeadingCoeffs(const CanonicalForm &A, CFList *&Aeval)
extract leading coefficients wrt Variable(1) from bivariate factors obtained from factorizations of A...
int * liftingBounds(const CanonicalForm &A, const int &bivarLiftBound)
compute lifting bounds
template CanonicalForm tmin(const CanonicalForm &, const CanonicalForm &)