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;
TIMING_END_AND_PRINT(fac_alg_resultant, "time to compute resultant0: ")
CFFList append(const CFFList &Inputlist, const CFFactor &TheFactor)
Variable getAlpha() const
getter
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.
const CanonicalForm int const CFList const Variable & y
CFList increasePrecisionFq2Fp(CanonicalForm &F, CFList &factors, int factorsFound, int oldNumCols, int oldL, const Variable &alpha, int precision, const CanonicalForm &eval)
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
CFList henselLiftAndLatticeRecombi(const CanonicalForm &G, const CFList &uniFactors, const Variable &alpha, const DegreePattern °Pat, bool symmetric, const CanonicalForm &eval)
CanonicalForm getDelta() const
getter
int getGFDegree() const
getter
TIMING_START(fac_alg_resultant)
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
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 ...
ExtensionInfo init4ext(const ExtensionInfo &info, const CanonicalForm &evaluation, int °Mipo)
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...
bool isIrreducible(const CanonicalForm &f)
bool isIrreducible ( const CanonicalForm & f )
CFList extIncreasePrecision(CanonicalForm &F, CFList &factors, int factorsFound, int oldNumCols, int oldL, const CanonicalForm &evaluation, const ExtensionInfo &info, CFList &source, CFList &dest, int precision)
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m )
bool delta(X x, Y y, D d)
CanonicalForm subst(const CanonicalForm &f, const CFList &a, const CFList &b, const CanonicalForm &Rstar, bool isFunctionField)
void intersect(const DegreePattern °Pat)
intersect two degree patterns
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 extHenselLiftAndLatticeRecombi(const CanonicalForm &G, const CFList &uniFactors, const ExtensionInfo &extInfo, const DegreePattern °Pat, const CanonicalForm &eval)
ExtensionInfo contains information about extension.
const CanonicalForm CFMap CFMap & N
CFList extBiFactorize(const CanonicalForm &F, const ExtensionInfo &info)
Factorization over an extension of initial field.
CanonicalForm decompress(const CanonicalForm &F, const mpz_t *inverseM, const mpz_t *A)
decompress a bivariate poly
int status int void * buf
const ExtensionInfo & info
< [in] sqrfree poly
int * computeBoundsWrtDiffMainvar(const CanonicalForm &F, int &n, bool &isIrreducible)
as above just wrt to the other variable
Variable getBeta() const
getter
int substituteCheck(const CanonicalForm &F, const Variable &x)
check if a substitution x^n->x is possible
CFList increasePrecision(CanonicalForm &F, CFList &factors, int factorsFound, int oldNumCols, int oldL, int precision, const CanonicalForm &eval)
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
CFList increasePrecision2(const CanonicalForm &F, CFList &factors, const Variable &alpha, int precision)
void refine()
Refine a degree pattern. Assumes that (*this)[0]:= d is the degree of the poly to be factored...
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 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...
int getLength() const
getter
bool isInExtension() const
getter
#define GaloisFieldDomain
CFList biFactorize(const CanonicalForm &F, const ExtensionInfo &info)
bivariate factorization over finite fields as decribed in "Factoring multivariate polynomials over a ...
CanonicalForm reverseSubst(const CanonicalForm &F, const int d, const Variable &x)
reverse a substitution x^d->x
#define DEBOUTLN(stream, objects)
CanonicalForm getGamma() const
getter
int * computeBounds(const CanonicalForm &F, int &n, bool &isIrreducible)
compute bounds for logarithmic derivative as described in K. Belabas, M. van Hoeij, J. Klüners, and A. Steel, Factoring polynomials over global fields
template CanonicalForm tmin(const CanonicalForm &, const CanonicalForm &)