facFqSquarefree.h File Reference

This file provides functions for squarefrees factorizing over , or GF. More...

#include "cf_assert.h"
#include "cf_factory.h"
#include "fac_sqrfree.h"

Go to the source code of this file.

Functions
CFFList	squarefreeFactorization (const CanonicalForm &F, const Variable &alpha)
	squarefree factorization over a finite field return a list of squarefree factors with multiplicity More...
CFFList	FpSqrf (const CanonicalForm &F, bool sort=true)
	squarefree factorization over . If input is not monic, the leading coefficient is dropped More...
CFFList	FqSqrf (const CanonicalForm &F, const Variable &alpha, bool sort=true)
	squarefree factorization over . If input is not monic, the leading coefficient is dropped More...
CFFList	GFSqrf (const CanonicalForm &F, bool sort=true)
	squarefree factorization over GF. If input is not monic, the leading coefficient is dropped More...
CanonicalForm	sqrfPart (const CanonicalForm &F, CanonicalForm &pthPower, const Variable &alpha)
	squarefree part of F/g, where g is the product of those squarefree factors whose multiplicity is 0 mod p, if F a pth power pthPower= F. More...
CanonicalForm	maxpthRoot (const CanonicalForm &F, int q, int &l)
	p^l-th root extraction, where l is maximal More...

Detailed Description

This file provides functions for squarefrees factorizing over , or GF.

Author

Martin Lee

Definition in file facFqSquarefree.h.

Function Documentation

FpSqrf()

CFFList FpSqrf ( const CanonicalForm &  F, bool  sort = true  )

inline

squarefree factorization over . If input is not monic, the leading coefficient is dropped

Returns

a list of squarefree factors with multiplicity

Parameters

[in]	F	a poly
[in]	sort	sort factors by exponent?

Definition at line 38 of file facFqSquarefree.h.

{
  Variable a= 1;
  int n= F.level();
  CanonicalForm cont, bufF= F;
  CFFList bufResult;
 
  CFFList result;
  for (int i= n; i >= 1; i++)
  {
    cont= content (bufF, i);
    bufResult= squarefreeFactorization (cont, a);
    if (bufResult.getFirst().factor().inCoeffDomain())
      bufResult.removeFirst();
    result= Union (result, bufResult);
    bufF /= cont;
    if (bufF.inCoeffDomain())
      break;
  }
  if (!bufF.inCoeffDomain())
  {
    bufResult= squarefreeFactorization (bufF, a);
    if (bufResult.getFirst().factor().inCoeffDomain())
      bufResult.removeFirst();
    result= Union (result, bufResult);
  }
  if (sort)
    result= sortCFFList (result);
  result.insert (CFFactor (Lc(F), 1));
  return result;
}

FqSqrf()

CFFList FqSqrf ( const CanonicalForm &  F, const Variable &  alpha, bool  sort = true  )

inline

squarefree factorization over . If input is not monic, the leading coefficient is dropped

Returns

a list of squarefree factors with multiplicity

Parameters

[in]	F	a poly
[in]	alpha	algebraic variable
[in]	sort	sort factors by exponent?

Definition at line 77 of file facFqSquarefree.h.

{
  int n= F.level();
  CanonicalForm cont, bufF= F;
  CFFList bufResult;
 
  CFFList result;
  for (int i= n; i >= 1; i++)
  {
    cont= content (bufF, i);
    bufResult= squarefreeFactorization (cont, alpha);
    if (bufResult.getFirst().factor().inCoeffDomain())
      bufResult.removeFirst();
    result= Union (result, bufResult);
    bufF /= cont;
    if (bufF.inCoeffDomain())
      break;
  }
  if (!bufF.inCoeffDomain())
  {
    bufResult= squarefreeFactorization (bufF, alpha);
    if (bufResult.getFirst().factor().inCoeffDomain())
      bufResult.removeFirst();
    result= Union (result, bufResult);
  }
  if (sort)
    result= sortCFFList (result);
  result.insert (CFFactor (Lc(F), 1));
  return result;
}

GFSqrf()

CFFList GFSqrf ( const CanonicalForm &  F, bool  sort = true  )

inline

squarefree factorization over GF. If input is not monic, the leading coefficient is dropped

Returns

a list of squarefree factors with multiplicity

Parameters

[in]	F	a poly
[in]	sort	sort factors by exponent?

Definition at line 116 of file facFqSquarefree.h.

{
  ASSERT (CFFactory::gettype() == GaloisFieldDomain,
          "GF as base field expected");
  return FpSqrf (F, sort);
}

maxpthRoot()

CanonicalForm maxpthRoot	(	const CanonicalForm &	F,
		int	q,
		int &	l
	)

p^l-th root extraction, where l is maximal

Returns

maxpthRoot returns a p^l-th root of F, where l is maximal

See also

pthRoot()

Parameters

[in]	F	a poly which is a pth power
[in]	q	size of the field
[in,out]	l	l maximal, s.t. F is a p^l-th power

Definition at line 127 of file facFqSquarefree.cc.

{
  CanonicalForm result= F;
  bool derivZero= true;
  l= 0;
  while (derivZero)
  {
    for (int i= 1; i <= result.level(); i++)
    {
      if (!deriv (result, Variable (i)).isZero())
      {
        derivZero= false;
        break;
      }
    }
    if (!derivZero)
      break;
    result= pthRoot (result, q);
    l++;
  }
  return result;
}

sqrfPart()

CanonicalForm sqrfPart	(	const CanonicalForm &	F,
		CanonicalForm &	pthPower,
		const Variable &	alpha
	)

squarefree part of F/g, where g is the product of those squarefree factors whose multiplicity is 0 mod p, if F a pth power pthPower= F.

Returns

sqrfPart returns 1, if F is a pthPower, else it returns the squarefree part of F/g, where g is the product of those squarefree factors whose multiplicity is 0 mod p

Parameters

[in]	F	a poly
[in,out]	pthPower	returns F is F is a pthPower
[in]	alpha	algebraic variable

Definition at line 303 of file facFqSquarefree.cc.

{
  if (F.inCoeffDomain())
  {
    pthPower= 1;
    return F;
  }
  CFMap M;
  CanonicalForm A= compress (F, M);
  Variable vBuf= alpha;
  CanonicalForm w, v, b;
  pthPower= 1;
  CanonicalForm result;
  int i= 1;
  bool allZero= true;
  for (; i <= A.level(); i++)
  {
    if (!deriv (A, Variable (i)).isZero())
    {
      allZero= false;
      break;
    }
  }
  if (allZero)
  {
    pthPower= F;
    return 1;
  }
  w= gcd (A, deriv (A, Variable (i)));
 
  b= A/w;
  result= b;
  if (degree (w) < 1)
    return M (result);
  i++;
  for (; i <= A.level(); i++)
  {
    if (!deriv (w, Variable (i)).isZero())
    {
      b= w;
      w= gcd (w, deriv (w, Variable (i)));
      b /= w;
      if (degree (b) < 1)
        break;
      CanonicalForm g;
      g= gcd (b, result);
      if (degree (g) > 0)
        result *= b/g;
      if (degree (g) <= 0)
        result *= b;
    }
  }
  result= M (result);
  return result;
}

squarefreeFactorization()

CFFList squarefreeFactorization	(	const CanonicalForm &	F,
		const Variable &	alpha
	)

squarefree factorization over a finite field return a list of squarefree factors with multiplicity

Parameters

[in]	F	a poly
[in]	alpha	either an algebraic variable, i.e. we are over some F_p (alpha) or a variable of level 1, i.e. we are F_p or GF

Definition at line 181 of file facFqSquarefree.cc.

{
  int p= getCharacteristic();
  CanonicalForm A= F;
  CFMap M;
  A= compress (A, M);
  Variable x= A.mvar();
  int l= x.level();
  int k;
  if (CFFactory::gettype() == GaloisFieldDomain)
    k= getGFDegree();
  else if (alpha.level() != 1)
    k= degree (getMipo (alpha));
  else
    k= 1;
  Variable buf, buf2;
  CanonicalForm tmp;
 
  CFFList tmp1, tmp2;
  bool found;
  for (int i= l; i > 0; i--)
  {
    buf= Variable (i);
    if (degree (deriv (A, buf)) >= 0)
    {
      tmp1= sqrfPosDer (A, buf, tmp);
      A= tmp;
      for (CFFListIterator j= tmp1; j.hasItem(); j++)
      {
        found= false;
        CFFListIterator k= tmp2;
        if (!k.hasItem() && !j.getItem().factor().inCoeffDomain()) tmp2.append (j.getItem());
        else
        {
          for (; k.hasItem(); k++)
          {
            if (k.getItem().exp() == j.getItem().exp())
            {
              k.getItem()= CFFactor (k.getItem().factor()*j.getItem().factor(),
                                     j.getItem().exp());
              found= true;
            }
          }
          if (found == false && !j.getItem().factor().inCoeffDomain())
            tmp2.append(j.getItem());
        }
      }
    }
  }
 
  bool degcheck= false;;
  for (int i= l; i > 0; i--)
  if (degree (A, Variable(i)) >= p)
    degcheck= true;
 
  if (degcheck == false && tmp1.isEmpty() && tmp2.isEmpty())
    return CFFList (CFFactor (F/Lc(F), 1));
 
  CanonicalForm buffer;
#if defined(HAVE_NTL) || (HAVE_FLINT && __FLINT_RELEASE >= 20400)
  if (alpha.level() == 1)
#endif
    buffer= pthRoot (A, ipower (p, k));
#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
  else
  {
    fmpz_t qq;
    fmpz_init_set_ui (qq, p);
    fmpz_pow_ui (qq, qq, k);
    buffer= pthRoot (A, qq, alpha);
    fmpz_clear (qq);
  }
#elif defined(HAVE_NTL)
  else
  {
    ZZ q;
    power (q, p, k);
    buffer= pthRoot (A, q, alpha);
  }
#else
  factoryError("NTL/FLINT missing: squarefreeFactorization");
#endif
 
  tmp1= squarefreeFactorization (buffer, alpha);
 
  CFFList result;
  buf= alpha;
  for (CFFListIterator i= tmp2; i.hasItem(); i++)
  {
    for (CFFListIterator j= tmp1; j.hasItem(); j++)
    {
      tmp= gcd (i.getItem().factor(), j.getItem().factor());
      i.getItem()= CFFactor (i.getItem().factor()/tmp, i.getItem().exp());
      j.getItem()= CFFactor (j.getItem().factor()/tmp, j.getItem().exp());
      if (!tmp.inCoeffDomain())
      {
        tmp= M (tmp);
        result.append (CFFactor (tmp/Lc(tmp),
                       j.getItem().exp()*p + i.getItem().exp()));
      }
    }
  }
  for (CFFListIterator i= tmp2; i.hasItem(); i++)
  {
    if (!i.getItem().factor().inCoeffDomain())
    {
      tmp= M (i.getItem().factor());
      result.append (CFFactor (tmp/Lc(tmp), i.getItem().exp()));
    }
  }
  for (CFFListIterator j= tmp1; j.hasItem(); j++)
  {
    if (!j.getItem().factor().inCoeffDomain())
    {
      tmp= M (j.getItem().factor());
      result.append (CFFactor (tmp/Lc(tmp), j.getItem().exp()*p));
    }
  }
  return result;
}