facAlgFuncUtil.cc File Reference

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

#include "config.h"
#include "cf_assert.h"
#include "canonicalform.h"
#include "facAlgFuncUtil.h"
#include "cfCharSetsUtil.h"
#include "cf_random.h"
#include "cf_irred.h"
#include "cf_algorithm.h"
#include "cf_util.h"
#include "cf_iter.h"

Go to the source code of this file.

Functions
CFFList	append (const CFFList &Inputlist, const CFFactor &TheFactor)
CFFList	merge (const CFFList &Inputlist1, const CFFList &Inputlist2)
Varlist	varsInAs (const Varlist &uord, const CFList &Astar)
CanonicalForm	generateMipo (int degOfExt)
CanonicalForm	alg_lc (const CanonicalForm &f)
CanonicalForm	alg_LC (const CanonicalForm &f, int lev)
CanonicalForm	subst (const CanonicalForm &f, const CFList &a, const CFList &b, const CanonicalForm &Rstar, bool isFunctionField)
CanonicalForm	backSubst (const CanonicalForm &F, const CFList &a, const CFList &b)
void	deflateDegree (const CanonicalForm &F, int &pExp, int n)
CanonicalForm	deflatePoly (const CanonicalForm &F, int exp)
CanonicalForm	deflatePoly (const CanonicalForm &F, int exps, int n)
CanonicalForm	inflatePoly (const CanonicalForm &F, int exp)
CanonicalForm	inflatePoly (const CanonicalForm &F, int exps, int n)
void	multiplicity (CFFList &factors, const CanonicalForm &F, const CFList &as)
int	hasAlgVar (const CanonicalForm &f, const Variable &v)
int	hasVar (const CanonicalForm &f, const Variable &v)
int	hasAlgVar (const CanonicalForm &f)
void	psqr (const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &q, CanonicalForm &r, CanonicalForm &multiplier, const Variable &x)
	pseudo division of f and g wrt. x s.t. multiplier*f=q*g+r More...
CanonicalForm	Sprem (const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &m, CanonicalForm &q)
CanonicalForm	divide (const CanonicalForm &ff, const CanonicalForm &f, const CFList &as)
bool	isInseparable (const CFList &Astar)
int	getDegOfExt (IntList &degreelist, int n)
CanonicalForm	QuasiInverse (const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
CanonicalForm	evaluate (const CanonicalForm &f, const CanonicalForm &g, const CanonicalForm &h, const CanonicalForm &powH)
CanonicalForm	evaluate (const CanonicalForm &f, const CanonicalForm &g, const CanonicalForm &h, const CanonicalForm &powH, const Variable &v)
	evaluate f at g/h at v such that powH*f is integral i.e. powH is assumed to be h^degree(f,v) More...

Detailed Description

This file provides utility 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.

Author

Martin Lee

Definition in file facAlgFuncUtil.cc.

Function Documentation

CanonicalForm alg_lc

(

const CanonicalForm &

f

)

Definition at line 100 of file facAlgFuncUtil.cc.

{
  if (f.level()>0)
  {
    return alg_lc(f.LC());
  }

  return f;
}

CanonicalForm alg_LC	(	const CanonicalForm &	f,
		int	lev
	)

Definition at line 110 of file facAlgFuncUtil.cc.

{
  CanonicalForm result= f;
  while (result.level() > lev)
    result= LC (result);
  return result;
}

CFFList append	(	const CFFList &	Inputlist,
		const CFFactor &	TheFactor
	)

Definition at line 32 of file facAlgFuncUtil.cc.

{
  CFFList Outputlist;
  CFFactor copy;
  CFFListIterator i;
  int exp=0;

  for (i= Inputlist; i.hasItem() ; i++)
  {
    copy= i.getItem();
    if (copy.factor() == TheFactor.factor())
      exp += copy.exp();
    else
      Outputlist.append(copy);
  }
  Outputlist.append (CFFactor (TheFactor.factor(), exp + TheFactor.exp()));
  return Outputlist;
}

CanonicalForm backSubst	(	const CanonicalForm &	F,
		const CFList &	a,
		const CFList &	b
	)

Definition at line 192 of file facAlgFuncUtil.cc.

{
  ASSERT (a.length() == b.length() - 1, "wrong length of lists in backSubst");
  CanonicalForm result= F;
  Variable tmp;
  CFList tmp2= b;
  tmp= tmp2.getLast().mvar();
  tmp2.removeLast();
  for (CFListIterator iter= a; iter.hasItem(); iter++)
  {
    result= result (tmp+iter.getItem()*tmp2.getLast().mvar(), tmp);
    tmp= tmp2.getLast().mvar();
    tmp2.removeLast();
  }
  return result;
}

void deflateDegree	(	const CanonicalForm &	F,
		int &	pExp,
		int	n
	)

Definition at line 209 of file facAlgFuncUtil.cc.

{
  if (n == 0 || n > F.level())
  {
    pExp= -1;
    return;
  }
  if (F.level() == n)
  {
    ASSERT (F.deriv().isZero(), "derivative of F is not zero");
    int termCount=0;
    CFIterator i= F;
    for (; i.hasTerms(); i++)
    {
      if (i.exp() != 0)
        termCount++;
    }

    int j= 1;
    i= F;
    for (;j < termCount; j++, i++)
      ;

    int exp= i.exp();
    int count= 0;
    int p= getCharacteristic();
    while ((exp >= p) && (exp != 0) && (exp % p == 0))
    {
      exp /= p;
      count++;
    }
    pExp= count;
  }
  else
  {
    CFIterator i= F;
    deflateDegree (i.coeff(), pExp, n);
    i++;
    int tmp= pExp;
    for (; i.hasTerms(); i++)
    {
      deflateDegree (i.coeff(), pExp, n);
      if (tmp == -1)
        tmp= pExp;
      else if (tmp != -1 && pExp != -1)
        pExp= (pExp < tmp) ? pExp : tmp;
      else
        pExp= tmp;
    }
  }
}

CanonicalForm deflatePoly	(	const CanonicalForm &	F,
		int	exp
	)

Definition at line 261 of file facAlgFuncUtil.cc.

{
  if (exp == 0)
    return F;
  int p= getCharacteristic();
  int pToExp= ipower (p, exp);
  Variable x=F.mvar();
  CanonicalForm result= 0;
  for (CFIterator i= F; i.hasTerms(); i++)
    result += i.coeff()*power (x, i.exp()/pToExp);
  return result;
}

CanonicalForm deflatePoly	(	const CanonicalForm &	F,
		int	exps,
		int	n
	)

Definition at line 274 of file facAlgFuncUtil.cc.

{
  if (n == 0 || exps <= 0 || F.level() < n)
    return F;
  if (F.level() == n)
    return deflatePoly (F, exps);
  else
  {
    CanonicalForm result= 0;
    for (CFIterator i= F; i.hasTerms(); i++)
      result += deflatePoly (i.coeff(), exps, n)*power(F.mvar(), i.exp());
    return result;
  }
}

CanonicalForm divide	(	const CanonicalForm &	ff,
		const CanonicalForm &	f,
		const CFList &	as
	)

Definition at line 523 of file facAlgFuncUtil.cc.

{
  CanonicalForm r, m, q;

  if (f.inCoeffDomain())
  {
    bool isRat= isOn(SW_RATIONAL);
    if (getCharacteristic() == 0)
      On(SW_RATIONAL);
    q= ff/f;
    if (!isRat && getCharacteristic() == 0)
      Off(SW_RATIONAL);
  }
  else
    r= Sprem (ff, f, m, q);

  r= Prem (q, as);
  return r;
}

CanonicalForm evaluate	(	const CanonicalForm &	f,
		const CanonicalForm &	g,
		const CanonicalForm &	h,
		const CanonicalForm &	powH
	)

Definition at line 663 of file facAlgFuncUtil.cc.

{
  if (f.inCoeffDomain())
    return f;
  CFIterator i= f;
  int lastExp = i.exp();
  CanonicalForm result = i.coeff()*powH;
  i++;
  while (i.hasTerms())
  {
    int i_exp= i.exp();
    if ((lastExp - i_exp) == 1)
    {
      result *= g;
      result /= h;
    }
    else
    {
      result *= power (g, lastExp - i_exp);
      result /= power (h, lastExp - i_exp);
    }
    result += i.coeff()*powH;
    lastExp = i_exp;
    i++;
  }
  if (lastExp != 0)
  {
    result *= power (g, lastExp);
    result /= power (h, lastExp);
  }
  return result;
}

CanonicalForm evaluate	(	const CanonicalForm &	f,
		const CanonicalForm &	g,
		const CanonicalForm &	h,
		const CanonicalForm &	powH,
		const Variable &	v
	)

evaluate f at g/h at v such that powH*f is integral i.e. powH is assumed to be h^degree(f,v)

Definition at line 700 of file facAlgFuncUtil.cc.

{
  if (f.inCoeffDomain())
  {
    return f*powH;
  }

  Variable x = f.mvar();
  if ( v > x )
    return f*powH;
  else  if ( v == x )
    return evaluate (f, g, h, powH);

  // v is less than main variable of f
  CanonicalForm result= 0;
  for (CFIterator i= f; i.hasTerms(); i++)
    result += evaluate (i.coeff(), g, h, powH, v)*power (x, i.exp());
  return result;
}

CanonicalForm generateMipo

(

int

degOfExt

)

Definition at line 90 of file facAlgFuncUtil.cc.

{
#ifndef HAVE_NTL
  FFRandom gen;
  return find_irreducible (degOfExt, gen, Variable (1));
#else
  return randomIrredpoly (degOfExt, Variable (1));
#endif
}

int getDegOfExt	(	IntList &	degreelist,
		int	n
	)

Definition at line 566 of file facAlgFuncUtil.cc.

{
  int charac= getCharacteristic();
  setCharacteristic(0); // need it for k !
  int k= 1, m= 1, length= degreelist.length();
  IntListIterator i;

  for (i= degreelist; i.hasItem(); i++)
     m= m*i.getItem();
  int q= charac;
  while (q <= ((n*m)*(n*m)/2))
  {
    k= k+1;
    q= q*charac;
  }
  int l= 0;
  do
  {
    for (i= degreelist; i.hasItem(); i++)
    {
      l= l + 1;
      if (igcd (k, i.getItem()) == 1)
      {
        if (l == length)
        {
          setCharacteristic (charac);
          return k;
        }
      }
      else
        break;
    }
    k= k + 1;
    l= 0;
  }
  while (1);
}

int hasAlgVar	(	const CanonicalForm &	f,
		const Variable &	v
	)

Definition at line 345 of file facAlgFuncUtil.cc.

{
  if (f.inBaseDomain())
    return 0;
  if (f.inCoeffDomain())
  {
    if (f.mvar() == v)
      return 1;
    return hasAlgVar (f.LC(), v);
  }
  if (f.inPolyDomain())
  {
    if (hasAlgVar(f.LC(), v))
      return 1;
    for (CFIterator i= f; i.hasTerms(); i++)
    {
      if (hasAlgVar (i.coeff(), v))
        return 1;
    }
  }
  return 0;
}

int hasAlgVar

(

const CanonicalForm &

f

)

Definition at line 393 of file facAlgFuncUtil.cc.

{
  if (f.inBaseDomain())
    return 0;
  if (f.inCoeffDomain())
  {
    if (f.level() != 0)
      return 1;
    return hasAlgVar(f.LC());
  }
  if (f.inPolyDomain())
  {
    if (hasAlgVar(f.LC()))
      return 1;
    for (CFIterator i= f; i.hasTerms(); i++)
    {
      if (hasAlgVar (i.coeff()))
        return 1;
    }
  }
  return 0;
}

int hasVar	(	const CanonicalForm &	f,
		const Variable &	v
	)

Definition at line 368 of file facAlgFuncUtil.cc.

{
  if (f.inBaseDomain())
    return 0;
  if (f.inCoeffDomain())
  {
    if (f.mvar() == v)
      return 1;
    return hasAlgVar (f.LC(), v);
  }
  if (f.inPolyDomain())
  {
    if (f.mvar() == v)
      return 1;
    if (hasVar (f.LC(), v))
      return 1;
    for (CFIterator i= f; i.hasTerms(); i++)
    {
      if (hasVar (i.coeff(), v))
        return 1;
    }
  }
  return 0;
}

CanonicalForm inflatePoly	(	const CanonicalForm &	F,
		int	exp
	)

Definition at line 289 of file facAlgFuncUtil.cc.

{
  if (exp == 0)
    return F;
  int p= getCharacteristic();
  int pToExp= ipower (p, exp);
  Variable x=F.mvar();
  CanonicalForm result= 0;
  for (CFIterator i= F; i.hasTerms(); i++)
    result += i.coeff()*power (x, i.exp()*pToExp);
  return result;
}

CanonicalForm inflatePoly	(	const CanonicalForm &	F,
		int	exps,
		int	n
	)

Definition at line 302 of file facAlgFuncUtil.cc.

{
  if (n == 0 || exps <= 0 || F.level() < n)
    return F;
  if (F.level() == n)
    return inflatePoly (F, exps);
  else
  {
    CanonicalForm result= 0;
    for (CFIterator i= F; i.hasTerms(); i++)
      result += inflatePoly (i.coeff(), exps, n)*power(F.mvar(), i.exp());
    return result;
  }
}

bool isInseparable

(

const CFList &

Astar

)

Definition at line 545 of file facAlgFuncUtil.cc.

{
  CanonicalForm elem;

  if (Astar.length() == 0)
    return false;
  for (CFListIterator i= Astar; i.hasItem(); i++)
  {
    elem= i.getItem();
    if (elem.deriv().isZero())
      return true;
  }
  return false;
}

CFFList merge	(	const CFFList &	Inputlist1,
		const CFFList &	Inputlist2
	)

Definition at line 52 of file facAlgFuncUtil.cc.

{
  CFFList Outputlist;
  CFFListIterator i;

  for (i= Inputlist1; i.hasItem(); i++)
    Outputlist= append (Outputlist, i.getItem());
  for (i= Inputlist2; i.hasItem() ; i++)
    Outputlist= append (Outputlist, i.getItem());

  return Outputlist;
}

void multiplicity	(	CFFList &	factors,
		const CanonicalForm &	F,
		const CFList &	as
	)

Definition at line 318 of file facAlgFuncUtil.cc.

{
  CanonicalForm G= F;
  Variable x= F.mvar();
  CanonicalForm q, r;
  int count= -1;
  for (CFFListIterator iter=factors; iter.hasItem(); iter++)
  {
    count= -1;
    if (iter.getItem().factor().inCoeffDomain())
      continue;
    while (1)
    {
      psqr (G, iter.getItem().factor(), q, r, x);

      q= Prem (q, as);
      r= Prem (r, as);
      if (!r.isZero())
        break;
      count++;
      G= q;
    }
    iter.getItem()= CFFactor (iter.getItem().factor(),
                              iter.getItem().exp() + count);
  }
}

void psqr	(	const CanonicalForm &	f,
		const CanonicalForm &	g,
		CanonicalForm &	q,
		CanonicalForm &	r,
		CanonicalForm &	multiplier,
		const Variable &	x
	)

pseudo division of f and g wrt. x s.t. multiplier*f=q*g+r

Definition at line 418 of file facAlgFuncUtil.cc.

{
    ASSERT( x.level() > 0, "type error: polynomial variable expected" );
    ASSERT( ! g.isZero(), "math error: division by zero" );

    // swap variables such that x's level is larger or equal
    // than both f's and g's levels.
    Variable X;
    if (f.level() > g.level())
      X= f.mvar();
    else
      X= g.mvar();
    if (X.level() < x.level())
      X= x;
    CanonicalForm F= swapvar (f, x, X);
    CanonicalForm G= swapvar (g, x, X);

    // now, we have to calculate the pseudo remainder of F and G
    // w.r.t. X
    int fDegree= degree (F, X);
    int gDegree= degree (G, X);
    if (fDegree < 0 || fDegree < gDegree)
    {
      q= 0;
      r= f;
    }
    else
    {
      CanonicalForm LCG= LC (G, X);
      multiplier= power (LCG, fDegree - gDegree + 1);
      divrem (multiplier*F, G, q, r);
      q= swapvar (q, x, X);
      r= swapvar (r, x, X);
    }
}

CanonicalForm QuasiInverse	(	const CanonicalForm &	f,
		const CanonicalForm &	g,
		const Variable &	x
	)

Definition at line 605 of file facAlgFuncUtil.cc.

{
  CanonicalForm pi, pi1, q, t0, t1, Hi, bi, pi2;
  bool isRat= isOn (SW_RATIONAL);
  pi= f;
  pi1= g;
  if (isRat)
  {
    pi *= bCommonDen (pi);
    pi1 *= bCommonDen (pi1);
  }
  CanonicalForm m,tmp;
  if (isRat && getCharacteristic() == 0)
    Off (SW_RATIONAL);

  pi= pi/content (pi,x);
  pi1= pi1/content (pi1,x);

  t0= 0;
  t1= 1;
  bi= 1;

  int delta= degree (f, x) - degree (g, x);
  Hi= power (LC (pi1, x), delta);
  if ( (delta+1) % 2 )
      bi = 1;
  else
      bi = -1;

  while (degree (pi1,x) > 0)
  {
    psqr (pi, pi1, q, pi2, m, x);
    pi2 /= bi;

    tmp= t1;
    t1= t0*m - t1*q;
    t0= tmp;
    t1 /= bi;
    pi= pi1;
    pi1= pi2;
    if (degree (pi1, x) > 0)
    {
      delta= degree (pi, x) - degree (pi1, x);
      if ((delta + 1) % 2)
        bi= LC (pi, x)*power (Hi, delta);
      else
        bi= -LC (pi, x)*power (Hi, delta);
      Hi= power (LC (pi1, x), delta)/power (Hi, delta - 1);
    }
  }
  t1 /= gcd (pi1, t1);
  if (isRat && getCharacteristic() == 0)
    On (SW_RATIONAL);
  return t1;
}

CanonicalForm Sprem	(	const CanonicalForm &	f,
		const CanonicalForm &	g,
		CanonicalForm &	m,
		CanonicalForm &	q
	)

Definition at line 456 of file facAlgFuncUtil.cc.

{
  CanonicalForm ff, gg, l, test, retvalue;
  int df, dg,n;
  bool reord;
  Variable vf, vg, v;

  if ((vf = f.mvar()) < (vg = g.mvar()))
  {
    m= 0;
    q= 0;
    return f;
  }
  else
  {
    if ( vf == vg )
    {
      ff= f;
      gg= g;
      reord= false;
      v= vg; // == x
    }
    else
    {
      v= Variable (f.level() + 1);
      ff= swapvar (f, vg, v); // == r
      gg= swapvar (g, vg, v); // == v
      reord=true;
    }
    dg= degree (gg, v); // == dv
    df= degree (ff, v); // == dr
    if (dg <= df)
    {
      l= LC (gg);
      gg= gg - LC(gg)*power(v,dg);
    }
    else
      l = 1;
    n= 0;
    while ((dg <= df) && (!ff.isZero()))
    {
      test= gg*LC (ff)*power (v, df - dg);
      if (df == 0)
        ff= 0;
      else
        ff= ff - LC(ff)*power(v,df);
      ff= l*ff - test;
      df= degree (ff, v);
      n++;
    }

    if (reord)
      retvalue= swapvar (ff, vg, v);
    else
      retvalue= ff;

    m= power (l, n);
    if (fdivides (g, m*f - retvalue))
      q= (m*f - retvalue)/g;
    else
      q= 0;
    return retvalue;
  }
}

CanonicalForm subst	(	const CanonicalForm &	f,
		const CFList &	a,
		const CFList &	b,
		const CanonicalForm &	Rstar,
		bool	isFunctionField
	)

Definition at line 120 of file facAlgFuncUtil.cc.

{
  if (isFunctionField)
    ASSERT (2*a.length() == b.length(), "wrong length of lists");
  else
    ASSERT (a.length() == b.length(), "lists of equal length expected");
  CFListIterator j= b;
  CanonicalForm result= f, tmp, powj;
  CFListIterator i= a;
  int length= a.length();
  int count= 0;
  for (; i.hasItem() && j.hasItem(); i++, j++, count++)
  {
    if (length - count == 2)
    {
      if (!isFunctionField)
      {
        result= result (b.getLast(), a.getLast().mvar());
        result= result (j.getItem(), i.getItem().mvar());
        break;
      }
      else
      {
        tmp= b.getLast();
        j++;
        j++;
        powj= power (tmp, degree (result, a.getLast().mvar()));
        result= evaluate (result, j.getItem(), tmp, powj, a.getLast().mvar());

        if (fdivides (powj, result, tmp))
          result= tmp;

        result /= vcontent (result, Variable (a.getLast().level() + 1));
        j--;
        j--;
        tmp= j.getItem();
        j++;
        powj= power (j.getItem(), degree (result, i.getItem().mvar()));
        result= evaluate (result, tmp, j.getItem(), powj, i.getItem().mvar());

        if (fdivides (powj, result, tmp))
          result= tmp;

        result /= vcontent (result, Variable (i.getItem().level() + 1));
        break;
      }
    }
    else
    {
      if (!isFunctionField)
        result= result (j.getItem(), i.getItem().mvar());
      else
      {
        tmp= j.getItem();
        j++;
        powj= power (j.getItem(), degree (result, i.getItem().mvar()));
        result= evaluate (result, tmp, j.getItem(), powj, i.getItem().mvar());

        if (fdivides (powj, result, tmp))
          result= tmp;

        result /= vcontent (result, Variable (i.getItem().level() + 1));
      }
    }
  }
  result= Prem (result, CFList (Rstar));
  result /= vcontent (result, Variable (Rstar.level() + 1));
  return result;
}

Varlist varsInAs	(	const Varlist &	uord,
		const CFList &	Astar
	)

Definition at line 66 of file facAlgFuncUtil.cc.

{
  Varlist output;
  CanonicalForm elem;
  Variable x;

  for (VarlistIterator i= uord; i.hasItem(); i++)
  {
    x= i.getItem();
    for (CFListIterator j= Astar; j.hasItem(); j++ )
    {
      elem= j.getItem();
      if (degree (elem, x) > 0) // x actually occures in Astar
      {
        output.append (x);
        break;
      }
    }
  }
  return output;
}