facAlgFunc.cc File Reference

This file provides functions to factorize polynomials over alg. More...

#include "config.h"
#include "cf_assert.h"
#include "debug.h"
#include "cf_generator.h"
#include "cf_iter.h"
#include "cf_util.h"
#include "cf_algorithm.h"
#include "templates/ftmpl_functions.h"
#include "cf_map.h"
#include "cfModResultant.h"
#include "cfCharSets.h"
#include "facAlgFunc.h"
#include "facAlgFuncUtil.h"

Go to the source code of this file.

Functions
void	out_cf (const char *s1, const CanonicalForm &f, const char *s2)
	cf_algorithm.cc - simple mathematical algorithms. More...
CanonicalForm	alg_content (const CanonicalForm &f, const CFList &as)
CanonicalForm	alg_gcd (const CanonicalForm &fff, const CanonicalForm &ggg, const CFList &as)
static CanonicalForm	resultante (const CanonicalForm &f, const CanonicalForm &g, const Variable &v)
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 addition getCharacteristic() > 0 the squarefree factors of R are returned. Based on Trager's sqrf_norm algorithm. More...
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. More...
static CFList	simpleExtension (CFList &backSubst, const CFList &Astar, const Variable &Extension, bool &isFunctionField, CanonicalForm &R)
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. More...
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 More...
CFFList	SteelTrager (const CanonicalForm &f, const CFList &AS)
	algorithm of A. Steel described in "Conquering Inseparability: Primary decomposition and multivariate factorization over algebraic function fields of positive characteristic" with the following modifications: we use characteristic sets in IdealOverSubfield and Trager's primitive element algorithm instead of FGLM More...
CFFList	facAlgFunc2 (const CanonicalForm &f, const CFList &as)
	factorize a polynomial that is irreducible over the ground field modulo an extension given by an irreducible characteristic set More...
CFFList	facAlgFunc (const CanonicalForm &f, const CFList &as)
	factorize a polynomial modulo an extension given by an irreducible characteristic set More...

Detailed Description

This file provides functions to factorize polynomials over alg.

function fields

Note

some of the code is code from libfac or derived from code from libfac. Libfac is written by M. Messollen. See also COPYING for license information and README for general information on characteristic sets.

ABSTRACT: Descriptions can be found in B. Trager "Algebraic Factoring and Rational Function Integration" and A. Steel "Conquering Inseparability: Primary decomposition and multivariate factorization over algebraic function fields of positive characteristic"

Author

Martin Lee

Definition in file facAlgFunc.cc.

Function Documentation

CanonicalForm alg_content	(	const CanonicalForm &	f,
		const CFList &	as
	)

Definition at line 42 of file facAlgFunc.cc.

{
  if (!f.inCoeffDomain())
  {
    CFIterator i= f;
    CanonicalForm result= abs (i.coeff());
    i++;
    while (i.hasTerms() && !result.isOne())
    {
      result= alg_gcd (i.coeff(), result, as);
      i++;
    }
    return result;
  }

  return abs (f);
}

CanonicalForm alg_gcd	(	const CanonicalForm &	fff,
		const CanonicalForm &	ggg,
		const CFList &	as
	)

Definition at line 61 of file facAlgFunc.cc.

{
  if (fff.inCoeffDomain() || ggg.inCoeffDomain())
    return 1;
  CanonicalForm f=fff;
  CanonicalForm g=ggg;
  f=Prem(f,as);
  g=Prem(g,as);
  if ( f.isZero() )
  {
    if ( g.lc().sign() < 0 ) return -g;
    else                     return g;
  }
  else  if ( g.isZero() )
  {
    if ( f.lc().sign() < 0 ) return -f;
    else                     return f;
  }

  int v= as.getLast().level();
  if (f.level() <= v || g.level() <= v)
    return 1;

  CanonicalForm res;

  // does as appear in f and g ?
  bool has_alg_var=false;
  for ( CFListIterator j=as;j.hasItem(); j++ )
  {
    Variable v=j.getItem().mvar();
    if (hasVar (f, v))
      has_alg_var=true;
    if (hasVar (g, v))
      has_alg_var=true;
  }
  if (!has_alg_var)
  {
    /*if ((hasAlgVar(f))
    || (hasAlgVar(g)))
    {
      Varlist ord;
      for ( CFListIterator j=as;j.hasItem(); j++ )
        ord.append(j.getItem().mvar());
      res=algcd(f,g,as,ord);
    }
    else*/
    if (!hasAlgVar (f) && !hasAlgVar (g))
      return res=gcd(f,g);
  }

  int mvf=f.level();
  int mvg=g.level();
  if (mvg > mvf)
  {
    CanonicalForm tmp=f; f=g; g=tmp;
    int tmp2=mvf; mvf=mvg; mvg=tmp2;
  }
  if (g.inBaseDomain() || f.inBaseDomain())
    return CanonicalForm(1);

  CanonicalForm c_f= alg_content (f, as);

  if (mvf != mvg)
  {
    res= alg_gcd (g, c_f, as);
    return res;
  }
  Variable x= f.mvar();

  // now: mvf==mvg, f.level()==g.level()
  CanonicalForm c_g= alg_content (g, as);

  int delta= degree (f) - degree (g);

  f= divide (f, c_f, as);
  g= divide (g, c_g, as);

  // gcd of contents
  CanonicalForm c_gcd= alg_gcd (c_f, c_g, as);
  CanonicalForm tmp;

  if (delta < 0)
  {
    tmp= f;
    f= g;
    g= tmp;
    delta= -delta;
  }

  CanonicalForm r= 1;

  while (degree (g, x) > 0)
  {
    r= Prem (f, g);
    r= Prem (r, as);
    if (!r.isZero())
    {
      r= divide (r, alg_content (r,as), as);
      r /= vcontent (r,Variable (v+1));
    }
    f= g;
    g= r;
  }

  if (degree (g, x) == 0)
    return c_gcd;

  c_f= alg_content (f, as);

  f= divide (f, c_f, as);

  f *= c_gcd;
  f /= vcontent (f, Variable (v+1));

  return f;
}

CFFList facAlgFunc	(	const CanonicalForm &	f,
		const CFList &	as
	)

factorize a polynomial modulo an extension given by an irreducible characteristic set

factorize a polynomial f modulo an extension given by an irreducible characteristic set as, f is assumed to be integral, i.e. , and each element of as is assumed to be integral as well. must be either or .

Parameters

[in]	f	univariate poly
[in]	as	irreducible characteristic set

Definition at line 1040 of file facAlgFunc.cc.

{
  bool isRat= isOn (SW_RATIONAL);
  if (!isRat && getCharacteristic() == 0)
    On (SW_RATIONAL);
  CFFList Output, output, Factors= factorize(f);
  if (Factors.getFirst().factor().inCoeffDomain())
    Factors.removeFirst();

  if (as.length() == 0)
  {
    if (!isRat && getCharacteristic() == 0)
      Off (SW_RATIONAL);
    return Factors;
  }
  if (f.level() <= as.getLast().level())
  {
    if (!isRat && getCharacteristic() == 0)
      Off (SW_RATIONAL);
    return Factors;
  }

  for (CFFListIterator i=Factors; i.hasItem(); i++)
  {
    if (i.getItem().factor().level() > as.getLast().level())
    {
      output= facAlgFunc2 (i.getItem().factor(), as);
      for (CFFListIterator j= output; j.hasItem(); j++)
        Output= append (Output, CFFactor (j.getItem().factor(),
                                          j.getItem().exp()*i.getItem().exp()));
    }
  }

  if (!isRat && getCharacteristic() == 0)
    Off (SW_RATIONAL);
  return Output;
}

CFFList facAlgFunc2	(	const CanonicalForm &	f,
		const CFList &	as
	)

factorize a polynomial that is irreducible over the ground field modulo an extension given by an irreducible characteristic set

factorize a polynomial f that is irreducible over the ground field modulo an extension given by an irreducible characteristic set as, f is assumed to be integral, i.e. , and each element of as is assumed to be integral as well. must be either or .

Parameters

[in]	f	univariate poly
[in]	as	irreducible characteristic set

Definition at line 902 of file facAlgFunc.cc.

{
  bool isRat= isOn (SW_RATIONAL);
  if (!isRat && getCharacteristic() == 0)
    On (SW_RATIONAL);
  Variable vf=f.mvar();
  CFListIterator i;
  CFFListIterator jj;
  CFList reduceresult;
  CFFList result;

// F1: [Test trivial cases]
// 1) first trivial cases:
  if (vf.level() <= as.getLast().level())
  {
    if (!isRat && getCharacteristic() == 0)
      Off (SW_RATIONAL);
    return CFFList(CFFactor(f,1));
  }

// 2) Setup list of those polys in AS having degree > 1
  CFList Astar;
  Variable x;
  CanonicalForm elem;
  Varlist ord, uord;
  for (int ii= 1; ii < level (vf); ii++)
    uord.append (Variable (ii));

  for (i= as; i.hasItem(); i++)
  {
    elem= i.getItem();
    x= elem.mvar();
    if (degree (elem, x) > 1)  // otherwise it's not an extension
    {
      Astar.append (elem);
      ord.append (x);
    }
  }
  uord= Difference (uord, ord);

// 3) second trivial cases: we already proved irr. of f over no extensions
  if (Astar.length() == 0)
  {
    if (!isRat && getCharacteristic() == 0)
      Off (SW_RATIONAL);
    return CFFList (CFFactor (f, 1));
  }

// 4) Look if elements in uord actually occur in any of the minimal
//    polynomials. If no element of uord occures in any of the minimal
//    polynomials the field is an alg. number field not an alg. function field
  Varlist newuord= varsInAs (uord, Astar);

  CFFList Factorlist;
  Varlist gcdord= Union (ord, newuord);
  gcdord.append (f.mvar());
  bool isFunctionField= (newuord.length() > 0);

  // TODO alg_sqrfree?
  CanonicalForm Fgcd= 0;
  if (isFunctionField)
    Fgcd= alg_gcd (f, f.deriv(), Astar);

  bool derivZero= f.deriv().isZero();
  if (isFunctionField && (degree (Fgcd, f.mvar()) > 0) && !derivZero)
  {
    CanonicalForm Ggcd= divide(f, Fgcd,Astar);
    if (getCharacteristic() == 0)
    {
      CFFList result= facAlgFunc2 (Ggcd, as); //Ggcd is the squarefree part of f
      multiplicity (result, f, Astar);
      if (!isRat && getCharacteristic() == 0)
        Off (SW_RATIONAL);
      return result;
    }

    Fgcd= pp (Fgcd);
    Ggcd= pp (Ggcd);
    if (!isRat && getCharacteristic() == 0)
      Off (SW_RATIONAL);
    return merge (facAlgFunc2 (Fgcd, as), facAlgFunc2 (Ggcd, as));
  }

  if (getCharacteristic() > 0)
  {
    IntList degreelist;
    Variable vminpoly;
    for (i= Astar; i.hasItem(); i++)
      degreelist.append (degree (i.getItem()));

    int extdeg= getDegOfExt (degreelist, degree (f));

    if (newuord.length() == 0) // no parameters
    {
      if (extdeg > 1)
      {
        CanonicalForm MIPO= generateMipo (extdeg);
        vminpoly= rootOf(MIPO);
      }
      Factorlist= Trager(f, Astar, vminpoly, as, isFunctionField);
      if (extdeg > 1)
        prune (vminpoly);
      return Factorlist;
    }
    else if (isInseparable(Astar) || derivZero) // inseparable case
    {
      Factorlist= SteelTrager (f, Astar);
      return Factorlist;
    }
    else // separable case
    {
      if (extdeg > 1)
      {
        CanonicalForm MIPO=generateMipo (extdeg);
        vminpoly= rootOf (MIPO);
      }
      Factorlist= Trager (f, Astar, vminpoly, as, isFunctionField);
      if (extdeg > 1)
        prune (vminpoly);
      return Factorlist;
    }
  }
  else // char 0
  {
    Variable vminpoly;
    Factorlist= Trager (f, Astar, vminpoly, as, isFunctionField);
    if (!isRat && getCharacteristic() == 0)
      Off (SW_RATIONAL);
    return Factorlist;
  }

  return CFFList (CFFactor(f,1));
}

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

Definition at line 606 of file facAlgFunc.cc.

{
  CanonicalForm varsG;
  int j, exp= 0, tmpExp;
  bool recurse= false;
  CFList asnew, as= AS;
  CFListIterator i= as, ii;
  CFFList varsGMapLevel, tmp;
  CFFListIterator iter;
  CFFList * varsGMap= new CFFList [as.length()];
  for (j= 0; j < as.length(); j++)
    varsGMap[j]= CFFList();
  j= 0;
  while (i.hasItem())
  {
    if (i.getItem().deriv() == 0)
    {
      deflateDegree (i.getItem(), exp, i.getItem().level());
      i.getItem()= deflatePoly (i.getItem(), exp, i.getItem().level());

      varsG= getVars (i.getItem());
      varsG /= i.getItem().mvar();

      lcmVars= lcm (varsG, lcmVars);

      while (!varsG.isOne())
      {
        if (i.getItem().deriv (varsG.level()).isZero())
        {
          deflateDegree (i.getItem(), tmpExp, varsG.level());
          if (exp >= tmpExp)
          {
            if (exp == tmpExp)
              i.getItem()= deflatePoly (i.getItem(), exp, varsG.level());
            else
            {
              if (j != 0)
                recurse= true;
              i.getItem()= deflatePoly (i.getItem(), tmpExp, varsG.level());
            }
            varsGMapLevel.insert (CFFactor (varsG.mvar(), exp - tmpExp));
          }
          else
          {
            i.getItem()= deflatePoly (i.getItem(), exp, varsG.level());
            varsGMapLevel.insert (CFFactor (varsG.mvar(), 0));
          }
        }
        else
        {
          if (j != 0)
            recurse= true;
          varsGMapLevel.insert (CFFactor (varsG.mvar(),exp));
        }
        varsG /= varsG.mvar();
      }

      if (recurse)
      {
        ii= as;
        for (; ii.hasItem(); ii++)
        {
          if (ii.getItem() == i.getItem())
            continue;
          for (iter= varsGMapLevel; iter.hasItem(); iter++)
            ii.getItem()= inflatePoly (ii.getItem(), iter.getItem().exp(),
                                       iter.getItem().factor().level());
        }
      }
      else
      {
        ii= i;
        ii++;
        for (; ii.hasItem(); ii++)
        {
          for (iter= varsGMapLevel; iter.hasItem(); iter++)
          {
            ii.getItem()= inflatePoly (ii.getItem(), iter.getItem().exp(),
                                       iter.getItem().factor().level());
          }
        }
      }
      if (varsGMap[j].isEmpty())
        varsGMap[j]= varsGMapLevel;
      else
      {
        if (!varsGMapLevel.isEmpty())
        {
          tmp= varsGMap[j];
          CFFListIterator iter2= varsGMapLevel;
          ASSERT (tmp.length() == varsGMapLevel.length(),
                  "wrong length of lists");
          for (iter=tmp; iter.hasItem(); iter++, iter2++)
            iter.getItem()= CFFactor (iter.getItem().factor(),
                                  iter.getItem().exp() + iter2.getItem().exp());
          varsGMap[j]= tmp;
        }
      }
      varsGMapLevel= CFFList();
    }
    asnew.append (i.getItem());
    if (!recurse)
    {
      i++;
      j++;
    }
    else
    {
      i= as;
      j= 0;
      recurse= false;
      asnew= CFList();
    }
  }

  while (!lcmVars.isOne())
  {
    varsMapLevel.insert (CFFactor (lcmVars.mvar(), 0));
    lcmVars /= lcmVars.mvar();
  }

  for (j= 0; j < as.length(); j++)
  {
    if (varsGMap[j].isEmpty())
      continue;

    for (CFFListIterator iter2= varsGMap[j]; iter2.hasItem(); iter2++)
    {
      for (iter= varsMapLevel; iter.hasItem(); iter++)
      {
        if (iter.getItem().factor() == iter2.getItem().factor())
        {
          iter.getItem()= CFFactor (iter.getItem().factor(),
                                  iter.getItem().exp() + iter2.getItem().exp());
        }
      }
    }
  }

  delete [] varsGMap;

  return asnew;
}

static CFFList norm ( const CanonicalForm &  f, const CanonicalForm &  PPalpha, CFGenerator &  myrandom, CanonicalForm &  s, CanonicalForm &  g, CanonicalForm &  R, bool  proof  )

static

compute the norm R of f over PPalpha, g= f (x-s*alpha) if proof==true, R is squarefree and if in addition getCharacteristic() > 0 the squarefree factors of R are returned. Based on Trager's sqrf_norm algorithm.

Definition at line 206 of file facAlgFunc.cc.

{
  Variable y= PPalpha.mvar(), vf= f.mvar();
  CanonicalForm temp, Palpha= PPalpha, t;
  int sqfreetest= 0;
  CFFList testlist;
  CFFListIterator i;

  if (proof)
  {
    myrandom.reset();
    s= myrandom.item();
    g= f;
    R= CanonicalForm(0);
  }
  else
  {
    if (getCharacteristic() == 0)
      t= CanonicalForm (mapinto (myrandom.item()));
    else
      t= CanonicalForm (myrandom.item());
    s= t;
    g= f (vf - t*Palpha.mvar(), vf);
  }

  // Norm, resultante taken with respect to y
  while (!sqfreetest)
  {
    R= resultante (Palpha, g, y);
    R= R* bCommonDen(R);
    R /= content (R);
    if (proof)
    {
      // sqfree check ; R is a polynomial in K[x]
      if (getCharacteristic() == 0)
      {
        temp= gcd (R, R.deriv (vf));
        if (degree(temp,vf) != 0 || temp == temp.genZero())
          sqfreetest= 0;
        else
          sqfreetest= 1;
      }
      else
      {
        Variable X;
        testlist= sqrFree (R);

        if (testlist.getFirst().factor().inCoeffDomain())
          testlist.removeFirst();
        sqfreetest= 1;
        for (i= testlist; i.hasItem(); i++)
        {
          if (i.getItem().exp() > 1 && degree (i.getItem().factor(),R.mvar()) > 0)
          {
            sqfreetest= 0;
            break;
          }
        }
      }
      if (!sqfreetest)
      {
        myrandom.next();
        if (getCharacteristic() == 0)
          t= CanonicalForm (mapinto (myrandom.item()));
        else
          t= CanonicalForm (myrandom.item());
        s= t;
        g= f (vf - t*Palpha.mvar(), vf);
      }
    }
    else
      break;
  }
  return testlist;
}

void out_cf	(	const char *	s1,
		const CanonicalForm &	f,
		const char *	s2
	)

cf_algorithm.cc - simple mathematical algorithms.

Hierarchy: mathematical algorithms on canonical forms

Developers note:

A "mathematical" algorithm is an algorithm which calculates some mathematical function in contrast to a "structural" algorithm which gives structural information on polynomials.

Compare these functions to the functions in `cf_ops.cc', which are structural algorithms.

Definition at line 90 of file cf_factor.cc.

{
  printf("%s",s1);
  if (f.isZero()) printf("+0");
  //else if (! f.inCoeffDomain() )
  else if (! f.inBaseDomain() )
  {
    int l = f.level();
    for ( CFIterator i = f; i.hasTerms(); i++ )
    {
      int e=i.exp();
      if (i.coeff().isOne())
      {
        printf("+");
        if (e==0) printf("1");
        else
        {
          printf("v(%d)",l);
          if (e!=1) printf("^%d",e);
        }
      }
      else
      {
        out_cf("+(",i.coeff(),")");
        if (e!=0)
        {
          printf("*v(%d)",l);
          if (e!=1) printf("^%d",e);
        }
      }
    }
  }
  else
  {
    if ( f.isImm() )
    {
      if (CFFactory::gettype()==GaloisFieldDomain)
      {
         long a= imm2int (f.getval());
         if ( a == gf_q )
           printf ("+%ld", a);
         else  if ( a == 0L )
           printf ("+1");
         else  if ( a == 1L )
           printf ("+%c",gf_name);
         else
         {
           printf ("+%c",gf_name);
           printf ("^%ld",a);
         }
      }
      else
        printf("+%ld",f.intval());
    }
    else
    {
    #ifdef NOSTREAMIO
      if (f.inZ())
      {
        mpz_t m;
        gmp_numerator(f,m);
        char * str = new char[mpz_sizeinbase( m, 10 ) + 2];
        str = mpz_get_str( str, 10, m );
        printf("%s",str);
        delete[] str;
        mpz_clear(m);
      }
      else if (f.inQ())
      {
        mpz_t m;
        gmp_numerator(f,m);
        char * str = new char[mpz_sizeinbase( m, 10 ) + 2];
        str = mpz_get_str( str, 10, m );
        printf("%s/",str);
        delete[] str;
        mpz_clear(m);
        gmp_denominator(f,m);
        str = new char[mpz_sizeinbase( m, 10 ) + 2];
        str = mpz_get_str( str, 10, m );
        printf("%s",str);
        delete[] str;
        mpz_clear(m);
      }
    #else
       std::cout << f;
    #endif
    }
    //if (f.inZ()) printf("(Z)");
    //else if (f.inQ()) printf("(Q)");
    //else if (f.inFF()) printf("(FF)");
    //else if (f.inPP()) printf("(PP)");
    //else if (f.inGF()) printf("(PP)");
    //else
    if (f.inExtension()) printf("E(%d)",f.level());
  }
  printf("%s",s2);
}

static CanonicalForm resultante ( const CanonicalForm &  f, const CanonicalForm &  g, const Variable &  v  )

static

Definition at line 179 of file facAlgFunc.cc.

{
  bool on_rational = isOn(SW_RATIONAL);
  if (!on_rational && getCharacteristic() == 0)
    On(SW_RATIONAL);
  CanonicalForm cd = bCommonDen( f );
  CanonicalForm fz = f * cd;
  cd = bCommonDen( g );
  CanonicalForm gz = g * cd;
  if (!on_rational && getCharacteristic() == 0)
    Off(SW_RATIONAL);
  CanonicalForm result;
#ifdef HAVE_NTL
  if (getCharacteristic() == 0)
    result= resultantZ (fz, gz,v);
  else
#endif
    result= resultant (fz,gz,v);

  return result;
}

static CFList simpleExtension ( CFList &  backSubst, const CFList &  Astar, const Variable &  Extension, bool &  isFunctionField, CanonicalForm &  R  )

static

Definition at line 313 of file facAlgFunc.cc.

{
  CFList Returnlist, Bstar= Astar;
  CanonicalForm s, g, ra, rb, oldR, h, denra, denrb= 1;
  Variable alpha;
  CFList tmp;

  bool isRat= isOn (SW_RATIONAL);

  CFListIterator j;
  if (Astar.length() == 1)
  {
    R= Astar.getFirst();
    rb= R.mvar();
  }
  else
  {
    R=Bstar.getFirst();
    Bstar.removeFirst();
    for (CFListIterator i= Bstar; i.hasItem(); i++)
    {
      j= i;
      j++;
      if (getCharacteristic() == 0)
        Off (SW_RATIONAL);
      R /= icontent (R);
      if (getCharacteristic() == 0)
        On (SW_RATIONAL);
      oldR= R;
      //TODO normalize i.getItem over K(R)?
      (void) sqrfNorm (i.getItem(), R, Extension, s, g, R);

      backSubst.insert (s);

      if (getCharacteristic() == 0)
        Off (SW_RATIONAL);
      R /= icontent (R);

      if (getCharacteristic() == 0)
        On (SW_RATIONAL);

      if (!isFunctionField)
      {
        alpha= rootOf (R);
        h= replacevar (g, g.mvar(), alpha);
        if (getCharacteristic() == 0)
          On (SW_RATIONAL); //needed for GCD
        h= gcd (h, oldR);
        h /= Lc (h);
        ra= -h[0];
        ra= replacevar(ra, alpha, g.mvar());
        rb= R.mvar()-s*ra;
        for (; j.hasItem(); j++)
        {
          j.getItem()= j.getItem() (rb, i.getItem().mvar());
          j.getItem()= j.getItem() (ra, oldR.mvar());
        }
        prune (alpha);
      }
      else
      {
        if (getCharacteristic() == 0)
          On (SW_RATIONAL);
        Variable v= Variable (tmax (g.level(), oldR.level()) + 1);
        h= swapvar (g, oldR.mvar(), v);
        tmp= CFList (R);
        h= alg_gcd (h, swapvar (oldR, oldR.mvar(), v), tmp);

        CanonicalForm numinv, deninv;
        numinv= QuasiInverse (tmp.getFirst(), LC (h), tmp.getFirst().mvar());
        h *= numinv;
        h= Prem (h, tmp);
        deninv= LC(h);

        ra= -h[0];
        denra= gcd (ra, deninv);
        ra /= denra;
        denra= deninv/denra;
        rb= R.mvar()*denra-s*ra;
        denrb= denra;
        for (; j.hasItem(); j++)
        {
          CanonicalForm powdenra= power (denra, degree (j.getItem(),
                                         i.getItem().mvar()));
          j.getItem()= evaluate (j.getItem(), rb, denrb, powdenra,
                                 i.getItem().mvar());
          powdenra= power (denra, degree (j.getItem(), oldR.mvar()));
          j.getItem()= evaluate (j.getItem(),ra, denra, powdenra, oldR.mvar());

        }
      }

      Returnlist.append (ra);
      if (isFunctionField)
        Returnlist.append (denra);
    }
  }
  Returnlist.append (rb);
  if (isFunctionField)
    Returnlist.append (denrb);

  if (isRat && getCharacteristic() == 0)
    On (SW_RATIONAL);
  else if (!isRat && getCharacteristic() == 0)
    Off (SW_RATIONAL);

  return Returnlist;
}

static CFFList sqrfNorm ( const CanonicalForm &  f, const CanonicalForm &  PPalpha, const Variable &  Extension, CanonicalForm &  s, CanonicalForm &  g, CanonicalForm &  R  )

static

see norm, R is guaranteed to be squarefree Based on Trager's sqrf_norm algorithm.

Definition at line 287 of file facAlgFunc.cc.

{
  CFFList result;
  if (getCharacteristic() == 0)
  {
    IntGenerator myrandom;
    result= norm (f, PPalpha, myrandom, s, g, R, true);
  }
  else if (degree (Extension) > 0)
  {
    AlgExtGenerator myrandom (Extension);
    result= norm (f, PPalpha, myrandom, s, g, R, true);
  }
  else
  {
    FFGenerator myrandom;
    result= norm (f, PPalpha, myrandom, s, g, R, true);
  }
  return result;
}

CFFList SteelTrager	(	const CanonicalForm &	f,
		const CFList &	AS
	)

algorithm of A. Steel described in "Conquering Inseparability: Primary decomposition and multivariate factorization over algebraic function fields of positive characteristic" with the following modifications: we use characteristic sets in IdealOverSubfield and Trager's primitive element algorithm instead of FGLM

Definition at line 756 of file facAlgFunc.cc.

{
  CanonicalForm F= f, lcmVars= 1;
  CFList asnew, as= AS;
  CFListIterator i, ii;

  bool derivZeroF= false;
  int j, expF= 0, tmpExp;
  CFFList varsMapLevel, tmp;
  CFFListIterator iter;

  // check if F is separable
  if (F.deriv().isZero())
  {
    derivZeroF= true;
    deflateDegree (F, expF, F.level());
  }

  CanonicalForm varsF= getVars (F);
  varsF /= F.mvar();

  lcmVars= lcm (varsF, lcmVars);

  if (derivZeroF)
    as.append (F);

  asnew= mapIntoPIE (varsMapLevel, lcmVars, as);

  if (derivZeroF)
  {
    asnew.removeLast();
    F= deflatePoly (F, expF, F.level());
  }

  // map variables in F
  for (iter= varsMapLevel; iter.hasItem(); iter++)
  {
    if (expF > 0)
      tmpExp= iter.getItem().exp() - expF;
    else
      tmpExp= iter.getItem().exp();

    if (tmpExp > 0)
      F= inflatePoly (F, tmpExp, iter.getItem().factor().level());
    else if (tmpExp < 0)
      F= deflatePoly (F, -tmpExp, iter.getItem().factor().level());
  }

  // factor F with minimal polys given in asnew
  asnew.append (F);
  asnew= charSetViaModCharSet (asnew, false);

  F= asnew.getLast();
  F /= content (F);

  asnew.removeLast();
  for (i= asnew; i.hasItem(); i++)
    i.getItem() /= content (i.getItem());

  tmp= facAlgFunc (F, asnew);

  // transform back
  j= 0;
  int p= getCharacteristic();
  CFList transBack;
  CFMap M;
  CanonicalForm g;

  for (iter= varsMapLevel; iter.hasItem(); iter++)
  {
    if (iter.getItem().exp() > 0)
    {
      j++;
      g= power (Variable (f.level() + j), ipower (p, iter.getItem().exp())) -
         iter.getItem().factor().mvar();
      transBack.append (g);
      M.newpair (iter.getItem().factor().mvar(), Variable (f.level() + j));
    }
  }

  for (i= asnew; i.hasItem(); i++)
    transBack.insert (M (i.getItem()));

  if (expF > 0)
    tmpExp= ipower (p, expF);

  CFFList result;
  CFList transform;

  bool found;
  for (iter= tmp; iter.hasItem(); iter++)
  {
    found= false;
    transform= transBack;
    CanonicalForm factor= iter.getItem().factor();
    factor= M (factor);
    transform.append (factor);
    transform= modCharSet (transform, false);

retry:
    if (transform.isEmpty())
    {
      transform= transBack;
      transform.append (factor);
      transform= charSetViaCharSetN (transform);
    }
    for (i= transform; i.hasItem(); i++)
    {
      if (degree (i.getItem(), f.mvar()) > 0)
      {
        if (i.getItem().level() > f.level())
          break;
        found= true;
        factor= i.getItem();
        break;
      }
    }

    if (!found)
    {
      found= false;
      transform= CFList();
      goto retry;
    }

    factor /= content (factor);

    if (expF > 0)
    {
      int mult= tmpExp/(degree (factor)/degree (iter.getItem().factor()));
      result.append (CFFactor (factor, iter.getItem().exp()*mult));
    }
    else
      result.append (CFFactor (factor, iter.getItem().exp()));
  }

  return result;
}

static CFFList Trager ( const CanonicalForm &  F, const CFList &  Astar, const Variable &  vminpoly, const CFList &  as, bool  isFunctionField  )

static

Trager's algorithm, i.e. convert to one field extension and factorize over this field extension.

Definition at line 427 of file facAlgFunc.cc.

{
  bool isRat= isOn (SW_RATIONAL);
  CFFList L, normFactors, tmp;
  CFFListIterator iter, iter2;
  CanonicalForm R, Rstar, s, g, h, f= F;
  CFList substlist, backSubsts;

  substlist= simpleExtension (backSubsts, Astar, vminpoly, isFunctionField,
                              Rstar);

  f= subst (f, Astar, substlist, Rstar, isFunctionField);

  Variable alpha;
  if (!isFunctionField)
  {
    alpha= rootOf (Rstar);
    g= replacevar (f, Rstar.mvar(), alpha);

    if (!isRat && getCharacteristic() == 0)
      On (SW_RATIONAL);
    tmp= factorize (g, alpha); // factorization over number field

    for (iter= tmp; iter.hasItem(); iter++)
    {
      h= iter.getItem().factor();
      if (!h.inCoeffDomain())
      {
        h= replacevar (h, alpha, Rstar.mvar());
        h *= bCommonDen(h);
        h= backSubst (h, backSubsts, Astar);
        h= Prem (h, as);
        L.append (CFFactor (h, iter.getItem().exp()));
      }
    }
    if (!isRat && getCharacteristic() == 0)
      Off (SW_RATIONAL);
    prune (alpha);
    return L;
  }
  // after here we are over an extension of a function field

  // make quasi monic
  CFList Rstarlist= CFList (Rstar);
  int algExtLevel= Astar.getLast().level(); //highest level of algebraic variables
  CanonicalForm numinv;
  if (!isRat && getCharacteristic() == 0)
    On (SW_RATIONAL);
  numinv= QuasiInverse (Rstar, alg_LC (f, algExtLevel), Rstar.mvar());

  f *= numinv;
  f= Prem (f, Rstarlist);
  f /= vcontent (f, Rstar.mvar());
  // end quasi monic

  if (degree (f) == 1)
  {
    f= backSubst (f, backSubsts, Astar);
    f *= bCommonDen (f);
    f= Prem (f, as);
    f /= vcontent (f, as.getFirst().mvar());

    return CFFList (CFFactor (f, 1));
  }

  CFGenerator * Gen;
  if (getCharacteristic() == 0)
    Gen= CFGenFactory::generate();
  else if (degree (vminpoly) > 0)
    Gen= AlgExtGenerator (vminpoly).clone();
  else
    Gen= CFGenFactory::generate();

  CFFList LL= CFFList (CFFactor (f, 1));

  Variable X;
  do
  {
    tmp= CFFList();
    for (iter= LL; iter.hasItem(); iter++)
    {
      f= iter.getItem().factor();
      (void) norm (f, Rstar, *Gen, s, g, R, false);

      if (hasFirstAlgVar (R, X))
        normFactors= factorize (R, X);
      else
        normFactors= factorize (R);

      if (normFactors.getFirst().factor().inCoeffDomain())
        normFactors.removeFirst();
      if (normFactors.length() < 1 || (normFactors.length() == 1 && normFactors.getLast().exp() == 1))
      {
        f= backSubst (f, backSubsts, Astar);
        f *= bCommonDen (f);
        f= Prem (f, as);
        f /= vcontent (f, as.getFirst().mvar());

        L.append (CFFactor (f, 1));
      }
      else
      {
        g= f;
        int count= 0;
        for (iter2= normFactors; iter2.hasItem(); iter2++)
        {
          CanonicalForm fnew= iter2.getItem().factor();
          if (fnew.level() <= Rstar.level()) //factor is a constant from the function field
            continue;
          else
          {
            fnew= fnew (g.mvar() + s*Rstar.mvar(), g.mvar());
            fnew= Prem (fnew, CFList (Rstar));
          }

          h= alg_gcd (g, fnew, Rstarlist);
          numinv= QuasiInverse (Rstar, alg_LC (h, algExtLevel), Rstar.mvar());
          h *= numinv;
          h= Prem (h, Rstarlist);
          h /= vcontent (h, Rstar.mvar());

          if (h.level() > Rstar.level())
          {
            g= divide (g, h, Rstarlist);
            if (degree (h) == 1 || iter2.getItem().exp() == 1)
            {
              h= backSubst (h, backSubsts, Astar);
              h= Prem (h, as);
              h *= bCommonDen (h);
              h /= vcontent (h, as.getFirst().mvar());
              L.append (CFFactor (h, 1));
            }
            else
              tmp.append (CFFactor (h, iter2.getItem().exp()));
          }
          count++;
          if (g.level() <= Rstar.level())
            break;
          if (count == normFactors.length() - 1)
          {
            if (normFactors.getLast().exp() == 1 && g.level() > Rstar.level())
            {
              g= backSubst (g, backSubsts, Astar);
              g= Prem (g, as);
              g *= bCommonDen (g);
              g /= vcontent (g, as.getFirst().mvar());
              L.append (CFFactor (g, 1));
            }
            else if (normFactors.getLast().exp() > 1 &&
                     g.level() > Rstar.level())
            {
              g /= vcontent (g, Rstar.mvar());
              tmp.append (CFFactor (g, normFactors.getLast().exp()));
            }
            break;
          }
        }
      }
    }
    LL= tmp;
    (*Gen).next();
  }
  while (!LL.isEmpty());

  if (!isRat && getCharacteristic() == 0)
    Off (SW_RATIONAL);

  delete Gen;

  return L;
}