66 for (
int i=
E.max();
i >=
E.min();
i--)
167 for (
int j= 0;
j <
A.level() - 2;
j++)
182 if (factors.
length() == 1)
214 if (
result.getFirst().inCoeffDomain())
223 if (
buf.getFirst().inCoeffDomain())
240 if (
A.inCoeffDomain())
244 if (
i.getItem().inCoeffDomain())
248 lcmCont /=
i.getItem();
258 return contentAFactors;
268 if (
A.isUnivariate ())
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++)
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)
349 biFactors= bufBiFactors;
351 for (
int j= 0;
j < lengthAeval2;
j++)
352 Aeval2 [
j]= bufAeval2 [
j];
353 differentSecondVar= counter;
359 counter > differentSecondVar)
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: ");
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));
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())
498 "time to precompute LC over Q: ");
502 bool LCheuristic=
false;
508 CFList oldFactors= factors;
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,
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,
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;
654 for (
int i= 0;
i < lengthAeval2-1;
i++)
659 for (
int i=
A.level() - 4;
i > -1;
i--)
661 if (
i + 1 == lengthAeval2-1)
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++)
678 bool noOneToOne=
false;
681 CFList commonDenominators;
686 for (
int i= 0;
i < lengthAeval2;
i++)
688 iter2= commonDenominators;
706 multiplier= tmp3/
tmp1;
707 iter2= commonDenominators;
714 for (
int i= 0;
i < lengthAeval2;
i++)
716 iter2= commonDenominators;
724 Pi, liftBounds, liftBoundsLength, noOneToOne);
726 "time for non monic hensel lifting over Q: ");
735 "time to recover factors over Q: ");
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;
764 for (;
i.hasItem();
i++)
772 for (;
i.hasItem();
i++)
774 LCA=
LC (
i.getItem(), 1);
775 extgcd (LCA, yToLift, LCA, dummy);
776 i.getItem()=
mod (
i.getItem()*LCA, yToLift);
779 liftBoundsLength= F.
level() - 1;
789 (
A, MOD, liftBounds, earlySuccess, earlyFactors,
796 "time for factor recombination: ");
799 factors=
Union (factors, earlyFactors);
806 if (
i.getItem().level() < kk)
808 i.getItem()=
i.getItem() (
Variable (kk) -
j.getItem(), kk);
819 append (factors, contentAFactors);
824 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 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
TIMING_END_AND_PRINT(fac_alg_resultant, "time to compute resultant0: ")
TIMING_START(fac_alg_resultant)
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
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
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.
const ExtensionInfo & info
< [in] sqrfree poly
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)