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++)
195#if defined(HAVE_NTL) || defined(HAVE_FLINT)
218 if (
result.getFirst().inCoeffDomain())
244 if (
A.inCoeffDomain())
248 if (
i.getItem().inCoeffDomain())
272 if (
A.isUnivariate ())
302 "time to preprocess poly and extract content over Q: ");
315 "time to find evaluation point over Q: ");
322 "time to eval wrt diff second vars over Q: ");
335 "time for bivariate factorization: ");
389 "time for bivariate factorization wrt diff second vars over Q: ");
392 "total time for eval and bivar factors over Q: ");
502 "time to precompute LC over Q: ");
528 "time for successful LucksWang over Q: ");
663 for (
int i=
A.level() - 4;
i > -1;
i--)
672 "time to shift evaluation point to zero: ");
730 "time for non monic hensel lifting over Q: ");
739 "time to recover factors over Q: ");
768 for (;
i.hasItem();
i++)
776 for (;
i.hasItem();
i++)
800 "time for factor recombination: ");
810 if (
i.getItem().level() <
kk)
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)