26 #include <flint/fmpz_poly_factor.h> 58 if (iter.
getItem().factor().inCoeffDomain())
104 if (f1Factors.
getFirst().factor().inCoeffDomain())
112 if (f2Factors.
getFirst().factor().inCoeffDomain())
135 if (
mod (D1, p) != 0 &&
mod (D2, p) != 0)
157 if (
mod (D1, p) != 0 &&
mod (D2, p) != 0)
195 mpz_t *
M=
new mpz_t [4];
201 mpz_t * S=
new mpz_t [2];
225 if (result.
getFirst().factor().inCoeffDomain())
283 if (factors.
getFirst().factor().inCoeffDomain())
327 smallestFactor= iter.
getItem().factor();
333 smallestFactor= iter.
getItem().factor();
341 if (!iter.
getItem().factor().isUnivariate() &&
344 smallestFactor= iter.
getItem().factor();
348 if (tdegF % minTdeg == 0)
362 !
gcd (Gpx, smallestFactorEvalx).inCoeffDomain());
364 !
gcd (Gpy, smallestFactorEvaly).inCoeffDomain());
365 if (!xValid || !yValid)
369 goto differentevalpoint;
378 for (
int i= 1;
i < 3;
i++)
382 int s= tdegF/minTdeg + 1;
389 while ( B < bound ) {
400 nmod_poly_t FLINTFpi, FLINTGpi;
404 smallestFactorEvalx/
lc (smallestFactorEvalx));
410 smallestFactorEvaly/
lc (smallestFactorEvaly));
413 nmod_poly_factor_t nmodFactors;
414 nmod_poly_factor_init (nmodFactors);
415 nmod_poly_factor_insert (nmodFactors, FLINTFpi, 1L);
416 nmod_poly_factor_insert (nmodFactors, FLINTGpi, 1L);
424 fmpz_poly_t *
v=
new fmpz_poly_t[2];
425 fmpz_poly_t *
w=
new fmpz_poly_t[2];
426 fmpz_poly_init(v[0]);
427 fmpz_poly_init(v[1]);
428 fmpz_poly_init(w[0]);
429 fmpz_poly_init(w[1]);
431 fmpz_poly_factor_t liftedFactors;
432 fmpz_poly_factor_init (liftedFactors);
433 _fmpz_poly_hensel_start_lift (liftedFactors, link, v, w, FLINTFi,
436 nmod_poly_factor_clear (nmodFactors);
457 zz_pX NTLFpi, NTLGpi;
468 vec_zz_pX modFactors;
469 modFactors.SetLength(2);
470 modFactors[0]= NTLFpi;
471 modFactors[1]= NTLGpi;
472 vec_ZZX liftedFactors;
473 MultiLift (liftedFactors, modFactors, NTLFi, (
long) k);
483 liftedSmallestFactor= pk (liftedSmallestFactor);
485 liftedSmallestFactor= liftedSmallestFactor (eval[0],1);
487 liftedSmallestFactor= liftedSmallestFactor (eval[1],1);
492 for (
int j= 1;
j <
s;
j++)
495 (*M) (j+1,
j)= -liftedSmallestFactor;
502 transpose (*NTLM, *NTLM);
503 (void) LLL (det, *NTLM, 1L, 1L);
504 transpose (*NTLM, *NTLM);
510 for (
int j= 1;
j <=
s;
j++)
511 mipo += (*M) (
j,1)*
power (x,s-
j);
515 if (mipoFactors.
getFirst().factor().inCoeffDomain())
519 fmpz_poly_clear (v[0]);
520 fmpz_poly_clear (v[1]);
521 fmpz_poly_clear (w[0]);
522 fmpz_poly_clear (w[1]);
526 fmpz_poly_factor_clear (liftedFactors);
529 if (mipoFactors.
length() > 1 ||
530 (mipoFactors.
length() == 1 && mipoFactors.
getFirst().exp() > 1) ||
534 goto differentevalpoint;
543 goto differentevalpoint;
557 mipoFactors=
factorize (mipos[1], alpha);
558 if (mipoFactors.
getFirst().factor().inCoeffDomain())
560 for (iter= mipoFactors; iter.
hasItem(); iter++)
565 if (wrongMipo == mipoFactors.
length())
568 goto differentevalpoint;
573 if (mipoFactors.
getFirst().factor().inCoeffDomain())
575 for (iter= mipoFactors; iter.
hasItem(); iter++)
580 if (wrongMipo == mipoFactors.
length())
583 goto differentevalpoint;
588 mipoFactors=
factorize (mipos[0], alpha);
589 if (mipoFactors.
getFirst().factor().inCoeffDomain())
591 for (iter= mipoFactors; iter.
hasItem(); iter++)
596 if (wrongMipo == mipoFactors.
length())
599 goto differentevalpoint;
604 if (mipoFactors.
getFirst().factor().inCoeffDomain())
606 for (iter= mipoFactors; iter.
hasItem(); iter++)
611 if (wrongMipo == mipoFactors.
length())
614 goto differentevalpoint;
620 if (
degree (F,1) > minTdeg)
636 if (QaF1Factors.
getFirst().factor().inCoeffDomain())
638 for (iter= QaF1Factors; iter.
hasItem(); iter++)
644 if (wrongMipo == QaF1Factors.
length())
648 goto differentevalpoint;
658 F= F (y + evaluation, y);
660 int liftBound=
degree (F,y) + 1;
669 for (iter=QaF1Factors; iter.
hasItem(); iter++)
706 bool earlySuccess=
false;
709 (F, earlySuccess, earlyFactors, degs, liftBound,
710 uniFactors, dummy, evaluation, b, den);
712 DEBOUTLN (cerr,
"lifted factors= " << uniFactors);
728 biFactors=
Union (earlyFactors, biFactors);
729 else if (!earlySuccess && degs.
getLength() == 1)
730 biFactors= earlyFactors;
762 goto differentevalpoint;
int status int void size_t count
int cf_getSmallPrime(int i)
const CanonicalForm int s
DegreePattern provides a functionality to create, intersect and refine degree patterns.
void convertFacCF2Fmpz_poly_t(fmpz_poly_t result, const CanonicalForm &f)
conversion of a factory univariate polynomial over Z to a fmpz_poly_t
const CanonicalForm int const CFList const Variable & y
Conversion to and from NTL.
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
int getLength() const
getter
static CanonicalForm bound(const CFMatrix &M)
This file defines functions for conversion to FLINT (www.flintlib.org) and back.
CFAFList absBiFactorizeMain(const CanonicalForm &G, bool full)
main absolute factorization routine, expects bivariate poly which is irreducible over Q ...
functions to print debug output
#define TIMING_END_AND_PRINT(t, msg)
factory's class for variables
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
generate random evaluation points
class to generate random evaluation points
nmod_poly_clear(FLINTmipo)
ZZX convertFacCF2NTLZZX(const CanonicalForm &f)
const CanonicalForm int const CFList & evaluation
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...
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m )
CanonicalForm inverse(const CanonicalForm &f, bool symmetric=true) const
Rational abs(const Rational &a)
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...
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
CFFList factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
ExtensionInfo contains information about extension.
bivariate absolute factorization over Q described in "Modular Las Vegas Algorithms for Polynomial Abs...
CFAFList uniAbsFactorize(const CanonicalForm &F, bool full=false)
univariate absolute factorization over Q
int choosePoint(const CanonicalForm &F, int tdegF, CFArray &eval, bool rec, int absValue)
CanonicalForm decompress(const CanonicalForm &F, const mpz_t *inverseM, const mpz_t *A)
decompress a bivariate poly
convertFacCF2nmod_poly_t(FLINTmipo, M)
Variable rootOf(const CanonicalForm &, char name= '@')
returns a symbolic root of polynomial with name name Use it to define algebraic variables ...
static const int SW_RATIONAL
set to 1 for computations over Q
bool absIrredTest(const CanonicalForm &F)
absolute irreducibility test as described in "Modular Las Vegas Algorithms for Polynomial Absolute Fa...
int cf_getNumSmallPrimes()
declarations of higher level algorithms.
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
mat_ZZ * convertFacCFMatrix2NTLmat_ZZ(const CFMatrix &m)
CanonicalForm maxNorm(const CanonicalForm &f)
CanonicalForm maxNorm ( const CanonicalForm & f )
const Variable & v
< [in] a sqrfree bivariate poly
CanonicalForm convertFmpz_poly_t2FacCF(const fmpz_poly_t poly, const Variable &x)
conversion of a FLINT poly over Z to CanonicalForm
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
int cf_getBigPrime(int i)
static BOOLEAN discriminant(leftv result, leftv arg)
CFMatrix * convertNTLmat_ZZ2FacCFMatrix(const mat_ZZ &m)
TIMING_DEFINE_PRINT(fac_Qa_factorize) TIMING_DEFINE_PRINT(fac_evalpoint) CFAFList uniAbsFactorize(const CanonicalForm &F
void findGoodPrime(const CanonicalForm &f, int &start)
find a big prime p from our tables such that no term of f vanishes mod p
This file provides functions for factorizing a bivariate polynomial over , or GF.
#define DEBOUTLN(stream, objects)
modpk coeffBound(const CanonicalForm &f, int p, const CanonicalForm &mipo)
compute p^k larger than the bound on the coefficients of a factor of f over Q (mipo) ...
bivariate factorization over Q(a)
bool modularIrredTestWithShift(const CanonicalForm &F)
modular absolute irreducibility test with shift as described in "Modular Las Vegas Algorithms for Pol...
static const int SW_SYMMETRIC_FF
set to 1 for symmetric representation over F_q
CanonicalForm convertZZ2CF(const ZZ &a)
NAME: convertZZ2CF.
CanonicalForm resultant(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
CanonicalForm resultant ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x ) ...
class to do operations mod p^k for int's p and k
CanonicalForm convertNTLZZX2CF(const ZZX &polynom, const Variable &x)