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
8317 int k=
info.getGFDegree();
8319 if (
A.isUnivariate())
8320 {
8323 else
8324 {
8328 }
8329 }
8330
8334
8337
8338
8341
8344
8346 {
8349 }
8350
8351
8353 if (
A.inCoeffDomain())
8354 {
8359 }
8360 else if (
A.isUnivariate())
8361 {
8367 }
8368
8369
8370
8373 {
8375
8378
8382 }
8383
8384
8390 else
8391 {
8394 {
8404 }
8405 }
8411 else
8412 {
8415 {
8425 }
8426 }
8427
8430 {
8432 {
8438 }
8439 }
8440
8445 {
8448
8451
8455 }
8456
8459 {
8462 }
8463
8468 {
8471 }
8472
8473
8479
8486
8487
8488
8489
8494
8497 {
8503 {
8505 {
8508 }
8513 "time to find eval point wrt y: ");
8514 }
8515
8516 if (
fail && (
i == 0))
8517 {
8519 {
8530 }
8531 else
8533 }
8534
8535
8536 if (
fail && (
i == 0))
8537 {
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 " <<
8559
8561 {
8565 "time for univariate factorization in y over Fq: ");
8566 DEBOUTLN (
cerr,
"Lc (bufAeval2)*prod (bufUniFactors2)== bufAeval2 " <<
8568 }
8569
8572 {
8574 {
8577 }
8578 else
8580
8583
8589 }
8590
8592 {
8594 {
8596
8598 {
8610 }
8611 }
8612
8614 {
8616
8618 {
8630 }
8631 }
8632 }
8633
8634
8638
8640 {
8646 {
8651 }
8652 }
8653 else
8654 {
8657 {
8660 {
8664 }
8665 }
8667 {
8671 }
8672 }
8676 }
8678 "total time for univariate factorizations: ");
8679
8681 {
8685 {
8692 }
8693 }
8694
8695 if (
degs.getLength() == 1)
8696 {
8698 {
8701 }
8702 else
8711 }
8712
8714
8716 {
8720 }
8721
8725 "time to shift eval to zero: ");
8726
8730
8732
8734 {
8742 "time for bivariate hensel lifting over Fq: ");
8744
8746
8751 else
8755 "time for naive bivariate factor recombi over Fq: ");
8756
8761 }
8763 {
8766 {
8769 );
8771 }
8773 {
8777 }
8779 {
8783 }
8785 "time to bivar lift and LLL recombi over Fq: ");
8787 }
8788 else
8789 {
8797 "time for bivar hensel lifting over Fq: ");
8799
8802 {
8806 "time for small subset naive recombi over Fq: ");
8807
8810 {
8816 );
8817 else
8818 {
8822 );
8823 else
8826 );
8827 }
8829 "time to increase precision: ");
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 );
8882 {
8885
8890 );
8894 )
8895 {
8902 )
8903 );
8904 }
8905 }
8906 }
8907 }
8908
8913 }
8914
8918
8923
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.
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 *& 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)
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)