 |
My Project
UNKNOWN_GIT_VERSION
|
Go to the documentation of this file.
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;
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)
static const int SW_RATIONAL
set to 1 for computations over Q
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...
bool isZero(const CFArray &A)
checks if entries of A are zero
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
generate random evaluation points
ideal lift(const ideal J, const ring r, const ideal inI, const ring s)
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...
CFList int bool & irred
[in,out] Is A irreducible?
void sortList(CFList &list, const Variable &x)
sort a list of polynomials by their degree in x.
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 ...
class to evaluate a polynomial at points
const CanonicalForm CFMap CFMap & N
void getLeadingCoeffs(const CanonicalForm &A, CFList *&Aeval)
extract leading coefficients wrt Variable(1) from bivariate factors obtained from factorizations of A...
generate random integers, random elements of finite fields
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 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...
CanonicalForm extgcd(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &a, CanonicalForm &b)
CanonicalForm extgcd ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & a,...
This file provides functions for sparse heuristic Hensel lifting.
univariate Gcd over finite fields and Z, extended GCD over finite fields and Q
This file provides utility functions for multivariate factorization.
CanonicalForm lcmContent(const CanonicalForm &A, CFList &contentAi)
compute the LCM of the contents of A wrt to each variable occuring in A.
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 int & minFactorsLength
[in,out] minimal length of bivariate factors
const CanonicalForm int const CFList & evaluation
CFList buildUniFactors(const CFList &biFactors, const CanonicalForm &evalPoint, const Variable &y)
plug in evalPoint for y in a list of polys
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
int status int void * buf
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...
TIMING_START(fac_alg_resultant)
CFList *& Aeval
<[in] poly
CFList conv(const CFFList &L)
convert a CFFList to a CFList by dropping the multiplicity
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...
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...
This file implements functions to map between extensions of finite fields.
int LucksWangSparseHeuristic(const CanonicalForm &F, const CFList &factors, int level, const CFList &leadingCoeffs, CFList &result)
sparse heuristic lifting by Wang and Lucks
declarations of higher level algorithms.
template CanonicalForm tmin(const CanonicalForm &, const CanonicalForm &)
CFList ratBiSqrfFactorize(const CanonicalForm &G, const Variable &v=Variable(1))
factorize a squarefree bivariate polynomial over .
class to generate random evaluation points
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...
CFFList append(const CFFList &Inputlist, const CFFactor &TheFactor)
CFFList factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
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 factorizationWRTDifferentSecondVars(const CanonicalForm &A, CFList *&Aeval, int &minFactorsLength, bool &irred, const Variable &w)
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...
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
CanonicalForm decompress(const CanonicalForm &F, const mpz_t *inverseM, const mpz_t *A)
decompress a bivariate poly
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....
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
void remove(int moveright)
CFList multiFactorize(const CanonicalForm &F, const Variable &v)
Factorization over Q (a)
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
TIMING_END_AND_PRINT(fac_alg_resultant, "time to compute resultant0: ")
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
factory's class for variables
ExtensionInfo contains information about extension.
This file defines functions for Hensel lifting.
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
multivariate factorization over Q(a)
int lcm(unsigned long *l, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
int * liftingBounds(const CanonicalForm &A, const int &bivarLiftBound)
compute lifting bounds
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
const Variable & v
< [in] a sqrfree bivariate poly
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...
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,...
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
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
static int index(p_Length length, p_Ord ord)
const ExtensionInfo & info
< [in] sqrfree poly
CanonicalForm shift2Zero(const CanonicalForm &F, CFList &Feval, const CFList &evaluation, int l)
shift evaluation point to zero
functions to print debug output
This file provides functions for factorizing a multivariate polynomial over , or GF.