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.
8317 if (
A.isUnivariate())
8319 if (extension ==
false)
8340 A=
A/(contentAx*contentAy);
8341 CFList contentAxFactors, contentAyFactors;
8351 if (
A.inCoeffDomain())
8353 append (factors, contentAxFactors);
8354 append (factors, contentAyFactors);
8358 else if (
A.isUnivariate())
8361 append (factors, contentAxFactors);
8362 append (factors, contentAyFactors);
8383 bool derivXZero=
false;
8390 gcdDerivX=
gcd (
A, derivX);
8391 if (
degree (gcdDerivX) > 0)
8396 append (factorsG, contentAxFactors);
8397 append (factorsG, contentAyFactors);
8404 bool derivYZero=
false;
8411 gcdDerivY=
gcd (
A, derivY);
8412 if (
degree (gcdDerivY) > 0)
8417 append (factorsG, contentAxFactors);
8418 append (factorsG, contentAyFactors);
8433 derivXZero= derivYZero;
8455 int minBound= bounds[0];
8456 for (
int i= 1;
i < boundsLength;
i++)
8459 minBound=
tmin (minBound, bounds[
i]);
8464 int minBound2= bounds2[0];
8465 for (
int i= 1;
i < boundsLength2;
i++)
8467 if (bounds2[
i] != 0)
8468 minBound2=
tmin (minBound2, bounds2[
i]);
8474 CFList uniFactors, list, bufUniFactors;
8479 CanonicalForm Aeval2, evaluation2, bufAeval2, bufEvaluation2;
8480 CFList bufUniFactors2, list2, uniFactors2;
8491 bool symmetric=
false;
8494 for (
int i= 0;
i < factorNums;
i++)
8500 if (!derivXZero && !fail2 && !symmetric)
8511 "time to find eval point wrt y: ");
8514 if (fail && (
i == 0))
8516 if (!derivXZero && !fail2 && !symmetric)
8518 bufEvaluation= bufEvaluation2;
8519 int dummy= subCheck2;
8520 subCheck2= subCheck1;
8525 bufAeval= bufAeval2;
8534 if (fail && (
i == 0))
8547 if (fail && (
i != 0))
8554 "time for univariate factorization over Fq: ");
8555 DEBOUTLN (cerr,
"Lc (bufAeval)*prod (bufUniFactors)== bufAeval " <<
8556 (
prod (bufUniFactors)*
Lc (bufAeval) == bufAeval));
8558 if (!derivXZero && !fail2 && !symmetric)
8563 "time for univariate factorization in y over Fq: ");
8564 DEBOUTLN (cerr,
"Lc (bufAeval2)*prod (bufUniFactors2)== bufAeval2 " <<
8565 (
prod (bufUniFactors2)*
Lc (bufAeval2) == bufAeval2));
8568 if (bufUniFactors.
length() == 1 ||
8569 (!fail2 && !derivXZero && !symmetric && (bufUniFactors2.
length() == 1)))
8589 if (
i == 0 && !extension)
8595 if (subCheck > 1 && (subCheck1%subCheck == 0))
8598 subst (bufA, bufA, subCheck,
x);
8611 if (!derivXZero && !fail2 && !symmetric && subCheck2 > 0)
8615 if (subCheck > 1 && (subCheck2%subCheck == 0))
8618 subst (bufA, bufA, subCheck,
y);
8634 if (!derivXZero && !fail2 && !symmetric)
8641 uniFactors= bufUniFactors;
8643 if (!derivXZero && !fail2 && !symmetric)
8646 evaluation2= bufEvaluation2;
8647 uniFactors2= bufUniFactors2;
8654 if (!derivXZero && !fail2 && !symmetric)
8659 uniFactors2= bufUniFactors2;
8661 evaluation2= bufEvaluation2;
8666 uniFactors= bufUniFactors;
8671 list.
append (bufEvaluation);
8672 if (!derivXZero && !fail2 && !symmetric)
8673 list2.
append (bufEvaluation2);
8676 "total time for univariate factorizations: ");
8678 if (!derivXZero && !fail2 && !symmetric)
8680 if ((uniFactors.
length() > uniFactors2.
length() && minBound2 <= minBound)||
8685 uniFactors= uniFactors2;
8717 minBound= minBound2;
8723 "time to shift eval to zero: ");
8729 DEBOUTLN (cerr,
"uniFactors= " << uniFactors);
8731 if ((GF && !extension) || (GF && extension &&
k != 1))
8733 bool earlySuccess=
false;
8737 (
A, earlySuccess, earlyFactors, degs, liftBound,
8740 "time for bivariate hensel lifting over Fq: ");
8741 DEBOUTLN (cerr,
"lifted factors= " << uniFactors);
8753 "time for naive bivariate factor recombi over Fq: ");
8756 factors=
Union (earlyFactors, factors);
8757 else if (!earlySuccess && degs.
getLength() == 1)
8758 factors= earlyFactors;
8768 factors=
Union (lll, factors);
8774 factors=
Union (lll, factors);
8776 else if (!extension && (
alpha !=
x || GF))
8780 factors=
Union (lll, factors);
8783 "time to bivar lift and LLL recombi over Fq: ");
8784 DEBOUTLN (cerr,
"lifted factors= " << uniFactors);
8788 bool earlySuccess=
false;
8792 (
A, earlySuccess, earlyFactors, degs, liftBound,
8795 "time for bivar hensel lifting over Fq: ");
8796 DEBOUTLN (cerr,
"lifted factors= " << uniFactors);
8804 "time for small subset naive recombi over Fq: ");
8806 int oldUniFactorsLength= uniFactors.
length();
8827 "time to increase precision: ");
8828 factors=
Union (factors, tmp);
8830 && uniFactors.
length() != oldUniFactorsLength)
8878 int oldUniFactorsLength= uniFactors.
length();
8887 info2, source, dest, liftBound
8889 factors=
Union (factors, tmp);
8891 && uniFactors.
length() != oldUniFactorsLength)
8908 factors=
Union (earlyFactors, factors);
8909 else if (!earlySuccess && degs.
getLength() == 1)
8910 factors= earlyFactors;
CanonicalForm normalize(const CanonicalForm &F)
normalize a poly, i.e. in char 0 clear denominators, remove integer content in char p divide by leadi...
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
int * computeBounds(const CanonicalForm &F, int &n, bool &isIrreducible)
compute bounds for logarithmic derivative as described in K. Belabas, M. van Hoeij,...
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 substituteCheck(const CanonicalForm &F, const Variable &x)
check if a substitution x^n->x is possible
int * computeBoundsWrtDiffMainvar(const CanonicalForm &F, int &n, bool &isIrreducible)
as above just wrt to the other variable
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)