 |
My Project
debian-1:4.1.2-p1+ds-2
|
Go to the documentation of this file.
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 convertZZ2CF(const ZZ &a)
NAME: convertZZ2CF.
static const int SW_RATIONAL
set to 1 for computations over Q
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
#define DEBOUTLN(stream, objects)
const CanonicalForm int const CFList const Variable & y
CFAFList uniAbsFactorize(const CanonicalForm &F, bool full=false)
univariate absolute factorization over Q
nmod_poly_clear(FLINTmipo)
CFAFList absBiFactorizeMain(const CanonicalForm &G, bool full)
main absolute factorization routine, expects bivariate poly which is irreducible over Q
Variable rootOf(const CanonicalForm &, char name='@')
returns a symbolic root of polynomial with name name Use it to define algebraic variables
int cf_getBigPrime(int i)
CanonicalForm maxNorm(const CanonicalForm &f)
CanonicalForm maxNorm ( const CanonicalForm & f )
const CanonicalForm int const CFList & evaluation
convertFacCF2nmod_poly_t(FLINTmipo, M)
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Rational abs(const Rational &a)
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...
TIMING_START(fac_alg_resultant)
int choosePoint(const CanonicalForm &F, int tdegF, CFArray &eval, bool rec, int absValue)
bool absIrredTest(const CanonicalForm &F)
absolute irreducibility test as described in "Modular Las Vegas Algorithms for Polynomial Absolute Fa...
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...
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m )
mat_ZZ * convertFacCFMatrix2NTLmat_ZZ(const CFMatrix &m)
class to generate random evaluation points
CFFList factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
ZZX convertFacCF2NTLZZX(const CanonicalForm &f)
CanonicalForm decompress(const CanonicalForm &F, const mpz_t *inverseM, const mpz_t *A)
decompress a bivariate poly
class to do operations mod p^k for int's p and k
CanonicalForm convertFmpz_poly_t2FacCF(const fmpz_poly_t poly, const Variable &x)
conversion of a FLINT poly over Z to CanonicalForm
int getLength() const
getter
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
CFMatrix * convertNTLmat_ZZ2FacCFMatrix(const mat_ZZ &m)
TIMING_END_AND_PRINT(fac_alg_resultant, "time to compute resultant0: ")
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
factory's class for variables
static CanonicalForm bound(const CFMatrix &M)
int cf_getSmallPrime(int i)
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)
CanonicalForm resultant(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
CanonicalForm resultant ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x )
CanonicalForm inverse(const CanonicalForm &f, bool symmetric=true) const
static const int SW_SYMMETRIC_FF
set to 1 for symmetric representation over F_q
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
CanonicalForm convertNTLZZX2CF(const ZZX &polynom, const Variable &x)
const Variable & v
< [in] a sqrfree bivariate poly
const CanonicalForm int s
TIMING_DEFINE_PRINT(fac_Qa_factorize) TIMING_DEFINE_PRINT(fac_evalpoint) CFAFList uniAbsFactorize(const CanonicalForm &F
int status int void size_t count
void findGoodPrime(const CanonicalForm &f, int &start)
find a big prime p from our tables such that no term of f vanishes mod p
int cf_getNumSmallPrimes()
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
void convertFacCF2Fmpz_poly_t(fmpz_poly_t result, const CanonicalForm &f)
conversion of a factory univariate polynomial over Z to a fmpz_poly_t
bool modularIrredTestWithShift(const CanonicalForm &F)
modular absolute irreducibility test with shift as described in "Modular Las Vegas Algorithms for Pol...