26 #include <flint/fmpz_poly_factor.h>
104 if (f1Factors.
getFirst().factor().inCoeffDomain())
112 if (f2Factors.
getFirst().factor().inCoeffDomain())
118 ZZ NTLD1= discriminant (NTLf1);
119 ZZ NTLD2= discriminant (NTLf2);
135 if (
mod (D1,
p) != 0 &&
mod (D2,
p) != 0)
145 else if (!
f.isZero())
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())
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;
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++)
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;
558 if (mipoFactors.
getFirst().factor().inCoeffDomain())
565 if (wrongMipo == mipoFactors.
length())
568 goto differentevalpoint;
573 if (mipoFactors.
getFirst().factor().inCoeffDomain())
580 if (wrongMipo == mipoFactors.
length())
583 goto differentevalpoint;
589 if (mipoFactors.
getFirst().factor().inCoeffDomain())
596 if (wrongMipo == mipoFactors.
length())
599 goto differentevalpoint;
604 if (mipoFactors.
getFirst().factor().inCoeffDomain())
611 if (wrongMipo == mipoFactors.
length())
614 goto differentevalpoint;
620 if (
degree (F,1) > minTdeg)
636 if (QaF1Factors.
getFirst().factor().inCoeffDomain())
644 if (wrongMipo == QaF1Factors.
length())
648 goto differentevalpoint;
660 int liftBound=
degree (F,
y) + 1;
676 ZZ NTLD= discriminant (NTLmipo);
699 if (bb.
getk() >
b.getk() )
b=bb;
701 if (bb.
getk() >
b.getk() )
b=bb;
706 bool earlySuccess=
false;
709 (F, earlySuccess, earlyFactors, degs, liftBound,
712 DEBOUTLN (cerr,
"lifted factors= " << uniFactors);
728 biFactors=
Union (earlyFactors, biFactors);
729 else if (!earlySuccess && degs.
getLength() == 1)
730 biFactors= earlyFactors;
762 goto differentevalpoint;
CanonicalForm convertFmpz_poly_t2FacCF(const fmpz_poly_t poly, const Variable &x)
conversion of a FLINT poly over Z to CanonicalForm
void convertFacCF2Fmpz_poly_t(fmpz_poly_t result, const CanonicalForm &f)
conversion of a factory univariate polynomial over Z to a fmpz_poly_t
This file defines functions for conversion to FLINT (www.flintlib.org) and back.
Rational abs(const Rational &a)
CFMatrix * convertNTLmat_ZZ2FacCFMatrix(const mat_ZZ &m)
CanonicalForm convertZZ2CF(const ZZ &a)
NAME: convertZZ2CF.
ZZX convertFacCF2NTLZZX(const CanonicalForm &f)
mat_ZZ * convertFacCFMatrix2NTLmat_ZZ(const CFMatrix &m)
CanonicalForm convertNTLZZX2CF(const ZZX &polynom, const Variable &x)
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
Conversion to and from NTL.
bool modularIrredTestWithShift(const CanonicalForm &F)
modular absolute irreducibility test with shift as described in "Modular Las Vegas Algorithms for Pol...
bool absIrredTest(const CanonicalForm &F)
absolute irreducibility test as described in "Modular Las Vegas Algorithms for Polynomial Absolute Fa...
CanonicalForm decompress(const CanonicalForm &F, const mpz_t *inverseM, const mpz_t *A)
decompress a bivariate poly
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
CanonicalForm maxNorm(const CanonicalForm &f)
CanonicalForm maxNorm ( const CanonicalForm & f )
declarations of higher level algorithms.
CFFList factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
CanonicalForm resultant(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
CanonicalForm resultant ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x )
static const int SW_RATIONAL
set to 1 for computations over Q
static const int SW_SYMMETRIC_FF
set to 1 for symmetric representation over F_q
static CanonicalForm bound(const CFMatrix &M)
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m )
int cf_getBigPrime(int i)
int cf_getNumSmallPrimes()
int cf_getSmallPrime(int i)
generate random evaluation points
DegreePattern provides a functionality to create, intersect and refine degree patterns.
int getLength() const
getter
ExtensionInfo contains information about extension.
class to generate random evaluation points
factory's class for variables
class to do operations mod p^k for int's p and k
CanonicalForm inverse(const CanonicalForm &f, bool symmetric=true) const
functions to print debug output
#define DEBOUTLN(stream, objects)
int choosePoint(const CanonicalForm &F, int tdegF, CFArray &eval, bool rec, int absValue)
TIMING_DEFINE_PRINT(fac_Qa_factorize) TIMING_DEFINE_PRINT(fac_evalpoint) CFAFList uniAbsFactorize(const CanonicalForm &F
CFAFList absBiFactorizeMain(const CanonicalForm &G, bool full)
main absolute factorization routine, expects bivariate poly which is irreducible over Q
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
const CanonicalForm int const CFList & evaluation
const CanonicalForm int s
const CanonicalForm int const CFList const Variable & y
TIMING_END_AND_PRINT(fac_alg_resultant, "time to compute resultant0: ")
TIMING_START(fac_alg_resultant)
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)
void findGoodPrime(const CanonicalForm &f, int &start)
find a big prime p from our tables such that no term of f vanishes mod p
bivariate factorization over Q(a)
const Variable & v
< [in] a sqrfree bivariate poly
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...
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 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...
This file provides functions for factorizing a bivariate polynomial over , or GF.
convertFacCF2nmod_poly_t(FLINTmipo, M)
nmod_poly_clear(FLINTmipo)
Variable rootOf(const CanonicalForm &, char name='@')
returns a symbolic root of polynomial with name name Use it to define algebraic variables
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
int status int void size_t count
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)