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