My Project
facFqBivar.h
Go to the documentation of this file.
1 /*****************************************************************************\
2  * Computer Algebra System SINGULAR
3 \*****************************************************************************/
4 /** @file facFqBivar.h
5  *
6  * This file provides functions for factorizing a bivariate polynomial over
7  * \f$ F_{p} \f$ , \f$ F_{p}(\alpha ) \f$ or GF.
8  *
9  * @author Martin Lee
10  *
11  **/
12 /*****************************************************************************/
13 
14 #ifndef FAC_FQ_BIVAR_H
15 #define FAC_FQ_BIVAR_H
16 
17 // #include "config.h"
18 
19 #include "timing.h"
20 #include "cf_assert.h"
21 
22 #include "facFqBivarUtil.h"
23 #include "DegreePattern.h"
24 #include "ExtensionInfo.h"
25 #include "cf_util.h"
26 #include "facFqSquarefree.h"
27 #include "cf_map.h"
28 #include "cfNewtonPolygon.h"
29 #include "fac_util.h"
30 #include "cf_algorithm.h"
31 
32 TIMING_DEFINE_PRINT(fac_fq_bi_sqrf)
33 TIMING_DEFINE_PRINT(fac_fq_bi_factor_sqrf)
34 
35 static const double log2exp= 1.442695041;
36 
37 #if defined(HAVE_NTL) || defined(HAVE_FLINT)
38 /// Factorization of a squarefree bivariate polynomials over an arbitrary finite
39 /// field, information on the current field we work over is in @a info. @a info
40 /// may also contain information about the initial field if initial and current
41 /// field do not coincide. In this case the current field is an extension of the
42 /// initial field and the factors returned are factors of F over the initial
43 /// field.
44 ///
45 /// @return @a biFactorize returns a list of factors of F. If F is not monic
46 /// its leading coefficient is not outputted.
47 /// @sa extBifactorize()
48 CFList
49 biFactorize (const CanonicalForm& F, ///< [in] a sqrfree bivariate poly
50  const ExtensionInfo& info ///< [in] information about extension
51  );
52 
53 #ifdef HAVE_NTL // biFactorize
54 inline CFList
56 {
57  CFMap N;
58  CanonicalForm F= compress (G, N);
59  CanonicalForm contentX= content (F, 1);
60  CanonicalForm contentY= content (F, 2);
61  F /= (contentX*contentY);
62  CFFList contentXFactors, contentYFactors;
63  if (info.getAlpha().level() != 1)
64  {
65  contentXFactors= factorize (contentX, info.getAlpha());
66  contentYFactors= factorize (contentY, info.getAlpha());
67  }
68  else if (info.getAlpha().level() == 1 && info.getGFDegree() == 1)
69  {
70  contentXFactors= factorize (contentX);
71  contentYFactors= factorize (contentY);
72  }
73  else if (info.getAlpha().level() == 1 && info.getGFDegree() != 1)
74  {
75  CFList bufContentX, bufContentY;
76  bufContentX= biFactorize (contentX, info);
77  bufContentY= biFactorize (contentY, info);
78  for (CFListIterator iter= bufContentX; iter.hasItem(); iter++)
79  contentXFactors.append (CFFactor (iter.getItem(), 1));
80  for (CFListIterator iter= bufContentY; iter.hasItem(); iter++)
81  contentYFactors.append (CFFactor (iter.getItem(), 1));
82  }
83 
84  if (contentXFactors.getFirst().factor().inCoeffDomain())
85  contentXFactors.removeFirst();
86  if (contentYFactors.getFirst().factor().inCoeffDomain())
87  contentYFactors.removeFirst();
88  if (F.inCoeffDomain())
89  {
90  CFList result;
91  for (CFFListIterator i= contentXFactors; i.hasItem(); i++)
92  result.append (N (i.getItem().factor()));
93  for (CFFListIterator i= contentYFactors; i.hasItem(); i++)
94  result.append (N (i.getItem().factor()));
95  normalize (result);
96  result.insert (Lc (G));
97  return result;
98  }
99  mpz_t * M=new mpz_t [4];
100  mpz_init (M[0]);
101  mpz_init (M[1]);
102  mpz_init (M[2]);
103  mpz_init (M[3]);
104 
105  mpz_t * S=new mpz_t [2];
106  mpz_init (S[0]);
107  mpz_init (S[1]);
108 
109  F= compress (F, M, S);
111  for (CFListIterator i= result; i.hasItem(); i++)
112  i.getItem()= N (decompress (i.getItem(), M, S));
113  for (CFFListIterator i= contentXFactors; i.hasItem(); i++)
114  result.append (N(i.getItem().factor()));
115  for (CFFListIterator i= contentYFactors; i.hasItem(); i++)
116  result.append (N (i.getItem().factor()));
117  normalize (result);
118  result.insert (Lc(G));
119 
120  mpz_clear (M[0]);
121  mpz_clear (M[1]);
122  mpz_clear (M[2]);
123  mpz_clear (M[3]);
124  delete [] M;
125 
126  mpz_clear (S[0]);
127  mpz_clear (S[1]);
128  delete [] S;
129 
130  return result;
131 }
132 #endif
133 
134 /// factorize a squarefree bivariate polynomial over \f$ F_{p} \f$.
135 ///
136 /// @return @a FpBiSqrfFactorize returns a list of monic factors, the first
137 /// element is the leading coefficient.
138 /// @sa FqBiSqrfFactorize(), GFBiSqrfFactorize()
139 #ifdef HAVE_NTL // biSqrfFactorizeHelper, biFactorize
140 inline
141 CFList FpBiSqrfFactorize (const CanonicalForm & G ///< [in] a bivariate poly
142  )
143 {
145  return biSqrfFactorizeHelper (G, info);
146 }
147 #endif
148 
149 /// factorize a squarefree bivariate polynomial over \f$ F_{p}(\alpha ) \f$.
150 ///
151 /// @return @a FqBiSqrfFactorize returns a list of monic factors, the first
152 /// element is the leading coefficient.
153 /// @sa FpBiSqrfFactorize(), GFBiSqrfFactorize()
154 #ifdef HAVE_NTL // biSqrfFactorizeHelper, biFactorize
155 inline
156 CFList FqBiSqrfFactorize (const CanonicalForm & G, ///< [in] a bivariate poly
157  const Variable& alpha ///< [in] algebraic variable
158  )
159 {
161  return biSqrfFactorizeHelper (G, info);
162 }
163 #endif
164 
165 /// factorize a squarefree bivariate polynomial over GF
166 ///
167 /// @return @a GFBiSqrfFactorize returns a list of monic factors, the first
168 /// element is the leading coefficient.
169 /// @sa FpBiSqrfFactorize(), FqBiSqrfFactorize()
170 #ifdef HAVE_NTL // biSqrfFactorizeHelper, biFactorize
171 inline
172 CFList GFBiSqrfFactorize (const CanonicalForm & G ///< [in] a bivariate poly
173  )
174 {
176  "GF as base field expected");
178  return biSqrfFactorizeHelper (G, info);
179 }
180 #endif
181 
182 /// factorize a bivariate polynomial over \f$ F_{p} \f$
183 ///
184 /// @return @a FpBiFactorize returns a list of monic factors with
185 /// multiplicity, the first element is the leading coefficient.
186 /// @sa FqBiFactorize(), GFBiFactorize()
187 #ifdef HAVE_NTL // biFactorize
188 inline
189 CFFList
190 FpBiFactorize (const CanonicalForm & G, ///< [in] a bivariate poly
191  bool substCheck= true ///< [in] enables substitute check
192  )
193 {
195  CFMap N;
196  CanonicalForm F= compress (G, N);
197 
198  if (substCheck)
199  {
200  bool foundOne= false;
201  int * substDegree= NEW_ARRAY(int,F.level());
202  for (int i= 1; i <= F.level(); i++)
203  {
204  substDegree[i-1]= substituteCheck (F, Variable (i));
205  if (substDegree [i-1] > 1)
206  {
207  foundOne= true;
208  subst (F, F, substDegree[i-1], Variable (i));
209  }
210  }
211  if (foundOne)
212  {
213  CFFList result= FpBiFactorize (F, false);
214  CFFList newResult, tmp;
216  newResult.insert (result.getFirst());
217  result.removeFirst();
218  for (CFFListIterator i= result; i.hasItem(); i++)
219  {
220  tmp2= i.getItem().factor();
221  for (int j= 1; j <= F.level(); j++)
222  {
223  if (substDegree[j-1] > 1)
224  tmp2= reverseSubst (tmp2, substDegree[j-1], Variable (j));
225  }
226  tmp= FpBiFactorize (tmp2, false);
227  tmp.removeFirst();
228  for (CFFListIterator j= tmp; j.hasItem(); j++)
229  newResult.append (CFFactor (j.getItem().factor(),
230  j.getItem().exp()*i.getItem().exp()));
231  }
232  decompress (newResult, N);
233  DELETE_ARRAY(substDegree);
234  return newResult;
235  }
236  DELETE_ARRAY(substDegree);
237  }
238 
239  CanonicalForm LcF= Lc (F);
240  CanonicalForm contentX= content (F, 1);
241  CanonicalForm contentY= content (F, 2);
242  F /= (contentX*contentY);
243  CFFList contentXFactors, contentYFactors;
244  contentXFactors= factorize (contentX);
245  contentYFactors= factorize (contentY);
246  if (contentXFactors.getFirst().factor().inCoeffDomain())
247  contentXFactors.removeFirst();
248  if (contentYFactors.getFirst().factor().inCoeffDomain())
249  contentYFactors.removeFirst();
250  decompress (contentXFactors, N);
251  decompress (contentYFactors, N);
252  CFFList result;
253  if (F.inCoeffDomain())
254  {
255  result= Union (contentXFactors, contentYFactors);
256  normalize (result);
257  result.insert (CFFactor (LcF, 1));
258  return result;
259  }
260  mpz_t * M=new mpz_t [4];
261  mpz_init (M[0]);
262  mpz_init (M[1]);
263  mpz_init (M[2]);
264  mpz_init (M[3]);
265 
266  mpz_t * S=new mpz_t [2];
267  mpz_init (S[0]);
268  mpz_init (S[1]);
269 
270  F= compress (F, M, S);
271 
272  TIMING_START (fac_fq_bi_sqrf);
273  CFFList sqrf= FpSqrf (F, false);
274  TIMING_END_AND_PRINT (fac_fq_bi_sqrf,
275  "time for bivariate sqrf factors over Fp: ");
276  CFList bufResult;
277  sqrf.removeFirst();
279  for (CFFListIterator iter= sqrf; iter.hasItem(); iter++)
280  {
281  TIMING_START (fac_fq_bi_factor_sqrf);
282  bufResult= biFactorize (iter.getItem().factor(), info);
283  TIMING_END_AND_PRINT (fac_fq_bi_factor_sqrf,
284  "time to factor bivariate sqrf factors over Fp: ");
285  for (i= bufResult; i.hasItem(); i++)
286  result.append (CFFactor (N (decompress (i.getItem(), M, S)),
287  iter.getItem().exp()));
288  }
289 
290  result= Union (result, contentXFactors);
291  result= Union (result, contentYFactors);
292  normalize (result);
293  result.insert (CFFactor (LcF, 1));
294 
295  mpz_clear (M[0]);
296  mpz_clear (M[1]);
297  mpz_clear (M[2]);
298  mpz_clear (M[3]);
299  delete [] M;
300 
301  mpz_clear (S[0]);
302  mpz_clear (S[1]);
303  delete [] S;
304 
305  return result;
306 }
307 #endif
308 
309 /// factorize a bivariate polynomial over \f$ F_{p}(\alpha ) \f$
310 ///
311 /// @return @a FqBiFactorize returns a list of monic factors with
312 /// multiplicity, the first element is the leading coefficient.
313 /// @sa FpBiFactorize(), FqBiFactorize()
314 #ifdef HAVE_NTL // biFactorize
315 inline
316 CFFList
317 FqBiFactorize (const CanonicalForm & G, ///< [in] a bivariate poly
318  const Variable & alpha, ///< [in] algebraic variable
319  bool substCheck= true ///< [in] enables substitute check
320  )
321 {
323  CFMap N;
324  CanonicalForm F= compress (G, N);
325 
326  if (substCheck)
327  {
328  bool foundOne= false;
329  int * substDegree= NEW_ARRAY(int,F.level());
330  for (int i= 1; i <= F.level(); i++)
331  {
332  substDegree[i-1]= substituteCheck (F, Variable (i));
333  if (substDegree [i-1] > 1)
334  {
335  foundOne= true;
336  subst (F, F, substDegree[i-1], Variable (i));
337  }
338  }
339  if (foundOne)
340  {
341  CFFList result= FqBiFactorize (F, alpha, false);
342  CFFList newResult, tmp;
344  newResult.insert (result.getFirst());
345  result.removeFirst();
346  for (CFFListIterator i= result; i.hasItem(); i++)
347  {
348  tmp2= i.getItem().factor();
349  for (int j= 1; j <= F.level(); j++)
350  {
351  if (substDegree[j-1] > 1)
352  tmp2= reverseSubst (tmp2, substDegree[j-1], Variable (j));
353  }
354  tmp= FqBiFactorize (tmp2, alpha, false);
355  tmp.removeFirst();
356  for (CFFListIterator j= tmp; j.hasItem(); j++)
357  newResult.append (CFFactor (j.getItem().factor(),
358  j.getItem().exp()*i.getItem().exp()));
359  }
360  decompress (newResult, N);
361  DELETE_ARRAY(substDegree);
362  return newResult;
363  }
364  DELETE_ARRAY(substDegree);
365  }
366 
367  CanonicalForm LcF= Lc (F);
368  CanonicalForm contentX= content (F, 1);
369  CanonicalForm contentY= content (F, 2);
370  F /= (contentX*contentY);
371  CFFList contentXFactors, contentYFactors;
372  contentXFactors= factorize (contentX, alpha);
373  contentYFactors= factorize (contentY, alpha);
374  if (contentXFactors.getFirst().factor().inCoeffDomain())
375  contentXFactors.removeFirst();
376  if (contentYFactors.getFirst().factor().inCoeffDomain())
377  contentYFactors.removeFirst();
378  decompress (contentXFactors, N);
379  decompress (contentYFactors, N);
380  CFFList result;
381  if (F.inCoeffDomain())
382  {
383  result= Union (contentXFactors, contentYFactors);
384  normalize (result);
385  result.insert (CFFactor (LcF, 1));
386  return result;
387  }
388 
389  mpz_t * M=new mpz_t [4];
390  mpz_init (M[0]);
391  mpz_init (M[1]);
392  mpz_init (M[2]);
393  mpz_init (M[3]);
394 
395  mpz_t * S=new mpz_t [2];
396  mpz_init (S[0]);
397  mpz_init (S[1]);
398 
399  F= compress (F, M, S);
400 
401  TIMING_START (fac_fq_bi_sqrf);
402  CFFList sqrf= FqSqrf (F, alpha, false);
403  TIMING_END_AND_PRINT (fac_fq_bi_sqrf,
404  "time for bivariate sqrf factors over Fq: ");
405  CFList bufResult;
406  sqrf.removeFirst();
408  for (CFFListIterator iter= sqrf; iter.hasItem(); iter++)
409  {
410  TIMING_START (fac_fq_bi_factor_sqrf);
411  bufResult= biFactorize (iter.getItem().factor(), info);
412  TIMING_END_AND_PRINT (fac_fq_bi_factor_sqrf,
413  "time to factor bivariate sqrf factors over Fq: ");
414  for (i= bufResult; i.hasItem(); i++)
415  result.append (CFFactor (N (decompress (i.getItem(), M, S)),
416  iter.getItem().exp()));
417  }
418 
419  result= Union (result, contentXFactors);
420  result= Union (result, contentYFactors);
421  normalize (result);
422  result.insert (CFFactor (LcF, 1));
423 
424  mpz_clear (M[0]);
425  mpz_clear (M[1]);
426  mpz_clear (M[2]);
427  mpz_clear (M[3]);
428  delete [] M;
429 
430  mpz_clear (S[0]);
431  mpz_clear (S[1]);
432  delete [] S;
433 
434  return result;
435 }
436 #endif
437 
438 /// factorize a bivariate polynomial over GF
439 ///
440 /// @return @a GFBiFactorize returns a list of monic factors with
441 /// multiplicity, the first element is the leading coefficient.
442 /// @sa FpBiFactorize(), FqBiFactorize()
443 #ifdef HAVE_NTL // biFactorize
444 inline
445 CFFList
446 GFBiFactorize (const CanonicalForm & G, ///< [in] a bivariate poly
447  bool substCheck= true ///< [in] enables substitute check
448  )
449 {
451  "GF as base field expected");
453  CFMap N;
454  CanonicalForm F= compress (G, N);
455 
456  if (substCheck)
457  {
458  bool foundOne= false;
459  int * substDegree=NEW_ARRAY(int,F.level());
460  for (int i= 1; i <= F.level(); i++)
461  {
462  substDegree[i-1]= substituteCheck (F, Variable (i));
463  if (substDegree [i-1] > 1)
464  {
465  foundOne= true;
466  subst (F, F, substDegree[i-1], Variable (i));
467  }
468  }
469  if (foundOne)
470  {
471  CFFList result= GFBiFactorize (F, false);
472  CFFList newResult, tmp;
474  newResult.insert (result.getFirst());
475  result.removeFirst();
476  for (CFFListIterator i= result; i.hasItem(); i++)
477  {
478  tmp2= i.getItem().factor();
479  for (int j= 1; j <= F.level(); j++)
480  {
481  if (substDegree[j-1] > 1)
482  tmp2= reverseSubst (tmp2, substDegree[j-1], Variable (j));
483  }
484  tmp= GFBiFactorize (tmp2, false);
485  tmp.removeFirst();
486  for (CFFListIterator j= tmp; j.hasItem(); j++)
487  newResult.append (CFFactor (j.getItem().factor(),
488  j.getItem().exp()*i.getItem().exp()));
489  }
490  decompress (newResult, N);
491  DELETE_ARRAY(substDegree);
492  return newResult;
493  }
494  DELETE_ARRAY(substDegree);
495  }
496 
497  CanonicalForm LcF= Lc (F);
498  CanonicalForm contentX= content (F, 1);
499  CanonicalForm contentY= content (F, 2);
500  F /= (contentX*contentY);
501  CFFList contentXFactors, contentYFactors;
502  contentXFactors= factorize (contentX);
503  contentYFactors= factorize (contentY);
504  if (contentXFactors.getFirst().factor().inCoeffDomain())
505  contentXFactors.removeFirst();
506  if (contentYFactors.getFirst().factor().inCoeffDomain())
507  contentYFactors.removeFirst();
508  decompress (contentXFactors, N);
509  decompress (contentYFactors, N);
510  CFFList result;
511  if (F.inCoeffDomain())
512  {
513  result= Union (contentXFactors, contentYFactors);
514  normalize (result);
515  result.insert (CFFactor (LcF, 1));
516  return result;
517  }
518 
519  mpz_t * M=new mpz_t [4];
520  mpz_init (M[0]);
521  mpz_init (M[1]);
522  mpz_init (M[2]);
523  mpz_init (M[3]);
524 
525  mpz_t * S=new mpz_t [2];
526  mpz_init (S[0]);
527  mpz_init (S[1]);
528 
529  F= compress (F, M, S);
530 
531  TIMING_START (fac_fq_bi_sqrf);
532  CFFList sqrf= GFSqrf (F, false);
533  TIMING_END_AND_PRINT (fac_fq_bi_sqrf,
534  "time for bivariate sqrf factors over GF: ");
535  CFList bufResult;
536  sqrf.removeFirst();
538  for (CFFListIterator iter= sqrf; iter.hasItem(); iter++)
539  {
540  TIMING_START (fac_fq_bi_factor_sqrf);
541  bufResult= biFactorize (iter.getItem().factor(), info);
542  TIMING_END_AND_PRINT (fac_fq_bi_factor_sqrf,
543  "time to factor bivariate sqrf factors over GF: ");
544  for (i= bufResult; i.hasItem(); i++)
545  result.append (CFFactor (N (decompress (i.getItem(), M, S)),
546  iter.getItem().exp()));
547  }
548 
549  result= Union (result, contentXFactors);
550  result= Union (result, contentYFactors);
551  normalize (result);
552  result.insert (CFFactor (LcF, 1));
553 
554  mpz_clear (M[0]);
555  mpz_clear (M[1]);
556  mpz_clear (M[2]);
557  mpz_clear (M[3]);
558  delete [] M;
559 
560  mpz_clear (S[0]);
561  mpz_clear (S[1]);
562  delete [] S;
563 
564  return result;
565 }
566 #endif
567 
568 /// \f$ \prod_{f\in L} {f (0, x)} \ mod\ M \f$ via divide-and-conquer
569 ///
570 /// @return @a prodMod0 computes the above defined product
571 /// @sa prodMod()
572 CanonicalForm prodMod0 (const CFList& L, ///< [in] a list of compressed,
573  ///< bivariate polynomials
574  const CanonicalForm& M,///< [in] a power of Variable (2)
575  const modpk& b= modpk()///< [in] coeff bound
576  );
577 
578 /// find an evaluation point p, s.t. F(p,y) is squarefree and
579 /// \f$ deg_{y} (F(p,y))= deg_{y} (F(x,y)) \f$.
580 ///
581 /// @return @a evalPoint returns an evaluation point, which is valid if and only
582 /// if fail == false.
584 evalPoint (const CanonicalForm& F, ///< [in] compressed, bivariate poly
585  CanonicalForm & eval, ///< [in,out] F (p, y)
586  const Variable& alpha, ///< [in] algebraic variable
587  CFList& list, ///< [in] list of points already considered
588  const bool& GF, ///< [in] GaloisFieldDomain?
589  bool& fail ///< [in,out] equals true, if there is no
590  ///< valid evaluation point
591  );
592 
593 /// Univariate factorization of squarefree monic polys over finite fields via
594 /// NTL. If the characteristic is even special GF2 routines of NTL are used.
595 ///
596 /// @return @a uniFactorizer returns a list of monic factors
597 CFList
598 uniFactorizer (const CanonicalForm& A, ///< [in] squarefree univariate poly
599  const Variable& alpha, ///< [in] algebraic variable
600  const bool& GF ///< [in] GaloisFieldDomain?
601  );
602 
603 /// naive factor recombination over an extension of the initial field.
604 /// Uses precomputed data to exclude combinations that are not possible.
605 ///
606 /// @return @a extFactorRecombination returns a list of factors over the initial
607 /// field, whose shift to zero is reversed.
608 /// @sa factorRecombination(), extEarlyFactorDetection()
609 CFList
611  CFList& factors, ///< [in,out] list of lifted factors that are
612  ///< monic wrt Variable (1),
613  ///< original factors-factors found
614  CanonicalForm& F, ///< [in,out] poly to be factored,
615  ///< F/factors found
616  const CanonicalForm& M, ///< [in] Variable (2)^liftBound
617  const ExtensionInfo& info,///< [in] contains information about
618  ///< extension
619  DegreePattern& degs,
620  const CanonicalForm& eval,///< [in] evaluation point
621  int s, ///< [in] algorithm starts checking subsets
622  ///< of size s
623  int thres ///< [in] threshold for the size of subsets
624  ///< which are checked, for a full factor
625  ///< recombination choose
626  ///< thres= factors.length()/2
627  );
628 
629 /// naive factor recombination.
630 /// Uses precomputed data to exclude combinations that are not possible.
631 ///
632 /// @return @a factorRecombination returns a list of factors of F.
633 /// @sa extFactorRecombination(), earlyFactorDetectection()
634 CFList
636  CFList& factors, ///< [in,out] list of lifted factors
637  ///< that are monic wrt Variable (1)
638  CanonicalForm& F, ///< [in,out] poly to be factored
639  const CanonicalForm& M, ///< [in] Variable (2)^liftBound
640  DegreePattern& degs, ///< [in] degree pattern
641  const CanonicalForm& eval, ///< [in] evaluation point
642  int s, ///< [in] algorithm starts checking
643  ///< subsets of size s
644  int thres, ///< [in] threshold for the size of
645  ///< subsets which are checked, for a
646  ///< full factor recombination choose
647  ///< thres= factors.length()/2
648  const modpk& b=modpk(), ///< [in] coeff bound
649  const CanonicalForm& den= 1 ///< [in] bound on the den if over Q (a)
650  );
651 
652 /// chooses a field extension.
653 ///
654 /// @return @a chooseExtension returns an extension specified by @a beta of
655 /// appropiate size
657  const Variable & alpha, ///< [in] some algebraic variable
658  const Variable & beta, ///< [in] some algebraic variable
659  int k ///< [in] some int
660  );
661 
662 /// compute lifting precisions from the shape of the Newton polygon of F
663 ///
664 /// @return @a getLiftPrecisions returns lifting precisions computed from the
665 /// shape of the Newton polygon of F
666 int *
667 getLiftPrecisions (const CanonicalForm& F, ///< [in] a bivariate poly
668  int& sizeOfOutput, ///< [in,out] size of the output
669  int degreeLC ///< [in] degree of the leading coeff
670  ///< [in] of F wrt. Variable (1)
671  );
672 
673 
674 /// detects factors of @a F at stage @a deg of Hensel lifting.
675 /// No combinations of more than one factor are tested. Lift bound and possible
676 /// degree pattern are updated.
677 ///
678 /// @sa factorRecombination(), extEarlyFactorDetection()
679 void
681  CFList& reconstructedFactors, ///< [in,out] list of reconstructed
682  ///< factors
683  CanonicalForm& F, ///< [in,out] poly to be factored, returns
684  ///< poly divided by detected factors in case
685  ///< of success
686  CFList& factors, ///< [in,out] list of factors lifted up to
687  ///< @a deg, returns a list of factors
688  ///< without detected factors
689  int& adaptedLiftBound, ///< [in,out] adapted lift bound
690  int*& factorsFoundIndex,///< [in,out] factors already considered
691  DegreePattern& degs, ///< [in,out] degree pattern, is updated
692  ///< whenever we find a factor
693  bool& success, ///< [in,out] indicating success
694  int deg, ///< [in] stage of Hensel lifting
695  const CanonicalForm& eval, ///<[in] evaluation point
696  const modpk& b= modpk()///< [in] coeff bound
697  );
698 
699 /// detects factors of @a F at stage @a deg of Hensel lifting.
700 /// No combinations of more than one factor are tested. Lift bound and possible
701 /// degree pattern are updated.
702 ///
703 /// @sa factorRecombination(), earlyFactorDetection()
704 void
706  CFList& reconstructedFactors, ///< [in,out] list of reconstructed
707  ///< factors
708  CanonicalForm& F, ///< [in,out] poly to be factored, returns
709  ///< poly divided by detected factors in case
710  ///< of success
711  CFList& factors, ///< [in,out] list of factors lifted up to
712  ///< @a deg, returns a list of factors
713  ///< without detected factors
714  int& adaptedLiftBound, ///< [in,out] adapted lift bound
715  int*& factorsFoundIndex, ///< [in,out] factors already considered
716  DegreePattern& degs, ///< [in,out] degree pattern, is updated
717  ///< whenever we find a factor
718  bool& success, ///< [in,out] indicating success
719  const ExtensionInfo& info, ///< [in] information about extension
720  const CanonicalForm& eval, ///< [in] evaluation point
721  int deg ///< [in] stage of Hensel lifting
722  );
723 
724 /// hensel Lifting and early factor detection
725 ///
726 /// @return @a henselLiftAndEarly returns monic (wrt Variable (1)) lifted
727 /// factors without factors which have been detected at an early stage
728 /// of Hensel lifting
729 /// @sa earlyFactorDetection(), extEarlyFactorDetection()
730 
731 CFList
733  CanonicalForm& A, ///< [in,out] poly to be factored,
734  ///< returns poly divided by detected factors
735  ///< in case of success
736  bool& earlySuccess, ///< [in,out] indicating success
737  CFList& earlyFactors, ///< [in,out] list of factors detected
738  ///< at early stage of Hensel lifting
739  DegreePattern& degs, ///< [in,out] degree pattern
740  int& liftBound, ///< [in,out] (adapted) lift bound
741  const CFList& uniFactors, ///< [in] univariate factors
742  const ExtensionInfo& info, ///< [in] information about extension
743  const CanonicalForm& eval, ///< [in] evaluation point
744  modpk& b, ///< [in] coeff bound
745  CanonicalForm& den ///< [in] bound on the den if over Q(a)
746  );
747 
748 /// hensel Lifting and early factor detection
749 ///
750 /// @return @a henselLiftAndEarly returns monic (wrt Variable (1)) lifted
751 /// factors without factors which have been detected at an early stage
752 /// of Hensel lifting
753 /// @sa earlyFactorDetection(), extEarlyFactorDetection()
754 
755 CFList
757  CanonicalForm& A, ///< [in,out] poly to be factored,
758  ///< returns poly divided by detected factors
759  ///< in case of success
760  bool& earlySuccess, ///< [in,out] indicating success
761  CFList& earlyFactors, ///< [in,out] list of factors detected
762  ///< at early stage of Hensel lifting
763  DegreePattern& degs, ///< [in,out] degree pattern
764  int& liftBound, ///< [in,out] (adapted) lift bound
765  const CFList& uniFactors, ///< [in] univariate factors
766  const ExtensionInfo& info, ///< [in] information about extension
767  const CanonicalForm& eval ///< [in] evaluation point
768  );
769 
770 /// Factorization over an extension of initial field
771 ///
772 /// @return @a extBiFactorize returns factorization of F over initial field
773 /// @sa biFactorize()
774 CFList
775 extBiFactorize (const CanonicalForm& F, ///< [in] poly to be factored
776  const ExtensionInfo& info ///< [in] info about extension
777  );
778 
779 #endif
780 #endif
781 /* FAC_FQ_BIVAR_H */
782 
This file provides a class to handle degree patterns.
This file provides a class to store information about finite fields and extensions thereof.
int getGFDegree()
Definition: cf_char.cc:75
CanonicalForm den(const CanonicalForm &f)
CanonicalForm Lc(const CanonicalForm &f)
CanonicalForm content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:603
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:56
static const double log2exp
Definition: cfEzgcd.cc:45
int i
Definition: cfEzgcd.cc:132
int k
Definition: cfEzgcd.cc:99
CanonicalForm b
Definition: cfModGcd.cc:4105
CanonicalForm decompress(const CanonicalForm &F, const mpz_t *inverseM, const mpz_t *A)
decompress a bivariate poly
This file provides functions to compute the Newton polygon of a bivariate polynomial.
declarations of higher level algorithms.
CFFList FACTORY_PUBLIC factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
Definition: cf_factor.cc:405
assertions for Factory
#define ASSERT(expression, message)
Definition: cf_assert.h:99
#define DELETE_ARRAY(P)
Definition: cf_defs.h:64
#define NEW_ARRAY(T, N)
Definition: cf_defs.h:63
#define GaloisFieldDomain
Definition: cf_defs.h:24
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m )
Definition: cf_map.cc:210
map polynomials
static int gettype()
Definition: cf_factory.h:28
class CFMap
Definition: cf_map.h:85
factory's main class
Definition: canonicalform.h:86
bool inCoeffDomain() const
int level() const
level() returns the level of CO.
DegreePattern provides a functionality to create, intersect and refine degree patterns.
Definition: DegreePattern.h:32
ExtensionInfo contains information about extension.
Definition: ExtensionInfo.h:51
int getGFDegree() const
getter
Variable getAlpha() const
getter
T & getItem() const
Definition: ftmpl_list.cc:431
T getFirst() const
Definition: ftmpl_list.cc:279
void removeFirst()
Definition: ftmpl_list.cc:287
void append(const T &)
Definition: ftmpl_list.cc:256
void insert(const T &)
Definition: ftmpl_list.cc:193
factory's class for variables
Definition: factory.h:134
int level() const
Definition: factory.h:150
class to do operations mod p^k for int's p and k
Definition: fac_util.h:23
CFFListIterator iter
Definition: facAbsBiFact.cc:53
Variable alpha
Definition: facAbsBiFact.cc:51
CanonicalForm LcF
Definition: facAbsBiFact.cc:50
return result
Definition: facAbsBiFact.cc:75
const CanonicalForm int s
Definition: facAbsFact.cc:51
Variable beta
Definition: facAbsFact.cc:95
TIMING_END_AND_PRINT(fac_alg_resultant, "time to compute resultant0: ")
TIMING_START(fac_alg_resultant)
CanonicalForm subst(const CanonicalForm &f, const CFList &a, const CFList &b, const CanonicalForm &Rstar, bool isFunctionField)
return modpk(p, k)
CFList & eval
Definition: facFactorize.cc:47
CanonicalForm reverseSubst(const CanonicalForm &F, const int d, const Variable &x)
reverse a substitution x^d->x
int substituteCheck(const CanonicalForm &F, const Variable &x)
check if a substitution x^n->x is possible
This file provides utility functions for bivariate factorization.
CFList tmp2
Definition: facFqBivar.cc:72
CFFList FqBiFactorize(const CanonicalForm &G, const Variable &alpha, bool substCheck=true)
factorize a bivariate polynomial over
Definition: facFqBivar.h:317
CFList biFactorize(const CanonicalForm &F, const ExtensionInfo &info)
Factorization of a squarefree bivariate polynomials over an arbitrary finite field,...
Definition: facFqBivar.cc:8303
void extEarlyFactorDetection(CFList &reconstructedFactors, CanonicalForm &F, CFList &factors, int &adaptedLiftBound, int *&factorsFoundIndex, DegreePattern &degs, bool &success, const ExtensionInfo &info, const CanonicalForm &eval, int deg)
detects factors of F at stage deg of Hensel lifting. No combinations of more than one factor are test...
Definition: facFqBivar.cc:982
CFList factorRecombination(CFList &factors, CanonicalForm &F, const CanonicalForm &M, DegreePattern &degs, const CanonicalForm &eval, int s, int thres, const modpk &b=modpk(), const CanonicalForm &den=1)
naive factor recombination. Uses precomputed data to exclude combinations that are not possible.
Definition: facFqBivar.cc:586
CFFList FpBiFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a bivariate polynomial over
Definition: facFqBivar.h:190
CFList extFactorRecombination(CFList &factors, CanonicalForm &F, const CanonicalForm &M, const ExtensionInfo &info, DegreePattern &degs, const CanonicalForm &eval, int s, int thres)
naive factor recombination over an extension of the initial field. Uses precomputed data to exclude c...
Definition: facFqBivar.cc:370
CFFList GFBiFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a bivariate polynomial over GF
Definition: facFqBivar.h:446
CFList FqBiSqrfFactorize(const CanonicalForm &G, const Variable &alpha)
factorize a squarefree bivariate polynomial over .
Definition: facFqBivar.h:156
CanonicalForm prodMod0(const CFList &L, const CanonicalForm &M, const modpk &b=modpk())
via divide-and-conquer
CFList biSqrfFactorizeHelper(const CanonicalForm &G, const ExtensionInfo &info)
Definition: facFqBivar.h:55
CFList extBiFactorize(const CanonicalForm &F, const ExtensionInfo &info)
Factorization over an extension of initial field.
Definition: facFqBivar.cc:8928
CFList FpBiSqrfFactorize(const CanonicalForm &G)
factorize a squarefree bivariate polynomial over .
Definition: facFqBivar.h:141
CanonicalForm evalPoint(const CanonicalForm &F, CanonicalForm &eval, const Variable &alpha, CFList &list, const bool &GF, bool &fail)
find an evaluation point p, s.t. F(p,y) is squarefree and .
Definition: facFqBivar.cc:84
CFList henselLiftAndEarly(CanonicalForm &A, bool &earlySuccess, CFList &earlyFactors, DegreePattern &degs, int &liftBound, const CFList &uniFactors, const ExtensionInfo &info, const CanonicalForm &eval, modpk &b, CanonicalForm &den)
hensel Lifting and early factor detection
Definition: facFqBivar.cc:1152
CFList GFBiSqrfFactorize(const CanonicalForm &G)
factorize a squarefree bivariate polynomial over GF
Definition: facFqBivar.h:172
CFList uniFactorizer(const CanonicalForm &A, const Variable &alpha, const bool &GF)
Univariate factorization of squarefree monic polys over finite fields via NTL. If the characteristic ...
Definition: facFqBivar.cc:160
Variable chooseExtension(const Variable &alpha, const Variable &beta, int k)
chooses a field extension.
Definition: facFqBivar.cc:806
TIMING_DEFINE_PRINT(fac_fq_bi_sqrf) TIMING_DEFINE_PRINT(fac_fq_bi_factor_sqrf) static const double log2exp
int * getLiftPrecisions(const CanonicalForm &F, int &sizeOfOutput, int degreeLC)
compute lifting precisions from the shape of the Newton polygon of F
Definition: facFqBivar.cc:1120
void earlyFactorDetection(CFList &reconstructedFactors, CanonicalForm &F, CFList &factors, int &adaptedLiftBound, int *&factorsFoundIndex, DegreePattern &degs, bool &success, int deg, const CanonicalForm &eval, const modpk &b=modpk())
detects factors of F at stage deg of Hensel lifting. No combinations of more than one factor are test...
Definition: facFqBivar.cc:971
const ExtensionInfo & info
< [in] sqrfree poly
This file provides functions for squarefrees factorizing over , or GF.
CFFList GFSqrf(const CanonicalForm &F, bool sort=true)
squarefree factorization over GF. 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 FpSqrf(const CanonicalForm &F, bool sort=true)
squarefree factorization over . If input is not monic, the leading coefficient is dropped
int j
Definition: facHensel.cc:110
operations mod p^k and some other useful functions for factorization
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
VAR char gf_name
Definition: gfops.cc:52
STATIC_VAR TreeM * G
Definition: janet.cc:31
#define A
Definition: sirandom.c:24
#define M
Definition: sirandom.c:25
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
Definition: syz3.cc:1026