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.
8307{
8310
8313
8318 int k=
info.getGFDegree();
8319 bool extension=
info.isInExtension();
8320 if (
A.isUnivariate())
8321 {
8322 if (extension == false)
8324 else
8325 {
8329 }
8330 }
8331
8335
8336 if (
y.level() > 2)
return CFList (F);
8338
8339
8342
8343 A=
A/(contentAx*contentAy);
8344 CFList contentAxFactors, contentAyFactors;
8345
8346 if (!extension)
8347 {
8350 }
8351
8352
8354 if (
A.inCoeffDomain())
8355 {
8356 append (factors, contentAxFactors);
8357 append (factors, contentAyFactors);
8359 return factors;
8360 }
8361 else if (
A.isUnivariate())
8362 {
8364 append (factors, contentAxFactors);
8365 append (factors, contentAyFactors);
8367 return factors;
8368 }
8369
8370
8371
8374 {
8376
8379
8380 if (!extension)
8382 return factors;
8383 }
8384
8385
8386 bool derivXZero= false;
8390 derivXZero= true;
8391 else
8392 {
8393 gcdDerivX=
gcd (
A, derivX);
8394 if (
degree (gcdDerivX) > 0)
8395 {
8399 append (factorsG, contentAxFactors);
8400 append (factorsG, contentAyFactors);
8402 if (!extension)
8404 return factorsG;
8405 }
8406 }
8407 bool derivYZero= false;
8411 derivYZero= true;
8412 else
8413 {
8414 gcdDerivY=
gcd (
A, derivY);
8415 if (
degree (gcdDerivY) > 0)
8416 {
8420 append (factorsG, contentAxFactors);
8421 append (factorsG, contentAyFactors);
8423 if (!extension)
8425 return factorsG;
8426 }
8427 }
8428
8431 {
8432 if (!derivYZero)
8433 {
8436 derivXZero= derivYZero;
8439 }
8440 }
8441
8442 int boundsLength;
8446 {
8447 delete [] bounds;
8449
8452
8453 if (!extension)
8455 return factors;
8456 }
8457
8458 int minBound= bounds[0];
8459 for (
int i= 1;
i < boundsLength;
i++)
8460 {
8462 minBound=
tmin (minBound, bounds[
i]);
8463 }
8464
8465 int boundsLength2;
8467 int minBound2= bounds2[0];
8468 for (
int i= 1;
i < boundsLength2;
i++)
8469 {
8470 if (bounds2[
i] != 0)
8471 minBound2=
tmin (minBound2, bounds2[
i]);
8472 }
8473
8474
8475 bool fail= false;
8477 CFList uniFactors, list, bufUniFactors;
8480
8481 bool fail2= false;
8482 CanonicalForm Aeval2, evaluation2, bufAeval2, bufEvaluation2;
8483 CFList bufUniFactors2, list2, uniFactors2;
8486 bool swap2= false;
8487
8488
8489
8490
8491 int factorNums= 3;
8494 bool symmetric= false;
8495
8497 for (
int i= 0;
i < factorNums;
i++)
8498 {
8503 if (!derivXZero && !fail2 && !symmetric)
8504 {
8506 {
8509 }
8514 "time to find eval point wrt y: ");
8515 }
8516
8517 if (fail && (
i == 0))
8518 {
8519 if (!derivXZero && !fail2 && !symmetric)
8520 {
8521 bufEvaluation= bufEvaluation2;
8522 int dummy= subCheck2;
8523 subCheck2= subCheck1;
8524 subCheck1= dummy;
8528 bufAeval= bufAeval2;
8529 swap2= true;
8530 fail= false;
8531 }
8532 else
8533 fail= true;
8534 }
8535
8536
8537 if (fail && (
i == 0))
8538 {
8543 delete [] bounds;
8544 delete [] bounds2;
8545 return factors;
8546 }
8547
8548
8549
8550 if (fail && (
i != 0))
8551 break;
8552
8553
8557 "time for univariate factorization over Fq: ");
8558 DEBOUTLN (cerr,
"Lc (bufAeval)*prod (bufUniFactors)== bufAeval " <<
8559 (
prod (bufUniFactors)*
Lc (bufAeval) == bufAeval));
8560
8561 if (!derivXZero && !fail2 && !symmetric)
8562 {
8566 "time for univariate factorization in y over Fq: ");
8567 DEBOUTLN (cerr,
"Lc (bufAeval2)*prod (bufUniFactors2)== bufAeval2 " <<
8568 (
prod (bufUniFactors2)*
Lc (bufAeval2) == bufAeval2));
8569 }
8570
8571 if (bufUniFactors.
length() == 1 ||
8572 (!fail2 && !derivXZero && !symmetric && (bufUniFactors2.
length() == 1)))
8573 {
8574 if (extension)
8575 {
8578 }
8579 else
8581
8584
8585 if (!extension)
8587 delete [] bounds;
8588 delete [] bounds2;
8589 return factors;
8590 }
8591
8592 if (
i == 0 && !extension)
8593 {
8594 if (subCheck1 > 0)
8595 {
8597
8598 if (subCheck > 1 && (subCheck1%subCheck == 0))
8599 {
8601 subst (bufA, bufA, subCheck,
x);
8606 if (!extension)
8608 delete [] bounds;
8609 delete [] bounds2;
8610 return factors;
8611 }
8612 }
8613
8614 if (!derivXZero && !fail2 && !symmetric && subCheck2 > 0)
8615 {
8617
8618 if (subCheck > 1 && (subCheck2%subCheck == 0))
8619 {
8621 subst (bufA, bufA, subCheck,
y);
8626 if (!extension)
8628 delete [] bounds;
8629 delete [] bounds2;
8630 return factors;
8631 }
8632 }
8633 }
8634
8635
8637 if (!derivXZero && !fail2 && !symmetric)
8639
8641 {
8644 uniFactors= bufUniFactors;
8645 degs= bufDegs;
8646 if (!derivXZero && !fail2 && !symmetric)
8647 {
8648 Aeval2= bufAeval2;
8649 evaluation2= bufEvaluation2;
8650 uniFactors2= bufUniFactors2;
8651 degs2= bufDegs2;
8652 }
8653 }
8654 else
8655 {
8657 if (!derivXZero && !fail2 && !symmetric)
8658 {
8661 {
8662 uniFactors2= bufUniFactors2;
8663 Aeval2= bufAeval2;
8664 evaluation2= bufEvaluation2;
8665 }
8666 }
8668 {
8669 uniFactors= bufUniFactors;
8672 }
8673 }
8674 list.
append (bufEvaluation);
8675 if (!derivXZero && !fail2 && !symmetric)
8676 list2.
append (bufEvaluation2);
8677 }
8679 "total time for univariate factorizations: ");
8680
8681 if (!derivXZero && !fail2 && !symmetric)
8682 {
8683 if ((uniFactors.
length() > uniFactors2.
length() && minBound2 <= minBound)||
8686 {
8687 degs= degs2;
8688 uniFactors= uniFactors2;
8692 swap2= true;
8693 }
8694 }
8695
8697 {
8698 if (extension)
8699 {
8702 }
8703 else
8707 if (!extension)
8709 delete [] bounds;
8710 delete [] bounds2;
8711 return factors;
8712 }
8713
8715
8716 if (swap2)
8717 {
8718 delete [] bounds;
8719 bounds= bounds2;
8720 minBound= minBound2;
8721 }
8722
8726 "time to shift eval to zero: ");
8727
8728 int degMipo= 1;
8729 if (extension &&
alpha.level() != 1 &&
k==1)
8731
8732 DEBOUTLN (cerr,
"uniFactors= " << uniFactors);
8733
8734 if ((GF && !extension) || (GF && extension &&
k != 1))
8735 {
8736 bool earlySuccess= false;
8740 (
A, earlySuccess, earlyFactors, degs, liftBound,
8743 "time for bivariate hensel lifting over Fq: ");
8744 DEBOUTLN (cerr,
"lifted factors= " << uniFactors);
8745
8747
8749 if (extension)
8752 else
8756 "time for naive bivariate factor recombi over Fq: ");
8757
8758 if (earlySuccess)
8759 factors=
Union (earlyFactors, factors);
8760 else if (!earlySuccess && degs.
getLength() == 1)
8761 factors= earlyFactors;
8762 }
8763 else if (
degree (
A) > 4 &&
beta.level() == 1 && (2*minBound)/degMipo < 32)
8764 {
8766 if (extension)
8767 {
8770 );
8771 factors=
Union (lll, factors);
8772 }
8773 else if (
alpha.level() == 1 && !GF)
8774 {
8777 factors=
Union (lll, factors);
8778 }
8779 else if (!extension && (
alpha !=
x || GF))
8780 {
8783 factors=
Union (lll, factors);
8784 }
8786 "time to bivar lift and LLL recombi over Fq: ");
8787 DEBOUTLN (cerr,
"lifted factors= " << uniFactors);
8788 }
8789 else
8790 {
8791 bool earlySuccess= false;
8795 (
A, earlySuccess, earlyFactors, degs, liftBound,
8798 "time for bivar hensel lifting over Fq: ");
8799 DEBOUTLN (cerr,
"lifted factors= " << uniFactors);
8800
8802 if (!extension)
8803 {
8807 "time for small subset naive recombi over Fq: ");
8808
8809 int oldUniFactorsLength= uniFactors.
length();
8811 {
8814 if (
alpha.level() == 1)
8817 );
8818 else
8819 {
8823 );
8824 else
8827 );
8828 }
8830 "time to increase precision: ");
8831 factors=
Union (factors, tmp);
8833 && uniFactors.
length() != oldUniFactorsLength)
8834 )
8835 {
8842 )
8843 );
8844 }
8845 }
8846 }
8847 else
8848 {
8849 if (
beta.level() != 1 ||
k > 1)
8850 {
8852 {
8855 );
8856 }
8857 else
8858 {
8861 );
8863 {
8871 )
8872 );
8873 }
8874 }
8875 }
8876 else
8877 {
8880 );
8881 int oldUniFactorsLength= uniFactors.
length();
8883 {
8884 int degMipo;
8886
8890 info2, source, dest, liftBound
8891 );
8892 factors=
Union (factors, tmp);
8894 && uniFactors.
length() != oldUniFactorsLength)
8895 )
8896 {
8903 )
8904 );
8905 }
8906 }
8907 }
8908 }
8909
8910 if (earlySuccess)
8911 factors=
Union (earlyFactors, factors);
8912 else if (!earlySuccess && degs.
getLength() == 1)
8913 factors= earlyFactors;
8914 }
8915
8916 if (!swap2)
8917 delete [] bounds2;
8918 delete [] bounds;
8919
8922 if (!extension)
8924
8925 return factors;
8926}
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.
factory's class for variables
#define DEBOUTLN(stream, objects)
const CanonicalForm int const CFList & evaluation
const CanonicalForm int const CFList const Variable & y
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 biFactorize(const CanonicalForm &F, const Variable &v)
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 "Factoringmultivariate polynomials over a f...
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 "Factoringmultivariate 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 "Factoringmultivariate 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)
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)
#define TIMING_END_AND_PRINT(t, msg)