Loading...
Searching...
No Matches
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
CFFList | FpSqrf (const CanonicalForm &F, bool sort=true)
| squarefree factorization over . If input is not monic, the leading coefficient is dropped
CFFList | FqSqrf (const CanonicalForm &F, const Variable &alpha, bool sort=true)
| squarefree factorization over . If input is not monic, the leading coefficient is dropped
CFFList | GFSqrf (const CanonicalForm &F, bool sort=true)
| squarefree factorization over GF. If input is not monic, the leading coefficient is dropped
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.
CanonicalForm | maxpthRoot (const CanonicalForm &F, int q, int &l)
| p^l-th root extraction, where l is maximal

## 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;
}
content
CanonicalForm FACTORY_PUBLIC content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f ).
Definition cf_gcd.cc:603
CFFList
List< CFFactor > CFFList
Definition canonicalform.h:393
Lc
CanonicalForm Lc(const CanonicalForm &f)
Definition canonicalform.h:307
CFFactor
Factor< CanonicalForm > CFFactor
Definition canonicalform.h:392
i
int i
Definition cfEzgcd.cc:132
sort
static void sort(int **points, int sizePoints)
Definition cfNewtonPolygon.cc:100
CanonicalForm
factory's main class
Definition canonicalform.h:86
CanonicalForm::inCoeffDomain
bool inCoeffDomain() const
Definition canonicalform.cc:122
CanonicalForm::level
int level() const
level() returns the level of CO.
Definition canonicalform.cc:576
Factor::factor
T factor() const
Definition ftmpl_factor.h:30
List::getFirst
T getFirst() const
Definition ftmpl_list.cc:279
List::removeFirst
void removeFirst()
Definition ftmpl_list.cc:287
Variable
factory's class for variables
Definition factory.h:127
result
return result
Definition facAbsBiFact.cc:76
squarefreeFactorization
CFFList squarefreeFactorization(const CanonicalForm &F, const Variable &alpha)
squarefree factorization over a finite field return a list of squarefree factors with multiplicity
Definition facFqSquarefree.cc:181
sortCFFList
CFFList sortCFFList(CFFList &F)
Definition fac_sqrfree.cc:25
Union
template List< Variable > Union(const List< Variable > &, const List< Variable > &)

## 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;
}
alpha
Variable alpha
Definition facAbsBiFact.cc:52

## 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);
}
ASSERT
#define ASSERT(expression, message)
Definition cf_assert.h:99
GaloisFieldDomain
#define GaloisFieldDomain
Definition cf_defs.h:18
CFFactory::gettype
static int gettype()
Definition cf_factory.h:28
FpSqrf
CFFList FpSqrf(const CanonicalForm &F, bool sort=true)
squarefree factorization over . If input is not monic, the leading coefficient is dropped
Definition facFqSquarefree.h:38

## 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;
}
deriv
CanonicalForm deriv(const CanonicalForm &f, const Variable &x)
Definition canonicalform.h:346
l
int l
Definition cfEzgcd.cc:100
pthRoot
static CanonicalForm pthRoot(const CanonicalForm &F, int q)
Definition facFqSquarefree.cc:37
isZero
bool isZero(const CFArray &A)
checks if entries of A are zero
Definition facSparseHensel.h:468

## 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;
}
degree
int degree(const CanonicalForm &f)
Definition canonicalform.h:316
g
g
Definition cfModGcd.cc:4098
b
CanonicalForm b
Definition cfModGcd.cc:4111
compress
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m ).
Definition cf_map.cc:210
CFMap
class CFMap
Definition cf_map.h:85
w
const CanonicalForm & w
Definition facAbsFact.cc:51
v
const Variable & v
< [in] a sqrfree bivariate poly
Definition facBivar.h:39
allZero
bool allZero
Definition facFactorize.cc:56
A
#define A
Definition sirandom.c:24
M
#define M
Definition sirandom.c:25
gcd
int gcd(int a, int b)
Definition walkSupport.cc:836

## 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;
}
power
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Definition canonicalform.cc:1896
getGFDegree
int getGFDegree()
Definition cf_char.cc:75
CFFListIterator
ListIterator< CFFactor > CFFListIterator
Definition canonicalform.h:394
getCharacteristic
int FACTORY_PUBLIC getCharacteristic()
Definition cf_char.cc:70
k
int k
Definition cfEzgcd.cc:99
x
Variable x
Definition cfModGcd.cc:4090
p
int p
Definition cfModGcd.cc:4086
factoryError
VAR void(* factoryError)(const char *s)
Definition cf_util.cc:80
ipower
int ipower(int b, int m)
int ipower ( int b, int m )
Definition cf_util.cc:27
found
bool found
Definition facFactorize.cc:55
tmp1
CFList tmp1
Definition facFqBivar.cc:75
buf2
CanonicalForm buf2
Definition facFqBivar.cc:76
tmp2
CFList tmp2
Definition facFqBivar.cc:75
sqrfPosDer
static CFFList sqrfPosDer(const CanonicalForm &F, const Variable &x, CanonicalForm &c)
Definition facFqSquarefree.cc:152
squarefreeFactorization
CFFList squarefreeFactorization(const CanonicalForm &F, const Variable &alpha)
squarefree factorization over a finite field return a list of squarefree factors with multiplicity
Definition facFqSquarefree.cc:181
j
int j
Definition facHensel.cc:110
getMipo
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition variable.cc:207
buf
int status int void * buf
Definition si_signals.h:69