51 if (
f.inBaseDomain() )
86 nmod_poly_gcd (
F1,
F1, G1);
99 fmpz_poly_gcd (
F1,
F1, G1);
101 fmpz_poly_clear (
F1);
102 fmpz_poly_clear (G1);
155 for (
i =
f;
i.hasTerms();
i++ )
180 CanonicalForm f,
g, c,
cg,
cl, BB,
B,
M, q, Dp, newD,
D, newq;
197 cl = (
f.lc() /
cg ) *
g.lc();
209 while (
i >= 0 && q <
B )
213 while (
i >= 0 &&
mod(
cl,
p ) == 0 )
232 if ( Dp.
degree() ==
D.degree() )
238 else if ( Dp.
degree() <
D.degree() )
259 DEBOUTLN( cerr,
"another try ..." );
266 if (
f.inCoeffDomain() ||
g.inCoeffDomain())
279 pi =
g; pi1 =
f; delta = -delta;
281 if (
pi.isUnivariate())
324 return gcd_univar_ntlp(
pi, pi1 ) * C;
355 C *=
gcd (oldPi, oldPi1);
367 C *=
gcd (oldPi, oldPi1);
374 powHi=
power (Hi, delta-1);
376 bi =
LC(
pi,
v ) * powHi*Hi;
378 bi = -
LC(
pi,
v ) * powHi*Hi;
379 Hi =
power(
LC( pi1,
v ), delta ) / powHi;
385 C *=
gcd (oldPi, oldPi1);
398 if (!
pi.isUnivariate())
429 pi =
g; pi1 =
f; delta = -delta;
432 pi1 = pi1 / Ci1;
pi =
pi / Ci;
443 return gcd_univar_ntl0(
pi, pi1 ) * C;
495 bool fc_isUnivariate=
f.isUnivariate();
496 bool gc_isUnivariate=
g.isUnivariate();
497 bool fc_and_gc_Univariate=fc_isUnivariate && gc_isUnivariate;
504 #if defined(HAVE_FLINT) && ( __FLINT_RELEASE >= 20503)
512 return gcdFlintMP_Zp(fc,gc);
521 #if defined(HAVE_NTL) || defined(HAVE_FLINT)
536 else if (!fc_and_gc_Univariate)
538 #if defined(HAVE_FLINT) && ( __FLINT_RELEASE >= 20503)
542 return gcdFlintMP_QQ(fc,gc);
551 #if defined(HAVE_NTL) || defined(HAVE_FLINT)
580 if (
f.inPolyDomain() || (
f.inExtension() && !
getReduce(
f.mvar() ) ) )
584 while (
i.hasTerms() && !
result.isOne() )
605 if (
f.inPolyDomain() || (
f.inExtension() && !
getReduce(
f.mvar() ) ) )
610 while (
i.hasTerms() && !
result.isOne() )
631 if (
f.inBaseDomain())
return f;
632 ASSERT(
x.
level() > 0,
"cannot calculate content with respect to algebraic variable" );
655 ASSERT(
x.
level() > 0,
"cannot calculate vcontent with respect to algebraic variable" );
662 for (
i =
f;
i.hasTerms() && ! d.
isOne();
i++ )
688 if (
b ||
g.isZero() )
695 if (
f.inPolyDomain() ||
g.inPolyDomain() )
697 if (
f.mvar() !=
g.mvar() )
699 if (
f.mvar() >
g.mvar() )
747 if (
f.inBaseDomain() &&
g.inBaseDomain() )
765 if (
f.isZero() ||
g.isZero() )
768 return (
f /
gcd(
f,
g ) ) *
g;
CanonicalForm convertnmod_poly_t2FacCF(const nmod_poly_t poly, const Variable &x)
conversion of a FLINT poly over Z/p 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)
ZZX convertFacCF2NTLZZX(const CanonicalForm &f)
CanonicalForm convertNTLzzpX2CF(const zz_pX &poly, const Variable &x)
CanonicalForm convertNTLZZX2CF(const ZZX &polynom, const Variable &x)
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
Conversion to and from NTL.
CanonicalForm EZGCD_P(const CanonicalForm &FF, const CanonicalForm &GG)
Extended Zassenhaus GCD for finite fields. In case things become too dense we switch to a modular alg...
static CanonicalForm ezgcd(const CanonicalForm &FF, const CanonicalForm &GG, REvaluation &b, bool internal)
real implementation of EZGCD over Z
Extended Zassenhaus GCD over finite fields and Z.
CanonicalForm QGCD(const CanonicalForm &F, const CanonicalForm &G)
gcd over Q(a)
bool gcd_test_one(const CanonicalForm &f, const CanonicalForm &g, bool swap, int &d)
Coprimality Check. f and g are assumed to have the same level. If swap is true, the main variables of...
CanonicalForm modGCDFq(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &coF, CanonicalForm &coG, Variable &alpha, CFList &l, bool &topLevel)
GCD of F and G over , l and topLevel are only used internally, output is monic based on Alg....
CanonicalForm modGCDFp(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &coF, CanonicalForm &coG, bool &topLevel, CFList &l)
CanonicalForm modGCDGF(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &coF, CanonicalForm &coG, CFList &l, bool &topLevel)
GCD of F and G over GF, based on Alg. 7.2. as described in "Algorithms for Computer Algebra" by Gedde...
modular and sparse modular GCD algorithms over finite fields and Z.
CanonicalForm modGCDZ(const CanonicalForm &FF, const CanonicalForm &GG)
modular GCD over Z
subresultant pseudo remainder sequence GCD over finite fields and Z
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
CanonicalForm maxNorm(const CanonicalForm &f)
CanonicalForm maxNorm ( const CanonicalForm & f )
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
CanonicalForm psr(const CanonicalForm &rr, const CanonicalForm &vv, const Variable &x)
CanonicalForm psr ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x )
declarations of higher level algorithms.
void FACTORY_PUBLIC chineseRemainder(const CanonicalForm &x1, const CanonicalForm &q1, const CanonicalForm &x2, const CanonicalForm &q2, CanonicalForm &xnew, CanonicalForm &qnew)
void chineseRemainder ( const CanonicalForm & x1, const CanonicalForm & q1, const CanonicalForm & x2,...
#define ASSERT(expression, message)
static const int SW_USE_QGCD
set to 1 to use Encarnacion GCD over Q(a)
static const int SW_USE_CHINREM_GCD
set to 1 to use modular gcd over Z
static const int SW_USE_FL_GCD_P
set to 1 to use Flints gcd over F_p
static const int SW_USE_EZGCD_P
set to 1 to use EZGCD over F_q
static const int SW_RATIONAL
set to 1 for computations over Q
static const int SW_USE_FF_MOD_GCD
set to 1 to use modular GCD over F_q
static const int SW_USE_EZGCD
set to 1 to use EZGCD over Z
static const int SW_USE_FL_GCD_0
set to 1 to use Flints gcd over Q/Z
#define GaloisFieldDomain
static CanonicalForm gcd_poly_0(const CanonicalForm &f, const CanonicalForm &g)
static CanonicalForm cf_content(const CanonicalForm &f, const CanonicalForm &g)
static CanonicalForm cf_content ( const CanonicalForm & f, const CanonicalForm & g )
static CanonicalForm gcd_univar_flintp(const CanonicalForm &F, const CanonicalForm &G)
static CanonicalForm gcd_poly_univar0(const CanonicalForm &F, const CanonicalForm &G, bool primitive)
CanonicalForm content(const CanonicalForm &f)
CanonicalForm content ( const CanonicalForm & f )
static CanonicalForm balance_p(const CanonicalForm &f, const CanonicalForm &q, const CanonicalForm &qh)
CanonicalForm gcd_poly(const CanonicalForm &f, const CanonicalForm &g)
CanonicalForm gcd_poly ( const CanonicalForm & f, const CanonicalForm & g )
bool isPurePoly(const CanonicalForm &)
CanonicalForm vcontent(const CanonicalForm &f, const Variable &x)
CanonicalForm vcontent ( const CanonicalForm & f, const Variable & x )
void out_cf(const char *s1, const CanonicalForm &f, const char *s2)
cf_algorithm.cc - simple mathematical algorithms.
CanonicalForm gcd(const CanonicalForm &f, const CanonicalForm &g)
static CanonicalForm icontent(const CanonicalForm &f, const CanonicalForm &c)
static CanonicalForm icontent ( const CanonicalForm & f, const CanonicalForm & c )
CanonicalForm pp(const CanonicalForm &f)
CanonicalForm pp ( const CanonicalForm & f )
static CanonicalForm gcd_poly_p(const CanonicalForm &f, const CanonicalForm &g)
CanonicalForm lcm(const CanonicalForm &f, const CanonicalForm &g)
CanonicalForm lcm ( const CanonicalForm & f, const CanonicalForm & g )
static CanonicalForm gcd_univar_flint0(const CanonicalForm &F, const CanonicalForm &G)
Iterators for CanonicalForm's.
int cf_getNumSmallPrimes()
int cf_getSmallPrime(int i)
generate random evaluation points
class to iterate through CanonicalForm's
factory's class for variables
functions to print debug output
#define DEBOUTLN(stream, objects)
const CanonicalForm int const CFList const Variable & y
int hasAlgVar(const CanonicalForm &f, const Variable &v)
Utility functions for factorization over algebraic function fields.
const Variable & v
< [in] a sqrfree bivariate poly
convertFacCF2nmod_poly_t(FLINTmipo, M)
nmod_poly_clear(FLINTmipo)
some useful template functions.
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
template CanonicalForm tmin(const CanonicalForm &, const CanonicalForm &)
int F1(int a1, int &r1)
F1.
bool getReduce(const Variable &alpha)