26#include "flint/nmod_poly_factor.h"
27#include <flint/fmpz_poly_factor.h>
34#if defined(HAVE_NTL) || defined(HAVE_FLINT)
58 if (
iter.getItem().factor().inCoeffDomain())
67 iter.getItem().exp()));
71 iter.getItem().exp()));
118 fmpz_t FLINTD1,FLINTD2;
127 fmpz_poly_discriminant(FLINTD1,FLINTf1);
128 fmpz_poly_discriminant(FLINTD2,FLINTf2);
133 fmpz_poly_clear(FLINTf1);
134 fmpz_poly_clear(FLINTf2);
137 #elif defined(HAVE_NTL)
140 ZZ NTLD1= discriminant (NTLf1);
141 ZZ NTLD2= discriminant (NTLf2);
160 if (
mod (D1,
p) != 0 &&
mod (D2,
p) != 0)
170 else if (!
f.isZero())
182 if (
mod (D1,
p) != 0 &&
mod (D2,
p) != 0)
220 mpz_t *
M=
new mpz_t [4];
226 mpz_t * S=
new mpz_t [2];
250 if (
result.getFirst().factor().inCoeffDomain())
254 iter.getItem().minpoly(),
iter.getItem().exp());
352 smallestFactor=
iter.getItem().factor();
358 smallestFactor=
iter.getItem().factor();
366 if (!
iter.getItem().factor().isUnivariate() &&
369 smallestFactor=
iter.getItem().factor();
373 if (tdegF % minTdeg == 0)
387 !
gcd (Gpx, smallestFactorEvalx).inCoeffDomain());
389 !
gcd (Gpy, smallestFactorEvaly).inCoeffDomain());
390 if (!xValid || !yValid)
394 goto differentevalpoint;
403 for (
int i= 1;
i < 3;
i++)
407 int s= tdegF/minTdeg + 1;
425 nmod_poly_t FLINTFpi, FLINTGpi;
429 smallestFactorEvalx/
lc (smallestFactorEvalx));
435 smallestFactorEvaly/
lc (smallestFactorEvaly));
438 nmod_poly_factor_t nmodFactors;
439 nmod_poly_factor_init (nmodFactors);
440 nmod_poly_factor_insert (nmodFactors, FLINTFpi, 1L);
441 nmod_poly_factor_insert (nmodFactors, FLINTGpi, 1L);
449 fmpz_poly_t *
v=
new fmpz_poly_t[2];
450 fmpz_poly_t *
w=
new fmpz_poly_t[2];
451 fmpz_poly_init(
v[0]);
452 fmpz_poly_init(
v[1]);
453 fmpz_poly_init(
w[0]);
454 fmpz_poly_init(
w[1]);
456 fmpz_poly_factor_t liftedFactors;
457 fmpz_poly_factor_init (liftedFactors);
458 _fmpz_poly_hensel_start_lift (liftedFactors, link,
v,
w, FLINTFi,
461 nmod_poly_factor_clear (nmodFactors);
472#elif defined(HAVE_NTL)
482 zz_pX NTLFpi, NTLGpi;
493 vec_zz_pX modFactors;
494 modFactors.SetLength(2);
495 modFactors[0]= NTLFpi;
496 modFactors[1]= NTLGpi;
497 vec_ZZX liftedFactors;
498 MultiLift (liftedFactors, modFactors, NTLFi, (
long)
k);
510 liftedSmallestFactor= pk (liftedSmallestFactor);
512 liftedSmallestFactor= liftedSmallestFactor (
eval[0],1);
514 liftedSmallestFactor= liftedSmallestFactor (
eval[1],1);
519 for (
int j= 1;
j <
s;
j++)
522 (*M) (
j+1,
j)= -liftedSmallestFactor;
529 fmpq_init(delta); fmpq_set_si(delta,1,1);
530 fmpq_init(eta); fmpq_set_si(eta,3,4);
531 fmpz_mat_transpose(FLINTM,FLINTM);
532 fmpz_mat_lll_storjohann(FLINTM,delta,eta);
533 fmpz_mat_transpose(FLINTM,FLINTM);
536 fmpz_mat_clear(FLINTM);
537 #elif defined(HAVE_NTL)
542 transpose (*NTLM, *NTLM);
543 (void) LLL (det, *NTLM, 1L, 1L);
544 transpose (*NTLM, *NTLM);
553 for (
int j= 1;
j <=
s;
j++)
562 fmpz_poly_clear (
v[0]);
563 fmpz_poly_clear (
v[1]);
564 fmpz_poly_clear (
w[0]);
565 fmpz_poly_clear (
w[1]);
569 fmpz_poly_factor_clear (liftedFactors);
572 if (mipoFactors.
length() > 1 ||
574 mipo.inCoeffDomain())
577 goto differentevalpoint;
586 goto differentevalpoint;
608 if (wrongMipo == mipoFactors.
length())
611 goto differentevalpoint;
623 if (wrongMipo == mipoFactors.
length())
626 goto differentevalpoint;
639 if (wrongMipo == mipoFactors.
length())
642 goto differentevalpoint;
654 if (wrongMipo == mipoFactors.
length())
657 goto differentevalpoint;
663 if (
degree (F,1) > minTdeg)
683 if (
degree (
iter.getItem().factor()) > minTdeg)
687 if (wrongMipo == QaF1Factors.
length())
691 goto differentevalpoint;
703 int liftBound=
degree (F,
y) + 1;
718 fmpz_t FLINTf,FLINTD;
721 fmpz_poly_t FLINTmipo;
722 fmpz_poly_t FLINTLcf;
727 fmpz_poly_resultant(FLINTf,FLINTmipo,FLINTLcf);
728 fmpz_poly_discriminant(FLINTD,FLINTmipo);
729 fmpz_mul(FLINTf,FLINTD,FLINTf);
734 fmpz_poly_clear(FLINTLcf);
735 fmpz_poly_clear(FLINTmipo);
736 #elif defined(HAVE_NTL)
740 ZZ NTLD= discriminant (NTLmipo);
761 #elif defined(HAVE_NTL)
771 if (bb.
getk() >
b.getk() )
b=bb;
773 if (bb.
getk() >
b.getk() )
b=bb;
778 bool earlySuccess=
false;
781 (F, earlySuccess, earlyFactors, degs, liftBound,
784 DEBOUTLN (cerr,
"lifted factors= " << uniFactors);
800 biFactors=
Union (earlyFactors, biFactors);
801 else if (!earlySuccess && degs.
getLength() == 1)
802 biFactors= earlyFactors;
834 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
This file defines functions for conversion to FLINT (www.flintlib.org) and back.
Rational abs(const Rational &a)
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)
Conversion to and from NTL.
bool modularIrredTestWithShift(const CanonicalForm &F)
modular absolute irreducibility test with shift as described in "Modular LasVegas Algorithms for Poly...
bool absIrredTest(const CanonicalForm &F)
absolute irreducibility test as described in "Modular Las Vegas Algorithmsfor Polynomial Absolute Fac...
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 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)
int cf_getNumSmallPrimes()
int cf_getSmallPrime(int i)
generate random evaluation points
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.
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)
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 VegasAlgorithms for Polynomial Abso...
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
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 "Factoringmultivariate 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 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 > &)
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)
int F1(int a1, int &r1)
F1.
#define TIMING_DEFINE_PRINT(t)
#define TIMING_END_AND_PRINT(t, msg)