facFqSquarefree.cc File Reference

This file provides functions for squarefrees factorizing over , or GF, as decribed in "Factoring multivariate polynomials over a finite field" by L. More...

#include "config.h"
#include "canonicalform.h"
#include "cf_iter.h"
#include "cf_map.h"
#include "cf_util.h"
#include "cf_factory.h"
#include "facFqSquarefree.h"
#include "NTLconvert.h"
#include "FLINTconvert.h"

Go to the source code of this file.

Functions
static CanonicalForm	pthRoot (const CanonicalForm &F, int q)
CanonicalForm	pthRoot (const CanonicalForm &F, const ZZ &q, const Variable &alpha)
CanonicalForm	pthRoot (const CanonicalForm &F, const fmpz_t &q, const Variable &alpha)
CanonicalForm	maxpthRoot (const CanonicalForm &F, int q, int &l)
	p^l-th root extraction, where l is maximal More...
static CFFList	sqrfPosDer (const CanonicalForm &F, const Variable &x, CanonicalForm &c)
CFFList	squarefreeFactorization (const CanonicalForm &F, const Variable &alpha)
	squarefree factorization over a finite field return a list of squarefree factors with multiplicity 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...

Detailed Description

This file provides functions for squarefrees factorizing over , or GF, as decribed in "Factoring multivariate polynomials over a finite field" by L.

Bernardin

Author

Martin Lee

Definition in file facFqSquarefree.cc.

Function Documentation

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;
}

pthRoot() [1/3]

CanonicalForm pthRoot	(	const CanonicalForm &	F,
		const fmpz_t &	q,
		const Variable &	alpha
	)

Definition at line 84 of file facFqSquarefree.cc.

{
  CanonicalForm A= F;
  int p= getCharacteristic ();
  if (A.inCoeffDomain())
  {
    nmod_poly_t FLINTmipo;
    fq_nmod_ctx_t fq_con;
    fmpz_t qp;
    fq_nmod_t FLINTA;
 
    nmod_poly_init (FLINTmipo, p);
    convertFacCF2nmod_poly_t (FLINTmipo, getMipo (alpha));
 
    fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
 
    fq_nmod_init2 (FLINTA, fq_con);
 
    convertFacCF2Fq_nmod_t (FLINTA, A, fq_con);
 
    fmpz_init_set (qp, q);
    fmpz_divexact_si (qp, qp, p);
 
    fq_nmod_pow (FLINTA, FLINTA, qp, fq_con);
    A= convertFq_nmod_t2FacCF (FLINTA, alpha, fq_con);
 
    fmpz_clear (qp);
    nmod_poly_clear (FLINTmipo);
    fq_nmod_clear (FLINTA, fq_con);
    fq_nmod_ctx_clear (fq_con);
    return A;
  }
  else
  {
    CanonicalForm buf= 0;
    for (CFIterator i= A; i.hasTerms(); i++)
      buf= buf + power(A.mvar(), i.exp()/p)*pthRoot (i.coeff(), q, alpha);
    return buf;
  }
}

pthRoot() [2/3]

CanonicalForm pthRoot	(	const CanonicalForm &	F,
		const ZZ &	q,
		const Variable &	alpha
	)

Definition at line 57 of file facFqSquarefree.cc.

{
  CanonicalForm A= F;
  int p= getCharacteristic ();
  if (A.inCoeffDomain())
  {
    zz_p::init (p);
    zz_pX NTLMipo= convertFacCF2NTLzzpX (getMipo (alpha));
    zz_pE::init (NTLMipo);
    zz_pX NTLA= convertFacCF2NTLzzpX (A);
    zz_pE NTLA2= to_zz_pE (NTLA);
    power (NTLA2, NTLA2, q/p);
    A= convertNTLzzpE2CF (NTLA2, alpha);
    return A;
  }
  else
  {
    CanonicalForm buf= 0;
    for (CFIterator i= A; i.hasTerms(); i++)
      buf= buf + power(A.mvar(), i.exp()/p)*pthRoot (i.coeff(), q, alpha);
    return buf;
  }
}

pthRoot() [3/3]

static CanonicalForm pthRoot ( const CanonicalForm &  F, int  q  )

inlinestatic

Definition at line 37 of file facFqSquarefree.cc.

{
  CanonicalForm A= F;
  int p= getCharacteristic ();
  if (A.inCoeffDomain())
  {
    A= power (A, q/p);
    return A;
  }
  else
  {
    CanonicalForm buf= 0;
    for (CFIterator i= A; i.hasTerms(); i++)
      buf= buf + power(A.mvar(), i.exp()/p)*pthRoot (i.coeff(), q);
    return buf;
  }
}

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;
}

sqrfPosDer()

static CFFList sqrfPosDer ( const CanonicalForm &  F, const Variable &  x, CanonicalForm &  c  )

inlinestatic

Definition at line 152 of file facFqSquarefree.cc.

{
  CanonicalForm b= deriv (F, x);
  c= gcd (F, b);
  CanonicalForm w= F/c;
  CanonicalForm v= b/c;
  CanonicalForm u= v - deriv (w, x);
  int j= 1;
  int p= getCharacteristic();
  CanonicalForm g;
  CFFList result;
  while (j < p - 1 && degree(u) >= 0)
  {
    g= gcd (w, u);
    if (!g.inCoeffDomain())
      result.append (CFFactor (g, j));
    w= w/g;
    c= c/w;
    v= u/g;
    u= v - deriv (w, x);
    j++;
  }
  if (!w.inCoeffDomain())
    result.append (CFFactor (w, j));
  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;
}