My Project  debian-1:4.1.1-p2+ds-4build1
facFqFactorize.h
Go to the documentation of this file.
1 /*****************************************************************************\
2  * Computer Algebra System SINGULAR
3 \*****************************************************************************/
4 /** @file facFqFactorize.h
5  *
6  * This file provides functions for factorizing a multivariate 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_FACTORIZE_H
15 #define FAC_FQ_FACTORIZE_H
16 
17 // #include "config.h"
18 #include "timing.h"
19 
20 #include "facFqBivar.h"
21 #include "DegreePattern.h"
22 #include "ExtensionInfo.h"
23 #include "cf_util.h"
24 #include "facFqSquarefree.h"
25 #include "facFqBivarUtil.h"
26 
27 
28 TIMING_DEFINE_PRINT (fac_fq_squarefree)
29 TIMING_DEFINE_PRINT (fac_fq_factor_squarefree)
30 
31 /// Factorization over a finite field
32 ///
33 /// @return @a multiFactorize returns a factorization of F
34 /// @sa biFactorize(), extFactorize()
35 CFList
36 multiFactorize (const CanonicalForm& F, ///< [in] sqrfree poly
37  const ExtensionInfo& info ///< [in] info about extension
38  );
39 
40 /// factorize a squarefree multivariate polynomial over \f$ F_{p} \f$
41 ///
42 /// @return @a FpSqrfFactorize returns a list of monic factors, the first
43 /// element is the leading coefficient.
44 /// @sa FqSqrfFactorize(), GFSqrfFactorize()
45 #ifdef HAVE_NTL
46 inline
47 CFList FpSqrfFactorize (const CanonicalForm & F ///< [in] a multivariate poly
48  )
49 {
50  if (getNumVars (F) == 2)
51  return FpBiSqrfFactorize (F);
54  result.insert (Lc(F));
55  return result;
56 }
57 
58 /// factorize a squarefree multivariate polynomial over \f$ F_{p} (\alpha ) \f$
59 ///
60 /// @return @a FqSqrfFactorize returns a list of monic factors, the first
61 /// element is the leading coefficient.
62 /// @sa FpSqrfFactorize(), GFSqrfFactorize()
63 inline
64 CFList FqSqrfFactorize (const CanonicalForm & F, ///< [in] a multivariate poly
65  const Variable& alpha ///< [in] algebraic variable
66  )
67 {
68  if (getNumVars (F) == 2)
69  return FqBiSqrfFactorize (F, alpha);
72  result.insert (Lc(F));
73  return result;
74 }
75 
76 /// factorize a squarefree multivariate polynomial over GF
77 ///
78 /// @return @a GFSqrfFactorize returns a list of monic factors, the first
79 /// element is the leading coefficient.
80 /// @sa FpSqrfFactorize(), FqSqrfFactorize()
81 inline
82 CFList GFSqrfFactorize (const CanonicalForm & F ///< [in] a multivariate poly
83  )
84 {
86  "GF as base field expected");
87  if (getNumVars (F) == 2)
88  return GFBiSqrfFactorize (F);
91  result.insert (Lc(F));
92  return result;
93 }
94 
95 /// factorize a multivariate polynomial over \f$ F_{p} \f$
96 ///
97 /// @return @a FpFactorize returns a list of monic factors with
98 /// multiplicity, the first element is the leading coefficient.
99 /// @sa FqFactorize(), GFFactorize()
100 inline
101 CFFList FpFactorize (const CanonicalForm& G,///< [in] a multivariate poly
102  bool substCheck= true ///< [in] enables substitute check
103  )
104 {
105  if (getNumVars (G) == 2)
106  return FpBiFactorize (G, substCheck);
107 
108  CanonicalForm F= G;
109  if (substCheck)
110  {
111  bool foundOne= false;
112  int * substDegree= NEW_ARRAY(int,F.level());
113  for (int i= 1; i <= F.level(); i++)
114  {
115  if (degree (F, i) > 0)
116  {
117  substDegree[i-1]= substituteCheck (F, Variable (i));
118  if (substDegree [i-1] > 1)
119  {
120  foundOne= true;
121  subst (F, F, substDegree[i-1], Variable (i));
122  }
123  }
124  else
125  substDegree[i-1]= -1;
126  }
127  if (foundOne)
128  {
129  CFFList result= FpFactorize (F, false);
130  CFFList newResult, tmp;
132  newResult.insert (result.getFirst());
133  result.removeFirst();
134  for (CFFListIterator i= result; i.hasItem(); i++)
135  {
136  tmp2= i.getItem().factor();
137  for (int j= 1; j <= G.level(); j++)
138  {
139  if (substDegree[j-1] > 1)
140  tmp2= reverseSubst (tmp2, substDegree[j-1], Variable (j));
141  }
142  tmp= FpFactorize (tmp2, false);
143  tmp.removeFirst();
144  for (CFFListIterator j= tmp; j.hasItem(); j++)
145  newResult.append (CFFactor (j.getItem().factor(),
146  j.getItem().exp()*i.getItem().exp()));
147  }
148  DELETE_ARRAY(substDegree);
149  return newResult;
150  }
151  DELETE_ARRAY(substDegree);
152  }
153 
155  Variable a= Variable (1);
156  CanonicalForm LcF= Lc (F);
157  TIMING_START (fac_fq_squarefree);
158  CFFList sqrf= FpSqrf (F, false);
159  TIMING_END_AND_PRINT (fac_fq_squarefree,
160  "time for squarefree factorization over Fq: ");
161  CFFList result;
162  CFList bufResult;
163  sqrf.removeFirst();
165  for (CFFListIterator iter= sqrf; iter.hasItem(); iter++)
166  {
167  TIMING_START (fac_fq_factor_squarefree);
168  bufResult= multiFactorize (iter.getItem().factor(), info);
169  TIMING_END_AND_PRINT (fac_fq_factor_squarefree,
170  "time to factorize sqrfree factor over Fq: ");
171  for (i= bufResult; i.hasItem(); i++)
172  result.append (CFFactor (i.getItem(), iter.getItem().exp()));
173  }
174  result.insert (CFFactor (LcF, 1));
175  return result;
176 }
177 
178 /// factorize a multivariate polynomial over \f$ F_{p} (\alpha ) \f$
179 ///
180 /// @return @a FqFactorize returns a list of monic factors with
181 /// multiplicity, the first element is the leading coefficient.
182 /// @sa FpFactorize(), GFFactorize()
183 inline
184 CFFList FqFactorize (const CanonicalForm& G, ///< [in] a multivariate poly
185  const Variable& alpha, ///< [in] algebraic variable
186  bool substCheck= true ///< [in] enables substitute check
187  )
188 {
189  if (getNumVars (G) == 2)
190  return FqBiFactorize (G, alpha, substCheck);
191 
192  CanonicalForm F= G;
193  if (substCheck)
194  {
195  bool foundOne= false;
196  int * substDegree= NEW_ARRAY(int,F.level());
197  for (int i= 1; i <= F.level(); i++)
198  {
199  if (degree (F, i) > 0)
200  {
201  substDegree[i-1]= substituteCheck (F, Variable (i));
202  if (substDegree [i-1] > 1)
203  {
204  foundOne= true;
205  subst (F, F, substDegree[i-1], Variable (i));
206  }
207  }
208  else
209  substDegree[i-1]= -1;
210  }
211  if (foundOne)
212  {
213  CFFList result= FqFactorize (F, alpha, 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 <= G.level(); j++)
222  {
223  if (substDegree[j-1] > 1)
224  tmp2= reverseSubst (tmp2, substDegree[j-1], Variable (j));
225  }
226  tmp= FqFactorize (tmp2, alpha, 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  DELETE_ARRAY(substDegree);
233  return newResult;
234  }
235  DELETE_ARRAY(substDegree);
236  }
237 
239  CanonicalForm LcF= Lc (F);
240  TIMING_START (fac_fq_squarefree);
241  CFFList sqrf= FqSqrf (F, alpha, false);
242  TIMING_END_AND_PRINT (fac_fq_squarefree,
243  "time for squarefree factorization over Fq: ");
244  CFFList result;
245  CFList bufResult;
246  sqrf.removeFirst();
248  for (CFFListIterator iter= sqrf; iter.hasItem(); iter++)
249  {
250  TIMING_START (fac_fq_factor_squarefree);
251  bufResult= multiFactorize (iter.getItem().factor(), info);
252  TIMING_END_AND_PRINT (fac_fq_factor_squarefree,
253  "time to factorize sqrfree factor over Fq: ");
254  for (i= bufResult; i.hasItem(); i++)
255  result.append (CFFactor (i.getItem(), iter.getItem().exp()));
256  }
257  result.insert (CFFactor (LcF, 1));
258  return result;
259 }
260 
261 /// factorize a multivariate polynomial over GF
262 ///
263 /// @return @a GFFactorize returns a list of monic factors with
264 /// multiplicity, the first element is the leading coefficient.
265 /// @sa FpFactorize(), FqFactorize()
266 inline
267 CFFList GFFactorize (const CanonicalForm& G, ///< [in] a multivariate poly
268  bool substCheck= true ///< [in] enables substitute check
269  )
270 {
272  "GF as base field expected");
273  if (getNumVars (G) == 2)
274  return GFBiFactorize (G, substCheck);
275 
276  CanonicalForm F= G;
277  if (substCheck)
278  {
279  bool foundOne= false;
280  int * substDegree= NEW_ARRAY(int,F.level());
281  for (int i= 1; i <= F.level(); i++)
282  {
283  if (degree (F, i) > 0)
284  {
285  substDegree[i-1]= substituteCheck (F, Variable (i));
286  if (substDegree [i-1] > 1)
287  {
288  foundOne= true;
289  subst (F, F, substDegree[i-1], Variable (i));
290  }
291  }
292  else
293  substDegree[i-1]= -1;
294  }
295  if (foundOne)
296  {
297  CFFList result= GFFactorize (F, false);
298  CFFList newResult, tmp;
300  newResult.insert (result.getFirst());
301  result.removeFirst();
302  for (CFFListIterator i= result; i.hasItem(); i++)
303  {
304  tmp2= i.getItem().factor();
305  for (int j= 1; j <= G.level(); j++)
306  {
307  if (substDegree[j-1] > 1)
308  tmp2= reverseSubst (tmp2, substDegree[j-1], Variable (j));
309  }
310  tmp= GFFactorize (tmp2, false);
311  tmp.removeFirst();
312  for (CFFListIterator j= tmp; j.hasItem(); j++)
313  newResult.append (CFFactor (j.getItem().factor(),
314  j.getItem().exp()*i.getItem().exp()));
315  }
316  DELETE_ARRAY(substDegree);
317  return newResult;
318  }
319  DELETE_ARRAY(substDegree);
320  }
321 
322  Variable a= Variable (1);
324  CanonicalForm LcF= Lc (F);
325  CFFList sqrf= GFSqrf (F, false);
326  CFFList result;
327  CFList bufResult;
328  sqrf.removeFirst();
330  for (CFFListIterator iter= sqrf; iter.hasItem(); iter++)
331  {
332  bufResult= multiFactorize (iter.getItem().factor(), info);
333  for (i= bufResult; i.hasItem(); i++)
334  result.append (CFFactor (i.getItem(), iter.getItem().exp()));
335  }
336  result.insert (CFFactor (LcF, 1));
337  return result;
338 }
339 
340 #endif
341 
342 /// Naive factor recombination for multivariate factorization over an extension
343 /// of the initial field. No precomputed is used to exclude combinations.
344 ///
345 /// @return @a extFactorRecombination returns a list of factors of @a F, whose
346 /// shift to zero is reversed.
347 /// @sa factorRecombination()
348 CFList
350  const CFList& factors, ///< [in] list of lifted factors
351  ///< that are monic wrt Variable (1)
352  const CanonicalForm& F, ///< [in] poly to be factored
353  const CFList& M, ///< [in] a list of powers of
354  ///< Variables
355  const ExtensionInfo& info, ///< [in] info about extension
356  const CFList& evaluation ///< [in] evaluation point
357  );
358 
359 /// Naive factor recombination for multivariate factorization.
360 /// No precomputed is used to exclude combinations.
361 ///
362 /// @return @a factorRecombination returns a list of factors of @a F
363 /// @sa extFactorRecombination()
364 CFList
365 factorRecombination (const CanonicalForm& F,///< [in] poly to be factored
366  const CFList& factors, ///< [in] list of lifted factors
367  ///< that are monic wrt Variable (1)
368  const CFList& M ///< [in] a list of powers of
369  ///< Variables
370  );
371 
372 /// recombination of bivariate factors @a factors1 s. t. the result evaluated
373 /// at @a evalPoint coincides with @a factors2
374 CFList
375 recombination (const CFList& factors1, ///<[in] list of bivariate factors
376  const CFList& factors2, ///<[in] list univariate factors
377  int s, ///<[in] algorithm starts checking
378  ///< subsets of size s
379  int thres, ///<[in] threshold for the size of
380  ///< subsets which are checked
381  const CanonicalForm& evalPoint,///<[in] evaluation point
382  const Variable& x ///<[in] second variable of
383  ///< bivariate factors
384  );
385 
386 /// Lift bound adaption. Essentially an early factor detection but only the lift
387 /// bound is adapted.
388 ///
389 /// @return @a liftBoundAdaption returns an adapted lift bound.
390 /// @sa earlyFactorDetect(), earlyFactorDetection()
391 int
392 liftBoundAdaption (const CanonicalForm& F, ///< [in] a poly
393  const CFList& factors, ///< [in] list of list of lifted
394  ///< factors that are monic wrt
395  ///< Variable (1)
396  bool& success, ///< [in,out] indicates that no
397  ///< further lifting is necessary
398  const int deg, ///< [in] stage of Hensel lifting
399  const CFList& MOD, ///< [in] a list of powers of
400  ///< Variables
401  const int bound ///< [in] initial lift bound
402  );
403 
404 /// Lift bound adaption over an extension of the initial field. Essentially an
405 ///early factor detection but only the lift bound is adapted.
406 ///
407 /// @return @a liftBoundAdaption returns an adapted lift bound.
408 /// @sa earlyFactorDetect(), earlyFactorDetection()
409 int
411  const CanonicalForm& F, ///< [in] a poly
412  const CFList& factors, ///< [in] list of list of lifted
413  ///< factors that are monic wrt
414  bool& success, ///< [in,out] indicates that no further
415  ///< lifting is necessary
416  const ExtensionInfo& info, ///< [in] info about extension
417  const CFList& eval, ///< [in] evaluation point
418  const int deg, ///< [in] stage of Hensel lifting
419  const CFList& MOD, ///< [in] a list of powers of
420  ///< Variables
421  const int bound ///< [in] initial lift bound
422  );
423 
424 /// detects factors of @a F at stage @a deg of Hensel lifting.
425 /// No combinations of more than one factor are tested. Lift bound is adapted.
426 ///
427 /// @return @a earlyFactorDetect returns a list of factors of F (possibly
428 /// incomplete), in case of success. Otherwise an empty list.
429 /// @sa factorRecombination(), extEarlyFactorDetect()
430 CFList
432  CanonicalForm& F, ///< [in,out] poly to be factored,
433  ///< returns poly divided by detected
434  ///< factors in case of success
435  CFList& factors, ///< [in,out] list of factors lifted up
436  ///< to @a deg, returns a list of factors
437  ///< without detected factors
438  int& adaptedLiftBound, ///< [in,out] adapted lift bound
439  bool& success, ///< [in,out] indicating success
440  const int deg, ///< [in] stage of Hensel lifting
441  const CFList& MOD, ///< [in] a list of powers of
442  ///< Variables
443  const int bound ///< [in] initial lift bound
444  );
445 
446 /// detects factors of @a F at stage @a deg of Hensel lifting.
447 /// No combinations of more than one factor are tested. Lift bound is adapted.
448 ///
449 /// @return @a extEarlyFactorDetect returns a list of factors of F (possibly
450 /// incomplete), whose shift to zero is reversed, in case of success.
451 /// Otherwise an empty list.
452 /// @sa factorRecombination(), earlyFactorDetection()
453 CFList
455  CanonicalForm& F, ///< [in,out] poly to be factored,
456  ///< returns poly divided by detected
457  ///< factors in case of success
458  CFList& factors, ///< [in,out] list of factors lifted up
459  ///< to @a deg, returns a list of factors
460  ///< without detected factors
461  int& adaptedLiftBound, ///< [in,out] adapted lift bound
462  bool& success, ///< [in,out] indicating succes
463  const ExtensionInfo& info, ///< [in] info about extension
464  const CFList& eval, ///< [in] evaluation point
465  const int deg, ///< [in] stage of Hensel lifting
466  const CFList& MOD, ///< [in] a list of powers of Variables
467  const int bound ///< [in] initial lift bound
468  );
469 
470 /// evaluation point search for multivariate factorization,
471 /// looks for a (F.level() - 1)-tuple such that the resulting univariate
472 /// polynomial has main variable Variable (1), is squarefree and its degree
473 /// coincides with degree(F) and the bivariate one is primitive wrt.
474 /// Variable(1), and successively evaluated polynomials have the same degree in
475 /// their main variable as F has, fails if there are no valid evaluation points,
476 /// eval contains the intermediate evaluated polynomials.
477 ///
478 /// @return @a evalPoints returns an evaluation point, which is valid if and
479 /// only if fail == false.
480 CFList
481 evalPoints (const CanonicalForm& F, ///< [in] a compressed poly
482  CFList & eval, ///< [in,out] an empty list, returns @a F
483  ///< successive evaluated
484  const Variable& alpha, ///< [in] algebraic variable
485  CFList& list, ///< [in,out] a list of points already
486  ///< considered, a point is encoded as a
487  ///< poly of degree F.level()-1 in
488  ///< Variable(1)
489  const bool& GF, ///< [in] GF?
490  bool& fail ///< [in,out] indicates failure
491  );
492 
493 /// hensel Lifting and early factor detection
494 ///
495 /// @return @a henselLiftAndEarly returns monic (wrt Variable (1)) lifted
496 /// factors without factors which have been detected at an early stage
497 /// of Hensel lifting
498 /// @sa earlyFactorDetectn(), extEarlyFactorDetect()
499 CFList
501  CanonicalForm& A, ///< [in,out] poly to be factored,
502  ///< returns poly divided by detected
503  ///< factors, in case of success
504  CFList& MOD, ///< [in,out] a list of powers of
505  ///< Variables
506  int*& liftBounds, ///< [in,out] initial lift bounds, returns
507  ///< adapted lift bounds
508  bool& earlySuccess, ///< [in,out] indicating success
509  CFList& earlyFactors, ///< [in,out] early factors
510  const CFList& Aeval, ///< [in] @a A successively evaluated at
511  ///< elements of @a evaluation
512  const CFList& biFactors, ///< [in] bivariate factors
513  const CFList& evaluation, ///< [in] evaluation point
514  const ExtensionInfo& info ///< [in] info about extension
515  );
516 
517 /// Factorization over an extension of initial field
518 ///
519 /// @return @a extFactorize returns factorization of F over initial field
520 /// @sa extBiFactorize(), multiFactorize()
521 CFList
522 extFactorize (const CanonicalForm& F, ///< [in] poly to be factored
523  const ExtensionInfo& info ///< [in] info about extension
524  );
525 
526 /// compute the LCM of the contents of @a A wrt to each variable occuring in @a
527 /// A.
528 ///
529 /// @return @a lcmContent returns the LCM of the contents of @a A wrt to each
530 /// variable occuring in @a A.
532 lcmContent (const CanonicalForm& A, ///< [in] a compressed multivariate poly
533  CFList& contentAi ///< [in,out] an empty list, returns a list
534  ///< of the contents of @a A wrt to each
535  ///< variable occuring in @a A starting from
536  ///< @a A.mvar().
537  );
538 
539 /// compress a polynomial s.t. \f$ deg_{x_{i}} (F) >= deg_{x_{i+1}} (F) \f$ and
540 /// no gaps between the variables occur
541 ///
542 /// @return a compressed poly with the above properties
543 CanonicalForm myCompress (const CanonicalForm& F, ///< [in] a poly
544  CFMap& N ///< [in,out] a map to
545  ///< decompress
546  );
547 
548 /// evaluate a poly A with main variable at level 1 at an evaluation point in
549 /// K^(n-1) wrt different second variables. If this evaluation is valid (see
550 /// evalPoints) then Aeval contains A successively evaluated at this point,
551 /// otherwise this entry is empty
552 void
554  CFList*& Aeval, ///<[in,out] an array of length n-2
555  ///< if variable at level i > 2
556  ///< admits a valid evaluation
557  ///< this entry contains A
558  ///< successively evaluated at this
559  ///< point otherwise an empty list
560  const CFList& evaluation,///<[in] a valid evaluation point
561  ///< for main variable at level 1
562  ///< and second variable at level 2
563  const CanonicalForm& A ///<[in] some poly
564  );
565 
566 /// refine a bivariate factorization of A with l factors to one with
567 /// minFactorsLength if possible
568 void
569 refineBiFactors (const CanonicalForm& A, ///< [in] some poly
570  CFList& biFactors, ///< [in,out] list of bivariate to be
571  ///< refined, returns refined factors
572  CFList* const& factors, ///< [in] list of bivariate
573  ///< factorizations of A wrt different
574  ///< second variables
575  const CFList& evaluation,///< [in] the evaluation point
576  int minFactorsLength ///< [in] the minimal number of factors
577  );
578 
579 /// plug in evalPoint for y in a list of polys
580 ///
581 /// @return returns a list of the evaluated polys, these evaluated polys are
582 /// made monic
583 CFList
584 buildUniFactors (const CFList& biFactors, ///< [in] a list of polys
585  const CanonicalForm& evalPoint,///< [in] some evaluation point
586  const Variable& y ///< [in] some variable
587  );
588 
589 
590 /// sort bivariate factors in Aeval such that their corresponding univariate
591 /// factors coincide with uniFactors, uniFactors and biFactors may get
592 /// recombined if necessary
593 void sortByUniFactors (CFList*& Aeval, ///< [in,out] array of bivariate
594  ///< factors
595  int AevalLength, ///< [in] length of Aeval
596  CFList& uniFactors, ///< [in,out] univariate factors
597  CFList& biFactors, ///< [in,out] bivariate factors
598  const CFList& evaluation ///< [in] evaluation point
599  );
600 
601 /// extract leading coefficients wrt Variable(1) from bivariate factors obtained
602 /// from factorizations of A wrt different second variables
603 void
604 getLeadingCoeffs (const CanonicalForm& A, ///< [in] some poly
605  CFList*& Aeval ///< [in,out] array of bivariate
606  ///< factors, returns the leading
607  ///< coefficients of these factors
608  );
609 
610 /// normalize precomputed leading coefficients such that leading coefficients
611 /// evaluated at @a evaluation in K^(n-2) equal the leading coeffs wrt
612 /// Variable(1) of bivariate factors and change @a A and @a Aeval accordingly
613 void
614 prepareLeadingCoeffs (CFList*& LCs, ///<[in,out]
615  CanonicalForm& A, ///<[in,out]
616  CFList& Aeval, ///<[in,out]
617  int n, ///<[in] level of poly to be
618  ///< factored
619  const CFList& leadingCoeffs,///<[in] precomputed leading
620  ///< coeffs
621  const CFList& biFactors, ///<[in] bivariate factors
622  const CFList& evaluation ///<[in] evaluation point
623  );
624 
625 /// obtain factors of F by reconstructing their leading coeffs
626 ///
627 /// @return returns the reconstructed factors
628 /// @sa factorRecombination()
629 CFList
630 leadingCoeffReconstruction (const CanonicalForm& F,///<[in] poly to be factored
631  const CFList& factors, ///<[in] factors of f monic
632  ///< wrt Variable (1)
633  const CFList& M ///<[in] a list of powers of
634  ///< Variables
635  );
636 
637 /// distribute content
638 ///
639 /// @return returns a list result of polys such that prod (result)= prod (L)
640 /// but the first entry of L may be (partially) factorized and these factors
641 /// are distributed onto other entries in L
642 CFList
644  const CFList& L, ///<[in] list of polys, first
645  ///< entry the content to be
646  ///< distributed
647  const CFList* differentSecondVarFactors,///<[in] factorization wrt
648  ///< different second vars
649  int length ///<[in] length of
650  ///<differentSecondVarFactors
651  );
652 
653 /// gcd free basis of two lists of factors
654 void
655 gcdFreeBasis (CFFList& factors1, ///< [in,out] list of factors, returns gcd free
656  ///< factors
657  CFFList& factors2 ///< [in,out] list of factors, returns gcd free
658  ///< factors
659  );
660 
661 /// computes a list l of length length(LCFFactors)+1 of polynomials such that
662 /// prod (l)=LCF, note that the first entry of l may be non constant. Intended
663 /// to be used to precompute coefficients of a polynomial f from its bivariate
664 /// factorizations.
665 ///
666 /// @return see above
667 CFList
668 precomputeLeadingCoeff (const CanonicalForm& LCF, ///<[in] a multivariate
669  ///< poly
670  const CFList& LCFFactors, ///<[in] a list of
671  ///< univariate factors
672  ///< of LCF of level 2
673  const Variable& alpha, ///<[in] algebraic var.
674  const CFList& evaluation, ///<[in] an evaluation
675  ///< point having
676  ///< lSecondVarLCs+1
677  ///< components
678  CFList* & differentSecondVarLCs,///<[in] LCs of factors
679  ///< of f wrt different
680  ///< second variables
681  int lSecondVarLCs, ///<[in] length of the
682  ///< above
683  Variable& y ///<[in,out] if y.level()
684  ///< is not 1 on output
685  ///< the second variable
686  ///< has been changed to
687  ///< y
688  );
689 
690 /// changes the second variable to be @a w and updates all relevant data
691 void
692 changeSecondVariable (CanonicalForm& A, ///<[in,out] a multivariate poly
693  CFList& biFactors, ///<[in,out] bivariate factors
694  CFList& evaluation, ///<[in,out] evaluation point
695  CFList*& oldAeval, ///<[in,out] old bivariate factors
696  ///< wrt. different second vars
697  int lengthAeval2, ///<[in] length of oldAeval
698  const CFList& uniFactors,///<[in] univariate factors
699  const Variable& w ///<[in] some variable
700  );
701 
702 /// distributes a divisor LCmultiplier of LC(A,1) on the bivariate factors and
703 /// the precomputed leading coefficients
704 void
705 distributeLCmultiplier (CanonicalForm& A, ///<[in,out] some poly
706  CFList& leadingCoeffs, ///<[in,out] leading
707  ///< coefficients
708  CFList& biFactors, ///<[in,out] bivariate
709  ///< factors
710  const CFList& evaluation, ///<[in] eval. point
711  const CanonicalForm& LCmultipler///<[in] multiplier
712  );
713 
714 /// heuristic to distribute @a LCmultiplier onto factors based on the variables
715 /// that occur in @a LCmultiplier and in the leading coeffs of bivariate factors
716 void
717 LCHeuristic (CanonicalForm& A, ///<[in,out] a poly
718  const CanonicalForm& LCmultiplier,///<[in,out] divisor of LC (A,1)
719  CFList& biFactors, ///<[in,out] bivariate factors
720  CFList*& leadingCoeffs, ///<[in,out] leading coeffs
721  const CFList* oldAeval, ///<[in] bivariate factors wrt.
722  ///< different second vars
723  int lengthAeval, ///<[in] length of oldAeval
724  const CFList& evaluation, ///<[in] evaluation point
725  const CFList& oldBiFactors ///<[in] bivariate factors
726  ///< without LCmultiplier
727  ///< distributed on them
728  );
729 
730 /// checks if prod(LCs)==LC (oldA,1) and if so divides elements of leadingCoeffs
731 /// by elements in contents, sets A to oldA and sets foundTrueMultiplier to true
732 void
733 LCHeuristicCheck (const CFList& LCs, ///<[in] leading coeffs computed
734  const CFList& contents, ///<[in] content of factors
735  CanonicalForm& A, ///<[in,out] oldA*LCmultiplier^m
736  const CanonicalForm& oldA,///<[in] some poly
737  CFList& leadingCoeffs, ///<[in,out] leading coefficients
738  bool& foundTrueMultiplier ///<[in,out] success?
739  );
740 
741 /// heuristic to distribute @a LCmultiplier onto factors based on the contents
742 /// of @a factors. @a factors are assumed to come from LucksWangSparseHeuristic.
743 /// If not successful @a contents will contain the content of each element of @a
744 /// factors and @a LCs will contain the LC of each element of @a factors divided
745 /// by its content
746 void
747 LCHeuristic2 (const CanonicalForm& LCmultiplier,///<[in] divisor of LC (A,1)
748  const CFList& factors, ///<[in] result of
749  ///< LucksWangSparseHeuristic
750  CFList& leadingCoeffs, ///<[in,out] leading coeffs
751  CFList& contents, ///<[in,out] content of factors
752  CFList& LCs, ///<[in,out] LC of factors
753  ///< divided by content of
754  ///< factors
755  bool& foundTrueMultiplier ///<[in,out] success?
756  );
757 
758 /// heuristic to remove @a LCmultiplier from a factor based on the contents
759 /// of @a factors. @a factors are assumed to come from LucksWangSparseHeuristic.
760 void
761 LCHeuristic3 (const CanonicalForm& LCmultiplier,///<[in] divisor of LC (A,1)
762  const CFList& factors, ///<[in] result of
763  ///< LucksWangSparseHeuristic
764  const CFList& oldBiFactors, ///<[in] bivariate factors
765  ///< without LCmultiplier
766  ///< distributed on them
767  const CFList& contents, ///<[in] content of factors
768  const CFList* oldAeval, ///<[in] bivariate factors wrt.
769  ///< different second vars
770  CanonicalForm& A, ///<[in,out] poly
771  CFList*& leadingCoeffs, ///<[in,out] leading coeffs
772  int lengthAeval, ///<[in] length of oldAeval
773  bool& foundMultiplier ///<[in,out] success?
774  );
775 
776 /// heuristic to remove factors of @a LCmultiplier from @a factors.
777 /// More precisely checks if elements of @a contents divide @a LCmultiplier.
778 /// Assumes LCHeuristic3 is run before it and was successful.
779 void
780 LCHeuristic4 (const CFList& oldBiFactors, ///<[in] bivariate factors
781  ///< without LCmultiplier
782  ///< distributed on them
783  const CFList* oldAeval, ///<[in] bivariate factors wrt.
784  ///< different second vars
785  const CFList& contents, ///<[in] content of factors
786  const CFList& factors, ///<[in] result of
787  ///< LucksWangSparseHeuristic
788  const CanonicalForm& testVars,///<[in] product of second vars that
789  ///< occur among oldAeval
790  int lengthAeval, ///<[in] length of oldAeval
791  CFList*& leadingCoeffs, ///<[in,out] leading coeffs
792  CanonicalForm& A, ///<[in,out] poly
793  CanonicalForm& LCmultiplier, ///<[in,out] divisor of LC (A,1)
794  bool& foundMultiplier ///<[in] success?
795  );
796 
797 #endif
798 /* FAC_FQ_FACTORIZE_H */
timing.h
myCompress
CanonicalForm myCompress(const CanonicalForm &F, CFMap &N)
compress a polynomial s.t. and no gaps between the variables occur
Definition: facFqFactorize.cc:136
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
x
Variable x
Definition: cfModGcd.cc:4023
extLiftBoundAdaption
int extLiftBoundAdaption(const CanonicalForm &F, const CFList &factors, bool &success, const ExtensionInfo &info, const CFList &eval, const int deg, const CFList &MOD, const int bound)
Lift bound adaption over an extension of the initial field. Essentially an early factor detection but...
Definition: facFqFactorize.cc:509
y
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
result
return result
Definition: facAbsBiFact.cc:76
GFBiSqrfFactorize
CFList GFBiSqrfFactorize(const CanonicalForm &G)
factorize a squarefree bivariate polynomial over GF
Definition: facFqBivar.h:164
FqFactorize
CFFList FqFactorize(const CanonicalForm &G, const Variable &alpha, bool substCheck=true)
factorize a multivariate polynomial over
Definition: facFqFactorize.h:184
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
DELETE_ARRAY
#define DELETE_ARRAY(P)
Definition: cf_defs.h:49
CFFactory::gettype
static int gettype()
Definition: cf_factory.h:28
FpSqrfFactorize
CFList FpSqrfFactorize(const CanonicalForm &F)
factorize a squarefree multivariate polynomial over
Definition: facFqFactorize.h:47
CFMap
class CFMap
Definition: cf_map.h:84
sortByUniFactors
void sortByUniFactors(CFList *&Aeval, int AevalLength, CFList &uniFactors, CFList &biFactors, const CFList &evaluation)
sort bivariate factors in Aeval such that their corresponding univariate factors coincide with uniFac...
Definition: facFqFactorize.cc:2234
length
static BOOLEAN length(leftv result, leftv arg)
Definition: interval.cc:267
LCHeuristicCheck
void LCHeuristicCheck(const CFList &LCs, const CFList &contents, CanonicalForm &A, const CanonicalForm &oldA, CFList &leadingCoeffs, bool &foundTrueMultiplier)
checks if prod(LCs)==LC (oldA,1) and if so divides elements of leadingCoeffs by elements in contents,...
Definition: facFqFactorize.cc:2746
prepareLeadingCoeffs
void prepareLeadingCoeffs(CFList *&LCs, CanonicalForm &A, CFList &Aeval, int n, const CFList &leadingCoeffs, const CFList &biFactors, const CFList &evaluation)
normalize precomputed leading coefficients such that leading coefficients evaluated at evaluation in ...
Definition: facFqFactorize.cc:2365
N
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:48
leadingCoeffReconstruction
CFList leadingCoeffReconstruction(const CanonicalForm &F, const CFList &factors, const CFList &M)
obtain factors of F by reconstructing their leading coeffs
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
w
const CanonicalForm & w
Definition: facAbsFact.cc:55
TIMING_DEFINE_PRINT
TIMING_DEFINE_PRINT(fac_fq_squarefree) TIMING_DEFINE_PRINT(fac_fq_factor_squarefree) CFList multiFactorize(const CanonicalForm &F
Factorization over a finite field.
refineBiFactors
void refineBiFactors(const CanonicalForm &A, CFList &biFactors, CFList *const &factors, const CFList &evaluation, int minFactorsLength)
refine a bivariate factorization of A with l factors to one with minFactorsLength if possible
Definition: facFqFactorize.cc:2318
CanonicalForm
factory's main class
Definition: canonicalform.h:77
extFactorRecombination
CFList extFactorRecombination(const CFList &factors, const CanonicalForm &F, const CFList &M, const ExtensionInfo &info, const CFList &evaluation)
Naive factor recombination for multivariate factorization over an extension of the initial field....
Definition: facFqFactorize.cc:217
reverseSubst
CanonicalForm reverseSubst(const CanonicalForm &F, const int d, const Variable &x)
reverse a substitution x^d->x
Definition: facFqBivarUtil.cc:1295
minFactorsLength
CFList int & minFactorsLength
[in,out] minimal length of bivariate factors
Definition: facFactorize.h:31
evaluation
const CanonicalForm int const CFList & evaluation
Definition: facAbsFact.cc:55
GaloisFieldDomain
#define GaloisFieldDomain
Definition: cf_defs.h:22
factors2
const CFList & factors2
Definition: facFqBivarUtil.cc:42
FqSqrfFactorize
CFList FqSqrfFactorize(const CanonicalForm &F, const Variable &alpha)
factorize a squarefree multivariate polynomial over
Definition: facFqFactorize.h:64
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
precomputeLeadingCoeff
CFList precomputeLeadingCoeff(const CanonicalForm &LCF, const CFList &LCFFactors, const Variable &alpha, const CFList &evaluation, CFList *&differentSecondVarLCs, int lSecondVarLCs, Variable &y)
computes a list l of length length(LCFFactors)+1 of polynomials such that prod (l)=LCF,...
Definition: facFqFactorize.cc:1464
TIMING_START
TIMING_START(fac_alg_resultant)
Aeval
CFList *& Aeval
<[in] poly
Definition: facFactorize.h:31
recombination
CFList recombination(const CFList &factors1, const CFList &factors2, int s, int thres, const CanonicalForm &evalPoint, const Variable &x)
recombination of bivariate factors factors1 s. t. the result evaluated at evalPoint coincides with fa...
Definition: facFqFactorize.cc:2100
evalPoint
static void evalPoint(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &FEval, CanonicalForm &GEval, CFGenerator &evalPoint)
Definition: cfModResultant.cc:311
alpha
Variable alpha
Definition: facAbsBiFact.cc:52
cf_util.h
LcF
CanonicalForm LcF
Definition: facAbsBiFact.cc:51
DegreePattern.h
FpBiFactorize
CFFList FpBiFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a bivariate polynomial over
Definition: facFqBivar.h:180
distributeContent
CFList distributeContent(const CFList &L, const CFList *differentSecondVarFactors, int length)
distribute content
Definition: facFqFactorize.cc:1281
factorRecombination
CFList factorRecombination(const CanonicalForm &F, const CFList &factors, const CFList &M)
Naive factor recombination for multivariate factorization. No precomputed is used to exclude combinat...
Definition: facFqFactorize.cc:360
eval
CFList & eval
Definition: facFactorize.cc:48
extFactorize
CFList extFactorize(const CanonicalForm &F, const ExtensionInfo &info)
Factorization over an extension of initial field.
Definition: facFqFactorize.cc:3640
ListIterator::hasItem
int hasItem()
Definition: ftmpl_list.cc:439
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
getGFDegree
int getGFDegree()
Definition: cf_char.cc:56
Factor
Definition: ftmpl_factor.h:18
buildUniFactors
CFList buildUniFactors(const CFList &biFactors, const CanonicalForm &evalPoint, const Variable &y)
plug in evalPoint for y in a list of polys
Definition: facFqFactorize.cc:2304
multiFactorize
CFList multiFactorize(const CanonicalForm &F, const Variable &v)
Factorization over Q (a)
Definition: facFactorize.cc:194
LCHeuristic3
void LCHeuristic3(const CanonicalForm &LCmultiplier, const CFList &factors, const CFList &oldBiFactors, const CFList &contents, const CFList *oldAeval, CanonicalForm &A, CFList *&leadingCoeffs, int lengthAeval, bool &foundMultiplier)
heuristic to remove LCmultiplier from a factor based on the contents of factors. factors are assumed ...
Definition: facFqFactorize.cc:2792
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: ")
facFqBivarUtil.h
earlyFactorDetect
CFList earlyFactorDetect(CanonicalForm &F, CFList &factors, int &adaptedLiftBound, bool &success, const int deg, const CFList &MOD, const int bound)
detects factors of F at stage deg of Hensel lifting. No combinations of more than one factor are test...
Definition: facFqFactorize.cc:605
FpFactorize
CFFList FpFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a multivariate polynomial over
Definition: facFqFactorize.h:101
Variable
factory's class for variables
Definition: factory.h:117
evalPoints
CFList evalPoints(const CanonicalForm &F, CFList &eval, const Variable &alpha, CFList &list, const bool &GF, bool &fail)
evaluation point search for multivariate factorization, looks for a (F.level() - 1)-tuple such that t...
Definition: facFqFactorize.cc:740
ListIterator::getItem
T & getItem() const
Definition: ftmpl_list.cc:431
bound
static CanonicalForm bound(const CFMatrix &M)
Definition: cf_linsys.cc:460
getNumVars
int getNumVars(const CanonicalForm &f)
int getNumVars ( const CanonicalForm & f )
Definition: cf_ops.cc:314
ExtensionInfo
Definition: ExtensionInfo.h:50
evaluationWRTDifferentSecondVars
void evaluationWRTDifferentSecondVars(CFList *&Aeval, const CFList &evaluation, const CanonicalForm &A)
evaluate a poly A with main variable at level 1 at an evaluation point in K^(n-1) wrt different secon...
Definition: facFqFactorize.cc:1950
gcdFreeBasis
void gcdFreeBasis(CFFList &factors1, CFFList &factors2)
gcd free basis of two lists of factors
Definition: facFqFactorize.cc:1255
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
lcmContent
CanonicalForm lcmContent(const CanonicalForm &A, CFList &contentAi)
compute the LCM of the contents of A wrt to each variable occuring in A.
Definition: facFqFactorize.cc:954
GFSqrfFactorize
CFList GFSqrfFactorize(const CanonicalForm &F)
factorize a squarefree multivariate polynomial over GF
Definition: facFqFactorize.h:82
getLeadingCoeffs
void getLeadingCoeffs(const CanonicalForm &A, CFList *&Aeval)
extract leading coefficients wrt Variable(1) from bivariate factors obtained from factorizations of A...
Definition: facFqFactorize.cc:2216
GFFactorize
CFFList GFFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a multivariate polynomial over GF
Definition: facFqFactorize.h:267
distributeLCmultiplier
void distributeLCmultiplier(CanonicalForm &A, CFList &leadingCoeffs, CFList &biFactors, const CFList &evaluation, const CanonicalForm &LCmultipler)
distributes a divisor LCmultiplier of LC(A,1) on the bivariate factors and the precomputed leading co...
Definition: facFqFactorize.cc:2574
LCHeuristic2
void LCHeuristic2(const CanonicalForm &LCmultiplier, const CFList &factors, CFList &leadingCoeffs, CFList &contents, CFList &LCs, bool &foundTrueMultiplier)
heuristic to distribute LCmultiplier onto factors based on the contents of factors....
Definition: facFqFactorize.cc:2762
List< CanonicalForm >
s
const CanonicalForm int s
Definition: facAbsFact.cc:55
changeSecondVariable
void changeSecondVariable(CanonicalForm &A, CFList &biFactors, CFList &evaluation, CFList *&oldAeval, int lengthAeval2, const CFList &uniFactors, const Variable &w)
changes the second variable to be w and updates all relevant data
Definition: facFqFactorize.cc:2527
tmp2
CFList tmp2
Definition: facFqBivar.cc:70
LCHeuristic
void LCHeuristic(CanonicalForm &A, const CanonicalForm &LCmultiplier, CFList &biFactors, CFList *&leadingCoeffs, const CFList *oldAeval, int lengthAeval, const CFList &evaluation, const CFList &oldBiFactors)
heuristic to distribute LCmultiplier onto factors based on the variables that occur in LCmultiplier a...
Definition: facFqFactorize.cc:2598
henselLiftAndEarly
CFList henselLiftAndEarly(CanonicalForm &A, CFList &MOD, int *&liftBounds, bool &earlySuccess, CFList &earlyFactors, const CFList &Aeval, const CFList &biFactors, const CFList &evaluation, const ExtensionInfo &info)
hensel Lifting and early factor detection
Definition: facFqFactorize.cc:972
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
subst
CanonicalForm subst(const CanonicalForm &f, const CFList &a, const CFList &b, const CanonicalForm &Rstar, bool isFunctionField)
Definition: facAlgFuncUtil.cc:120
A
#define A
Definition: sirandom.c:23
info
const ExtensionInfo & info
< [in] sqrfree poly
Definition: facFqFactorize.h:38
LCHeuristic4
void LCHeuristic4(const CFList &oldBiFactors, const CFList *oldAeval, const CFList &contents, const CFList &factors, const CanonicalForm &testVars, int lengthAeval, CFList *&leadingCoeffs, CanonicalForm &A, CanonicalForm &LCmultiplier, bool &foundMultiplier)
heuristic to remove factors of LCmultiplier from factors. More precisely checks if elements of conten...
Definition: facFqFactorize.cc:2840
degree
int degree(const CanonicalForm &f)
Definition: canonicalform.h:309
List::insert
void insert(const T &)
Definition: ftmpl_list.cc:193
LCF
CanonicalForm LCF
Definition: facFactorize.cc:53
liftBoundAdaption
int liftBoundAdaption(const CanonicalForm &F, const CFList &factors, bool &success, const int deg, const CFList &MOD, const int bound)
Lift bound adaption. Essentially an early factor detection but only the lift bound is adapted.
Definition: facFqFactorize.cc:445
extEarlyFactorDetect
CFList extEarlyFactorDetect(CanonicalForm &F, CFList &factors, int &adaptedLiftBound, bool &success, const ExtensionInfo &info, const CFList &eval, const int deg, const CFList &MOD, const int bound)
detects factors of F at stage deg of Hensel lifting. No combinations of more than one factor are test...
Definition: facFqFactorize.cc:656
NEW_ARRAY
#define NEW_ARRAY(T, N)
Definition: cf_defs.h:48
ListIterator
Definition: ftmpl_list.h:17
facFqBivar.h