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();
8320 if (
A.isUnivariate())
8321 {
8324 else
8325 {
8329 }
8330 }
8331
8335
8338
8339
8342
8345
8347 {
8350 }
8351
8352
8354 if (
A.inCoeffDomain())
8355 {
8360 }
8361 else if (
A.isUnivariate())
8362 {
8368 }
8369
8370
8371
8374 {
8376
8379
8383 }
8384
8385
8391 else
8392 {
8395 {
8405 }
8406 }
8412 else
8413 {
8416 {
8426 }
8427 }
8428
8431 {
8433 {
8439 }
8440 }
8441
8446 {
8449
8452
8456 }
8457
8460 {
8463 }
8464
8469 {
8472 }
8473
8474
8480
8487
8488
8489
8490
8495
8498 {
8504 {
8506 {
8509 }
8514 "time to find eval point wrt y: ");
8515 }
8516
8517 if (
fail && (
i == 0))
8518 {
8520 {
8531 }
8532 else
8534 }
8535
8536
8537 if (
fail && (
i == 0))
8538 {
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 " <<
8560
8562 {
8566 "time for univariate factorization in y over Fq: ");
8567 DEBOUTLN (
cerr,
"Lc (bufAeval2)*prod (bufUniFactors2)== bufAeval2 " <<
8569 }
8570
8573 {
8575 {
8578 }
8579 else
8581
8584
8590 }
8591
8593 {
8595 {
8597
8599 {
8611 }
8612 }
8613
8615 {
8617
8619 {
8631 }
8632 }
8633 }
8634
8635
8639
8641 {
8647 {
8652 }
8653 }
8654 else
8655 {
8658 {
8661 {
8665 }
8666 }
8668 {
8672 }
8673 }
8677 }
8679 "total time for univariate factorizations: ");
8680
8682 {
8686 {
8693 }
8694 }
8695
8696 if (
degs.getLength() == 1)
8697 {
8699 {
8702 }
8703 else
8712 }
8713
8715
8717 {
8721 }
8722
8726 "time to shift eval to zero: ");
8727
8731
8733
8735 {
8743 "time for bivariate hensel lifting over Fq: ");
8745
8747
8752 else
8756 "time for naive bivariate factor recombi over Fq: ");
8757
8762 }
8764 {
8767 {
8770 );
8772 }
8774 {
8778 }
8780 {
8784 }
8786 "time to bivar lift and LLL recombi over Fq: ");
8788 }
8789 else
8790 {
8798 "time for bivar hensel lifting over Fq: ");
8800
8803 {
8807 "time for small subset naive recombi over Fq: ");
8808
8811 {
8817 );
8818 else
8819 {
8823 );
8824 else
8827 );
8828 }
8830 "time to increase precision: ");
8834 )
8835 {
8842 )
8843 );
8844 }
8845 }
8846 }
8847 else
8848 {
8850 {
8852 {
8855 );
8856 }
8857 else
8858 {
8861 );
8863 {
8871 )
8872 );
8873 }
8874 }
8875 }
8876 else
8877 {
8880 );
8883 {
8886
8891 );
8895 )
8896 {
8903 )
8904 );
8905 }
8906 }
8907 }
8908 }
8909
8914 }
8915
8919
8924
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.
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)