main absolute factorization routine, expects bivariate poly which is irreducible over Q
219 mpz_t *
M=
new mpz_t [4];
225 mpz_t * S=
new mpz_t [2];
249 if (
result.getFirst().factor().inCoeffDomain())
307 if (factors.
getFirst().factor().inCoeffDomain())
372 if (tdegF % minTdeg == 0)
389 if (!xValid || !yValid)
393 goto differentevalpoint;
402 for (
int i= 1;
i < 3;
i++)
406 int s= tdegF/minTdeg + 1;
424 nmod_poly_t FLINTFpi, FLINTGpi;
428 smallestFactorEvalx/
lc (smallestFactorEvalx));
434 smallestFactorEvaly/
lc (smallestFactorEvaly));
437 nmod_poly_factor_t nmodFactors;
438 nmod_poly_factor_init (nmodFactors);
439 nmod_poly_factor_insert (nmodFactors, FLINTFpi, 1L);
440 nmod_poly_factor_insert (nmodFactors, FLINTGpi, 1L);
448 fmpz_poly_t *
v=
new fmpz_poly_t[2];
449 fmpz_poly_t *
w=
new fmpz_poly_t[2];
450 fmpz_poly_init(
v[0]);
451 fmpz_poly_init(
v[1]);
452 fmpz_poly_init(
w[0]);
453 fmpz_poly_init(
w[1]);
455 fmpz_poly_factor_t liftedFactors;
456 fmpz_poly_factor_init (liftedFactors);
457 _fmpz_poly_hensel_start_lift (liftedFactors, link,
v,
w, FLINTFi,
460 nmod_poly_factor_clear (nmodFactors);
471#elif defined(HAVE_NTL)
481 zz_pX NTLFpi, NTLGpi;
492 vec_zz_pX modFactors;
493 modFactors.SetLength(2);
494 modFactors[0]= NTLFpi;
495 modFactors[1]= NTLGpi;
496 vec_ZZX liftedFactors;
497 MultiLift (liftedFactors, modFactors, NTLFi, (
long)
k);
509 liftedSmallestFactor= pk (liftedSmallestFactor);
511 liftedSmallestFactor= liftedSmallestFactor (
eval[0],1);
513 liftedSmallestFactor= liftedSmallestFactor (
eval[1],1);
518 for (
int j= 1;
j <
s;
j++)
521 (*M) (
j+1,
j)= -liftedSmallestFactor;
529 fmpq_init(eta); fmpq_set_si(eta,3,4);
530 fmpz_mat_transpose(FLINTM,FLINTM);
531 fmpz_mat_lll_storjohann(FLINTM,
delta,eta);
532 fmpz_mat_transpose(FLINTM,FLINTM);
535 fmpz_mat_clear(FLINTM);
536 #elif defined(HAVE_NTL)
541 transpose (*NTLM, *NTLM);
542 (void) LLL (det, *NTLM, 1L, 1L);
543 transpose (*NTLM, *NTLM);
552 for (
int j= 1;
j <=
s;
j++)
557 if (mipoFactors.
getFirst().factor().inCoeffDomain())
561 fmpz_poly_clear (
v[0]);
562 fmpz_poly_clear (
v[1]);
563 fmpz_poly_clear (
w[0]);
564 fmpz_poly_clear (
w[1]);
568 fmpz_poly_factor_clear (liftedFactors);
571 if (mipoFactors.
length() > 1 ||
572 (mipoFactors.
length() == 1 && mipoFactors.
getFirst().exp() > 1) ||
576 goto differentevalpoint;
585 goto differentevalpoint;
600 if (mipoFactors.
getFirst().factor().inCoeffDomain())
607 if (wrongMipo == mipoFactors.
length())
610 goto differentevalpoint;
615 if (mipoFactors.
getFirst().factor().inCoeffDomain())
622 if (wrongMipo == mipoFactors.
length())
625 goto differentevalpoint;
631 if (mipoFactors.
getFirst().factor().inCoeffDomain())
638 if (wrongMipo == mipoFactors.
length())
641 goto differentevalpoint;
646 if (mipoFactors.
getFirst().factor().inCoeffDomain())
653 if (wrongMipo == mipoFactors.
length())
656 goto differentevalpoint;
662 if (
degree (F,1) > minTdeg)
678 if (QaF1Factors.
getFirst().factor().inCoeffDomain())
686 if (wrongMipo == QaF1Factors.
length())
690 goto differentevalpoint;
702 int liftBound=
degree (F,
y) + 1;
717 fmpz_t FLINTf,FLINTD;
720 fmpz_poly_t FLINTmipo;
721 fmpz_poly_t FLINTLcf;
726 fmpz_poly_resultant(FLINTf,FLINTmipo,FLINTLcf);
727 fmpz_poly_discriminant(FLINTD,FLINTmipo);
728 fmpz_mul(FLINTf,FLINTD,FLINTf);
733 fmpz_poly_clear(FLINTLcf);
734 fmpz_poly_clear(FLINTmipo);
735 #elif defined(HAVE_NTL)
739 ZZ NTLD= discriminant (NTLmipo);
760 #elif defined(HAVE_NTL)
770 if (bb.
getk() >
b.getk() )
b=bb;
772 if (bb.
getk() >
b.getk() )
b=bb;
777 bool earlySuccess=
false;
780 (F, earlySuccess, earlyFactors, degs, liftBound,
783 DEBOUTLN (cerr,
"lifted factors= " << uniFactors);
799 biFactors=
Union (earlyFactors, biFactors);
800 else if (!earlySuccess && degs.
getLength() == 1)
801 biFactors= earlyFactors;
833 goto differentevalpoint;
void convertFacCFMatrix2Fmpz_mat_t(fmpz_mat_t M, const CFMatrix &m)
conversion of a factory matrix over Z to a fmpz_mat_t
CFMatrix * convertFmpz_mat_t2FacCFMatrix(const fmpz_mat_t m)
conversion of a FLINT matrix over Z to a factory matrix
CanonicalForm convertFmpz2CF(const fmpz_t coefficient)
conversion of a FLINT integer to CanonicalForm
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
CanonicalForm convertZZ2CF(const ZZ &a)
NAME: convertZZ2CF.
ZZX convertFacCF2NTLZZX(const CanonicalForm &f)
CanonicalForm convertNTLZZX2CF(const ZZX &polynom, const Variable &x)
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
mat_ZZ * convertFacCFMatrix2NTLmat_ZZ(const CFMatrix &m)
CFMatrix * convertNTLmat_ZZ2FacCFMatrix(const mat_ZZ &m)
CanonicalForm normalize(const CanonicalForm &F)
normalize a poly, i.e. in char 0 clear denominators, remove integer content in char p divide by leadi...
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 )
CanonicalForm abs(const CanonicalForm &f)
inline CanonicalForm abs ( const CanonicalForm & f )
CFFList FACTORY_PUBLIC factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
CanonicalForm FACTORY_PUBLIC 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)
VAR void(* factoryError)(const char *s)
DegreePattern provides a functionality to create, intersect and refine degree patterns.
int getLength() const
getter
ExtensionInfo contains information about extension.
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
#define DEBOUTLN(stream, objects)
int choosePoint(const CanonicalForm &F, int tdegF, CFArray &eval, bool rec, int absValue)
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
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...
convertFacCF2nmod_poly_t(FLINTmipo, M)
nmod_poly_clear(FLINTmipo)
Variable FACTORY_PUBLIC 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 > &)
bool delta(X x, Y y, D d)