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.
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)
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 > &)
CFFList factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
CF_NO_INLINE CanonicalForm coeff() const
get the current coefficient
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.
virtual CanonicalForm item() const
void prune(Variable &alpha)
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
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...
CFGenerator * clone() const
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 > &)
Variable rootOf(const CanonicalForm &mipo, char name)
returns a symbolic root of polynomial with name name Use it to define algebraic variables ...
CFFList SteelTrager(const CanonicalForm &f, const CFList &AS)
algorithm of A. Steel described in "Conquering Inseparability: Primary decomposition and multivariate...