My Project  UNKNOWN_GIT_VERSION
Functions
facFqSquarefree.h File Reference

This file provides functions for squarefrees factorizing over $ F_{p} $ , $ F_{p}(\alpha ) $ 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 $ F_{p} $. 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 $ F_{p}(\alpha ) $. 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 $ F_{p} $ , $ F_{p}(\alpha ) $ 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 $ F_{p} $. If input is not monic, the leading coefficient is dropped

Returns
a list of squarefree factors with multiplicity
Parameters
[in]Fa poly
[in]sortsort factors by exponent?

Definition at line 38 of file facFqSquarefree.h.

41 {
42  Variable a= 1;
43  int n= F.level();
44  CanonicalForm cont, bufF= F;
45  CFFList bufResult;
46 
48  for (int i= n; i >= 1; i++)
49  {
50  cont= content (bufF, i);
51  bufResult= squarefreeFactorization (cont, a);
52  if (bufResult.getFirst().factor().inCoeffDomain())
53  bufResult.removeFirst();
54  result= Union (result, bufResult);
55  bufF /= cont;
56  if (bufF.inCoeffDomain())
57  break;
58  }
59  if (!bufF.inCoeffDomain())
60  {
61  bufResult= squarefreeFactorization (bufF, a);
62  if (bufResult.getFirst().factor().inCoeffDomain())
63  bufResult.removeFirst();
64  result= Union (result, bufResult);
65  }
66  if (sort)
68  result.insert (CFFactor (Lc(F), 1));
69  return result;
70 }

◆ FqSqrf()

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

squarefree factorization over $ F_{p}(\alpha ) $. If input is not monic, the leading coefficient is dropped

Returns
a list of squarefree factors with multiplicity
Parameters
[in]Fa poly
[in]alphaalgebraic variable
[in]sortsort factors by exponent?

Definition at line 77 of file facFqSquarefree.h.

81 {
82  int n= F.level();
83  CanonicalForm cont, bufF= F;
84  CFFList bufResult;
85 
87  for (int i= n; i >= 1; i++)
88  {
89  cont= content (bufF, i);
90  bufResult= squarefreeFactorization (cont, alpha);
91  if (bufResult.getFirst().factor().inCoeffDomain())
92  bufResult.removeFirst();
93  result= Union (result, bufResult);
94  bufF /= cont;
95  if (bufF.inCoeffDomain())
96  break;
97  }
98  if (!bufF.inCoeffDomain())
99  {
100  bufResult= squarefreeFactorization (bufF, alpha);
101  if (bufResult.getFirst().factor().inCoeffDomain())
102  bufResult.removeFirst();
103  result= Union (result, bufResult);
104  }
105  if (sort)
107  result.insert (CFFactor (Lc(F), 1));
108  return result;
109 }

◆ 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]Fa poly
[in]sortsort factors by exponent?

Definition at line 116 of file facFqSquarefree.h.

119 {
121  "GF as base field expected");
122  return FpSqrf (F, sort);
123 }

◆ 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]Fa poly which is a pth power
[in]qsize of the field
[in,out]ll maximal, s.t. F is a p^l-th power

Definition at line 127 of file facFqSquarefree.cc.

128 {
130  bool derivZero= true;
131  l= 0;
132  while (derivZero)
133  {
134  for (int i= 1; i <= result.level(); i++)
135  {
136  if (!deriv (result, Variable (i)).isZero())
137  {
138  derivZero= false;
139  break;
140  }
141  }
142  if (!derivZero)
143  break;
144  result= pthRoot (result, q);
145  l++;
146  }
147  return result;
148 }

◆ 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]Fa poly
[in,out]pthPowerreturns F is F is a pthPower
[in]alphaalgebraic variable

Definition at line 301 of file facFqSquarefree.cc.

303 {
304  if (F.inCoeffDomain())
305  {
306  pthPower= 1;
307  return F;
308  }
309  CFMap M;
310  CanonicalForm A= compress (F, M);
311  Variable vBuf= alpha;
312  CanonicalForm w, v, b;
313  pthPower= 1;
315  int i= 1;
316  bool allZero= true;
317  for (; i <= A.level(); i++)
318  {
319  if (!deriv (A, Variable (i)).isZero())
320  {
321  allZero= false;
322  break;
323  }
324  }
325  if (allZero)
326  {
327  pthPower= F;
328  return 1;
329  }
330  w= gcd (A, deriv (A, Variable (i)));
331 
332  b= A/w;
333  result= b;
334  if (degree (w) < 1)
335  return M (result);
336  i++;
337  for (; i <= A.level(); i++)
338  {
339  if (!deriv (w, Variable (i)).isZero())
340  {
341  b= w;
342  w= gcd (w, deriv (w, Variable (i)));
343  b /= w;
344  if (degree (b) < 1)
345  break;
347  g= gcd (b, result);
348  if (degree (g) > 0)
349  result *= b/g;
350  if (degree (g) <= 0)
351  result *= b;
352  }
353  }
354  result= M (result);
355  return result;
356 }

◆ 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]Fa poly
[in]alphaeither 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.

182 {
183  int p= getCharacteristic();
184  CanonicalForm A= F;
185  CFMap M;
186  A= compress (A, M);
187  Variable x= A.mvar();
188  int l= x.level();
189  int k;
191  k= getGFDegree();
192  else if (alpha.level() != 1)
193  k= degree (getMipo (alpha));
194  else
195  k= 1;
196  Variable buf, buf2;
197  CanonicalForm tmp;
198 
199  CFFList tmp1, tmp2;
200  bool found;
201  for (int i= l; i > 0; i--)
202  {
203  buf= Variable (i);
204  if (degree (deriv (A, buf)) >= 0)
205  {
206  tmp1= sqrfPosDer (A, buf, tmp);
207  A= tmp;
208  for (CFFListIterator j= tmp1; j.hasItem(); j++)
209  {
210  found= false;
212  if (!k.hasItem() && !j.getItem().factor().inCoeffDomain()) tmp2.append (j.getItem());
213  else
214  {
215  for (; k.hasItem(); k++)
216  {
217  if (k.getItem().exp() == j.getItem().exp())
218  {
219  k.getItem()= CFFactor (k.getItem().factor()*j.getItem().factor(),
220  j.getItem().exp());
221  found= true;
222  }
223  }
224  if (found == false && !j.getItem().factor().inCoeffDomain())
225  tmp2.append(j.getItem());
226  }
227  }
228  }
229  }
230 
231  bool degcheck= false;;
232  for (int i= l; i > 0; i--)
233  if (degree (A, Variable(i)) >= p)
234  degcheck= true;
235 
236  if (degcheck == false && tmp1.isEmpty() && tmp2.isEmpty())
237  return CFFList (CFFactor (F/Lc(F), 1));
238 
239  CanonicalForm buffer;
240 #if defined(HAVE_NTL) || (HAVE_FLINT && __FLINT_RELEASE >= 20400)
241  if (alpha.level() == 1)
242 #endif
243  buffer= pthRoot (A, ipower (p, k));
244 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
245  else
246  {
247  fmpz_t qq;
248  fmpz_init_set_ui (qq, p);
249  fmpz_pow_ui (qq, qq, k);
250  buffer= pthRoot (A, qq, alpha);
251  fmpz_clear (qq);
252  }
253 #elif defined(HAVE_NTL)
254  else
255  {
256  ZZ q;
257  power (q, p, k);
258  buffer= pthRoot (A, q, alpha);
259  }
260 #endif
261 
263 
264  CFFList result;
265  buf= alpha;
266  for (CFFListIterator i= tmp2; i.hasItem(); i++)
267  {
268  for (CFFListIterator j= tmp1; j.hasItem(); j++)
269  {
270  tmp= gcd (i.getItem().factor(), j.getItem().factor());
271  i.getItem()= CFFactor (i.getItem().factor()/tmp, i.getItem().exp());
272  j.getItem()= CFFactor (j.getItem().factor()/tmp, j.getItem().exp());
273  if (!tmp.inCoeffDomain())
274  {
275  tmp= M (tmp);
276  result.append (CFFactor (tmp/Lc(tmp),
277  j.getItem().exp()*p + i.getItem().exp()));
278  }
279  }
280  }
281  for (CFFListIterator i= tmp2; i.hasItem(); i++)
282  {
283  if (!i.getItem().factor().inCoeffDomain())
284  {
285  tmp= M (i.getItem().factor());
286  result.append (CFFactor (tmp/Lc(tmp), i.getItem().exp()));
287  }
288  }
289  for (CFFListIterator j= tmp1; j.hasItem(); j++)
290  {
291  if (!j.getItem().factor().inCoeffDomain())
292  {
293  tmp= M (j.getItem().factor());
294  result.append (CFFactor (tmp/Lc(tmp), j.getItem().exp()*p));
295  }
296  }
297  return result;
298 }
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
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
j
int j
Definition: facHensel.cc:105
k
int k
Definition: cfEzgcd.cc:92
x
Variable x
Definition: cfModGcd.cc:4023
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
result
return result
Definition: facAbsBiFact.cc:76
CFFactory::gettype
static int gettype()
Definition: cf_factory.h:28
CFMap
class CFMap
Definition: cf_map.h:85
CFFList
List< CFFactor > CFFList
Definition: canonicalform.h:386
power
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Definition: canonicalform.cc:1837
g
g
Definition: cfModGcd.cc:4031
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
deriv
CanonicalForm deriv(const CanonicalForm &f, const Variable &x)
Definition: canonicalform.h:339
w
const CanonicalForm & w
Definition: facAbsFact.cc:55
getCharacteristic
int getCharacteristic()
Definition: cf_char.cc:51
b
CanonicalForm b
Definition: cfModGcd.cc:4044
CanonicalForm
factory's main class
Definition: canonicalform.h:83
found
bool found
Definition: facFactorize.cc:56
GaloisFieldDomain
#define GaloisFieldDomain
Definition: cf_defs.h:22
i
int i
Definition: cfEzgcd.cc:125
Lc
CanonicalForm Lc(const CanonicalForm &f)
Definition: canonicalform.h:300
getMipo
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
sqrfPosDer
static CFFList sqrfPosDer(const CanonicalForm &F, const Variable &x, CanonicalForm &c)
Definition: facFqSquarefree.cc:152
ASSERT
#define ASSERT(expression, message)
Definition: cf_assert.h:99
M
#define M
Definition: sirandom.c:24
buf
int status int void * buf
Definition: si_signals.h:59
content
CanonicalForm content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:175
alpha
Variable alpha
Definition: facAbsBiFact.cc:52
List::isEmpty
int isEmpty() const
Definition: ftmpl_list.cc:267
allZero
bool allZero
Definition: facFactorize.cc:57
compress
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m )
Definition: cf_map.cc:210
Variable::level
int level() const
Definition: factory.h:134
tmp1
CFList tmp1
Definition: facFqBivar.cc:70
ipower
int ipower(int b, int m)
int ipower ( int b, int m )
Definition: cf_util.cc:25
sortCFFList
CFFList sortCFFList(CFFList &F)
Definition: fac_sqrfree.cc:21
sort
void sort(CFArray &A, int l=0)
quick sort A
Definition: facSparseHensel.h:114
List::removeFirst
void removeFirst()
Definition: ftmpl_list.cc:287
List::getFirst
T getFirst() const
Definition: ftmpl_list.cc:279
getGFDegree
int getGFDegree()
Definition: cf_char.cc:56
Factor
Definition: ftmpl_factor.h:18
CanonicalForm::inCoeffDomain
bool inCoeffDomain() const
Definition: canonicalform.cc:119
Variable
factory's class for variables
Definition: factory.h:118
l
int l
Definition: cfEzgcd.cc:93
Union
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
gcd
int gcd(int a, int b)
Definition: walkSupport.cc:836
v
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
p
int p
Definition: cfModGcd.cc:4019
List
Definition: ftmpl_list.h:52
tmp2
CFList tmp2
Definition: facFqBivar.cc:70
CanonicalForm::level
int level() const
level() returns the level of CO.
Definition: canonicalform.cc:543
CFFactor
Factor< CanonicalForm > CFFactor
Definition: canonicalform.h:385
List::append
void append(const T &)
Definition: ftmpl_list.cc:256
A
#define A
Definition: sirandom.c:23
buf2
CanonicalForm buf2
Definition: facFqBivar.cc:71
degree
int degree(const CanonicalForm &f)
Definition: canonicalform.h:309
ListIterator
Definition: ftmpl_list.h:87