49 while (i.hasTerms() && !result.
isOne())
71 if ( g.
lc().
sign() < 0 )
return -g;
76 if ( f.
lc().
sign() < 0 )
return -f;
87 bool has_alg_var=
false;
230 g=
f (vf - t*Palpha.
mvar(), vf);
255 if (testlist.
getFirst().factor().inCoeffDomain())
258 for (i= testlist; i.
hasItem(); i++)
275 g=
f (vf - t*Palpha.
mvar(), vf);
295 result=
norm (f, PPalpha, myrandom, s, g, R,
true);
297 else if (
degree (Extension) > 0)
300 result=
norm (f, PPalpha, myrandom, s, g, R,
true);
305 result=
norm (f, PPalpha, myrandom, s, g, R,
true);
314 const Variable & Extension,
bool& isFunctionField,
317 CFList Returnlist, Bstar= Astar;
331 Returnlist.
append (denrb);
359 if (!isFunctionField)
393 denra=
gcd (ra, deninv);
396 rb= R.
mvar()*denra-s*ra;
401 i.getItem().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)
454 for (iter= tmp; iter.
hasItem(); iter++)
482 f=
Prem (f, Rstarlist);
499 else if (
degree (vminpoly) > 0)
510 for (iter= LL; iter.
hasItem(); iter++)
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++)
546 h=
alg_gcd (g, fnew, Rstarlist);
549 h=
Prem (h, Rstarlist);
552 if (h.level() > Rstar.
level())
554 g=
divide (g, h, Rstarlist);
569 if (count == normFactors.
length() - 1)
579 else if (normFactors.
getLast().exp() > 1 &&
612 int j,
exp= 0, tmpExp;
619 for (j= 0; j < as.
length(); j++)
632 lcmVars=
lcm (varsG, lcmVars);
634 while (!varsG.isOne())
663 varsG /= varsG.mvar();
669 for (; ii.hasItem(); ii++)
671 if (ii.getItem() == i.
getItem())
673 for (iter= varsGMapLevel; iter.
hasItem(); iter++)
675 iter.
getItem().factor().level());
682 for (; ii.hasItem(); ii++)
684 for (iter= varsGMapLevel; iter.
hasItem(); iter++)
687 iter.
getItem().factor().level());
691 if (varsGMap[j].isEmpty())
692 varsGMap[j]= varsGMapLevel;
700 "wrong length of lists");
701 for (iter=tmp; iter.
hasItem(); iter++, iter2++)
724 while (!lcmVars.
isOne())
727 lcmVars /= lcmVars.
mvar();
730 for (j= 0; j < as.
length(); j++)
732 if (varsGMap[j].isEmpty())
737 for (iter= varsMapLevel; iter.
hasItem(); iter++)
739 if (iter.
getItem().factor() == iter2.getItem().factor())
742 iter.
getItem().exp() + iter2.getItem().exp());
765 bool derivZeroF=
false;
766 int j, expF= 0, tmpExp;
780 lcmVars=
lcm (varsF, lcmVars);
785 asnew=
mapIntoPIE (varsMapLevel, lcmVars, as);
794 for (iter= varsMapLevel; iter.
hasItem(); iter++)
797 tmpExp= iter.
getItem().exp() - expF;
815 for (i= asnew; i.
hasItem(); i++)
827 for (iter= varsMapLevel; iter.
hasItem(); iter++)
833 iter.
getItem().factor().mvar();
839 for (i= asnew; i.
hasItem(); i++)
849 for (iter= tmp; iter.
hasItem(); iter++)
852 transform= transBack;
855 transform.
append (factor);
861 transform= transBack;
862 transform.
append (factor);
865 for (i= transform; i.
hasItem(); i++)
930 for (
int ii= 1; ii <
level (vf); ii++)
961 bool isFunctionField= (newuord.
length() > 0);
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())
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.
gmp_float exp(const gmp_float &a)
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
CF_NO_INLINE CanonicalForm coeff() const
get the current coefficient
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 newpair(const Variable &v, const CanonicalForm &s)
void CFMap::newpair ( const Variable & v, const CanonicalForm & s )
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...