44 if (!
f.inCoeffDomain())
49 while (
i.hasTerms() && !
result.isOne())
71 if (
g.lc().sign() < 0 )
return -
g;
74 else if (
g.isZero() )
76 if (
f.lc().sign() < 0 )
return -
f;
81 if (
f.level() <=
v ||
g.level() <=
v)
87 bool has_alg_var=
false;
118 if (
g.inBaseDomain() ||
f.inBaseDomain())
230 g=
f (vf - t*Palpha.
mvar(), vf);
244 temp=
gcd (
R,
R.deriv (vf));
255 if (testlist.
getFirst().factor().inCoeffDomain())
258 for (
i= testlist;
i.hasItem();
i++)
260 if (
i.getItem().exp() > 1 &&
degree (
i.getItem().factor(),
R.mvar()) > 0)
275 g=
f (vf - t*Palpha.
mvar(), vf);
297 else if (
degree (Extension) > 0)
314 const Variable & Extension,
bool& isFunctionField,
317 CFList Returnlist, Bstar= Astar;
331 Returnlist.
append (denrb);
359 if (!isFunctionField)
370 for (;
j.hasItem();
j++)
372 j.getItem()=
j.getItem() (rb,
i.getItem().mvar());
373 j.getItem()=
j.getItem() (ra, oldR.
mvar());
393 denra=
gcd (ra, deninv);
396 rb=
R.mvar()*denra-
s*ra;
398 for (;
j.hasItem();
j++)
401 i.getItem().mvar()));
402 j.getItem()=
evaluate (
j.getItem(), rb, denrb, powdenra,
405 j.getItem()=
evaluate (
j.getItem(),ra, denra, powdenra, oldR.
mvar());
412 Returnlist.
append (denra);
415 Returnlist.
append (denrb);
431 const Variable & vminpoly,
const CFList & as,
bool isFunctionField)
437 CFList substlist, backSubsts;
439 substlist=
simpleExtension (backSubsts, Astar, vminpoly, isFunctionField,
442 f=
subst (
f, Astar, substlist, Rstar, isFunctionField);
445 if (!isFunctionField)
457 if (!
h.inCoeffDomain())
475 int algExtLevel= Astar.
getLast().level();
499 else if (
degree (vminpoly) > 0)
513 (void)
norm (
f, Rstar, *Gen,
s,
g,
R,
false);
520 if (normFactors.
getFirst().factor().inCoeffDomain())
522 if (normFactors.
length() < 1 || (normFactors.
length() == 1 && normFactors.
getLast().exp() == 1))
535 for (iter2= normFactors; iter2.
hasItem(); iter2++)
542 fnew= fnew (
g.mvar() +
s*Rstar.
mvar(),
g.mvar());
552 if (
h.level() > Rstar.
level())
567 if (
g.level() <= Rstar.
level())
571 if (normFactors.
getLast().exp() == 1 &&
g.level() > Rstar.
level())
579 else if (normFactors.
getLast().exp() > 1 &&
580 g.level() > Rstar.
level())
612 int j,
exp= 0, tmpExp;
624 if (
i.getItem().deriv() == 0)
630 varsG /=
i.getItem().mvar();
632 lcmVars=
lcm (varsG, lcmVars);
634 while (!varsG.isOne())
636 if (
i.getItem().deriv (varsG.level()).
isZero())
647 i.getItem()=
deflatePoly (
i.getItem(), tmpExp, varsG.level());
663 varsG /= varsG.mvar();
669 for (; ii.hasItem(); ii++)
671 if (ii.getItem() ==
i.getItem())
682 for (; ii.hasItem(); ii++)
691 if (varsGMap[
j].isEmpty())
692 varsGMap[
j]= varsGMapLevel;
700 "wrong length of lists");
724 while (!lcmVars.
isOne())
727 lcmVars /= lcmVars.
mvar();
732 if (varsGMap[
j].isEmpty())
739 if (
iter.
getItem().factor() == iter2.getItem().factor())
765 bool derivZeroF=
false;
766 int j, expF= 0, tmpExp;
780 lcmVars=
lcm (varsF, lcmVars);
785 asnew=
mapIntoPIE (varsMapLevel, lcmVars, as);
815 for (
i= asnew;
i.hasItem();
i++)
839 for (
i= asnew;
i.hasItem();
i++)
852 transform= transBack;
861 transform= transBack;
865 for (
i= transform;
i.hasItem();
i++)
867 if (
degree (
i.getItem(),
f.mvar()) > 0)
869 if (
i.getItem().level() >
f.level())
930 for (
int ii= 1; ii <
level (vf); ii++)
933 for (
i= as;
i.hasItem();
i++)
961 bool isFunctionField= (newuord.
length() > 0);
968 bool derivZero=
f.deriv().isZero();
969 if (isFunctionField && (
degree (Fgcd,
f.mvar()) > 0) && !derivZero)
992 for (
i= Astar;
i.hasItem();
i++)
997 if (newuord.
length() == 0)
1004 Factorlist=
Trager(
f, Astar, vminpoly, as, isFunctionField);
1021 Factorlist=
Trager (
f, Astar, vminpoly, as, isFunctionField);
1030 Factorlist=
Trager (
f, Astar, vminpoly, as, isFunctionField);
1049 if (Factors.
getFirst().factor().inCoeffDomain())
1058 if (
f.level() <= as.
getLast().level())
1067 if (
i.getItem().factor().level() > as.
getLast().level())
1072 j.getItem().exp()*
i.getItem().exp()));
int status int void size_t count
CFFList append(const CFFList &Inputlist, const CFFactor &TheFactor)
const CanonicalForm int s
generate all elements in F_p(alpha) starting from 0
const CanonicalForm int const CFList const Variable & y
int lcm(unsigned long *l, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
int ** merge(int **points1, int sizePoints1, int **points2, int sizePoints2, int &sizeResult)
CFFList facAlgFunc2(const CanonicalForm &f, const CFList &as)
factorize a polynomial that is irreducible over the ground field modulo an extension given by an irre...
CanonicalForm cd(bCommonDen(FF))
Utility functions for factorization over algebraic function fields.
some useful template functions.
functions to print debug output
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
CanonicalForm generateMipo(int degOfExt)
factory's class for variables
virtual class for generators
static CFFList Trager(const CanonicalForm &F, const CFList &Astar, const Variable &vminpoly, const CFList &as, bool isFunctionField)
Trager's algorithm, i.e. convert to one field extension and factorize over this field extension...
generate all elements in F_p starting from 0
int getDegOfExt(IntList °reelist, int n)
static int * multiplicity
CanonicalForm divide(const CanonicalForm &ff, const CanonicalForm &f, const CFList &as)
CFList charSetViaModCharSet(const CFList &PS, StoreFactors &StoredFactors, bool removeContents)
characteristic set via modified medial set
generate integers starting from 0
static CanonicalForm resultante(const CanonicalForm &f, const CanonicalForm &g, const Variable &v)
CanonicalForm deflatePoly(const CanonicalForm &F, int exp)
bool delta(X x, Y y, D d)
Varlist varsInAs(const Varlist &uord, const CFList &Astar)
Rational abs(const Rational &a)
void prune(Variable &alpha)
CanonicalForm subst(const CanonicalForm &f, const CFList &a, const CFList &b, const CanonicalForm &Rstar, bool isFunctionField)
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
Variable rootOf(const CanonicalForm &, char name='@')
returns a symbolic root of polynomial with name name Use it to define algebraic variables ...
CFFList factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
static CFFList sqrfNorm(const CanonicalForm &f, const CanonicalForm &PPalpha, const Variable &Extension, CanonicalForm &s, CanonicalForm &g, CanonicalForm &R)
see norm, R is guaranteed to be squarefree Based on Trager's sqrf_norm algorithm. ...
void deflateDegree(const CanonicalForm &F, int &pExp, int n)
CanonicalForm alg_content(const CanonicalForm &f, const CFList &as)
Factorization over algebraic function fields.
generate integers, elements of finite fields
This file provides functions to compute characteristic sets.
static const int SW_RATIONAL
set to 1 for computations over Q
bool isInseparable(const CFList &Astar)
Iterators for CanonicalForm's.
CFArray evaluate(const CFArray &A, const CFList &evalPoints)
CFList mapIntoPIE(CFFList &varsMapLevel, CanonicalForm &lcmVars, const CFList &AS)
map elements in AS into a PIE and record where the variables are mapped to in varsMapLevel, i.e varsMapLevel contains a list of pairs of variables and integers such that
declarations of higher level algorithms.
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
CanonicalForm resultantZ(const CanonicalForm &A, const CanonicalForm &B, const Variable &x, bool prob)
modular resultant algorihtm over Z
class to iterate through CanonicalForm's
const Variable & v
< [in] a sqrfree bivariate poly
modular resultant algorithm as described by G.
CanonicalForm alg_gcd(const CanonicalForm &fff, const CanonicalForm &ggg, const CFList &as)
void mult(unsigned long *result, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
void out_cf(const char *s1, const CanonicalForm &f, const char *s2)
cf_algorithm.cc - simple mathematical algorithms.
int ipower(int b, int m)
int ipower ( int b, int m )
static CFGenerator * generate()
CFList charSetViaCharSetN(const CFList &PS)
compute a characteristic set via medial set
CFGenerator * clone() const
static CFList simpleExtension(CFList &backSubst, const CFList &Astar, const Variable &Extension, bool &isFunctionField, CanonicalForm &R)
CanonicalForm Prem(const CanonicalForm &F, const CanonicalForm &G)
pseudo remainder of F by G with certain factors of LC (g) cancelled
bool isZero(const CFArray &A)
checks if entries of A are zero
static CFFList norm(const CanonicalForm &f, const CanonicalForm &PPalpha, CFGenerator &myrandom, CanonicalForm &s, CanonicalForm &g, CanonicalForm &R, bool proof)
compute the norm R of f over PPalpha, g= f (x-s*alpha) if proof==true, R is squarefree and if in addi...
CanonicalForm inflatePoly(const CanonicalForm &F, int exp)
CanonicalForm backSubst(const CanonicalForm &F, const CFList &a, const CFList &b)
#define ASSERT(expression, message)
CFList modCharSet(const CFList &L, StoreFactors &StoredFactors, bool removeContents)
modified medial set
CFFList facAlgFunc(const CanonicalForm &f, const CFList &as)
factorize a polynomial modulo an extension given by an irreducible characteristic set ...
int hasAlgVar(const CanonicalForm &f, const Variable &v)
int hasVar(const CanonicalForm &f, const Variable &v)
CanonicalForm QuasiInverse(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
CanonicalForm resultant(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
CanonicalForm resultant ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x ) ...
CFFList sqrFree(const CanonicalForm &f, bool sort=false)
squarefree factorization
CanonicalForm alg_LC(const CanonicalForm &f, int lev)
template List< Variable > Difference(const List< Variable > &, const List< Variable > &)
virtual CanonicalForm item() const
CFFList SteelTrager(const CanonicalForm &f, const CFList &AS)
algorithm of A. Steel described in "Conquering Inseparability: Primary decomposition and multivariate...