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);
108  CFList result= biFactorize (F, info);
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 {
154  ExtensionInfo info= ExtensionInfo (alpha, false);
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 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 [] substDegree;
224  return newResult;
225  }
226  delete [] 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 {
310  ExtensionInfo info= ExtensionInfo (alpha, false);
311  CFMap N;
312  CanonicalForm F= compress (G, N);
313 
314  if (substCheck)
315  {
316  bool foundOne= false;
317  int * substDegree= new 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 [] substDegree;
350  return newResult;
351  }
352  delete [] 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 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 [] substDegree;
478  return newResult;
479  }
480  delete [] 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 
const CanonicalForm int s
Definition: facAbsFact.cc:55
int level() const
Definition: factory.h:132
DegreePattern provides a functionality to create, intersect and refine degree patterns.
Definition: DegreePattern.h:31
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
Definition: syz3.cc:1028
bool inCoeffDomain() const
CFFList FpSqrf(const CanonicalForm &F, bool sort=true)
squarefree factorization over . If input is not monic, the leading coefficient is dropped ...
This file provides functions to compute the Newton polygon of a bivariate polynomial.
#define TIMING_END_AND_PRINT(t, msg)
Definition: timing.h:89
factory&#39;s class for variables
Definition: factory.h:115
CFFList GFBiFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a bivariate polynomial over GF
Definition: facFqBivar.h:432
CFFListIterator iter
Definition: facAbsBiFact.cc:54
CFList GFBiSqrfFactorize(const CanonicalForm &G)
factorize a squarefree bivariate polynomial over GF
Definition: facFqBivar.h:164
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
factory&#39;s main class
Definition: canonicalform.h:75
char gf_name
Definition: gfops.cc:52
assertions for Factory
CFFList FqSqrf(const CanonicalForm &F, const Variable &alpha, bool sort=true)
squarefree factorization over . If input is not monic, the leading coefficient is dropped ...
int k
Definition: cfEzgcd.cc:93
Variable alpha
Definition: facAbsBiFact.cc:52
CFList FqBiSqrfFactorize(const CanonicalForm &G, const Variable &alpha)
factorize a squarefree bivariate polynomial over .
Definition: facFqBivar.h:150
static const double log2exp
Definition: cfEzgcd.cc:40
CanonicalForm prodMod0(const CFList &L, const CanonicalForm &M, const modpk &b=modpk())
via divide-and-conquer
void insert(const T &)
Definition: ftmpl_list.cc:193
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
static TreeM * G
Definition: janet.cc:38
CanonicalForm Lc(const CanonicalForm &f)
Variable getAlpha() const
getter
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m )
Definition: cf_map.cc:210
CanonicalForm LcF
Definition: facAbsBiFact.cc:51
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
void removeFirst()
Definition: ftmpl_list.cc:287
map polynomials
CanonicalForm subst(const CanonicalForm &f, const CFList &a, const CFList &b, const CanonicalForm &Rstar, bool isFunctionField)
CanonicalForm content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:180
int level() const
level() returns the level of CO.
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
This file provides functions for squarefrees factorizing over , or GF.
return modpk(p, k)
#define M
Definition: sirandom.c:24
CFFList factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
Definition: cf_factor.cc:390
ExtensionInfo contains information about extension.
Definition: ExtensionInfo.h:50
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
CFFList GFSqrf(const CanonicalForm &F, bool sort=true)
squarefree factorization over GF. If input is not monic, the leading coefficient is dropped ...
TIMING_DEFINE_PRINT(fac_fq_bi_sqrf) TIMING_DEFINE_PRINT(fac_fq_bi_factor_sqrf) static const double log2exp
int getGFDegree() const
getter
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:49
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
int j
Definition: myNF.cc:70
CanonicalForm decompress(const CanonicalForm &F, const mpz_t *inverseM, const mpz_t *A)
decompress a bivariate poly
const ExtensionInfo & info
< [in] sqrfree poly
#define A
Definition: sirandom.c:23
CFList & eval
Definition: facFactorize.cc:48
CFFList FpBiFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a bivariate polynomial over
Definition: facFqBivar.h:180
int substituteCheck(const CanonicalForm &F, const Variable &x)
check if a substitution x^n->x is possible
CFList FpBiSqrfFactorize(const CanonicalForm &G)
factorize a squarefree bivariate polynomial over .
Definition: facFqBivar.h:137
T getFirst() const
Definition: ftmpl_list.cc:279
CFList biSqrfFactorizeHelper(const CanonicalForm &G, const ExtensionInfo &info)
Definition: facFqBivar.h:53
int i
Definition: cfEzgcd.cc:123
CFFList FqBiFactorize(const CanonicalForm &G, const Variable &alpha, bool substCheck=true)
factorize a bivariate polynomial over
Definition: facFqBivar.h:305
CFList extBiFactorize(const CanonicalForm &F, const ExtensionInfo &info)
Factorization over an extension of initial field.
Definition: facFqBivar.cc:8824
CFList tmp2
Definition: facFqBivar.cc:70
Variable beta
Definition: facAbsFact.cc:99
class CFMap
Definition: cf_map.h:84
This file provides utility functions for bivariate factorization.
static int gettype()
Definition: cf_factory.h:27
CanonicalForm den(const CanonicalForm &f)
T & getItem() const
Definition: ftmpl_list.cc:431
#define TIMING_START(t)
Definition: timing.h:87
int getGFDegree()
Definition: cf_char.cc:56
#define GaloisFieldDomain
Definition: cf_defs.h:22
This file provides a class to handle degree patterns.
CanonicalForm reverseSubst(const CanonicalForm &F, const int d, const Variable &x)
reverse a substitution x^d->x
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
#define const
Definition: fegetopt.c:41
#define ASSERT(expression, message)
Definition: cf_assert.h:99
operations mod p^k and some other useful functions for factorization
void append(const T &)
Definition: ftmpl_list.cc:256
Variable chooseExtension(const Variable &alpha, const Variable &beta, int k)
chooses a field extension.
Definition: facFqBivar.cc:780
CFList biFactorize(const CanonicalForm &F, const ExtensionInfo &info)
Factorization of a squarefree bivariate polynomials over an arbitrary finite field, information on the current field we work over is in info. info may also contain information about the initial field if initial and current field do not coincide. In this case the current field is an extension of the initial field and the factors returned are factors of F over the initial field.
Definition: facFqBivar.cc:8201
const poly b
Definition: syzextra.cc:213
class to do operations mod p^k for int&#39;s p and k
Definition: fac_util.h:22
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
return result
Definition: facAbsBiFact.cc:76
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
This file provides a class to store information about finite fields and extensions thereof...