My Project
Loading...
Searching...
No Matches
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
28TIMING_DEFINE_PRINT (fac_fq_squarefree)
29TIMING_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()
36multiFactorize (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
46inline
47CFList 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()
63inline
64CFList 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()
81inline
82CFList 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()
100inline
101CFFList 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: ");
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()
183inline
184CFFList 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: ");
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()
266inline
267CFFList 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);
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()
348CFList
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()
364CFList
365factorRecombination (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
374CFList
375recombination (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()
391int
392liftBoundAdaption (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()
409int
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()
430CFList
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()
453CFList
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.
480CFList
481evalPoints (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()
499CFList
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()
521CFList
522extFactorize (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.
532lcmContent (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
543CanonicalForm 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
552void
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
568void
569refineBiFactors (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
583CFList
584buildUniFactors (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
593void 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
603void
604getLeadingCoeffs (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
613void
614prepareLeadingCoeffs (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()
629CFList
630leadingCoeffReconstruction (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
642CFList
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
654void
655gcdFreeBasis (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
667CFList
668precomputeLeadingCoeff (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
691void
692changeSecondVariable (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
704void
705distributeLCmultiplier (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
716void
717LCHeuristic (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
732void
733LCHeuristicCheck (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
746void
747LCHeuristic2 (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.
760void
761LCHeuristic3 (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.
779void
780LCHeuristic4 (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 */
This file provides a class to handle degree patterns.
This file provides a class to store information about finite fields and extensions thereof.
int getNumVars(const CanonicalForm &f)
int getNumVars ( const CanonicalForm & f )
Definition: cf_ops.cc:314
int degree(const CanonicalForm &f)
int getGFDegree()
Definition: cf_char.cc:75
CanonicalForm Lc(const CanonicalForm &f)
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:56
int i
Definition: cfEzgcd.cc:132
Variable x
Definition: cfModGcd.cc:4082
static void evalPoint(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &FEval, CanonicalForm &GEval, CFGenerator &evalPoint)
#define ASSERT(expression, message)
Definition: cf_assert.h:99
#define DELETE_ARRAY(P)
Definition: cf_defs.h:65
#define NEW_ARRAY(T, N)
Definition: cf_defs.h:64
#define GaloisFieldDomain
Definition: cf_defs.h:18
static CanonicalForm bound(const CFMatrix &M)
Definition: cf_linsys.cc:460
static int gettype()
Definition: cf_factory.h:28
class CFMap
Definition: cf_map.h:85
factory's main class
Definition: canonicalform.h:86
int level() const
level() returns the level of CO.
ExtensionInfo contains information about extension.
Definition: ExtensionInfo.h:51
T & getItem() const
Definition: ftmpl_list.cc:431
void removeFirst()
Definition: ftmpl_list.cc:287
void append(const T &)
Definition: ftmpl_list.cc:256
void insert(const T &)
Definition: ftmpl_list.cc:193
factory's class for variables
Definition: variable.h:33
CFFListIterator iter
Definition: facAbsBiFact.cc:53
Variable alpha
Definition: facAbsBiFact.cc:51
CanonicalForm LcF
Definition: facAbsBiFact.cc:50
return result
Definition: facAbsBiFact.cc:75
const CanonicalForm int const CFList & evaluation
Definition: facAbsFact.cc:52
const CanonicalForm int s
Definition: facAbsFact.cc:51
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:53
const CanonicalForm & w
Definition: facAbsFact.cc:51
CanonicalForm subst(const CanonicalForm &f, const CFList &a, const CFList &b, const CanonicalForm &Rstar, bool isFunctionField)
CanonicalForm LCF
Definition: facFactorize.cc:52
CFList & eval
Definition: facFactorize.cc:47
CFList multiFactorize(const CanonicalForm &F, const Variable &v)
Factorization over Q (a)
CFList int & minFactorsLength
[in,out] minimal length of bivariate factors
Definition: facFactorize.h:33
CFList *& Aeval
<[in] poly
Definition: facFactorize.h:31
const CFList & factors2
CanonicalForm reverseSubst(const CanonicalForm &F, const int d, const Variable &x)
reverse a substitution x^d->x
int substituteCheck(const CanonicalForm &F, const Variable &x)
check if a substitution x^n->x is possible
This file provides utility functions for bivariate factorization.
CFList tmp2
Definition: facFqBivar.cc:72
This file provides functions for factorizing a bivariate polynomial over , or GF.
CFFList FqBiFactorize(const CanonicalForm &G, const Variable &alpha, bool substCheck=true)
factorize a bivariate polynomial over
Definition: facFqBivar.h:317
CFFList FpBiFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a bivariate polynomial over
Definition: facFqBivar.h:190
CFFList GFBiFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a bivariate polynomial over GF
Definition: facFqBivar.h:446
CFList FqBiSqrfFactorize(const CanonicalForm &G, const Variable &alpha)
factorize a squarefree bivariate polynomial over .
Definition: facFqBivar.h:156
CFList FpBiSqrfFactorize(const CanonicalForm &G)
factorize a squarefree bivariate polynomial over .
Definition: facFqBivar.h:141
CFList GFBiSqrfFactorize(const CanonicalForm &G)
factorize a squarefree bivariate polynomial over GF
Definition: facFqBivar.h:172
CFList FpSqrfFactorize(const CanonicalForm &F)
factorize a squarefree multivariate polynomial over
CFList factorRecombination(const CanonicalForm &F, const CFList &factors, const CFList &M)
Naive factor recombination for multivariate factorization. No precomputed is used to exclude combinat...
CFFList FpFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a multivariate polynomial over
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,...
const ExtensionInfo & info
< [in] sqrfree poly
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,...
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.
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...
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...
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
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 ...
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....
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...
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...
CanonicalForm myCompress(const CanonicalForm &F, CFMap &N)
compress a polynomial s.t. and no gaps between the variables occur
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
CFList distributeContent(const CFList &L, const CFList *differentSecondVarFactors, int length)
distribute content
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...
CFFList GFFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a multivariate polynomial over GF
CanonicalForm lcmContent(const CanonicalForm &A, CFList &contentAi)
compute the LCM of the contents of A wrt to each variable occuring in A.
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...
void gcdFreeBasis(CFFList &factors1, CFFList &factors2)
gcd free basis of two lists of factors
void getLeadingCoeffs(const CanonicalForm &A, CFList *&Aeval)
extract leading coefficients wrt Variable(1) from bivariate factors obtained from factorizations of A...
CFList GFSqrfFactorize(const CanonicalForm &F)
factorize a squarefree multivariate polynomial over GF
CFList extFactorize(const CanonicalForm &F, const ExtensionInfo &info)
Factorization over an extension of initial field.
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...
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 ...
CFFList FqFactorize(const CanonicalForm &G, const Variable &alpha, bool substCheck=true)
factorize a multivariate polynomial over
CFList FqSqrfFactorize(const CanonicalForm &F, const Variable &alpha)
factorize a squarefree multivariate polynomial over
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
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...
CFList leadingCoeffReconstruction(const CanonicalForm &F, const CFList &factors, const CFList &M)
obtain factors of F by reconstructing their leading coeffs
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....
CFList buildUniFactors(const CFList &biFactors, const CanonicalForm &evalPoint, const Variable &y)
plug in evalPoint for y in a list of polys
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...
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...
This file provides functions for squarefrees factorizing over , or GF.
CFFList GFSqrf(const CanonicalForm &F, bool sort=true)
squarefree factorization over GF. If input is not monic, the leading coefficient is dropped
CFFList FqSqrf(const CanonicalForm &F, const Variable &alpha, bool sort=true)
squarefree factorization over . If input is not monic, the leading coefficient is dropped
CFFList FpSqrf(const CanonicalForm &F, bool sort=true)
squarefree factorization over . If input is not monic, the leading coefficient is dropped
int j
Definition: facHensel.cc:110
VAR char gf_name
Definition: gfops.cc:52
static BOOLEAN length(leftv result, leftv arg)
Definition: interval.cc:257
STATIC_VAR TreeM * G
Definition: janet.cc:31
#define A
Definition: sirandom.c:24
#define M
Definition: sirandom.c:25
#define TIMING_DEFINE_PRINT(t)
Definition: timing.h:95
#define TIMING_START(t)
Definition: timing.h:92
#define TIMING_END_AND_PRINT(t, msg)
Definition: timing.h:94