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)
67  result= sortCFFList (result);
68  result.insert (CFFactor (Lc(F), 1));
69  return result;
70 }
factory's class for variables
Definition: factory.h:117
factory's main class
Definition: canonicalform.h:77
void insert(const T &)
Definition: ftmpl_list.cc:193
CanonicalForm Lc(const CanonicalForm &f)
void removeFirst()
Definition: ftmpl_list.cc:287
CanonicalForm content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:175
T getFirst() const
Definition: ftmpl_list.cc:279
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
CFFList squarefreeFactorization(const CanonicalForm &F, const Variable &alpha)
squarefree factorization over a finite field return a list of squarefree factors with multiplicity ...
int i
Definition: cfEzgcd.cc:125
CFFList sortCFFList(CFFList &F)
Definition: fac_sqrfree.cc:21
void sort(CFArray &A, int l=0)
quick sort A
int level() const
level() returns the level of CO.
return result
Definition: facAbsBiFact.cc:76
bool inCoeffDomain() const

◆ 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)
106  result= sortCFFList (result);
107  result.insert (CFFactor (Lc(F), 1));
108  return result;
109 }
factory&#39;s main class
Definition: canonicalform.h:77
void insert(const T &)
Definition: ftmpl_list.cc:193
CanonicalForm Lc(const CanonicalForm &f)
void removeFirst()
Definition: ftmpl_list.cc:287
CanonicalForm content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:175
T getFirst() const
Definition: ftmpl_list.cc:279
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
CFFList squarefreeFactorization(const CanonicalForm &F, const Variable &alpha)
squarefree factorization over a finite field return a list of squarefree factors with multiplicity ...
int i
Definition: cfEzgcd.cc:125
CFFList sortCFFList(CFFList &F)
Definition: fac_sqrfree.cc:21
void sort(CFArray &A, int l=0)
quick sort A
int level() const
level() returns the level of CO.
return result
Definition: facAbsBiFact.cc:76
bool inCoeffDomain() const

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

◆ 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 }
CanonicalForm deriv(const CanonicalForm &f, const Variable &x)
factory&#39;s class for variables
Definition: factory.h:117
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
factory&#39;s main class
Definition: canonicalform.h:77
int i
Definition: cfEzgcd.cc:125
static CanonicalForm pthRoot(const CanonicalForm &F, int q)
int level() const
level() returns the level of CO.
int l
Definition: cfEzgcd.cc:93
return result
Definition: facAbsBiFact.cc:76

◆ 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 }
CanonicalForm deriv(const CanonicalForm &f, const Variable &x)
factory&#39;s class for variables
Definition: factory.h:117
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
factory&#39;s main class
Definition: canonicalform.h:77
g
Definition: cfModGcd.cc:4031
Variable alpha
Definition: facAbsBiFact.cc:52
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m )
Definition: cf_map.cc:210
#define M
Definition: sirandom.c:25
CanonicalForm b
Definition: cfModGcd.cc:4044
#define A
Definition: sirandom.c:24
bool allZero
Definition: facFactorize.cc:57
int i
Definition: cfEzgcd.cc:125
class CFMap
Definition: cf_map.h:84
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
int gcd(int a, int b)
Definition: walkSupport.cc:836
const CanonicalForm & w
Definition: facAbsFact.cc:55
int level() const
level() returns the level of CO.
int degree(const CanonicalForm &f)
return result
Definition: facAbsBiFact.cc:76
bool inCoeffDomain() const

◆ 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 
262  tmp1= squarefreeFactorization (buffer, alpha);
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 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
int j
Definition: facHensel.cc:105
int isEmpty() const
Definition: ftmpl_list.cc:267
CanonicalForm deriv(const CanonicalForm &f, const Variable &x)
factory&#39;s class for variables
Definition: factory.h:117
factory&#39;s main class
Definition: canonicalform.h:77
int k
Definition: cfEzgcd.cc:92
Variable alpha
Definition: facAbsBiFact.cc:52
CanonicalForm Lc(const CanonicalForm &f)
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m )
Definition: cf_map.cc:210
int getCharacteristic()
Definition: cf_char.cc:51
bool found
Definition: facFactorize.cc:56
#define M
Definition: sirandom.c:25
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 ...
int status int void * buf
Definition: si_signals.h:59
int level() const
Definition: factory.h:134
T & getItem() const
Definition: ftmpl_list.cc:431
#define A
Definition: sirandom.c:24
int i
Definition: cfEzgcd.cc:125
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
CFList tmp2
Definition: facFqBivar.cc:70
CanonicalForm buf2
Definition: facFqBivar.cc:71
class CFMap
Definition: cf_map.h:84
static CanonicalForm pthRoot(const CanonicalForm &F, int q)
int ipower(int b, int m)
int ipower ( int b, int m )
Definition: cf_util.cc:26
static int gettype()
Definition: cf_factory.h:28
Factor< CanonicalForm > CFFactor
int gcd(int a, int b)
Definition: walkSupport.cc:836
CFList tmp1
Definition: facFqBivar.cc:70
int getGFDegree()
Definition: cf_char.cc:56
Variable x
Definition: cfModGcd.cc:4023
#define GaloisFieldDomain
Definition: cf_defs.h:23
void append(const T &)
Definition: ftmpl_list.cc:256
int p
Definition: cfModGcd.cc:4019
int degree(const CanonicalForm &f)
return result
Definition: facAbsBiFact.cc:76
int l
Definition: cfEzgcd.cc:93
bool inCoeffDomain() const