Factorization of a squarefree bivariate polynomials over an arbitrary finite field, information on the current field we work over is in info. info may also contain information about the initial field if initial and current field do not coincide. In this case the current field is an extension of the initial field and the factors returned are factors of F over the initial field.
Factorization of a squarefree bivariate polynomials over an arbitrary finite field, information on the current field we work over is in info. info may also contain information about the initial field if initial and current field do not coincide. In this case the current field is an extension of the initial field and the factors returned are factors of F over the initial field.
8215 if (
A.isUnivariate())
8217 if (extension ==
false)
8238 A=
A/(contentAx*contentAy);
8239 CFList contentAxFactors, contentAyFactors;
8249 if (
A.inCoeffDomain())
8251 append (factors, contentAxFactors);
8252 append (factors, contentAyFactors);
8256 else if (
A.isUnivariate())
8259 append (factors, contentAxFactors);
8260 append (factors, contentAyFactors);
8281 bool derivXZero=
false;
8288 gcdDerivX=
gcd (
A, derivX);
8289 if (
degree (gcdDerivX) > 0)
8294 append (factorsG, contentAxFactors);
8295 append (factorsG, contentAyFactors);
8302 bool derivYZero=
false;
8309 gcdDerivY=
gcd (
A, derivY);
8310 if (
degree (gcdDerivY) > 0)
8315 append (factorsG, contentAxFactors);
8316 append (factorsG, contentAyFactors);
8331 derivXZero= derivYZero;
8353 int minBound= bounds[0];
8354 for (
int i= 1;
i < boundsLength;
i++)
8357 minBound=
tmin (minBound, bounds[
i]);
8362 int minBound2= bounds2[0];
8363 for (
int i= 1;
i < boundsLength2;
i++)
8365 if (bounds2[
i] != 0)
8366 minBound2=
tmin (minBound2, bounds2[
i]);
8372 CFList uniFactors, list, bufUniFactors;
8377 CanonicalForm Aeval2, evaluation2, bufAeval2, bufEvaluation2;
8378 CFList bufUniFactors2, list2, uniFactors2;
8389 bool symmetric=
false;
8392 for (
int i= 0;
i < factorNums;
i++)
8398 if (!derivXZero && !fail2 && !symmetric)
8409 "time to find eval point wrt y: ");
8412 if (fail && (
i == 0))
8414 if (!derivXZero && !fail2 && !symmetric)
8416 bufEvaluation= bufEvaluation2;
8417 int dummy= subCheck2;
8418 subCheck2= subCheck1;
8423 bufAeval= bufAeval2;
8432 if (fail && (
i == 0))
8445 if (fail && (
i != 0))
8452 "time for univariate factorization over Fq: ");
8453 DEBOUTLN (cerr,
"Lc (bufAeval)*prod (bufUniFactors)== bufAeval " <<
8454 (
prod (bufUniFactors)*
Lc (bufAeval) == bufAeval));
8456 if (!derivXZero && !fail2 && !symmetric)
8461 "time for univariate factorization in y over Fq: ");
8462 DEBOUTLN (cerr,
"Lc (bufAeval2)*prod (bufUniFactors2)== bufAeval2 " <<
8463 (
prod (bufUniFactors2)*
Lc (bufAeval2) == bufAeval2));
8466 if (bufUniFactors.
length() == 1 ||
8467 (!fail2 && !derivXZero && !symmetric && (bufUniFactors2.
length() == 1)))
8487 if (
i == 0 && !extension)
8493 if (subCheck > 1 && (subCheck1%subCheck == 0))
8496 subst (bufA, bufA, subCheck,
x);
8509 if (!derivXZero && !fail2 && !symmetric && subCheck2 > 0)
8513 if (subCheck > 1 && (subCheck2%subCheck == 0))
8516 subst (bufA, bufA, subCheck,
y);
8532 if (!derivXZero && !fail2 && !symmetric)
8539 uniFactors= bufUniFactors;
8541 if (!derivXZero && !fail2 && !symmetric)
8544 evaluation2= bufEvaluation2;
8545 uniFactors2= bufUniFactors2;
8552 if (!derivXZero && !fail2 && !symmetric)
8557 uniFactors2= bufUniFactors2;
8559 evaluation2= bufEvaluation2;
8564 uniFactors= bufUniFactors;
8569 list.
append (bufEvaluation);
8570 if (!derivXZero && !fail2 && !symmetric)
8571 list2.
append (bufEvaluation2);
8574 "total time for univariate factorizations: ");
8576 if (!derivXZero && !fail2 && !symmetric)
8578 if ((uniFactors.
length() > uniFactors2.
length() && minBound2 <= minBound)||
8583 uniFactors= uniFactors2;
8615 minBound= minBound2;
8621 "time to shift eval to zero: ");
8627 DEBOUTLN (cerr,
"uniFactors= " << uniFactors);
8629 if ((GF && !extension) || (GF && extension &&
k != 1))
8631 bool earlySuccess=
false;
8635 (
A, earlySuccess, earlyFactors, degs, liftBound,
8638 "time for bivariate hensel lifting over Fq: ");
8639 DEBOUTLN (cerr,
"lifted factors= " << uniFactors);
8651 "time for naive bivariate factor recombi over Fq: ");
8654 factors=
Union (earlyFactors, factors);
8655 else if (!earlySuccess && degs.
getLength() == 1)
8656 factors= earlyFactors;
8666 factors=
Union (lll, factors);
8672 factors=
Union (lll, factors);
8674 else if (!extension && (
alpha !=
x || GF))
8678 factors=
Union (lll, factors);
8681 "time to bivar lift and LLL recombi over Fq: ");
8682 DEBOUTLN (cerr,
"lifted factors= " << uniFactors);
8686 bool earlySuccess=
false;
8690 (
A, earlySuccess, earlyFactors, degs, liftBound,
8693 "time for bivar hensel lifting over Fq: ");
8694 DEBOUTLN (cerr,
"lifted factors= " << uniFactors);
8702 "time for small subset naive recombi over Fq: ");
8704 int oldUniFactorsLength= uniFactors.
length();
8725 "time to increase precision: ");
8726 factors=
Union (factors, tmp);
8728 && uniFactors.
length() != oldUniFactorsLength)
8776 int oldUniFactorsLength= uniFactors.
length();
8785 info2, source, dest, liftBound
8787 factors=
Union (factors, tmp);
8789 && uniFactors.
length() != oldUniFactorsLength)
8806 factors=
Union (earlyFactors, factors);
8807 else if (!earlySuccess && degs.
getLength() == 1)
8808 factors= earlyFactors;
const CanonicalForm CFMap CFMap & N
CanonicalForm decompress(const CanonicalForm &F, const mpz_t *inverseM, const mpz_t *A)
decompress a bivariate poly
#define GaloisFieldDomain
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m )
static CanonicalForm mapDown(const CanonicalForm &F, const Variable &alpha, const CanonicalForm &G, CFList &source, CFList &dest)
the CanonicalForm G is the output of map_up, returns F considered as an element over ,...
DegreePattern provides a functionality to create, intersect and refine degree patterns.
void intersect(const DegreePattern °Pat)
intersect two degree patterns
int getLength() const
getter
void refine()
Refine a degree pattern. Assumes that (*this)[0]:= d is the degree of the poly to be factored....
ExtensionInfo contains information about extension.
int getGFDegree() const
getter
bool isInExtension() const
getter
CanonicalForm getGamma() const
getter
CanonicalForm getDelta() const
getter
Variable getAlpha() const
getter
Variable getBeta() const
getter
factory's class for variables
#define DEBOUTLN(stream, objects)
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)
CanonicalForm subst(const CanonicalForm &f, const CFList &a, const CFList &b, const CanonicalForm &Rstar, bool isFunctionField)
CFList *& Aeval
<[in] poly
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...
void appendMapDown(CFList &factors, const CanonicalForm &g, const ExtensionInfo &info, CFList &source, CFList &dest)
map g down into a subfield of the current field and append it to factors
CanonicalForm reverseSubst(const CanonicalForm &F, const int d, const Variable &x)
reverse a substitution x^d->x
int * computeBoundsWrtDiffMainvar(const CanonicalForm &F, int &n, bool &isIrreducible)
as above just wrt to the other variable
int * computeBounds(const CanonicalForm &F, int &n, bool &isIrreducible)
compute bounds for logarithmic derivative as described in K. Belabas, M. van Hoeij,...
int substituteCheck(const CanonicalForm &F, const Variable &x)
check if a substitution x^n->x is possible
CFList biFactorize(const CanonicalForm &F, const ExtensionInfo &info)
bivariate factorization over finite fields as decribed in "Factoring multivariate polynomials over a ...
CFList increasePrecision(CanonicalForm &F, CFList &factors, int factorsFound, int oldNumCols, int oldL, int precision, const CanonicalForm &eval)
CFList extHenselLiftAndLatticeRecombi(const CanonicalForm &G, const CFList &uniFactors, const ExtensionInfo &extInfo, const DegreePattern °Pat, const CanonicalForm &eval)
CFList extBiFactorize(const CanonicalForm &F, const ExtensionInfo &info)
Factorization over an extension of initial field.
CFList increasePrecisionFq2Fp(CanonicalForm &F, CFList &factors, int factorsFound, int oldNumCols, int oldL, const Variable &alpha, int precision, const CanonicalForm &eval)
CFList extIncreasePrecision(CanonicalForm &F, CFList &factors, int factorsFound, int oldNumCols, int oldL, const CanonicalForm &evaluation, const ExtensionInfo &info, CFList &source, CFList &dest, int precision)
CFList henselLiftAndLatticeRecombi(const CanonicalForm &G, const CFList &uniFactors, const Variable &alpha, const DegreePattern °Pat, bool symmetric, const CanonicalForm &eval)
CFList extFactorRecombination(CFList &factors, CanonicalForm &F, const CanonicalForm &N, const ExtensionInfo &info, DegreePattern °s, const CanonicalForm &eval, int s, int thres)
naive factor recombination as decribed in "Factoring multivariate polynomials over a finite field" by...
CanonicalForm evalPoint(const CanonicalForm &F, CanonicalForm &eval, const Variable &alpha, CFList &list, const bool &GF, bool &fail)
find an evaluation point p, s.t. F(p,y) is squarefree and .
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 uniFactorizer(const CanonicalForm &A, const Variable &alpha, const bool &GF)
Univariate factorization of squarefree monic polys over finite fields via NTL. If the characteristic ...
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...
ExtensionInfo init4ext(const ExtensionInfo &info, const CanonicalForm &evaluation, int °Mipo)
CFList increasePrecision2(const CanonicalForm &F, CFList &factors, const Variable &alpha, int precision)
const ExtensionInfo & info
< [in] sqrfree poly
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
template CanonicalForm tmin(const CanonicalForm &, const CanonicalForm &)
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
bool isIrreducible(const CanonicalForm &f)
bool isIrreducible ( const CanonicalForm & f )
bool delta(X x, Y y, D d)
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)