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.
8306{
8309
8312
8319 if (
A.isUnivariate())
8320 {
8321 if (extension == false)
8323 else
8324 {
8328 }
8329 }
8330
8334
8337
8338
8341
8342 A=
A/(contentAx*contentAy);
8343 CFList contentAxFactors, contentAyFactors;
8344
8345 if (!extension)
8346 {
8349 }
8350
8351
8353 if (
A.inCoeffDomain())
8354 {
8355 append (factors, contentAxFactors);
8356 append (factors, contentAyFactors);
8358 return factors;
8359 }
8360 else if (
A.isUnivariate())
8361 {
8363 append (factors, contentAxFactors);
8364 append (factors, contentAyFactors);
8366 return factors;
8367 }
8368
8369
8370
8373 {
8375
8378
8379 if (!extension)
8381 return factors;
8382 }
8383
8384
8385 bool derivXZero= false;
8389 derivXZero= true;
8390 else
8391 {
8392 gcdDerivX=
gcd (
A, derivX);
8393 if (
degree (gcdDerivX) > 0)
8394 {
8398 append (factorsG, contentAxFactors);
8399 append (factorsG, contentAyFactors);
8401 if (!extension)
8403 return factorsG;
8404 }
8405 }
8406 bool derivYZero= false;
8410 derivYZero= true;
8411 else
8412 {
8413 gcdDerivY=
gcd (
A, derivY);
8414 if (
degree (gcdDerivY) > 0)
8415 {
8419 append (factorsG, contentAxFactors);
8420 append (factorsG, contentAyFactors);
8422 if (!extension)
8424 return factorsG;
8425 }
8426 }
8427
8430 {
8431 if (!derivYZero)
8432 {
8435 derivXZero= derivYZero;
8438 }
8439 }
8440
8441 int boundsLength;
8445 {
8446 delete [] bounds;
8448
8451
8452 if (!extension)
8454 return factors;
8455 }
8456
8457 int minBound= bounds[0];
8458 for (
int i= 1;
i < boundsLength;
i++)
8459 {
8461 minBound=
tmin (minBound, bounds[
i]);
8462 }
8463
8464 int boundsLength2;
8466 int minBound2= bounds2[0];
8467 for (
int i= 1;
i < boundsLength2;
i++)
8468 {
8469 if (bounds2[
i] != 0)
8470 minBound2=
tmin (minBound2, bounds2[
i]);
8471 }
8472
8473
8474 bool fail= false;
8476 CFList uniFactors, list, bufUniFactors;
8479
8480 bool fail2= false;
8481 CanonicalForm Aeval2, evaluation2, bufAeval2, bufEvaluation2;
8482 CFList bufUniFactors2, list2, uniFactors2;
8485 bool swap2= false;
8486
8487
8488
8489
8490 int factorNums= 3;
8493 bool symmetric= false;
8494
8496 for (
int i= 0;
i < factorNums;
i++)
8497 {
8502 if (!derivXZero && !fail2 && !symmetric)
8503 {
8505 {
8508 }
8513 "time to find eval point wrt y: ");
8514 }
8515
8516 if (fail && (
i == 0))
8517 {
8518 if (!derivXZero && !fail2 && !symmetric)
8519 {
8520 bufEvaluation= bufEvaluation2;
8521 int dummy= subCheck2;
8522 subCheck2= subCheck1;
8523 subCheck1= dummy;
8527 bufAeval= bufAeval2;
8528 swap2= true;
8529 fail= false;
8530 }
8531 else
8532 fail= true;
8533 }
8534
8535
8536 if (fail && (
i == 0))
8537 {
8542 delete [] bounds;
8543 delete [] bounds2;
8544 return factors;
8545 }
8546
8547
8548
8549 if (fail && (
i != 0))
8550 break;
8551
8552
8556 "time for univariate factorization over Fq: ");
8557 DEBOUTLN (cerr,
"Lc (bufAeval)*prod (bufUniFactors)== bufAeval " <<
8558 (
prod (bufUniFactors)*
Lc (bufAeval) == bufAeval));
8559
8560 if (!derivXZero && !fail2 && !symmetric)
8561 {
8565 "time for univariate factorization in y over Fq: ");
8566 DEBOUTLN (cerr,
"Lc (bufAeval2)*prod (bufUniFactors2)== bufAeval2 " <<
8567 (
prod (bufUniFactors2)*
Lc (bufAeval2) == bufAeval2));
8568 }
8569
8570 if (bufUniFactors.
length() == 1 ||
8571 (!fail2 && !derivXZero && !symmetric && (bufUniFactors2.
length() == 1)))
8572 {
8573 if (extension)
8574 {
8577 }
8578 else
8580
8583
8584 if (!extension)
8586 delete [] bounds;
8587 delete [] bounds2;
8588 return factors;
8589 }
8590
8591 if (
i == 0 && !extension)
8592 {
8593 if (subCheck1 > 0)
8594 {
8596
8597 if (subCheck > 1 && (subCheck1%subCheck == 0))
8598 {
8600 subst (bufA, bufA, subCheck,
x);
8605 if (!extension)
8607 delete [] bounds;
8608 delete [] bounds2;
8609 return factors;
8610 }
8611 }
8612
8613 if (!derivXZero && !fail2 && !symmetric && subCheck2 > 0)
8614 {
8616
8617 if (subCheck > 1 && (subCheck2%subCheck == 0))
8618 {
8620 subst (bufA, bufA, subCheck,
y);
8625 if (!extension)
8627 delete [] bounds;
8628 delete [] bounds2;
8629 return factors;
8630 }
8631 }
8632 }
8633
8634
8636 if (!derivXZero && !fail2 && !symmetric)
8638
8640 {
8643 uniFactors= bufUniFactors;
8644 degs= bufDegs;
8645 if (!derivXZero && !fail2 && !symmetric)
8646 {
8647 Aeval2= bufAeval2;
8648 evaluation2= bufEvaluation2;
8649 uniFactors2= bufUniFactors2;
8650 degs2= bufDegs2;
8651 }
8652 }
8653 else
8654 {
8656 if (!derivXZero && !fail2 && !symmetric)
8657 {
8660 {
8661 uniFactors2= bufUniFactors2;
8662 Aeval2= bufAeval2;
8663 evaluation2= bufEvaluation2;
8664 }
8665 }
8667 {
8668 uniFactors= bufUniFactors;
8671 }
8672 }
8673 list.
append (bufEvaluation);
8674 if (!derivXZero && !fail2 && !symmetric)
8675 list2.
append (bufEvaluation2);
8676 }
8678 "total time for univariate factorizations: ");
8679
8680 if (!derivXZero && !fail2 && !symmetric)
8681 {
8682 if ((uniFactors.
length() > uniFactors2.
length() && minBound2 <= minBound)||
8685 {
8686 degs= degs2;
8687 uniFactors= uniFactors2;
8691 swap2= true;
8692 }
8693 }
8694
8696 {
8697 if (extension)
8698 {
8701 }
8702 else
8706 if (!extension)
8708 delete [] bounds;
8709 delete [] bounds2;
8710 return factors;
8711 }
8712
8714
8715 if (swap2)
8716 {
8717 delete [] bounds;
8718 bounds= bounds2;
8719 minBound= minBound2;
8720 }
8721
8725 "time to shift eval to zero: ");
8726
8727 int degMipo= 1;
8730
8731 DEBOUTLN (cerr,
"uniFactors= " << uniFactors);
8732
8733 if ((GF && !extension) || (GF && extension &&
k != 1))
8734 {
8735 bool earlySuccess= false;
8739 (
A, earlySuccess, earlyFactors, degs, liftBound,
8742 "time for bivariate hensel lifting over Fq: ");
8743 DEBOUTLN (cerr,
"lifted factors= " << uniFactors);
8744
8746
8748 if (extension)
8751 else
8755 "time for naive bivariate factor recombi over Fq: ");
8756
8757 if (earlySuccess)
8758 factors=
Union (earlyFactors, factors);
8759 else if (!earlySuccess && degs.
getLength() == 1)
8760 factors= earlyFactors;
8761 }
8763 {
8765 if (extension)
8766 {
8769 );
8770 factors=
Union (lll, factors);
8771 }
8773 {
8776 factors=
Union (lll, factors);
8777 }
8778 else if (!extension && (
alpha !=
x || GF))
8779 {
8782 factors=
Union (lll, factors);
8783 }
8785 "time to bivar lift and LLL recombi over Fq: ");
8786 DEBOUTLN (cerr,
"lifted factors= " << uniFactors);
8787 }
8788 else
8789 {
8790 bool earlySuccess= false;
8794 (
A, earlySuccess, earlyFactors, degs, liftBound,
8797 "time for bivar hensel lifting over Fq: ");
8798 DEBOUTLN (cerr,
"lifted factors= " << uniFactors);
8799
8801 if (!extension)
8802 {
8806 "time for small subset naive recombi over Fq: ");
8807
8808 int oldUniFactorsLength= uniFactors.
length();
8810 {
8816 );
8817 else
8818 {
8822 );
8823 else
8826 );
8827 }
8829 "time to increase precision: ");
8830 factors=
Union (factors, tmp);
8832 && uniFactors.
length() != oldUniFactorsLength)
8833 )
8834 {
8841 )
8842 );
8843 }
8844 }
8845 }
8846 else
8847 {
8849 {
8851 {
8854 );
8855 }
8856 else
8857 {
8860 );
8862 {
8870 )
8871 );
8872 }
8873 }
8874 }
8875 else
8876 {
8879 );
8880 int oldUniFactorsLength= uniFactors.
length();
8882 {
8883 int degMipo;
8885
8889 info2, source, dest, liftBound
8890 );
8891 factors=
Union (factors, tmp);
8893 && uniFactors.
length() != oldUniFactorsLength)
8894 )
8895 {
8902 )
8903 );
8904 }
8905 }
8906 }
8907 }
8908
8909 if (earlySuccess)
8910 factors=
Union (earlyFactors, factors);
8911 else if (!earlySuccess && degs.
getLength() == 1)
8912 factors= earlyFactors;
8913 }
8914
8915 if (!swap2)
8916 delete [] bounds2;
8917 delete [] bounds;
8918
8921 if (!extension)
8923
8924 return factors;
8925}
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)
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)