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