My Project
facFqSquarefree.cc
Go to the documentation of this file.
1 /*****************************************************************************\
2  * Computer Algebra System SINGULAR
3 \*****************************************************************************/
4 /** @file facFqSquarefree.cc
5  *
6  * This file provides functions for squarefrees factorizing over
7  * \f$ F_{p} \f$ , \f$ F_{p}(\alpha ) \f$ or GF, as decribed in "Factoring
8  * multivariate polynomials over a finite field" by L. Bernardin
9  *
10  * @author Martin Lee
11  *
12  **/
13 /*****************************************************************************/
14 
15 
16 #include "config.h"
17 
18 
19 #include "canonicalform.h"
20 
21 #include "cf_iter.h"
22 #include "cf_map.h"
23 #include "cf_util.h"
24 #include "cf_factory.h"
25 #include "facFqSquarefree.h"
26 
27 #ifdef HAVE_NTL
28 #include "NTLconvert.h"
29 #endif
30 
31 #ifdef HAVE_FLINT
32 #include "FLINTconvert.h"
33 #endif
34 
35 static inline
37 pthRoot (const CanonicalForm & F, int q)
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 }
54 
55 #ifdef HAVE_NTL
57 pthRoot (const CanonicalForm & F, const ZZ& q, const Variable& alpha)
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 }
80 #endif
81 
82 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
84 pthRoot (const CanonicalForm & F, const fmpz_t& q, const Variable& alpha)
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, fq_con);
109 
110  fmpz_clear (qp);
111  nmod_poly_clear (FLINTmipo);
112  fq_nmod_clear (FLINTA, 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 }
124 #endif
125 
127 maxpthRoot (const CanonicalForm & F, int q, int& l)
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 }
149 
150 static inline
151 CFFList
152 sqrfPosDer (const CanonicalForm & F, const Variable & x,
153  CanonicalForm & c)
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 }
179 
180 CFFList
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 #else
261  factoryError("NTL/FLINT missing: squarefreeFactorization");
262 #endif
263 
265 
266  CFFList result;
267  buf= alpha;
268  for (CFFListIterator i= tmp2; i.hasItem(); i++)
269  {
270  for (CFFListIterator j= tmp1; j.hasItem(); j++)
271  {
272  tmp= gcd (i.getItem().factor(), j.getItem().factor());
273  i.getItem()= CFFactor (i.getItem().factor()/tmp, i.getItem().exp());
274  j.getItem()= CFFactor (j.getItem().factor()/tmp, j.getItem().exp());
275  if (!tmp.inCoeffDomain())
276  {
277  tmp= M (tmp);
278  result.append (CFFactor (tmp/Lc(tmp),
279  j.getItem().exp()*p + i.getItem().exp()));
280  }
281  }
282  }
283  for (CFFListIterator i= tmp2; i.hasItem(); i++)
284  {
285  if (!i.getItem().factor().inCoeffDomain())
286  {
287  tmp= M (i.getItem().factor());
288  result.append (CFFactor (tmp/Lc(tmp), i.getItem().exp()));
289  }
290  }
291  for (CFFListIterator j= tmp1; j.hasItem(); j++)
292  {
293  if (!j.getItem().factor().inCoeffDomain())
294  {
295  tmp= M (j.getItem().factor());
296  result.append (CFFactor (tmp/Lc(tmp), j.getItem().exp()*p));
297  }
298  }
299  return result;
300 }
301 
303 sqrfPart (const CanonicalForm& F, CanonicalForm& pthPower,
304  const Variable& alpha)
305 {
306  if (F.inCoeffDomain())
307  {
308  pthPower= 1;
309  return F;
310  }
311  CFMap M;
312  CanonicalForm A= compress (F, M);
313  Variable vBuf= alpha;
314  CanonicalForm w, v, b;
315  pthPower= 1;
317  int i= 1;
318  bool allZero= true;
319  for (; i <= A.level(); i++)
320  {
321  if (!deriv (A, Variable (i)).isZero())
322  {
323  allZero= false;
324  break;
325  }
326  }
327  if (allZero)
328  {
329  pthPower= F;
330  return 1;
331  }
332  w= gcd (A, deriv (A, Variable (i)));
333 
334  b= A/w;
335  result= b;
336  if (degree (w) < 1)
337  return M (result);
338  i++;
339  for (; i <= A.level(); i++)
340  {
341  if (!deriv (w, Variable (i)).isZero())
342  {
343  b= w;
344  w= gcd (w, deriv (w, Variable (i)));
345  b /= w;
346  if (degree (b) < 1)
347  break;
349  g= gcd (b, result);
350  if (degree (g) > 0)
351  result *= b/g;
352  if (degree (g) <= 0)
353  result *= b;
354  }
355  }
356  result= M (result);
357  return result;
358 }
359 
CanonicalForm convertFq_nmod_t2FacCF(const fq_nmod_t poly, const Variable &alpha, const fq_nmod_ctx_t ctx)
conversion of a FLINT element of F_q to a CanonicalForm with alg. variable alpha
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...
This file defines functions for conversion to FLINT (www.flintlib.org) and back.
CanonicalForm convertNTLzzpE2CF(const zz_pE &coefficient, const Variable &x)
Definition: NTLconvert.cc:799
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
Definition: NTLconvert.cc:105
Conversion to and from NTL.
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Header for factory's main class CanonicalForm.
int degree(const CanonicalForm &f)
CanonicalForm deriv(const CanonicalForm &f, const Variable &x)
int getGFDegree()
Definition: cf_char.cc:75
List< CFFactor > CFFList
CanonicalForm Lc(const CanonicalForm &f)
Factor< CanonicalForm > CFFactor
int FACTORY_PUBLIC getCharacteristic()
Definition: cf_char.cc:70
int l
Definition: cfEzgcd.cc:100
int i
Definition: cfEzgcd.cc:132
int k
Definition: cfEzgcd.cc:99
Variable x
Definition: cfModGcd.cc:4084
int p
Definition: cfModGcd.cc:4080
g
Definition: cfModGcd.cc:4092
CanonicalForm b
Definition: cfModGcd.cc:4105
#define GaloisFieldDomain
Definition: cf_defs.h:24
Interface to generate InternalCF's over various domains from intrinsic types or mpz_t's.
Iterators for CanonicalForm's.
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m )
Definition: cf_map.cc:210
map polynomials
VAR void(* factoryError)(const char *s)
Definition: cf_util.cc:80
int ipower(int b, int m)
int ipower ( int b, int m )
Definition: cf_util.cc:27
static int gettype()
Definition: cf_factory.h:28
class to iterate through CanonicalForm's
Definition: cf_iter.h:44
class CFMap
Definition: cf_map.h:85
factory's main class
Definition: canonicalform.h:86
bool inCoeffDomain() const
void append(const T &)
Definition: ftmpl_list.cc:256
int isEmpty() const
Definition: ftmpl_list.cc:267
factory's class for variables
Definition: factory.h:134
int level() const
Definition: factory.h:150
Variable alpha
Definition: facAbsBiFact.cc:51
return result
Definition: facAbsBiFact.cc:75
const CanonicalForm & w
Definition: facAbsFact.cc:51
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:39
bool allZero
Definition: facFactorize.cc:56
bool found
Definition: facFactorize.cc:55
CFList tmp1
Definition: facFqBivar.cc:72
CanonicalForm buf2
Definition: facFqBivar.cc:73
CFList tmp2
Definition: facFqBivar.cc:72
static CFFList sqrfPosDer(const CanonicalForm &F, const Variable &x, CanonicalForm &c)
CanonicalForm maxpthRoot(const CanonicalForm &F, int q, int &l)
p^l-th root extraction, where l is maximal
CFFList squarefreeFactorization(const CanonicalForm &F, const Variable &alpha)
squarefree factorization over a finite field return a list of squarefree factors with multiplicity
static CanonicalForm pthRoot(const CanonicalForm &F, int q)
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 mo...
This file provides functions for squarefrees factorizing over , or GF.
fq_nmod_ctx_t fq_con
Definition: facHensel.cc:99
int j
Definition: facHensel.cc:110
fq_nmod_ctx_clear(fq_con)
nmod_poly_init(FLINTmipo, getCharacteristic())
fq_nmod_ctx_init_modulus(fq_con, FLINTmipo, "Z")
convertFacCF2nmod_poly_t(FLINTmipo, M)
nmod_poly_clear(FLINTmipo)
bool isZero(const CFArray &A)
checks if entries of A are zero
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
void init()
Definition: lintree.cc:864
int status int void * buf
Definition: si_signals.h:59
#define A
Definition: sirandom.c:24
#define M
Definition: sirandom.c:25
int gcd(int a, int b)
Definition: walkSupport.cc:836