Functions
facFqSquarefree.cc File Reference

This file provides functions for squarefrees factorizing over $ F_{p} $ , $ F_{p}(\alpha ) $ 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 $ F_{p} $ , $ F_{p}(\alpha ) $ 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]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:115
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
factory&#39;s main class
Definition: canonicalform.h:75
int i
Definition: cfEzgcd.cc:123
static CanonicalForm pthRoot(const CanonicalForm &F, int q)
int level() const
level() returns the level of CO.
int l
Definition: cfEzgcd.cc:94
return result
Definition: facAbsBiFact.cc:76

◆ pthRoot() [1/3]

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

Definition at line 37 of file facFqSquarefree.cc.

38 {
39  CanonicalForm A= F;
40  int p= getCharacteristic ();
41  if (A.inCoeffDomain())
42  {
43  A= power (A, q/p);
44  return A;
45  }
46  else
47  {
48  CanonicalForm buf= 0;
49  for (CFIterator i= A; i.hasTerms(); i++)
50  buf= buf + power(A.mvar(), i.exp()/p)*pthRoot (i.coeff(), q);
51  return buf;
52  }
53 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
return P p
Definition: myNF.cc:203
factory&#39;s main class
Definition: canonicalform.h:75
int getCharacteristic()
Definition: cf_char.cc:51
int status int void * buf
Definition: si_signals.h:59
#define A
Definition: sirandom.c:23
int i
Definition: cfEzgcd.cc:123
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
class to iterate through CanonicalForm&#39;s
Definition: cf_iter.h:44
static CanonicalForm pthRoot(const CanonicalForm &F, int q)
bool inCoeffDomain() const

◆ pthRoot() [2/3]

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

Definition at line 57 of file facFqSquarefree.cc.

58 {
59  CanonicalForm A= F;
60  int p= getCharacteristic ();
61  if (A.inCoeffDomain())
62  {
63  zz_p::init (p);
64  zz_pX NTLMipo= convertFacCF2NTLzzpX (getMipo (alpha));
65  zz_pE::init (NTLMipo);
66  zz_pX NTLA= convertFacCF2NTLzzpX (A);
67  zz_pE NTLA2= to_zz_pE (NTLA);
68  power (NTLA2, NTLA2, q/p);
69  A= convertNTLzzpE2CF (NTLA2, alpha);
70  return A;
71  }
72  else
73  {
74  CanonicalForm buf= 0;
75  for (CFIterator i= A; i.hasTerms(); i++)
76  buf= buf + power(A.mvar(), i.exp()/p)*pthRoot (i.coeff(), q, alpha);
77  return buf;
78  }
79 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
return P p
Definition: myNF.cc:203
CanonicalForm convertNTLzzpE2CF(const zz_pE &coefficient, const Variable &x)
Definition: NTLconvert.cc:797
factory&#39;s main class
Definition: canonicalform.h:75
Variable alpha
Definition: facAbsBiFact.cc:52
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
int getCharacteristic()
Definition: cf_char.cc:51
int status int void * buf
Definition: si_signals.h:59
#define A
Definition: sirandom.c:23
int i
Definition: cfEzgcd.cc:123
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
class to iterate through CanonicalForm&#39;s
Definition: cf_iter.h:44
static CanonicalForm pthRoot(const CanonicalForm &F, int q)
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
Definition: NTLconvert.cc:103
bool inCoeffDomain() const

◆ pthRoot() [3/3]

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

Definition at line 84 of file facFqSquarefree.cc.

85 {
86  CanonicalForm A= F;
87  int p= getCharacteristic ();
88  if (A.inCoeffDomain())
89  {
90  nmod_poly_t FLINTmipo;
91  fq_nmod_ctx_t fq_con;
92  fmpz_t qp;
93  fq_nmod_t FLINTA;
94 
95  nmod_poly_init (FLINTmipo, p);
96  convertFacCF2nmod_poly_t (FLINTmipo, getMipo (alpha));
97 
98  fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
99 
100  fq_nmod_init2 (FLINTA, fq_con);
101 
102  convertFacCF2Fq_nmod_t (FLINTA, A, fq_con);
103 
104  fmpz_init_set (qp, q);
105  fmpz_divexact_si (qp, qp, p);
106 
107  fq_nmod_pow (FLINTA, FLINTA, qp, fq_con);
108  A= convertFq_nmod_t2FacCF (FLINTA, alpha);
109 
110  fmpz_clear (qp);
111  nmod_poly_clear (FLINTmipo);
112  fq_nmod_clear (FLINTA, fq_con);
113  fq_nmod_ctx_clear (fq_con);
114  return A;
115  }
116  else
117  {
118  CanonicalForm buf= 0;
119  for (CFIterator i= A; i.hasTerms(); i++)
120  buf= buf + power(A.mvar(), i.exp()/p)*pthRoot (i.coeff(), q, alpha);
121  return buf;
122  }
123 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
nmod_poly_init(FLINTmipo, getCharacteristic())
CanonicalForm convertFq_nmod_t2FacCF(const fq_nmod_t poly, const Variable &alpha)
conversion of a FLINT element of F_q to a CanonicalForm with alg. variable alpha
return P p
Definition: myNF.cc:203
factory&#39;s main class
Definition: canonicalform.h:75
nmod_poly_clear(FLINTmipo)
fq_nmod_ctx_t fq_con
Definition: facHensel.cc:94
Variable alpha
Definition: facAbsBiFact.cc:52
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
int getCharacteristic()
Definition: cf_char.cc:51
fq_nmod_ctx_clear(fq_con)
convertFacCF2nmod_poly_t(FLINTmipo, M)
int status int void * buf
Definition: si_signals.h:59
#define A
Definition: sirandom.c:23
void convertFacCF2Fq_nmod_t(fq_nmod_t result, const CanonicalForm &f, const fq_nmod_ctx_t ctx)
conversion of a factory element of F_q to a FLINT fq_nmod_t, does not do any memory allocation for po...
int i
Definition: cfEzgcd.cc:123
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
class to iterate through CanonicalForm&#39;s
Definition: cf_iter.h:44
static CanonicalForm pthRoot(const CanonicalForm &F, int q)
bool inCoeffDomain() const
fq_nmod_ctx_init_modulus(fq_con, FLINTmipo, "Z")

◆ 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:115
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
factory&#39;s main class
Definition: canonicalform.h:75
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:24
#define A
Definition: sirandom.c:23
bool allZero
Definition: facFactorize.cc:57
int i
Definition: cfEzgcd.cc:123
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:839
const CanonicalForm & w
Definition: facAbsFact.cc:55
int level() const
level() returns the level of CO.
int degree(const CanonicalForm &f)
const poly b
Definition: syzextra.cc:213
return result
Definition: facAbsBiFact.cc:76
bool inCoeffDomain() const

◆ sqrfPosDer()

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

Definition at line 152 of file facFqSquarefree.cc.

154 {
155  CanonicalForm b= deriv (F, x);
156  c= gcd (F, b);
157  CanonicalForm w= F/c;
158  CanonicalForm v= b/c;
159  CanonicalForm u= v - deriv (w, x);
160  int j= 1;
161  int p= getCharacteristic();
163  CFFList result;
164  while (j < p - 1 && degree(u) >= 0)
165  {
166  g= gcd (w, u);
167  if (!g.inCoeffDomain())
168  result.append (CFFactor (g, j));
169  w= w/g;
170  c= c/w;
171  v= u/g;
172  u= v - deriv (w, x);
173  j++;
174  }
175  if (!w.inCoeffDomain())
176  result.append (CFFactor (w, j));
177  return result;
178 }
CanonicalForm deriv(const CanonicalForm &f, const Variable &x)
return P p
Definition: myNF.cc:203
factory&#39;s main class
Definition: canonicalform.h:75
g
Definition: cfModGcd.cc:4031
int getCharacteristic()
Definition: cf_char.cc:51
int j
Definition: myNF.cc:70
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
int gcd(int a, int b)
Definition: walkSupport.cc:839
const CanonicalForm & w
Definition: facAbsFact.cc:55
void append(const T &)
Definition: ftmpl_list.cc:256
int degree(const CanonicalForm &f)
const poly b
Definition: syzextra.cc:213
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 isEmpty() const
Definition: ftmpl_list.cc:267
CanonicalForm deriv(const CanonicalForm &f, const Variable &x)
return P p
Definition: myNF.cc:203
factory&#39;s class for variables
Definition: factory.h:115
factory&#39;s main class
Definition: canonicalform.h:75
int k
Definition: cfEzgcd.cc:93
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:24
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 j
Definition: myNF.cc:70
int status int void * buf
Definition: si_signals.h:59
int level() const
Definition: factory.h:132
T & getItem() const
Definition: ftmpl_list.cc:431
#define A
Definition: sirandom.c:23
int i
Definition: cfEzgcd.cc:123
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:25
static int gettype()
Definition: cf_factory.h:28
Factor< CanonicalForm > CFFactor
int gcd(int a, int b)
Definition: walkSupport.cc:839
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:22
void append(const T &)
Definition: ftmpl_list.cc:256
int degree(const CanonicalForm &f)
return result
Definition: facAbsBiFact.cc:76
int l
Definition: cfEzgcd.cc:94
bool inCoeffDomain() const