My Project
Loading...
Searching...
No Matches
facFqFactorize.cc
Go to the documentation of this file.
1/*****************************************************************************\
2 * Computer Algebra System SINGULAR
3\*****************************************************************************/
4/** @file facFqFactorize.cc
5 *
6 * This file implements functions for factoring a multivariate polynomial over
7 * a finite field.
8 *
9 * ABSTRACT: "Efficient Multivariate Factorization over Finite Fields" by
10 * L. Bernardin & M. Monagon. Precomputation of leading coefficients is
11 * described in "Sparse Hensel lifting" by E. Kaltofen
12 *
13 * @author Martin Lee
14 *
15 **/
16/*****************************************************************************/
17
18
19#include "config.h"
20
21#include <math.h>
22
23#include "cf_assert.h"
24#include "debug.h"
25#include "timing.h"
26
27#include "facFqFactorizeUtil.h"
28#include "facFqFactorize.h"
29#include "cf_random.h"
30#include "facHensel.h"
31#include "cf_irred.h"
32#include "cf_map_ext.h"
33#include "facSparseHensel.h"
34#include "facMul.h"
35#include "cfUnivarGcd.h"
36
37TIMING_DEFINE_PRINT(fac_fq_bi_factorizer)
38TIMING_DEFINE_PRINT(fac_fq_hensel_lift)
39TIMING_DEFINE_PRINT(fac_fq_factor_recombination)
40TIMING_DEFINE_PRINT(fac_fq_shift_to_zero)
41TIMING_DEFINE_PRINT(fac_fq_precompute_leadcoeff)
42TIMING_DEFINE_PRINT(fac_fq_evaluation)
43TIMING_DEFINE_PRINT(fac_fq_recover_factors)
44TIMING_DEFINE_PRINT(fac_fq_preprocess_and_content)
45TIMING_DEFINE_PRINT(fac_fq_bifactor_total)
46TIMING_DEFINE_PRINT(fac_fq_luckswang)
47TIMING_DEFINE_PRINT(fac_fq_lcheuristic)
48TIMING_DEFINE_PRINT(fac_fq_content)
49TIMING_DEFINE_PRINT(fac_fq_check_mainvar)
50TIMING_DEFINE_PRINT(fac_fq_compress)
51
52
53static inline
55listGCD (const CFList& L);
56
57static inline
60{
61 Variable x= Variable (1);
62 CanonicalForm G= swapvar (F, F.mvar(), x);
63 CFList L;
64 for (CFIterator i= G; i.hasTerms(); i++)
65 L.append (i.coeff());
66 if (L.length() == 2)
67 return swapvar (gcd (L.getFirst(), L.getLast()), F.mvar(), x);
68 if (L.length() == 1)
69 return LC (F, x);
70 return swapvar (listGCD (L), F.mvar(), x);
71}
72
73static inline
75listGCD (const CFList& L)
76{
77 if (L.length() == 0)
78 return 0;
79 if (L.length() == 1)
80 return L.getFirst();
81 if (L.length() == 2)
82 return gcd (L.getFirst(), L.getLast());
83 else
84 {
85 CFList lHi, lLo;
86 CanonicalForm resultHi, resultLo;
87 int length= L.length()/2;
88 int j= 0;
89 for (CFListIterator i= L; j < length; i++, j++)
90 lHi.append (i.getItem());
91 lLo= Difference (L, lHi);
92 resultHi= listGCD (lHi);
93 resultLo= listGCD (lLo);
94 if (resultHi.isOne() || resultLo.isOne())
95 return 1;
96 return gcd (resultHi, resultLo);
97 }
98}
99
100static inline
103{
104 if (degree (F, x) <= 0)
105 return 1;
106 CanonicalForm G= F;
107 bool swap= false;
108 if (x != F.mvar())
109 {
110 swap= true;
111 G= swapvar (F, x, F.mvar());
112 }
113 CFList L;
115 for (CFIterator i= G; i.hasTerms(); i++)
116 L.append (i.coeff());
117 if (L.length() == 2)
118 {
119 if (swap)
120 return swapvar (gcd (L.getFirst(), L.getLast()), F.mvar(), x);
121 else
122 return gcd (L.getFirst(), L.getLast());
123 }
124 if (L.length() == 1)
125 {
126 return LC (F, x);
127 }
128 if (swap)
129 return swapvar (listGCD (L), F.mvar(), x);
130 else
131 return listGCD (L);
132}
133
135{
136 int n= F.level();
137 int * degsf= NEW_ARRAY(int,n + 1);
138 int ** swap= new int* [n + 1];
139 for (int i= 0; i <= n; i++)
140 {
141 degsf[i]= 0;
142 swap [i]= new int [3];
143 swap [i] [0]= 0;
144 swap [i] [1]= 0;
145 swap [i] [2]= 0;
146 }
147 int i= 1;
148 n= 1;
149 degsf= degrees (F, degsf);
150
152 while ( i <= F.level() )
153 {
154 while( degsf[i] == 0 ) i++;
155 swap[n][0]= i;
156 swap[n][1]= size (LC (F,i));
157 swap[n][2]= degsf [i];
158 if (i != n)
160 n++; i++;
161 }
162
163 int buf1, buf2, buf3;
164 n--;
165
166 for (i= 1; i < n; i++)
167 {
168 for (int j= 1; j < n - i + 1; j++)
169 {
170 if (swap[j][1] > swap[j + 1][1])
171 {
172 buf1= swap [j + 1] [0];
173 buf2= swap [j + 1] [1];
174 buf3= swap [j + 1] [2];
175 swap[j + 1] [0]= swap[j] [0];
176 swap[j + 1] [1]= swap[j] [1];
177 swap[j + 1] [2]= swap[j] [2];
178 swap[j][0]= buf1;
179 swap[j][1]= buf2;
180 swap[j][2]= buf3;
181 result= swapvar (result, Variable (j + 1), Variable (j));
182 }
183 else if (swap[j][1] == swap[j + 1][1] && swap[j][2] < swap[j + 1][2])
184 {
185 buf1= swap [j + 1] [0];
186 buf2= swap [j + 1] [1];
187 buf3= swap [j + 1] [2];
188 swap[j + 1] [0]= swap[j] [0];
189 swap[j + 1] [1]= swap[j] [1];
190 swap[j + 1] [2]= swap[j] [2];
191 swap[j][0]= buf1;
192 swap[j][1]= buf2;
193 swap[j][2]= buf3;
194 result= swapvar (result, Variable (j + 1), Variable (j));
195 }
196 }
197 }
198
199 for (i= n; i > 0; i--)
200 {
201 if (i != swap[i] [0])
202 N.newpair (Variable (i), Variable (swap[i] [0]));
203 }
204
205 for (i= F.level(); i >=0 ; i--)
206 delete [] swap[i];
207 delete [] swap;
208
210
211 return result;
212}
213
214#if defined(HAVE_NTL) || defined(HAVE_FLINT)
215CFList
217 const CFList& M, const ExtensionInfo& info,
218 const CFList& evaluation)
219{
220 Variable alpha= info.getAlpha();
221 Variable beta= info.getBeta();
222 CanonicalForm gamma= info.getGamma();
223 CanonicalForm delta= info.getDelta();
224 int k= info.getGFDegree();
225 CFList source, dest;
226 if (factors.length() == 1)
227 {
229 return CFList (mapDown (buf, info, source, dest));
230 }
231 if (factors.length() < 1)
232 return CFList();
233
234 int degMipoBeta= 1;
235 if (!k && beta.level() != 1)
236 degMipoBeta= degree (getMipo (beta));
237
238 CFList T, S;
239 T= factors;
240
241 int s= 1;
244
245 buf= F;
246
247 Variable x= Variable (1);
248 CanonicalForm g, LCBuf= LC (buf, x);
249 CanonicalForm buf2, quot;
250 int * v= new int [T.length()];
251 for (int i= 0; i < T.length(); i++)
252 v[i]= 0;
253 bool noSubset= false;
254 CFArray TT;
255 TT= copy (factors);
256 bool recombination= false;
257 bool trueFactor= false;
258 while (T.length() >= 2*s)
259 {
260 while (noSubset == false)
261 {
262 if (T.length() == s)
263 {
264 delete [] v;
265 if (recombination)
266 {
267 T.insert (LCBuf);
268 g= prodMod (T, M);
269 T.removeFirst();
270 result.append (g/myContent (g));
272 g /= Lc (g);
273 appendTestMapDown (result, g, info, source, dest);
274 return result;
275 }
276 else
277 {
279 return CFList (buf);
280 }
281 }
282
283 S= subset (v, s, TT, noSubset);
284 if (noSubset) break;
285
286 S.insert (LCBuf);
287 g= prodMod (S, M);
288 S.removeFirst();
289 g /= myContent (g);
290 if (fdivides (g, buf, quot))
291 {
293 buf2 /= Lc (buf2);
294 if (!k && beta == x)
295 {
296 if (degree (buf2, alpha) < degMipoBeta)
297 {
298 appendTestMapDown (result, buf2, info, source, dest);
299 buf= quot;
300 LCBuf= LC (buf, x);
301 recombination= true;
302 trueFactor= true;
303 }
304 }
305 else
306 {
307 if (!isInExtension (buf2, gamma, k, delta, source, dest))
308 {
309 appendTestMapDown (result, buf2, info, source, dest);
310 buf /= g;
311 LCBuf= LC (buf, x);
312 recombination= true;
313 trueFactor= true;
314 }
315 }
316
317 if (trueFactor)
318 {
319 T= Difference (T, S);
320
321 if (T.length() < 2*s || T.length() == s)
322 {
324 buf /= Lc (buf);
325 appendTestMapDown (result, buf, info, source, dest);
326 delete [] v;
327 return result;
328 }
329 trueFactor= false;
330 TT= copy (T);
331 indexUpdate (v, s, T.length(), noSubset);
332 if (noSubset) break;
333 }
334 }
335 }
336 s++;
337 if (T.length() < 2*s || T.length() == s)
338 {
340 appendTestMapDown (result, buf, info, source, dest);
341 delete [] v;
342 return result;
343 }
344 for (int i= 0; i < T.length(); i++)
345 v[i]= 0;
346 noSubset= false;
347 }
348 if (T.length() < 2*s)
349 {
351 appendMapDown (result, buf, info, source, dest);
352 }
353
354 delete [] v;
355 return result;
356}
357#endif
358
359#if defined(HAVE_NTL) || defined(HAVE_FLINT)
360CFList
361factorRecombination (const CanonicalForm& F, const CFList& factors,
362 const CFList& M)
363{
364 if (factors.length() == 1)
365 return CFList(F);
366 if (factors.length() < 1)
367 return CFList();
368
369 CFList T, S;
370
371 T= factors;
372
373 int s= 1;
375 CanonicalForm LCBuf= LC (F, Variable (1));
376 CanonicalForm g, buf= F;
377 int * v= new int [T.length()];
378 for (int i= 0; i < T.length(); i++)
379 v[i]= 0;
380 bool noSubset= false;
381 CFArray TT;
382 TT= copy (factors);
383 Variable y= F.level() - 1;
384 bool recombination= false;
385 CanonicalForm h, quot;
386 while (T.length() >= 2*s)
387 {
388 while (noSubset == false)
389 {
390 if (T.length() == s)
391 {
392 delete [] v;
393 if (recombination)
394 {
395 T.insert (LC (buf));
396 g= prodMod (T, M);
397 result.append (g/myContent (g));
398 return result;
399 }
400 else
401 return CFList (F);
402 }
403 S= subset (v, s, TT, noSubset);
404 if (noSubset) break;
405 S.insert (LCBuf);
406 g= prodMod (S, M);
407 S.removeFirst();
408 g /= myContent (g);
409 if (fdivides (g, buf, quot))
410 {
411 recombination= true;
412 result.append (g);
413 buf= quot;
414 LCBuf= LC (buf, Variable(1));
415 T= Difference (T, S);
416 if (T.length() < 2*s || T.length() == s)
417 {
418 result.append (buf);
419 delete [] v;
420 return result;
421 }
422 TT= copy (T);
423 indexUpdate (v, s, T.length(), noSubset);
424 if (noSubset) break;
425 }
426 }
427 s++;
428 if (T.length() < 2*s || T.length() == s)
429 {
430 result.append (buf);
431 delete [] v;
432 return result;
433 }
434 for (int i= 0; i < T.length(); i++)
435 v[i]= 0;
436 noSubset= false;
437 }
438 if (T.length() < 2*s)
439 result.append (F);
440
441 delete [] v;
442 return result;
443}
444#endif
445
446#if defined(HAVE_NTL) || defined(HAVE_FLINT)
447int
448liftBoundAdaption (const CanonicalForm& F, const CFList& factors, bool&
449 success, const int deg, const CFList& MOD, const int bound)
450{
451 int adaptedLiftBound= 0;
453 Variable y= F.mvar();
454 Variable x= Variable (1);
455 CanonicalForm LCBuf= LC (buf, x);
456 CanonicalForm g, quot;
457 CFList M= MOD;
458 M.append (power (y, deg));
459 int d= bound;
460 int e= 0;
461 int nBuf;
462 for (CFListIterator i= factors; i.hasItem(); i++)
463 {
464 g= mulMod (i.getItem(), LCBuf, M);
465 g /= myContent (g);
466 if (fdivides (g, buf, quot))
467 {
468 nBuf= degree (g, y) + degree (LC (g, 1), y);
469 d -= nBuf;
470 e= tmax (e, nBuf);
471 buf= quot;
472 LCBuf= LC (buf, x);
473 }
474 }
475 adaptedLiftBound= d;
476
477 if (adaptedLiftBound < deg)
478 {
479 if (adaptedLiftBound < degree (F) + 1)
480 {
481 if (d == 1)
482 {
483 if (e + 1 > deg)
484 {
485 adaptedLiftBound= deg;
486 success= false;
487 }
488 else
489 {
490 success= true;
491 if (e + 1 < degree (F) + 1)
492 adaptedLiftBound= deg;
493 else
494 adaptedLiftBound= e + 1;
495 }
496 }
497 else
498 {
499 success= true;
500 adaptedLiftBound= deg;
501 }
502 }
503 else
504 {
505 success= true;
506 }
507 }
508 return adaptedLiftBound;
509}
510#endif
511
512#if defined(HAVE_NTL) || defined(HAVE_FLINT)
513int
514extLiftBoundAdaption (const CanonicalForm& F, const CFList& factors, bool&
515 success, const ExtensionInfo& info, const CFList& eval,
516 const int deg, const CFList& MOD, const int bound)
517{
518 Variable alpha= info.getAlpha();
519 Variable beta= info.getBeta();
520 CanonicalForm gamma= info.getGamma();
521 CanonicalForm delta= info.getDelta();
522 int k= info.getGFDegree();
523 int adaptedLiftBound= 0;
525 Variable y= F.mvar();
526 Variable x= Variable (1);
527 CanonicalForm LCBuf= LC (buf, x);
528 CanonicalForm g, gg, quot;
529 CFList M= MOD;
530 M.append (power (y, deg));
531 adaptedLiftBound= 0;
532 int d= bound;
533 int e= 0;
534 int nBuf;
535 int degMipoBeta= 1;
536 if (!k && beta.level() != 1)
537 degMipoBeta= degree (getMipo (beta));
538
539 CFList source, dest;
540 for (CFListIterator i= factors; i.hasItem(); i++)
541 {
542 g= mulMod (i.getItem(), LCBuf, M);
543 g /= myContent (g);
544 if (fdivides (g, buf, quot))
545 {
546 gg= reverseShift (g, eval);
547 gg /= Lc (gg);
548 if (!k && beta == x)
549 {
550 if (degree (gg, alpha) < degMipoBeta)
551 {
552 buf= quot;
553 nBuf= degree (g, y) + degree (LC (g, x), y);
554 d -= nBuf;
555 e= tmax (e, nBuf);
556 LCBuf= LC (buf, x);
557 }
558 }
559 else
560 {
561 if (!isInExtension (gg, gamma, k, delta, source, dest))
562 {
563 buf= quot;
564 nBuf= degree (g, y) + degree (LC (g, x), y);
565 d -= nBuf;
566 e= tmax (e, nBuf);
567 LCBuf= LC (buf, x);
568 }
569 }
570 }
571 }
572 adaptedLiftBound= d;
573
574 if (adaptedLiftBound < deg)
575 {
576 if (adaptedLiftBound < degree (F) + 1)
577 {
578 if (d == 1)
579 {
580 if (e + 1 > deg)
581 {
582 adaptedLiftBound= deg;
583 success= false;
584 }
585 else
586 {
587 success= true;
588 if (e + 1 < degree (F) + 1)
589 adaptedLiftBound= deg;
590 else
591 adaptedLiftBound= e + 1;
592 }
593 }
594 else
595 {
596 success= true;
597 adaptedLiftBound= deg;
598 }
599 }
600 else
601 {
602 success= true;
603 }
604 }
605
606 return adaptedLiftBound;
607}
608#endif
609
610#if defined(HAVE_NTL) || defined(HAVE_FLINT)
611CFList
612earlyFactorDetect (CanonicalForm& F, CFList& factors, int& adaptedLiftBound,
613 bool& success, const int deg, const CFList& MOD,
614 const int bound)
615{
617 CFList T= factors;
619 Variable y= F.mvar();
620 Variable x= Variable (1);
621 CanonicalForm LCBuf= LC (buf, x);
622 CanonicalForm g, quot;
623 CFList M= MOD;
624 M.append (power (y, deg));
625 adaptedLiftBound= 0;
626 int d= bound;
627 int e= 0;
628 int nBuf;
629 for (CFListIterator i= factors; i.hasItem(); i++)
630 {
631 g= mulMod (i.getItem(), LCBuf, M);
632 g /= myContent (g);
633 if (fdivides (g, buf, quot))
634 {
635 result.append (g);
636 nBuf= degree (g, y) + degree (LC (g, x), y);
637 d -= nBuf;
638 e= tmax (e, nBuf);
639 buf= quot;
640 LCBuf= LC (buf, x);
641 T= Difference (T, CFList (i.getItem()));
642 }
643 }
644 adaptedLiftBound= d;
645
646 if (adaptedLiftBound < deg)
647 {
648 if (adaptedLiftBound < degree (F) + 1)
649 {
650 if (d == 1)
651 adaptedLiftBound= tmin (e + 1, deg);
652 else
653 adaptedLiftBound= deg;
654 }
655 factors= T;
656 F= buf;
657 success= true;
658 }
659 return result;
660}
661#endif
662
663#if defined(HAVE_NTL) || defined(HAVE_FLINT)
664CFList
665extEarlyFactorDetect (CanonicalForm& F, CFList& factors, int& adaptedLiftBound,
666 bool& success, const ExtensionInfo& info, const CFList&
667 eval, const int deg, const CFList& MOD, const int bound)
668{
669 Variable alpha= info.getAlpha();
670 Variable beta= info.getBeta();
671 CanonicalForm gamma= info.getGamma();
672 CanonicalForm delta= info.getDelta();
673 int k= info.getGFDegree();
675 CFList T= factors;
677 Variable y= F.mvar();
678 Variable x= Variable (1);
679 CanonicalForm LCBuf= LC (buf, x);
680 CanonicalForm g, gg, quot;
681 CFList M= MOD;
682 M.append (power (y, deg));
683 adaptedLiftBound= 0;
684 int d= bound;
685 int e= 0;
686 int nBuf;
687 CFList source, dest;
688
689 int degMipoBeta= 1;
690 if (!k && beta.level() != 1)
691 degMipoBeta= degree (getMipo (beta));
692
693 for (CFListIterator i= factors; i.hasItem(); i++)
694 {
695 g= mulMod (i.getItem(), LCBuf, M);
696 g /= myContent (g);
697 if (fdivides (g, buf, quot))
698 {
699 gg= reverseShift (g, eval);
700 gg /= Lc (gg);
701 if (!k && beta == x)
702 {
703 if (degree (gg, alpha) < degMipoBeta)
704 {
705 appendTestMapDown (result, gg, info, source, dest);
706 buf= quot;
707 nBuf= degree (g, y) + degree (LC (g, x), y);
708 d -= nBuf;
709 e= tmax (e, nBuf);
710 LCBuf= LC (buf, x);
711 T= Difference (T, CFList (i.getItem()));
712 }
713 }
714 else
715 {
716 if (!isInExtension (gg, gamma, k, delta, source, dest))
717 {
718 appendTestMapDown (result, gg, info, source, dest);
719 buf= quot;
720 nBuf= degree (g, y) + degree (LC (g, x), y);
721 d -= nBuf;
722 e= tmax (e, nBuf);
723 LCBuf= LC (buf, x);
724 T= Difference (T, CFList (i.getItem()));
725 }
726 }
727 }
728 }
729 adaptedLiftBound= d;
730
731 if (adaptedLiftBound < deg)
732 {
733 if (adaptedLiftBound < degree (F) + 1)
734 {
735 if (d == 1)
736 adaptedLiftBound= tmin (e + 1, deg);
737 else
738 adaptedLiftBound= deg;
739 }
740 success= true;
741 factors= T;
742 F= buf;
743 }
744 return result;
745}
746#endif
747
748#if defined(HAVE_NTL) || defined(HAVE_FLINT)
749#define CHAR_THRESHOLD 8
750CFList
752 CFList& list, const bool& GF, bool& fail)
753{
754 int k= F.level() - 1;
755 Variable x= Variable (1);
756 CanonicalForm LCF=LC (F, x);
758
760 FFRandom genFF;
761 GFRandom genGF;
762 int p= getCharacteristic ();
763 if (p < CHAR_THRESHOLD)
764 {
765 if (!GF && alpha.level() == 1)
766 {
767 fail= true;
768 return CFList();
769 }
770 else if (!GF && alpha.level() != 1)
771 {
772 if ((p == 2 && degree (getMipo (alpha)) < 6) ||
773 (p == 3 && degree (getMipo (alpha)) < 4) ||
774 (p == 5 && degree (getMipo (alpha)) < 3))
775 {
776 fail= true;
777 return CFList();
778 }
779 }
780 }
781 double bound;
782 if (alpha != x)
783 {
784 bound= pow ((double) p, (double) degree (getMipo(alpha)));
785 bound *= (double) k;
786 }
787 else if (GF)
788 {
789 bound= pow ((double) p, (double) getGFDegree());
790 bound *= (double) k;
791 }
792 else
793 bound= pow ((double) p, (double) k);
794
795 CanonicalForm random;
797 do
798 {
799 random= 0;
800 // possible overflow if list.length() does not fit into a int
801 if (list.length() >= bound)
802 {
803 fail= true;
804 break;
805 }
806 for (int i= 0; i < k; i++)
807 {
808 if (list.isEmpty())
809 result.append (0);
810 else if (GF)
811 {
812 result.append (genGF.generate());
813 random += result.getLast()*power (x, i);
814 }
815 else if (alpha.level() != 1)
816 {
817 AlgExtRandomF genAlgExt (alpha);
818 result.append (genAlgExt.generate());
819 random += result.getLast()*power (x, i);
820 }
821 else
822 {
823 result.append (genFF.generate());
824 random += result.getLast()*power (x, i);
825 }
826 }
827 if (find (list, random))
828 {
829 result= CFList();
830 continue;
831 }
832 int l= F.level();
833 eval.insert (F);
834 LCFeval.insert (LCF);
835 bool bad= false;
836 for (CFListIterator i= result; i.hasItem(); i++, l--)
837 {
838 eval.insert (eval.getFirst()(i.getItem(), l));
839 LCFeval.insert (LCFeval.getFirst()(i.getItem(), l));
840 if (degree (eval.getFirst(), l - 1) != degree (F, l - 1))
841 {
842 if (!find (list, random))
843 list.append (random);
844 result= CFList();
845 eval= CFList();
846 LCFeval= CFList();
847 bad= true;
848 break;
849 }
850 if ((l != 2) && (degree (LCFeval.getFirst(), l-1) != degree (LCF, l-1)))
851 {
852 if (!find (list, random))
853 list.append (random);
854 result= CFList();
855 eval= CFList();
856 LCFeval= CFList();
857 bad= true;
858 break;
859 }
860 }
861
862 if (bad)
863 continue;
864
865 if (degree (eval.getFirst()) != degree (F, 1))
866 {
867 if (!find (list, random))
868 list.append (random);
869 result= CFList();
870 LCFeval= CFList();
871 eval= CFList();
872 continue;
873 }
874
875 deriv_x= deriv (eval.getFirst(), x);
876 gcd_deriv= gcd (eval.getFirst(), deriv_x);
877 if (degree (gcd_deriv) > 0)
878 {
879 if (!find (list, random))
880 list.append (random);
881 result= CFList();
882 LCFeval= CFList();
883 eval= CFList();
884 continue;
885 }
887 i++;
888 CanonicalForm contentx= content (i.getItem(), x);
889 if (degree (contentx) > 0)
890 {
891 if (!find (list, random))
892 list.append (random);
893 result= CFList();
894 LCFeval= CFList();
895 eval= CFList();
896 continue;
897 }
898
899 contentx= content (i.getItem());
900 if (degree (contentx) > 0)
901 {
902 if (!find (list, random))
903 list.append (random);
904 result= CFList();
905 LCFeval= CFList();
906 eval= CFList();
907 continue;
908 }
909
910 if (list.length() >= bound)
911 {
912 fail= true;
913 break;
914 }
915 } while (find (list, random));
916
917 if (!eval.isEmpty())
918 eval.removeFirst();
919
920 return result;
921}
922#endif
923
924static inline
926 evaluation, const Variable& alpha, const int lev,
928 )
929{
930 Variable x= Variable (1);
931 CanonicalForm derivI, buf;
933 int swapLevel= 0;
934 CFList list;
935 bool fail= false;
936 buf= A;
937 Aeval= CFList();
939 for (int i= lev; i <= A.level(); i++)
940 {
941 derivI= deriv (buf, Variable (i));
942 if (!derivI.isZero())
943 {
944 g= gcd (buf, derivI);
945 if (degree (g) > 0)
946 return -1;
947
948 buf= swapvar (buf, x, Variable (i));
949 Aeval= CFList();
951 fail= false;
952 evaluation= evalPoints (buf, Aeval, alpha, list, GF, fail);
953 if (!fail)
954 {
955 A= buf;
956 swapLevel= i;
957 break;
958 }
959 else
960 buf= A;
961 }
962 }
963 return swapLevel;
964}
965
967{
968 int i= A.level();
970 contentAi.append (content (buf, i));
971 buf /= contentAi.getLast();
972 contentAi.append (content (buf, i - 1));
973 CanonicalForm result= lcm (contentAi.getFirst(), contentAi.getLast());
974 for (i= i - 2; i > 0; i--)
975 {
976 contentAi.append (content (buf, i));
977 buf /= contentAi.getLast();
978 result= lcm (result, contentAi.getLast());
979 }
980 return result;
981}
982
983#if defined(HAVE_NTL) || defined(HAVE_FLINT) // henselLift23
984CFList
985henselLiftAndEarly (CanonicalForm& A, CFList& MOD, int*& liftBounds, bool&
986 earlySuccess, CFList& earlyFactors, const CFList& Aeval,
987 const CFList& biFactors, const CFList& evaluation,
988 const ExtensionInfo& info)
989{
990 bool extension= info.isInExtension();
991 CFList bufFactors= biFactors;
992 bufFactors.insert (LC (Aeval.getFirst(), 1));
993
994 sortList (bufFactors, Variable (1));
995
996 CFList diophant;
997 CFArray Pi;
998 int smallFactorDeg= 11; //tunable parameter
1000 int adaptedLiftBound= 0;
1001 int liftBound= liftBounds[1];
1002
1003 earlySuccess= false;
1004 CFList earlyReconstFactors;
1006 j++;
1007 CanonicalForm buf= j.getItem();
1008 CFMatrix Mat= CFMatrix (liftBound, bufFactors.length() - 1);
1009 MOD= CFList (power (Variable (2), liftBounds[0]));
1010 if (smallFactorDeg >= liftBound)
1011 {
1012 result= henselLift23 (Aeval, bufFactors, liftBounds, diophant, Pi, Mat);
1013 }
1014 else if (smallFactorDeg >= degree (buf) + 1)
1015 {
1016 liftBounds[1]= degree (buf) + 1;
1017 result= henselLift23 (Aeval, bufFactors, liftBounds, diophant, Pi, Mat);
1018 if (Aeval.length() == 2)
1019 {
1020 if (!extension)
1021 earlyFactors= earlyFactorDetect
1022 (buf, result, adaptedLiftBound, earlySuccess,
1023 degree (buf) + 1, MOD, liftBound);
1024 else
1025 earlyFactors= extEarlyFactorDetect
1026 (buf, result, adaptedLiftBound, earlySuccess,
1028 (buf) + 1, MOD, liftBound);
1029 }
1030 else
1031 {
1032 if (!extension)
1033 adaptedLiftBound= liftBoundAdaption (buf, result, earlySuccess,
1034 degree (buf) + 1, MOD, liftBound);
1035 else
1036 adaptedLiftBound= extLiftBoundAdaption (buf, result, earlySuccess, info,
1037 evaluation, degree (buf) + 1,
1038 MOD, liftBound);
1039 }
1040 if (!earlySuccess)
1041 {
1042 result.insert (LC (buf, 1));
1043 liftBounds[1]= adaptedLiftBound;
1044 liftBound= adaptedLiftBound;
1045 henselLiftResume (buf, result, degree (buf) + 1, liftBound,
1046 Pi, diophant, Mat, MOD);
1047 }
1048 else
1049 liftBounds[1]= adaptedLiftBound;
1050 }
1051 else if (smallFactorDeg < degree (buf) + 1)
1052 {
1053 liftBounds[1]= smallFactorDeg;
1054 result= henselLift23 (Aeval, bufFactors, liftBounds, diophant, Pi, Mat);
1055 if (Aeval.length() == 2)
1056 {
1057 if (!extension)
1058 earlyFactors= earlyFactorDetect (buf, result, adaptedLiftBound,
1059 earlySuccess, smallFactorDeg, MOD,
1060 liftBound);
1061 else
1062 earlyFactors= extEarlyFactorDetect (buf, result, adaptedLiftBound,
1063 earlySuccess, info, evaluation,
1064 smallFactorDeg, MOD, liftBound);
1065 }
1066 else
1067 {
1068 if (!extension)
1069 adaptedLiftBound= liftBoundAdaption (buf, result, earlySuccess,
1070 smallFactorDeg, MOD, liftBound);
1071 else
1072 adaptedLiftBound= extLiftBoundAdaption (buf, result, earlySuccess, info,
1073 evaluation, smallFactorDeg, MOD,
1074 liftBound);
1075 }
1076
1077 if (!earlySuccess)
1078 {
1079 result.insert (LC (buf, 1));
1080 henselLiftResume (buf, result, smallFactorDeg, degree (buf) + 1,
1081 Pi, diophant, Mat, MOD);
1082 if (Aeval.length() == 2)
1083 {
1084 if (!extension)
1085 earlyFactors= earlyFactorDetect (buf, result, adaptedLiftBound,
1086 earlySuccess, degree (buf) + 1,
1087 MOD, liftBound);
1088 else
1089 earlyFactors= extEarlyFactorDetect (buf, result, adaptedLiftBound,
1090 earlySuccess, info, evaluation,
1091 degree (buf) + 1, MOD,
1092 liftBound);
1093 }
1094 else
1095 {
1096 if (!extension)
1097 adaptedLiftBound= liftBoundAdaption (buf, result, earlySuccess,
1098 degree (buf) + 1, MOD,liftBound);
1099 else
1100 adaptedLiftBound= extLiftBoundAdaption (buf, result, earlySuccess,
1102 degree (buf) + 1, MOD,
1103 liftBound);
1104 }
1105 if (!earlySuccess)
1106 {
1107 result.insert (LC (buf, 1));
1108 liftBounds[1]= adaptedLiftBound;
1109 liftBound= adaptedLiftBound;
1110 henselLiftResume (buf, result, degree (buf) + 1, liftBound,
1111 Pi, diophant, Mat, MOD);
1112 }
1113 else
1114 liftBounds[1]= adaptedLiftBound;
1115 }
1116 else
1117 liftBounds[1]= adaptedLiftBound;
1118 }
1119
1120 MOD.append (power (Variable (3), liftBounds[1]));
1121
1122 if (Aeval.length() > 2)
1123 {
1125 j++;
1126 CFList bufEval;
1127 bufEval.append (j.getItem());
1128 j++;
1129 int liftBoundsLength= Aeval.getLast().level() - 1;
1130 for (int i= 2; i <= liftBoundsLength && j.hasItem(); i++, j++)
1131 {
1132 earlySuccess= false;
1133 result.insert (LC (bufEval.getFirst(), 1));
1134 bufEval.append (j.getItem());
1135 liftBound= liftBounds[i];
1136 Mat= CFMatrix (liftBounds[i], result.length() - 1);
1137
1138 buf= j.getItem();
1139 if (smallFactorDeg >= liftBound)
1140 result= henselLift (bufEval, result, MOD, diophant, Pi, Mat,
1141 liftBounds[i - 1], liftBounds[i]);
1142 else if (smallFactorDeg >= degree (buf) + 1)
1143 {
1144 result= henselLift (bufEval, result, MOD, diophant, Pi, Mat,
1145 liftBounds[i - 1], degree (buf) + 1);
1146
1147 if (Aeval.length() == i + 1)
1148 {
1149 if (!extension)
1150 earlyFactors= earlyFactorDetect
1151 (buf, result, adaptedLiftBound, earlySuccess,
1152 degree (buf) + 1, MOD, liftBound);
1153 else
1154 earlyFactors= extEarlyFactorDetect
1155 (buf, result, adaptedLiftBound, earlySuccess,
1156 info, evaluation, degree (buf) + 1, MOD, liftBound);
1157 }
1158 else
1159 {
1160 if (!extension)
1161 adaptedLiftBound= liftBoundAdaption
1162 (buf, result, earlySuccess, degree (buf)
1163 + 1, MOD, liftBound);
1164 else
1165 adaptedLiftBound= extLiftBoundAdaption
1166 (buf, result, earlySuccess, info, evaluation,
1167 degree (buf) + 1, MOD, liftBound);
1168 }
1169
1170 if (!earlySuccess)
1171 {
1172 result.insert (LC (buf, 1));
1173 liftBounds[i]= adaptedLiftBound;
1174 liftBound= adaptedLiftBound;
1175 henselLiftResume (buf, result, degree (buf) + 1, liftBound,
1176 Pi, diophant, Mat, MOD);
1177 }
1178 else
1179 {
1180 liftBounds[i]= adaptedLiftBound;
1181 }
1182 }
1183 else if (smallFactorDeg < degree (buf) + 1)
1184 {
1185 result= henselLift (bufEval, result, MOD, diophant, Pi, Mat,
1186 liftBounds[i - 1], smallFactorDeg);
1187
1188 if (Aeval.length() == i + 1)
1189 {
1190 if (!extension)
1191 earlyFactors= earlyFactorDetect
1192 (buf, result, adaptedLiftBound, earlySuccess,
1193 smallFactorDeg, MOD, liftBound);
1194 else
1195 earlyFactors= extEarlyFactorDetect
1196 (buf, result, adaptedLiftBound, earlySuccess,
1197 info, evaluation, smallFactorDeg, MOD, liftBound);
1198 }
1199 else
1200 {
1201 if (!extension)
1202 adaptedLiftBound= liftBoundAdaption
1203 (buf, result, earlySuccess,
1204 smallFactorDeg, MOD, liftBound);
1205 else
1206 adaptedLiftBound= extLiftBoundAdaption
1207 (buf, result, earlySuccess, info, evaluation,
1208 smallFactorDeg, MOD, liftBound);
1209 }
1210
1211 if (!earlySuccess)
1212 {
1213 result.insert (LC (buf, 1));
1214 henselLiftResume (buf, result, smallFactorDeg,
1215 degree (buf) + 1, Pi, diophant, Mat, MOD);
1216 if (Aeval.length() == i + 1)
1217 {
1218 if (!extension)
1219 earlyFactors= earlyFactorDetect
1220 (buf, result, adaptedLiftBound, earlySuccess,
1221 degree (buf) + 1, MOD, liftBound);
1222 else
1223 earlyFactors= extEarlyFactorDetect
1224 (buf, result, adaptedLiftBound, earlySuccess,
1225 info, evaluation, degree (buf) + 1, MOD,
1226 liftBound);
1227 }
1228 else
1229 {
1230 if (!extension)
1231 adaptedLiftBound= liftBoundAdaption
1232 (buf, result, earlySuccess, degree
1233 (buf) + 1, MOD, liftBound);
1234 else
1235 adaptedLiftBound= extLiftBoundAdaption
1236 (buf, result, earlySuccess, info, evaluation,
1237 degree (buf) + 1, MOD, liftBound);
1238 }
1239
1240 if (!earlySuccess)
1241 {
1242 result.insert (LC (buf, 1));
1243 liftBounds[i]= adaptedLiftBound;
1244 liftBound= adaptedLiftBound;
1245 henselLiftResume (buf, result, degree (buf) + 1, liftBound,
1246 Pi, diophant, Mat, MOD);
1247 }
1248 else
1249 liftBounds[i]= adaptedLiftBound;
1250 }
1251 else
1252 liftBounds[i]= adaptedLiftBound;
1253 }
1254 MOD.append (power (Variable (i + 2), liftBounds[i]));
1255 bufEval.removeFirst();
1256 }
1257 bufFactors= result;
1258 }
1259 else
1260 bufFactors= result;
1261
1262 if (earlySuccess)
1263 A= buf;
1264 return result;
1265}
1266#endif
1267
1268void
1270{
1272 int k= factors1.length();
1273 int l= factors2.length();
1274 int n= 0;
1275 int m;
1277 for (CFFListIterator i= factors1; (n < k && i.hasItem()); i++, n++)
1278 {
1279 m= 0;
1280 for (j= factors2; (m < l && j.hasItem()); j++, m++)
1281 {
1282 g= gcd (i.getItem().factor(), j.getItem().factor());
1283 if (degree (g,1) > 0)
1284 {
1285 j.getItem()= CFFactor (j.getItem().factor()/g, j.getItem().exp());
1286 i.getItem()= CFFactor (i.getItem().factor()/g, i.getItem().exp());
1287 factors1.append (CFFactor (g, i.getItem().exp()));
1288 factors2.append (CFFactor (g, j.getItem().exp()));
1289 }
1290 }
1291 }
1292}
1293
1294CFList
1295distributeContent (const CFList& L, const CFList* differentSecondVarFactors,
1296 int length
1297 )
1298{
1299 CFList l= L;
1300 CanonicalForm content= l.getFirst();
1301
1302 if (content.inCoeffDomain())
1303 return l;
1304
1305 if (l.length() == 1)
1306 {
1307 CFList result;
1308 for (int i= 0; i < length; i++)
1309 {
1310 if (differentSecondVarFactors[i].isEmpty())
1311 continue;
1312 if (result.isEmpty())
1313 {
1314 result= differentSecondVarFactors[i];
1315 for (CFListIterator iter= result; iter.hasItem(); iter++)
1316 content /= iter.getItem();
1317 }
1318 else
1319 {
1320 CFListIterator iter1= result;
1321 for (CFListIterator iter2= differentSecondVarFactors[i];iter2.hasItem();
1322 iter2++, iter1++)
1323 {
1324 iter1.getItem() *= iter2.getItem();
1325 content /= iter2.getItem();
1326 }
1327 }
1328 }
1329 result.insert (content);
1330 return result;
1331 }
1332
1333 Variable v;
1334 CFListIterator iter1, iter2;
1335 CanonicalForm tmp, g;
1336 CFList multiplier;
1337 for (int i= 0; i < length; i++)
1338 {
1339 if (differentSecondVarFactors[i].isEmpty())
1340 continue;
1341 iter1= l;
1342 iter1++;
1343
1344 tmp= 1;
1345 for (iter2= differentSecondVarFactors[i]; iter2.hasItem();
1346 iter2++, iter1++)
1347 {
1348 if (iter2.getItem().inCoeffDomain())
1349 {
1350 multiplier.append (1);
1351 continue;
1352 }
1353 v= iter2.getItem().mvar();
1354 if (degree (iter2.getItem()) == degree (iter1.getItem(),v))
1355 {
1356 multiplier.append (1);
1357 continue;
1358 }
1359 g= gcd (iter2.getItem(), content);
1360 if (!g.inCoeffDomain())
1361 {
1362 tmp *= g;
1363 multiplier.append (g);
1364 }
1365 else
1366 multiplier.append (1);
1367 }
1368 if (!tmp.isOne() && fdivides (tmp, content))
1369 {
1370 iter1= l;
1371 iter1++;
1372 content /= tmp;
1373 for (iter2= multiplier; iter2.hasItem(); iter1++, iter2++)
1374 iter1.getItem() *= iter2.getItem();
1375 }
1376 multiplier= CFList();
1377 }
1378
1379 l.removeFirst();
1380 l.insert (content);
1381 return l;
1382}
1383
1384int
1385testFactors (const CanonicalForm& G, const CFList& uniFactors,
1386 const Variable& alpha, CanonicalForm& sqrfPartF, CFList& factors,
1387 CFFList*& bufSqrfFactors, CFList& evalSqrfPartF,
1388 const CFArray& evalPoint)
1389{
1390 CanonicalForm F= G;
1391 CFFList sqrfFactorization;
1392 if (getCharacteristic() > 0)
1393 sqrfFactorization= squarefreeFactorization (F, alpha);
1394 else
1395 sqrfFactorization= sqrFree (F);
1396
1397 sqrfPartF= 1;
1398 for (CFFListIterator i= sqrfFactorization; i.hasItem(); i++)
1399 sqrfPartF *= i.getItem().factor();
1400
1401 evalSqrfPartF= evaluateAtEval (sqrfPartF, evalPoint);
1402
1403 CanonicalForm test= evalSqrfPartF.getFirst() (evalPoint[0], 2);
1404
1405 if (degree (test) != degree (sqrfPartF, 1) || test.inCoeffDomain())
1406 return 0;
1407
1408 CFFList sqrfFactors;
1409 CanonicalForm tmp;
1410 CFList tmp2;
1411 int k= 0;
1412 factors= uniFactors;
1414 for (CFListIterator i= factors; i.hasItem(); i++, k++)
1415 {
1416 tmp= 1;
1417 if (getCharacteristic() > 0)
1418 sqrfFactors= squarefreeFactorization (i.getItem(), alpha);
1419 else
1420 sqrfFactors= sqrFree (i.getItem());
1421
1422 for (iter= sqrfFactors; iter.hasItem(); iter++)
1423 {
1424 tmp2.append (iter.getItem().factor());
1425 tmp *= iter.getItem().factor();
1426 }
1427 i.getItem()= tmp/Lc(tmp);
1428 bufSqrfFactors [k]= sqrfFactors;
1429 }
1430
1431 for (int i= 0; i < factors.length() - 1; i++)
1432 {
1433 for (k= i + 1; k < factors.length(); k++)
1434 {
1435 gcdFreeBasis (bufSqrfFactors [i], bufSqrfFactors[k]);
1436 }
1437 }
1438
1439 factors= CFList();
1440 for (int i= 0; i < uniFactors.length(); i++)
1441 {
1442 if (i == 0)
1443 {
1444 for (iter= bufSqrfFactors [i]; iter.hasItem(); iter++)
1445 {
1446 if (iter.getItem().factor().inCoeffDomain())
1447 continue;
1448 iter.getItem()= CFFactor (iter.getItem().factor()/
1449 Lc (iter.getItem().factor()),
1450 iter.getItem().exp());
1451 factors.append (iter.getItem().factor());
1452 }
1453 }
1454 else
1455 {
1456 for (iter= bufSqrfFactors [i]; iter.hasItem(); iter++)
1457 {
1458 if (iter.getItem().factor().inCoeffDomain())
1459 continue;
1460 iter.getItem()= CFFactor (iter.getItem().factor()/
1461 Lc (iter.getItem().factor()),
1462 iter.getItem().exp());
1463 if (!find (factors, iter.getItem().factor()))
1464 factors.append (iter.getItem().factor());
1465 }
1466 }
1467 }
1468
1469 test= prod (factors);
1470 tmp= evalSqrfPartF.getFirst() (evalPoint[0],2);
1471 if (test/Lc (test) != tmp/Lc (tmp))
1472 return 0;
1473 else
1474 return 1;
1475}
1476
1477#if defined(HAVE_NTL) || defined(HAVE_FLINT) // nonMonicHenselLift12
1478CFList
1480 const Variable& alpha, const CFList& evaluation,
1481 CFList* & differentSecondVarLCs, int lSecondVarLCs,
1482 Variable& y
1483 )
1484{
1485 y= Variable (1);
1486 if (LCF.inCoeffDomain())
1487 {
1488 CFList result;
1489 for (int i= 1; i <= LCFFactors.length() + 1; i++)
1490 result.append (1);
1491 return result;
1492 }
1493
1494 CFMap N, M;
1495 CFArray dummy= CFArray (2);
1496 dummy [0]= LCF;
1497 dummy [1]= Variable (2);
1498 compress (dummy, M, N);
1499 CanonicalForm F= M (LCF);
1500 if (LCF.isUnivariate())
1501 {
1502 CFList result;
1503 int LCFLevel= LCF.level();
1504 bool found= false;
1505 if (LCFLevel == 2)
1506 {
1507 //bivariate leading coefficients are already the true leading coefficients
1508 result= LCFFactors;
1509 found= true;
1510 }
1511 else
1512 {
1514 for (int i= 0; i < lSecondVarLCs; i++)
1515 {
1516 for (j= differentSecondVarLCs[i]; j.hasItem(); j++)
1517 {
1518 if (j.getItem().level() == LCFLevel)
1519 {
1520 found= true;
1521 break;
1522 }
1523 }
1524 if (found)
1525 {
1526 result= differentSecondVarLCs [i];
1527 break;
1528 }
1529 }
1530 if (!found)
1531 result= LCFFactors;
1532 }
1533 if (found)
1534 result.insert (Lc (LCF));
1535 else
1536 result.insert (LCF);
1537
1538 return result;
1539 }
1540
1541 CFList factors= LCFFactors;
1542
1543 for (CFListIterator i= factors; i.hasItem(); i++)
1544 i.getItem()= M (i.getItem());
1545
1546 CanonicalForm sqrfPartF;
1547 CFFList * bufSqrfFactors= new CFFList [factors.length()];
1548 CFList evalSqrfPartF, bufFactors;
1549 CFArray evalPoint= CFArray (evaluation.length() - 1);
1550 CFArray buf= CFArray (evaluation.length());
1551 CFArray swap= CFArray (evaluation.length());
1553 CanonicalForm vars=getVars (LCF)*Variable (2);
1554 for (int i= evaluation.length() +1; i > 1; i--, iter++)
1555 {
1556 buf[i-2]=iter.getItem();
1557 if (degree (vars, i) > 0)
1558 swap[M(Variable (i)).level()-1]=buf[i-2];
1559 }
1560 buf= swap;
1561 for (int i= 0; i < evaluation.length() - 1; i++)
1562 evalPoint[i]= buf[i+1];
1563
1564 int pass= testFactors (F, factors, alpha, sqrfPartF,
1565 bufFactors, bufSqrfFactors, evalSqrfPartF, evalPoint);
1566
1567 bool foundDifferent= false;
1568 Variable z, x= y;
1569 int j= 0;
1570 if (!pass)
1571 {
1572 int lev= 0;
1573 // LCF is non-constant here
1574 CFList bufBufFactors;
1575 CanonicalForm bufF;
1576 for (int i= 0; i < lSecondVarLCs; i++)
1577 {
1578 if (!differentSecondVarLCs [i].isEmpty())
1579 {
1580 bool allConstant= true;
1581 for (iter= differentSecondVarLCs[i]; iter.hasItem(); iter++)
1582 {
1583 if (!iter.getItem().inCoeffDomain())
1584 {
1585 allConstant= false;
1586 y= Variable (iter.getItem().level());
1587 lev= M(y).level();
1588 }
1589 }
1590 if (allConstant)
1591 continue;
1592
1593 bufFactors= differentSecondVarLCs [i];
1594 for (iter= bufFactors; iter.hasItem(); iter++)
1595 iter.getItem()= swapvar (iter.getItem(), x, y);
1596 bufF= F;
1597 z= Variable (lev);
1598 bufF= swapvar (bufF, x, z);
1599 bufBufFactors= bufFactors;
1600 evalPoint= CFArray (evaluation.length() - 1);
1601 for (int k= 1; k < evaluation.length(); k++)
1602 {
1603 if (N (Variable (k+1)).level() != y.level())
1604 evalPoint[k-1]= buf[k];
1605 else
1606 evalPoint[k-1]= buf[0];
1607 }
1608 pass= testFactors (bufF, bufBufFactors, alpha, sqrfPartF, bufFactors,
1609 bufSqrfFactors, evalSqrfPartF, evalPoint);
1610 if (pass)
1611 {
1612 foundDifferent= true;
1613 F= bufF;
1614 CFList l= factors;
1615 for (iter= l; iter.hasItem(); iter++)
1616 iter.getItem()= swapvar (iter.getItem(), x, y);
1617 differentSecondVarLCs [i]= l;
1618 j= i;
1619 break;
1620 }
1621 if (!pass && i == lSecondVarLCs - 1)
1622 {
1623 CFList result;
1624 result.append (LCF);
1625 for (int j= 1; j <= factors.length(); j++)
1626 result.append (1);
1627 result= distributeContent (result, differentSecondVarLCs, lSecondVarLCs);
1628 y= Variable (1);
1629 delete [] bufSqrfFactors;
1630 return result;
1631 }
1632 }
1633 }
1634 }
1635 if (!pass)
1636 {
1637 CFList result;
1638 result.append (LCF);
1639 for (int j= 1; j <= factors.length(); j++)
1640 result.append (1);
1641 result= distributeContent (result, differentSecondVarLCs, lSecondVarLCs);
1642 y= Variable (1);
1643 delete [] bufSqrfFactors;
1644 return result;
1645 }
1646 else
1647 factors= bufFactors;
1648
1649 bufFactors= factors;
1650
1651 CFMap MM, NN;
1652 dummy [0]= sqrfPartF;
1653 dummy [1]= 1;
1654 compress (dummy, MM, NN);
1655 sqrfPartF= MM (sqrfPartF);
1656 CanonicalForm varsSqrfPartF= getVars (sqrfPartF);
1657 for (CFListIterator iter= factors; iter.hasItem(); iter++)
1658 iter.getItem()= MM (iter.getItem());
1659
1660 CFList evaluation2;
1661 for (int i= 2; i <= varsSqrfPartF.level(); i++)
1662 evaluation2.insert (evalPoint[NN (Variable (i)).level()-2]);
1663
1664 CFList interMedResult;
1665 CanonicalForm oldSqrfPartF= sqrfPartF;
1666 sqrfPartF= shift2Zero (sqrfPartF, evalSqrfPartF, evaluation2);
1667 if (factors.length() > 1)
1668 {
1669 CanonicalForm LC1= LC (oldSqrfPartF, 1);
1670 CFList leadingCoeffs;
1671 for (int i= 0; i < factors.length(); i++)
1672 leadingCoeffs.append (LC1);
1673
1674 CFList LC1eval= evaluateAtEval (LC1, evaluation2, 2);
1675 CFList oldFactors= factors;
1676 for (CFListIterator i= oldFactors; i.hasItem(); i++)
1677 i.getItem() *= LC1eval.getFirst()/Lc (i.getItem());
1678
1679 bool success= false;
1680 CanonicalForm oldSqrfPartFPowLC= oldSqrfPartF*power(LC1,factors.length()-1);
1681 CFList heuResult;
1682 if (size (oldSqrfPartFPowLC)/getNumVars (oldSqrfPartFPowLC) < 500 &&
1683 LucksWangSparseHeuristic (oldSqrfPartFPowLC,
1684 oldFactors, 2, leadingCoeffs, heuResult))
1685 {
1686 interMedResult= recoverFactors (oldSqrfPartF, heuResult);
1687 if (oldFactors.length() == interMedResult.length())
1688 success= true;
1689 }
1690 if (!success)
1691 {
1692 LC1= LC (evalSqrfPartF.getFirst(), 1);
1693
1694 CFArray leadingCoeffs= CFArray (factors.length());
1695 for (int i= 0; i < factors.length(); i++)
1696 leadingCoeffs[i]= LC1;
1697
1698 for (CFListIterator i= factors; i.hasItem(); i++)
1699 i.getItem() *= LC1 (0,2)/Lc (i.getItem());
1700 factors.insert (1);
1701
1703 newSqrfPartF= evalSqrfPartF.getFirst()*power (LC1, factors.length() - 2);
1704
1705 int liftBound= degree (newSqrfPartF,2) + 1;
1706
1707 CFMatrix M= CFMatrix (liftBound, factors.length() - 1);
1708 CFArray Pi;
1709 CFList diophant;
1710 nonMonicHenselLift12 (newSqrfPartF, factors, liftBound, Pi, diophant, M,
1711 leadingCoeffs, false);
1712
1713 if (sqrfPartF.level() > 2)
1714 {
1715 int* liftBounds= new int [sqrfPartF.level() - 1];
1716 bool noOneToOne= false;
1717 CFList *leadingCoeffs2= new CFList [sqrfPartF.level()-2];
1718 LC1= LC (evalSqrfPartF.getLast(), 1);
1719 CFList LCs;
1720 for (int i= 0; i < factors.length(); i++)
1721 LCs.append (LC1);
1722 leadingCoeffs2 [sqrfPartF.level() - 3]= LCs;
1723 for (int i= sqrfPartF.level() - 1; i > 2; i--)
1724 {
1725 for (CFListIterator j= LCs; j.hasItem(); j++)
1726 j.getItem()= j.getItem() (0, i + 1);
1727 leadingCoeffs2 [i - 3]= LCs;
1728 }
1729 sqrfPartF *= power (LC1, factors.length()-1);
1730
1731 int liftBoundsLength= sqrfPartF.level() - 1;
1732 for (int i= 0; i < liftBoundsLength; i++)
1733 liftBounds [i]= degree (sqrfPartF, i + 2) + 1;
1734 evalSqrfPartF= evaluateAtZero (sqrfPartF);
1735 evalSqrfPartF.removeFirst();
1736 factors= nonMonicHenselLift (evalSqrfPartF, factors, leadingCoeffs2,
1737 diophant, Pi, liftBounds, sqrfPartF.level() - 1, noOneToOne);
1738 delete [] leadingCoeffs2;
1739 delete [] liftBounds;
1740 }
1741 for (CFListIterator iter= factors; iter.hasItem(); iter++)
1742 iter.getItem()= reverseShift (iter.getItem(), evaluation2);
1743
1744 interMedResult=
1745 recoverFactors (reverseShift(evalSqrfPartF.getLast(),evaluation2),
1746 factors);
1747 }
1748 }
1749 else
1750 {
1751 CanonicalForm contF=content (oldSqrfPartF,1);
1752 factors= CFList (oldSqrfPartF/contF);
1753 interMedResult= recoverFactors (oldSqrfPartF, factors);
1754 }
1755
1756 for (CFListIterator iter= interMedResult; iter.hasItem(); iter++)
1757 iter.getItem()= NN (iter.getItem());
1758
1759 CFList result;
1761 for (int i= 0; i < LCFFactors.length(); i++)
1762 {
1763 CanonicalForm tmp= 1;
1764 for (k= bufSqrfFactors[i]; k.hasItem(); k++)
1765 {
1766 int pos= findItem (bufFactors, k.getItem().factor());
1767 if (pos)
1768 tmp *= power (getItem (interMedResult, pos), k.getItem().exp());
1769 }
1770 result.append (tmp);
1771 }
1772
1773 for (CFListIterator i= result; i.hasItem(); i++)
1774 {
1775 F /= i.getItem();
1776 if (foundDifferent)
1777 i.getItem()= swapvar (i.getItem(), x, z);
1778 i.getItem()= N (i.getItem());
1779 }
1780
1781 if (foundDifferent)
1782 {
1783 CFList l= differentSecondVarLCs [j];
1784 for (CFListIterator i= l; i.hasItem(); i++)
1785 i.getItem()= swapvar (i.getItem(), y, z);
1786 differentSecondVarLCs [j]= l;
1787 F= swapvar (F, x, z);
1788 }
1789
1790 result.insert (N (F));
1791
1792 result= distributeContent (result, differentSecondVarLCs, lSecondVarLCs);
1793
1794 if (!result.getFirst().inCoeffDomain())
1795 {
1796 // prepare input for recursion
1797 if (foundDifferent)
1798 {
1799 for (CFListIterator i= result; i.hasItem(); i++)
1800 i.getItem()= swapvar (i.getItem(), Variable (2), y);
1801 CFList l= differentSecondVarLCs [j];
1802 for (CFListIterator i= l; i.hasItem(); i++)
1803 i.getItem()= swapvar (i.getItem(), y, z);
1804 differentSecondVarLCs [j]= l;
1805 }
1806
1807 F= result.getFirst();
1808 int level= 0;
1809 if (foundDifferent)
1810 {
1811 level= y.level() - 2;
1812 for (int i= y.level(); i > 1; i--)
1813 {
1814 if (degree (F,i) > 0)
1815 {
1816 if (y.level() == 3)
1817 level= 0;
1818 else
1819 level= i-3;
1820 }
1821 }
1822 }
1823lcretry:
1824 if (lSecondVarLCs - level > 0)
1825 {
1826 CFList evaluation2= evaluation;
1827 int j= lSecondVarLCs+2;
1830 for (i= evaluation2; i.hasItem(); i++, j--)
1831 {
1832 if (j==y.level())
1833 {
1834 swap= i.getItem();
1835 i.getItem()= evaluation2.getLast();
1836 evaluation2.removeLast();
1837 evaluation2.append (swap);
1838 }
1839 }
1840
1841 CFList newLCs= differentSecondVarLCs[level];
1842 if (newLCs.isEmpty())
1843 {
1844 if (degree (F, level+3) > 0)
1845 {
1846 delete [] bufSqrfFactors;
1847 return result; //TODO handle this case
1848 }
1849 level=level+1;
1850 goto lcretry;
1851 }
1852 i= newLCs;
1854 iter++;
1855 CanonicalForm quot;
1856 for (;iter.hasItem(); iter++, i++)
1857 {
1858 swap= iter.getItem();
1859 if (degree (swap, level+3) > 0)
1860 {
1861 int count= evaluation.length()+1;
1862 for (CFListIterator iter2= evaluation2; iter2.hasItem(); iter2++,
1863 count--)
1864 {
1865 if (count != level+3)
1866 swap= swap (iter2.getItem(), count);
1867 }
1868 if (fdivides (swap, i.getItem(), quot))
1869 i.getItem()= quot;
1870 }
1871 }
1872 CFList * differentSecondVarLCs2= new CFList [lSecondVarLCs - level - 1];
1873 for (int j= level+1; j < lSecondVarLCs; j++)
1874 {
1875 if (degree (F, j+3) > 0)
1876 {
1877 if (!differentSecondVarLCs[j].isEmpty())
1878 {
1879 differentSecondVarLCs2[j - level - 1]= differentSecondVarLCs[j];
1880 i= differentSecondVarLCs2[j-level - 1];
1881 iter=result;
1882 iter++;
1883 for (;iter.hasItem(); iter++, i++)
1884 {
1885 swap= iter.getItem();
1886 if (degree (swap, j+3) > 0)
1887 {
1888 int count= evaluation.length()+1;
1889 for (CFListIterator iter2= evaluation2; iter2.hasItem();iter2++,
1890 count--)
1891 {
1892 if (count != j+3)
1893 swap= swap (iter2.getItem(), count);
1894 }
1895 if (fdivides (swap, i.getItem(), quot))
1896 i.getItem()= quot;
1897 }
1898 }
1899 }
1900 }
1901 }
1902
1903 for (int j= 0; j < level+1; j++)
1904 evaluation2.removeLast();
1905 Variable dummyvar= Variable (1);
1906
1907 CanonicalForm newLCF= result.getFirst();
1908 newLCF=swapvar (newLCF, Variable (2), Variable (level+3));
1909 for (i=newLCs; i.hasItem(); i++)
1910 i.getItem()= swapvar (i.getItem(), Variable (2), Variable (level+3));
1911 for (int j= 1; j < lSecondVarLCs-level;j++)
1912 {
1913 for (i= differentSecondVarLCs2[j-1]; i.hasItem(); i++)
1914 i.getItem()= swapvar (i.getItem(), Variable (2+j),
1915 Variable (level+3+j));
1916 newLCF= swapvar (newLCF, Variable (2+j), Variable (level+3+j));
1917 }
1918
1919 CFList recursiveResult=
1920 precomputeLeadingCoeff (newLCF, newLCs, alpha, evaluation2,
1921 differentSecondVarLCs2, lSecondVarLCs - level - 1,
1922 dummyvar);
1923
1924 if (dummyvar.level() != 1)
1925 {
1926 for (i= recursiveResult; i.hasItem(); i++)
1927 i.getItem()= swapvar (i.getItem(), Variable (2), dummyvar);
1928 }
1929 for (i= recursiveResult; i.hasItem(); i++)
1930 {
1931 for (int j= lSecondVarLCs-level-1; j > 0; j--)
1932 i.getItem()=swapvar (i.getItem(), Variable (2+j),
1933 Variable (level+3+j));
1934 i.getItem()= swapvar (i.getItem(), Variable (2), Variable (level+3));
1935 }
1936
1937 if (recursiveResult.getFirst() == result.getFirst())
1938 {
1939 delete [] bufSqrfFactors;
1940 delete [] differentSecondVarLCs2;
1941 return result;
1942 }
1943 else
1944 {
1945 iter=recursiveResult;
1946 i= result;
1947 i.getItem()= iter.getItem();
1948 i++;
1949 iter++;
1950 for (; i.hasItem(); i++, iter++)
1951 i.getItem() *= iter.getItem();
1952 delete [] differentSecondVarLCs2;
1953 }
1954 }
1955 }
1956 else
1957 y= Variable (1);
1958
1959 delete [] bufSqrfFactors;
1960
1961 return result;
1962}
1963#endif
1964
1965void
1967 const CanonicalForm& A)
1968{
1969 CanonicalForm tmp;
1970 CFList tmp2;
1972 bool preserveDegree= true;
1973 Variable x= Variable (1);
1974 int j, degAi, degA1= degree (A,1);
1975 for (int i= A.level(); i > 2; i--)
1976 {
1977 tmp= A;
1978 tmp2= CFList();
1980 preserveDegree= true;
1981 degAi= degree (A,i);
1982 for (j= A.level(); j > 1; j--, iter++)
1983 {
1984 if (j == i)
1985 continue;
1986 else
1987 {
1988 tmp= tmp (iter.getItem(), j);
1989 tmp2.insert (tmp);
1990 if ((degree (tmp, i) != degAi) ||
1991 (degree (tmp, 1) != degA1))
1992 {
1993 preserveDegree= false;
1994 break;
1995 }
1996 }
1997 }
1998 if (!content(tmp,1).inCoeffDomain())
1999 preserveDegree= false;
2000 if (!content(tmp).inCoeffDomain())
2001 preserveDegree= false;
2002 if (!(gcd (deriv (tmp,x), tmp)).inCoeffDomain())
2003 preserveDegree= false;
2004 if (preserveDegree)
2005 Aeval [i - 3]= tmp2;
2006 else
2007 Aeval [i - 3]= CFList();
2008 }
2009}
2010
2011static inline
2013 const Variable& v)
2014{
2016 for (CFListIterator i= l; i.hasItem(); i++)
2017 result *= i.getItem() (evalPoint, v);
2018 return result;
2019}
2020
2021void
2023 CFList& l1, CFList& l2)
2024{
2025 CanonicalForm g1= f1, g2;
2026 CFListIterator iter1= factors1, iter2= factors2;
2027 for (; iter1.hasItem(); iter1++, iter2++)
2028 {
2029 g2= gcd (g1, iter1.getItem());
2030 if (!g2.inCoeffDomain())
2031 {
2032 l1.append (iter1.getItem());
2033 l2.append (iter2.getItem());
2034 g1 /= g2;
2035 }
2036 }
2037 factors1= Difference (factors1, l1);
2039}
2040
2041/// check if univariate factors @a factors2 of @a factors3 coincide with
2042/// univariate factors of @a factors1 and recombine if necessary.
2043/// The recombined factors of @a factors1 are returned and @a factors3 is
2044/// recombined accordingly.
2045CFList
2046checkOneToOne (const CFList& factors1, const CFList& factors2, CFList& factors3,
2047 const CanonicalForm& evalPoint, const Variable& x)
2048{
2049 CFList uniFactorsOfFactors1;
2050 CFList result, result2;
2051 CFList bad1= factors2;
2052 CFListIterator iter, iter2, iter3;
2053 CanonicalForm tmp;
2054 int pos;
2055
2056 for (iter= factors1; iter.hasItem(); iter++)
2057 {
2058 tmp= iter.getItem() (evalPoint, x);
2059 tmp /= Lc (tmp);
2060 if ((pos= findItem (factors2, tmp)))
2061 {
2062 result2.append (getItem (factors3, pos));
2063 result.append (iter.getItem());
2064 bad1= Difference (bad1, CFList (tmp));
2065 }
2066 else
2067 uniFactorsOfFactors1.append (tmp);
2068 }
2069
2070 CFList bad2, bad3;
2071 bad2= Difference (factors1, result);
2072 bad3= Difference (factors3, result2);
2073 CFList tmp2, tmp3;
2074 CanonicalForm g1, g2, g3, g4;
2075
2076 while (!uniFactorsOfFactors1.isEmpty())
2077 {
2078 tmp= uniFactorsOfFactors1.getFirst();
2079 checkHelper (tmp, bad1, bad3, tmp2, tmp3);
2080 g1= prod (tmp2);
2081 g2= prod (tmp3);
2082 tmp2= CFList();
2083 tmp3= CFList();
2084 checkHelper (g1, uniFactorsOfFactors1, bad2, tmp2, tmp3);
2085 g3= prod (tmp2);
2086 g4= prod (tmp3);
2087 tmp2= CFList();
2088 tmp3= CFList();
2089 do
2090 {
2091 checkHelper (g3, bad1, bad3, tmp2, tmp3);
2092 g1 *= prod (tmp2);
2093 g2 *= prod (tmp3);
2094 tmp2= CFList();
2095 tmp3= CFList();
2096 checkHelper (g1, uniFactorsOfFactors1, bad2, tmp2, tmp3);
2097 g3 *= prod (tmp2);
2098 g4 *= prod (tmp3);
2099 tmp2= CFList();
2100 tmp3= CFList();
2101 } while (!bad2.isEmpty() && !bad3.isEmpty());
2102 result.append (g4);
2103 result2.append (g2);
2104 }
2105
2106 if (factors3.length() != result2.length())
2107 factors3= result2;
2108 return result;
2109}
2110
2111//recombine bivariate factors in case one bivariate factorization yields less
2112// factors than the other
2113CFList
2114recombination (const CFList& factors1, const CFList& factors2, int s, int thres,
2115 const CanonicalForm& evalPoint, const Variable& x)
2116{
2117 CFList T, S;
2118
2119 T= factors1;
2120 CFList result;
2122 int * v= new int [T.length()];
2123 for (int i= 0; i < T.length(); i++)
2124 v[i]= 0;
2125 bool nosubset= false;
2126 CFArray TT;
2127 TT= copy (factors1);
2128 int recombinations= 0;
2129 while (T.length() >= 2*s && s <= thres)
2130 {
2131 while (nosubset == false)
2132 {
2133 if (T.length() == s)
2134 {
2135 delete [] v;
2136 if (recombinations == factors2.length() - 1)
2137 result.append (prod (T));
2138 else
2139 result= Union (result, T);
2140 return result;
2141 }
2142 S= subset (v, s, TT, nosubset);
2143 if (nosubset) break;
2144 buf= prodEval (S, evalPoint, x);
2145 buf /= Lc (buf);
2146 if (find (factors2, buf))
2147 {
2148 recombinations++;
2149 T= Difference (T, S);
2150 result.append (prod (S));
2151 TT= copy (T);
2152 indexUpdate (v, s, T.length(), nosubset);
2153 if (nosubset) break;
2154 }
2155 }
2156 s++;
2157 if (T.length() < 2*s || T.length() == s)
2158 {
2159 if (recombinations == factors2.length() - 1)
2160 result.append (prod (T));
2161 else
2162 result= Union (result, T);
2163 delete [] v;
2164 return result;
2165 }
2166 for (int i= 0; i < T.length(); i++)
2167 v[i]= 0;
2168 nosubset= false;
2169 }
2170
2171 delete [] v;
2172 if (T.length() < 2*s)
2173 {
2174 result= Union (result, T);
2175 return result;
2176 }
2177
2178 return result;
2179}
2180
2181#if defined(HAVE_NTL) || defined(HAVE_FLINT)
2182#ifdef HAVE_NTL // GFBiSqrfFactorize
2183void
2185 const ExtensionInfo& info,
2186 int& minFactorsLength, bool& irred)
2187{
2188 Variable x= Variable (1);
2190 irred= false;
2191 CFList factors;
2192 Variable v;
2193 for (int j= 0; j < A.level() - 2; j++)
2194 {
2195 if (!Aeval[j].isEmpty())
2196 {
2197 v= Variable (Aeval[j].getFirst().level());
2199 factors= GFBiSqrfFactorize (Aeval[j].getFirst());
2200 else if (info.getAlpha().level() == 1)
2201 factors= FpBiSqrfFactorize (Aeval[j].getFirst());
2202 else
2203 factors= FqBiSqrfFactorize (Aeval[j].getFirst(), info.getAlpha());
2204
2205 factors.removeFirst();
2206 if (minFactorsLength == 0)
2207 minFactorsLength= factors.length();
2208 else
2210
2211 if (factors.length() == 1)
2212 {
2213 irred= true;
2214 return;
2215 }
2216 sortList (factors, x);
2217 Aeval [j]= factors;
2218 }
2219 }
2220}
2221#endif
2222#endif
2223
2225{
2226 CFList result;
2227 for (int i= A.max(); i >= A.min(); i--)
2228 result.insert (A[i]);
2229 return result;
2230}
2231
2232
2234 )
2235{
2237 CFList LCs;
2238 for (int j= 0; j < A.level() - 2; j++)
2239 {
2240 if (!Aeval[j].isEmpty())
2241 {
2242 LCs= CFList();
2243 for (iter= Aeval[j]; iter.hasItem(); iter++)
2244 LCs.append (LC (iter.getItem(), 1));
2245 //normalize (LCs);
2246 Aeval[j]= LCs;
2247 }
2248 }
2249}
2250
2251void sortByUniFactors (CFList*& Aeval, int AevalLength,
2252 CFList& uniFactors, CFList& biFactors,
2253 const CFList& evaluation
2254 )
2255{
2257 int i;
2258 CFListIterator iter, iter2;
2259 Variable v;
2260 CFList LCs, buf;
2261 CFArray l;
2262 int pos, index, checklength;
2263 bool leaveLoop=false;
2264recurse:
2265 for (int j= 0; j < AevalLength; j++)
2266 {
2267 if (!Aeval[j].isEmpty())
2268 {
2269 i= evaluation.length() + 1;
2270 for (iter= evaluation; iter.hasItem(); iter++, i--)
2271 {
2272 for (iter2= Aeval[j]; iter2.hasItem(); iter2++)
2273 {
2274 if (i == iter2.getItem().level())
2275 {
2276 evalPoint= iter.getItem();
2277 leaveLoop= true;
2278 break;
2279 }
2280 }
2281 if (leaveLoop)
2282 {
2283 leaveLoop= false;
2284 break;
2285 }
2286 }
2287
2288 v= Variable (i);
2289 if (Aeval[j].length() > uniFactors.length())
2290 Aeval[j]= recombination (Aeval[j], uniFactors, 1,
2291 Aeval[j].length() - uniFactors.length() + 1,
2292 evalPoint, v);
2293
2294 checklength= biFactors.length();
2295 Aeval[j]= checkOneToOne (Aeval[j], uniFactors, biFactors, evalPoint, v);
2296 if (checklength > biFactors.length())
2297 {
2298 uniFactors= buildUniFactors (biFactors, evaluation.getLast(),
2299 Variable (2));
2300 goto recurse;
2301 }
2302
2304 l= CFArray (uniFactors.length());
2305 index= 1;
2306 for (iter= buf; iter.hasItem(); iter++, index++)
2307 {
2308 pos= findItem (uniFactors, iter.getItem());
2309 if (pos)
2310 l[pos-1]= getItem (Aeval[j], index);
2311 }
2312 buf= conv (l);
2313 Aeval [j]= buf;
2314
2316 }
2317 }
2318}
2319
2320CFList
2322 const Variable& y)
2323{
2324 CFList result;
2325 CanonicalForm tmp;
2326 for (CFListIterator i= biFactors; i.hasItem(); i++)
2327 {
2328 tmp= mod (i.getItem(), y - evalPoint);
2329 tmp /= Lc (tmp);
2330 result.append (tmp);
2331 }
2332 return result;
2333}
2334
2335void refineBiFactors (const CanonicalForm& A, CFList& biFactors,
2336 CFList* const& Aeval, const CFList& evaluation,
2337 int minFactorsLength)
2338{
2339 CFListIterator iter, iter2;
2341 int i;
2342 Variable v;
2343 Variable y= Variable (2);
2344 CFList list;
2345 bool leaveLoop= false;
2346 for (int j= 0; j < A.level() - 2; j++)
2347 {
2348 if (Aeval[j].length() == minFactorsLength)
2349 {
2350 i= A.level();
2351
2352 for (iter= evaluation; iter.hasItem(); iter++, i--)
2353 {
2354 for (iter2= Aeval[j]; iter2.hasItem(); iter2++)
2355 {
2356 if (i == iter2.getItem().level())
2357 {
2358 evalPoint= iter.getItem();
2359 leaveLoop= true;
2360 break;
2361 }
2362 }
2363 if (leaveLoop)
2364 {
2365 leaveLoop= false;
2366 break;
2367 }
2368 }
2369
2370 v= Variable (i);
2371 list= buildUniFactors (Aeval[j], evalPoint, v);
2372
2373 biFactors= recombination (biFactors, list, 1,
2374 biFactors.length() - list.length() + 1,
2375 evaluation.getLast(), y);
2376 return;
2377 }
2378 }
2379}
2380
2381void
2383 const CFList& leadingCoeffs, const CFList& biFactors,
2384 const CFList& evaluation)
2385{
2386 CFList l= leadingCoeffs;
2387 LCs [n-3]= l;
2390 for (int i= n - 1; i > 2; i--, iter++)
2391 {
2392 for (j= l; j.hasItem(); j++)
2393 j.getItem()= j.getItem() (iter.getItem(), i + 1);
2394 LCs [i - 3]= l;
2395 }
2396 l= LCs [0];
2397 for (CFListIterator i= l; i.hasItem(); i++)
2398 i.getItem()= i.getItem() (iter.getItem(), 3);
2399 CFListIterator ii= biFactors;
2400 CFList normalizeFactor;
2401 for (CFListIterator i= l; i.hasItem(); i++, ii++)
2402 normalizeFactor.append (Lc (LC (ii.getItem(), 1))/Lc (i.getItem()));
2403 for (int i= 0; i < n-2; i++)
2404 {
2405 ii= normalizeFactor;
2406 for (j= LCs [i]; j.hasItem(); j++, ii++)
2407 j.getItem() *= ii.getItem();
2408 }
2409
2411
2412 CanonicalForm hh= 1/Lc (Aeval.getFirst());
2413
2414 for (iter= Aeval; iter.hasItem(); iter++)
2415 iter.getItem() *= hh;
2416
2417 A *= hh;
2418}
2419
2420CFList
2422 const ExtensionInfo& info)
2423{
2424 Variable alpha= info.getAlpha();
2425 Variable beta= info.getBeta();
2426 CanonicalForm gamma= info.getGamma();
2427 CanonicalForm delta= info.getDelta();
2428 int k= info.getGFDegree();
2429 CFList source, dest;
2430
2431 int degMipoBeta= 1;
2432 if (!k && beta != Variable(1))
2433 degMipoBeta= degree (getMipo (beta));
2434
2435 CFList T, S;
2436 T= factors;
2437 int s= 1;
2438 CFList result;
2439 CanonicalForm quot, buf= F;
2440
2443 int * v= new int [T.length()];
2444 for (int i= 0; i < T.length(); i++)
2445 v[i]= 0;
2446 bool noSubset= false;
2447 CFArray TT;
2448 TT= copy (factors);
2449 bool recombination= false;
2450 bool trueFactor= false;
2451 while (T.length() >= 2*s)
2452 {
2453 while (noSubset == false)
2454 {
2455 if (T.length() == s)
2456 {
2457 delete [] v;
2458 if (recombination)
2459 {
2460 g= prod (T);
2461 T.removeFirst();
2462 g /= myContent (g);
2463 g /= Lc (g);
2464 appendTestMapDown (result, g, info, source, dest);
2465 return result;
2466 }
2467 else
2468 return CFList (buf/myContent(buf));
2469 }
2470
2471 S= subset (v, s, TT, noSubset);
2472 if (noSubset) break;
2473
2474 g= prod (S);
2475 g /= myContent (g);
2476 if (fdivides (g, buf, quot))
2477 {
2478 buf2= g;
2479 buf2 /= Lc (buf2);
2480 if (!k && beta.level() == 1)
2481 {
2482 if (degree (buf2, alpha) < degMipoBeta)
2483 {
2484 appendTestMapDown (result, buf2, info, source, dest);
2485 buf= quot;
2486 recombination= true;
2487 trueFactor= true;
2488 }
2489 }
2490 else
2491 {
2492 if (!isInExtension (buf2, gamma, k, delta, source, dest))
2493 {
2494 appendTestMapDown (result, buf2, info, source, dest);
2495 buf= quot;
2496 recombination= true;
2497 trueFactor= true;
2498 }
2499 }
2500 if (trueFactor)
2501 {
2502 T= Difference (T, S);
2503
2504 if (T.length() < 2*s || T.length() == s)
2505 {
2506 delete [] v;
2507 buf /= myContent (buf);
2508 buf /= Lc (buf);
2509 appendTestMapDown (result, buf, info, source, dest);
2510 return result;
2511 }
2512 trueFactor= false;
2513 TT= copy (T);
2514 indexUpdate (v, s, T.length(), noSubset);
2515 if (noSubset) break;
2516 }
2517 }
2518 }
2519 s++;
2520 if (T.length() < 2*s || T.length() == s)
2521 {
2522 delete [] v;
2523 buf /= myContent (buf);
2524 buf /= Lc (buf);
2525 appendTestMapDown (result, buf, info, source, dest);
2526 return result;
2527 }
2528 for (int i= 0; i < T.length(); i++)
2529 v[i]= 0;
2530 noSubset= false;
2531 }
2532 if (T.length() < 2*s)
2533 {
2534 buf= F/myContent (F);
2535 buf /= Lc (buf);
2536 appendMapDown (result, buf, info, source, dest);
2537 }
2538
2539 delete [] v;
2540 return result;
2541}
2542
2543void
2545 CFList*& oldAeval, int lengthAeval2,
2546 const CFList& uniFactors, const Variable& w)
2547{
2548 Variable y= Variable (2);
2549 A= swapvar (A, y, w);
2550 int i= A.level();
2552 for (CFListIterator iter= evaluation; iter.hasItem(); iter++, i--)
2553 {
2554 if (i == w.level())
2555 {
2556 evalPoint= iter.getItem();
2557 iter.getItem()= evaluation.getLast();
2558 evaluation.removeLast();
2559 evaluation.append (evalPoint);
2560 break;
2561 }
2562 }
2563 for (i= 0; i < lengthAeval2; i++)
2564 {
2565 if (oldAeval[i].isEmpty())
2566 continue;
2567 if (oldAeval[i].getFirst().level() == w.level())
2568 {
2569 CFArray tmp= copy (oldAeval[i]);
2570 oldAeval[i]= biFactors;
2571 for (CFListIterator iter= oldAeval[i]; iter.hasItem(); iter++)
2572 iter.getItem()= swapvar (iter.getItem(), w, y);
2573 for (int ii= 0; ii < tmp.size(); ii++)
2574 tmp[ii]= swapvar (tmp[ii], w, y);
2575 CFArray tmp2= CFArray (tmp.size());
2577 for (int ii= 0; ii < tmp.size(); ii++)
2578 {
2579 buf= tmp[ii] (evaluation.getLast(),y);
2580 buf /= Lc (buf);
2581 tmp2[findItem (uniFactors, buf)-1]=tmp[ii];
2582 }
2583 biFactors= CFList();
2584 for (int j= 0; j < tmp2.size(); j++)
2585 biFactors.append (tmp2[j]);
2586 }
2587 }
2588}
2589
2590void
2592 CFList& biFactors, const CFList& evaluation,
2593 const CanonicalForm& LCmultipler)
2594{
2595 CanonicalForm tmp= power (LCmultipler, biFactors.length() - 1);
2596 A *= tmp;
2597 tmp= LCmultipler;
2598 CFListIterator iter= leadingCoeffs;
2599 for (;iter.hasItem(); iter++)
2600 iter.getItem() *= LCmultipler;
2602 for (int i= A.level(); i > 2; i--, iter++)
2603 tmp= tmp (iter.getItem(), i);
2604 if (!tmp.inCoeffDomain())
2605 {
2606 for (CFListIterator i= biFactors; i.hasItem(); i++)
2607 {
2608 i.getItem() *= tmp/LC (i.getItem(), 1);
2609 i.getItem() /= Lc (i.getItem());
2610 }
2611 }
2612}
2613
2614void
2616 CFList& biFactors, CFList*& leadingCoeffs, const CFList* oldAeval,
2617 int lengthAeval, const CFList& evaluation,
2618 const CFList& oldBiFactors)
2619{
2620 CFListIterator iter, iter2;
2621 int index;
2622 Variable xx;
2623 CFList vars1;
2624 CFFList sqrfMultiplier= sqrFree (LCmultiplier);
2625 if (sqrfMultiplier.getFirst().factor().inCoeffDomain())
2626 sqrfMultiplier.removeFirst();
2627 sqrfMultiplier= sortCFFListByNumOfVars (sqrfMultiplier);
2628 xx= Variable (2);
2629 for (iter= oldBiFactors; iter.hasItem(); iter++)
2630 vars1.append (power (xx, degree (LC (iter.getItem(),1), xx)));
2631 for (int i= 0; i < lengthAeval; i++)
2632 {
2633 if (oldAeval[i].isEmpty())
2634 continue;
2635 xx= oldAeval[i].getFirst().mvar();
2636 iter2= vars1;
2637 for (iter= oldAeval[i]; iter.hasItem(); iter++, iter2++)
2638 iter2.getItem() *= power (xx, degree (LC (iter.getItem(),1), xx));
2639 }
2640 CanonicalForm tmp, quot1, quot2, quot3;
2641 iter2= vars1;
2642 for (iter= leadingCoeffs[lengthAeval-1]; iter.hasItem(); iter++, iter2++)
2643 {
2644 tmp= iter.getItem()/LCmultiplier;
2645 for (int i=1; i <= tmp.level(); i++)
2646 {
2647 if (degree (tmp,i) > 0 && (degree (iter2.getItem(),i) > degree (tmp,i)))
2648 iter2.getItem() /= power (Variable (i), degree (tmp,i));
2649 }
2650 }
2651 int multi;
2652 for (CFFListIterator ii= sqrfMultiplier; ii.hasItem(); ii++)
2653 {
2654 multi= 0;
2655 for (iter= vars1; iter.hasItem(); iter++)
2656 {
2657 tmp= iter.getItem();
2658 while (fdivides (myGetVars (ii.getItem().factor()), tmp))
2659 {
2660 multi++;
2661 tmp /= myGetVars (ii.getItem().factor());
2662 }
2663 }
2664 if (multi == ii.getItem().exp())
2665 {
2666 index= 1;
2667 for (iter= vars1; iter.hasItem(); iter++, index++)
2668 {
2669 while (fdivides (myGetVars (ii.getItem().factor()), iter.getItem()))
2670 {
2671 int index2= 1;
2672 for (iter2= leadingCoeffs[lengthAeval-1]; iter2.hasItem();iter2++,
2673 index2++)
2674 {
2675 if (index2 == index)
2676 continue;
2677 else
2678 {
2679 tmp= ii.getItem().factor();
2680 if (fdivides (tmp, iter2.getItem(), quot1))
2681 {
2683 for (int jj= A.level(); jj > 2; jj--, iter3++)
2684 tmp= tmp (iter3.getItem(), jj);
2685 if (!tmp.inCoeffDomain())
2686 {
2687 int index3= 1;
2688 for (iter3= biFactors; iter3.hasItem(); iter3++, index3++)
2689 {
2690 if (index3 == index2)
2691 {
2692 if (fdivides (tmp, iter3.getItem(), quot2))
2693 {
2694 if (fdivides (ii.getItem().factor(), A, quot3))
2695 {
2696 A = quot3;
2697 iter2.getItem() = quot2;
2698 iter3.getItem() = quot3;
2699 iter3.getItem() /= Lc (iter3.getItem());
2700 break;
2701 }
2702 }
2703 }
2704 }
2705 }
2706 }
2707 }
2708 }
2709 iter.getItem() /= getVars (ii.getItem().factor());
2710 }
2711 }
2712 }
2713 else
2714 {
2715 index= 1;
2716 for (iter= vars1; iter.hasItem(); iter++, index++)
2717 {
2718 if (!fdivides (myGetVars (ii.getItem().factor()), iter.getItem()))
2719 {
2720 int index2= 1;
2721 for (iter2= leadingCoeffs[lengthAeval-1];iter2.hasItem();iter2++,
2722 index2++)
2723 {
2724 if (index2 == index)
2725 {
2726 tmp= power (ii.getItem().factor(), ii.getItem().exp());
2727 if (fdivides (tmp, A, quot1))
2728 {
2729 if (fdivides (tmp, iter2.getItem()))
2730 {
2732 for (int jj= A.level(); jj > 2; jj--, iter3++)
2733 tmp= tmp (iter3.getItem(), jj);
2734 if (!tmp.inCoeffDomain())
2735 {
2736 int index3= 1;
2737 for (iter3= biFactors; iter3.hasItem(); iter3++, index3++)
2738 {
2739 if (index3 == index2)
2740 {
2741 if (fdivides (tmp, iter3.getItem(), quot3))
2742 {
2743 A = quot1;
2744 iter2.getItem() = quot2;
2745 iter3.getItem() = quot3;
2746 iter3.getItem() /= Lc (iter3.getItem());
2747 break;
2748 }
2749 }
2750 }
2751 }
2752 }
2753 }
2754 }
2755 }
2756 }
2757 }
2758 }
2759 }
2760}
2761
2762void
2763LCHeuristicCheck (const CFList& LCs, const CFList& contents, CanonicalForm& A,
2764 const CanonicalForm& oldA, CFList& leadingCoeffs,
2765 bool& foundTrueMultiplier)
2766{
2767 CanonicalForm pLCs= prod (LCs);
2768 if (fdivides (pLCs, LC (oldA,1)) && (LC(oldA,1)/pLCs).inCoeffDomain()) // check if the product of the lead coeffs of the primitive factors equals the lead coeff of the old A
2769 {
2770 A= oldA;
2771 CFListIterator iter2= leadingCoeffs;
2772 for (CFListIterator iter= contents; iter.hasItem(); iter++, iter2++)
2773 iter2.getItem() /= iter.getItem();
2774 foundTrueMultiplier= true;
2775 }
2776}
2777
2778void
2779LCHeuristic2 (const CanonicalForm& LCmultiplier, const CFList& factors,
2780 CFList& leadingCoeffs, CFList& contents, CFList& LCs,
2781 bool& foundTrueMultiplier)
2782{
2783 CanonicalForm cont;
2784 int index= 1;
2785 CFListIterator iter2;
2786 for (CFListIterator iter= factors; iter.hasItem(); iter++, index++)
2787 {
2788 cont= content (iter.getItem(), 1);
2789 cont= gcd (cont, LCmultiplier);
2790 contents.append (cont);
2791 if (cont.inCoeffDomain()) // trivial content->LCmultiplier needs to go there
2792 {
2793 foundTrueMultiplier= true;
2794 int index2= 1;
2795 for (iter2= leadingCoeffs; iter2.hasItem(); iter2++, index2++)
2796 {
2797 if (index2 == index)
2798 continue;
2799 iter2.getItem() /= LCmultiplier;
2800 }
2801 break;
2802 }
2803 else
2804 LCs.append (LC (iter.getItem()/cont, 1));
2805 }
2806}
2807
2808void
2809LCHeuristic3 (const CanonicalForm& LCmultiplier, const CFList& factors,
2810 const CFList& oldBiFactors, const CFList& contents,
2811 const CFList* oldAeval, CanonicalForm& A, CFList*& leadingCoeffs,
2812 int lengthAeval, bool& foundMultiplier)
2813{
2814 int index= 1;
2815 CFListIterator iter, iter2= factors;
2816 for (iter= contents; iter.hasItem(); iter++, iter2++, index++)
2817 {
2818 if (fdivides (iter.getItem(), LCmultiplier))
2819 {
2820 if ((LCmultiplier/iter.getItem()).inCoeffDomain() &&
2821 !isOnlyLeadingCoeff(iter2.getItem())) //content divides LCmultiplier completely and factor consists of more terms than just the leading coeff
2822 {
2823 Variable xx= Variable (2);
2824 CanonicalForm vars;
2825 vars= power (xx, degree (LC (getItem(oldBiFactors, index),1),
2826 xx));
2827 for (int i= 0; i < lengthAeval; i++)
2828 {
2829 if (oldAeval[i].isEmpty())
2830 continue;
2831 xx= oldAeval[i].getFirst().mvar();
2832 vars *= power (xx, degree (LC (getItem(oldAeval[i], index),1),
2833 xx));
2834 }
2835 if (vars.level() <= 2)
2836 {
2837 int index2= 1;
2838 for (CFListIterator iter3= leadingCoeffs[lengthAeval-1];
2839 iter3.hasItem(); iter3++, index2++)
2840 {
2841 if (index2 == index)
2842 {
2843 iter3.getItem() /= LCmultiplier;
2844 break;
2845 }
2846 }
2847 A /= LCmultiplier;
2848 foundMultiplier= true;
2849 iter.getItem()= 1;
2850 }
2851 }
2852 }
2853 }
2854}
2855
2856void
2857LCHeuristic4 (const CFList& oldBiFactors, const CFList* oldAeval,
2858 const CFList& contents, const CFList& factors,
2859 const CanonicalForm& testVars, int lengthAeval,
2860 CFList*& leadingCoeffs, CanonicalForm& A,
2861 CanonicalForm& LCmultiplier, bool& foundMultiplier)
2862{
2863 int index=1;
2864 CFListIterator iter, iter2= factors;
2865 for (iter= contents; iter.hasItem(); iter++, iter2++, index++)
2866 {
2867 if (!iter.getItem().isOne() &&
2868 fdivides (iter.getItem(), LCmultiplier))
2869 {
2870 if (!isOnlyLeadingCoeff (iter2.getItem())) // factor is more than just leading coeff
2871 {
2872 int index2= 1;
2873 for (iter2= leadingCoeffs[lengthAeval-1]; iter2.hasItem();
2874 iter2++, index2++)
2875 {
2876 if (index2 == index)
2877 {
2878 iter2.getItem() /= iter.getItem();
2879 foundMultiplier= true;
2880 break;
2881 }
2882 }
2883 A /= iter.getItem();
2884 LCmultiplier /= iter.getItem();
2885 iter.getItem()= 1;
2886 }
2887 else if (fdivides (getVars (LCmultiplier), testVars))//factor consists of just leading coeff
2888 {
2889 Variable xx= Variable (2);
2890 CanonicalForm vars;
2891 vars= power (xx, degree (LC (getItem(oldBiFactors, index),1),
2892 xx));
2893 for (int i= 0; i < lengthAeval; i++)
2894 {
2895 if (oldAeval[i].isEmpty())
2896 continue;
2897 xx= oldAeval[i].getFirst().mvar();
2898 vars *= power (xx, degree (LC (getItem(oldAeval[i], index),1),
2899 xx));
2900 }
2901 if (myGetVars(content(getItem(leadingCoeffs[lengthAeval-1],index),1))
2902 /myGetVars (LCmultiplier) == vars)
2903 {
2904 int index2= 1;
2905 for (iter2= leadingCoeffs[lengthAeval-1]; iter2.hasItem();
2906 iter2++, index2++)
2907 {
2908 if (index2 == index)
2909 {
2910 iter2.getItem() /= LCmultiplier;
2911 foundMultiplier= true;
2912 break;
2913 }
2914 }
2915 A /= LCmultiplier;
2916 iter.getItem()= 1;
2917 }
2918 }
2919 }
2920 }
2921}
2922
2923#if defined(HAVE_NTL) || defined(HAVE_FLINT)
2924#ifdef HAVE_NTL // biSqrfFactorizeHelper
2925CFList
2926extFactorize (const CanonicalForm& F, const ExtensionInfo& info);
2927
2928CFList
2930{
2931 if (F.inCoeffDomain())
2932 return CFList (F);
2933
2934 TIMING_START (fac_fq_preprocess_and_content);
2935 // compress and find main Variable
2936 CFMap N;
2937 TIMING_START (fac_fq_compress)
2939 TIMING_END_AND_PRINT (fac_fq_compress, "time to compress poly over Fq: ")
2940
2941 A /= Lc (A); // make monic
2942
2943 Variable alpha= info.getAlpha();
2944 Variable beta= info.getBeta();
2945 CanonicalForm gamma= info.getGamma();
2946 CanonicalForm delta= info.getDelta();
2947 bool extension= info.isInExtension();
2948 bool GF= (CFFactory::gettype() == GaloisFieldDomain);
2949 //univariate case
2950 if (F.isUnivariate())
2951 {
2952 if (extension == false)
2953 return uniFactorizer (F, alpha, GF);
2954 else
2955 {
2956 CFList source, dest;
2957 A= mapDown (F, info, source, dest);
2958 return uniFactorizer (A, beta, GF);
2959 }
2960 }
2961
2962 //bivariate case
2963 if (A.level() == 2)
2964 {
2966 if (buf.getFirst().inCoeffDomain())
2967 buf.removeFirst();
2968 return buf;
2969 }
2970
2971 Variable x= Variable (1);
2972 Variable y= Variable (2);
2973
2974 // remove content
2975 TIMING_START (fac_fq_content);
2976 CFList contentAi;
2977 CanonicalForm lcmCont= lcmContent (A, contentAi);
2978 A /= lcmCont;
2979 TIMING_END_AND_PRINT (fac_fq_content, "time to extract content over Fq: ");
2980
2981 // trivial after content removal
2982 CFList contentAFactors;
2983 if (A.inCoeffDomain())
2984 {
2985 for (CFListIterator i= contentAi; i.hasItem(); i++)
2986 {
2987 if (i.getItem().inCoeffDomain())
2988 continue;
2989 else
2990 {
2991 lcmCont /= i.getItem();
2992 contentAFactors=
2993 Union (multiFactorize (lcmCont, info),
2994 multiFactorize (i.getItem(), info));
2995 break;
2996 }
2997 }
2998 decompress (contentAFactors, N);
2999 if (!extension)
3000 normalize (contentAFactors);
3001 return contentAFactors;
3002 }
3003
3004 // factorize content
3005 TIMING_START (fac_fq_content);
3006 contentAFactors= multiFactorize (lcmCont, info);
3007 TIMING_END_AND_PRINT (fac_fq_content, "time to factor content over Fq: ");
3008
3009 // univariate after content removal
3010 CFList factors;
3011 if (A.isUnivariate ())
3012 {
3013 factors= uniFactorizer (A, alpha, GF);
3014 append (factors, contentAFactors);
3015 decompress (factors, N);
3016 return factors;
3017 }
3018
3019 // check main variable
3020 TIMING_START (fac_fq_check_mainvar);
3021 int swapLevel= 0;
3022 CanonicalForm derivZ;
3023 CanonicalForm gcdDerivZ;
3024 CanonicalForm bufA= A;
3025 Variable z;
3026 for (int i= 1; i <= A.level(); i++)
3027 {
3028 z= Variable (i);
3029 derivZ= deriv (bufA, z);
3030 if (derivZ.isZero())
3031 {
3032 if (i == 1)
3033 swapLevel= 1;
3034 else
3035 continue;
3036 }
3037 else
3038 {
3039 gcdDerivZ= gcd (bufA, derivZ);
3040 if (degree (gcdDerivZ) > 0 && !derivZ.isZero())
3041 {
3042 CanonicalForm g= bufA/gcdDerivZ;
3043 CFList factorsG=
3045 multiFactorize (gcdDerivZ, info));
3046 appendSwapDecompress (factorsG, contentAFactors, N, swapLevel, x);
3047 if (!extension)
3048 normalize (factorsG);
3049 return factorsG;
3050 }
3051 else
3052 {
3053 if (swapLevel == 1)
3054 {
3055 swapLevel= i;
3056 bufA= swapvar (A, x, z);
3057 }
3058 A= bufA;
3059 break;
3060 }
3061 }
3062 }
3063 TIMING_END_AND_PRINT (fac_fq_check_mainvar,
3064 "time to check main var over Fq: ");
3065 TIMING_END_AND_PRINT (fac_fq_preprocess_and_content,
3066 "time to preprocess poly and extract content over Fq: ");
3067
3068 CFList Aeval, list, evaluation, bufEvaluation, bufAeval;
3069 bool fail= false;
3070 int swapLevel2= 0;
3071 //int level;
3072 int factorNums= 3;
3073 CFList biFactors, bufBiFactors;
3074 CanonicalForm evalPoly;
3075 int lift, bufLift, lengthAeval2= A.level()-2;
3076 double logarithm= (double) ilog2 (totaldegree (A));
3077 logarithm /= log2exp;
3078 logarithm= ceil (logarithm);
3079 if (factorNums < (int) logarithm)
3080 factorNums= (int) logarithm;
3081 CFList* bufAeval2= new CFList [lengthAeval2];
3082 CFList* Aeval2= new CFList [lengthAeval2];
3083 int counter;
3084 int differentSecondVar= 0;
3085 // several bivariate factorizations
3086 TIMING_START (fac_fq_bifactor_total);
3087 for (int i= 0; i < factorNums; i++)
3088 {
3089 counter= 0;
3090 bufA= A;
3091 bufAeval= CFList();
3092 TIMING_START (fac_fq_evaluation);
3093 bufEvaluation= evalPoints (bufA, bufAeval, alpha, list, GF, fail);
3094 TIMING_END_AND_PRINT (fac_fq_evaluation,
3095 "time to find evaluation point over Fq: ");
3096 evalPoly= 0;
3097
3098 if (fail && (i == 0))
3099 {
3100 /*if (!swapLevel) //uncomment to reenable search for new main variable
3101 level= 2;
3102 else
3103 level= swapLevel + 1;*/
3104
3105 //CanonicalForm g;
3106 //swapLevel2= newMainVariableSearch (A, Aeval, evaluation, alpha, level, g);
3107
3108 /*if (!swapLevel2) // need to pass to an extension
3109 {*/
3110 factors= extFactorize (A, info);
3111 appendSwapDecompress (factors, contentAFactors, N, swapLevel, x);
3112 normalize (factors);
3113 delete [] bufAeval2;
3114 delete [] Aeval2;
3115 return factors;
3116 /*}
3117 else
3118 {
3119 if (swapLevel2 == -1)
3120 {
3121 CFList factorsG=
3122 Union (multiFactorize (g, info),
3123 multiFactorize (A/g, info));
3124 appendSwapDecompress (factorsG, contentAFactors, N, swapLevel, x);
3125 if (!extension)
3126 normalize (factorsG);
3127 delete [] bufAeval2;
3128 delete [] Aeval2;
3129 return factorsG;
3130 }
3131 fail= false;
3132 bufAeval= Aeval;
3133 bufA= A;
3134 bufEvaluation= evaluation;
3135 }*/ //end uncomment
3136 }
3137 else if (fail && (i > 0))
3138 break;
3139
3140 TIMING_START (fac_fq_evaluation);
3141 evaluationWRTDifferentSecondVars (bufAeval2, bufEvaluation, A);
3142 TIMING_END_AND_PRINT (fac_fq_evaluation,
3143 "time for evaluation wrt diff second vars over Fq: ");
3144
3145 for (int j= 0; j < lengthAeval2; j++)
3146 {
3147 if (!bufAeval2[j].isEmpty())
3148 counter++;
3149 }
3150
3151 bufLift= degree (A, y) + 1 + degree (LC(A, x), y);
3152
3153 TIMING_START (fac_fq_bi_factorizer);
3154 if (!GF && alpha.level() == 1)
3155 bufBiFactors= FpBiSqrfFactorize (bufAeval.getFirst());
3156 else if (GF)
3157 bufBiFactors= GFBiSqrfFactorize (bufAeval.getFirst());
3158 else
3159 bufBiFactors= FqBiSqrfFactorize (bufAeval.getFirst(), alpha);
3160 TIMING_END_AND_PRINT (fac_fq_bi_factorizer,
3161 "time for bivariate factorization: ");
3162 bufBiFactors.removeFirst();
3163
3164 if (bufBiFactors.length() == 1)
3165 {
3166 if (extension)
3167 {
3168 CFList source, dest;
3169 A= mapDown (A, info, source, dest);
3170 }
3171 factors.append (A);
3172 appendSwapDecompress (factors, contentAFactors, N, swapLevel,
3173 swapLevel2, x);
3174 if (!extension)
3175 normalize (factors);
3176 delete [] bufAeval2;
3177 delete [] Aeval2;
3178 return factors;
3179 }
3180
3181 if (i == 0)
3182 {
3183 Aeval= bufAeval;
3184 evaluation= bufEvaluation;
3185 biFactors= bufBiFactors;
3186 lift= bufLift;
3187 for (int j= 0; j < lengthAeval2; j++)
3188 Aeval2 [j]= bufAeval2 [j];
3189 differentSecondVar= counter;
3190 }
3191 else
3192 {
3193 if (bufBiFactors.length() < biFactors.length() ||
3194 ((bufLift < lift) && (bufBiFactors.length() == biFactors.length())) ||
3195 counter > differentSecondVar)
3196 {
3197 Aeval= bufAeval;
3198 evaluation= bufEvaluation;
3199 biFactors= bufBiFactors;
3200 lift= bufLift;
3201 for (int j= 0; j < lengthAeval2; j++)
3202 Aeval2 [j]= bufAeval2 [j];
3203 differentSecondVar= counter;
3204 }
3205 }
3206 int k= 0;
3207 for (CFListIterator j= bufEvaluation; j.hasItem(); j++, k++)
3208 evalPoly += j.getItem()*power (x, k);
3209 list.append (evalPoly);
3210 }
3211
3212 delete [] bufAeval2;
3213
3214 sortList (biFactors, x);
3215
3216 int minFactorsLength;
3217 bool irred= false;
3218 TIMING_START (fac_fq_bi_factorizer);
3220 TIMING_END_AND_PRINT (fac_fq_bi_factorizer,
3221 "time for bivariate factorization wrt diff second vars over Fq: ");
3222
3223 TIMING_END_AND_PRINT (fac_fq_bifactor_total,
3224 "total time for eval and bivar factors over Fq: ");
3225 if (irred)
3226 {
3227 if (extension)
3228 {
3229 CFList source, dest;
3230 A= mapDown (A, info, source, dest);
3231 }
3232 factors.append (A);
3233 appendSwapDecompress (factors, contentAFactors, N, swapLevel,
3234 swapLevel2, x);
3235 if (!extension)
3236 normalize (factors);
3237 delete [] Aeval2;
3238 return factors;
3239 }
3240
3241 if (minFactorsLength == 0)
3242 minFactorsLength= biFactors.length();
3243 else if (biFactors.length() > minFactorsLength)
3244 refineBiFactors (A, biFactors, Aeval2, evaluation, minFactorsLength);
3246
3247 CFList uniFactors= buildUniFactors (biFactors, evaluation.getLast(), y);
3248
3249 sortByUniFactors (Aeval2, lengthAeval2, uniFactors, biFactors, evaluation);
3250
3252
3253 if (minFactorsLength == 1)
3254 {
3255 if (extension)
3256 {
3257 CFList source, dest;
3258 A= mapDown (A, info, source, dest);
3259 }
3260 factors.append (A);
3261 appendSwapDecompress (factors, contentAFactors, N, swapLevel,
3262 swapLevel2, x);
3263 if (!extension)
3264 normalize (factors);
3265 delete [] Aeval2;
3266 return factors;
3267 }
3268
3269 if (differentSecondVar == lengthAeval2)
3270 {
3271 bool zeroOccured= false;
3272 for (CFListIterator iter= evaluation; iter.hasItem(); iter++)
3273 {
3274 if (iter.getItem().isZero())
3275 {
3276 zeroOccured= true;
3277 break;
3278 }
3279 }
3280 if (!zeroOccured)
3281 {
3282 factors= sparseHeuristic (A, biFactors, Aeval2, evaluation,
3284 if (factors.length() == biFactors.length())
3285 {
3286 if (extension)
3287 factors= extNonMonicFactorRecombination (factors, A, info);
3288
3289 appendSwapDecompress (factors, contentAFactors, N, swapLevel,
3290 swapLevel2, x);
3291 if (!extension)
3292 normalize (factors);
3293 delete [] Aeval2;
3294 return factors;
3295 }
3296 else
3297 factors= CFList();
3298 //TODO case where factors.length() > 0
3299 }
3300 }
3301
3302 CFList * oldAeval= new CFList [lengthAeval2]; //TODO use bufAeval2 for this
3303 for (int i= 0; i < lengthAeval2; i++)
3304 oldAeval[i]= Aeval2[i];
3305
3306 getLeadingCoeffs (A, Aeval2);
3307
3308 CFList biFactorsLCs;
3309 for (CFListIterator i= biFactors; i.hasItem(); i++)
3310 biFactorsLCs.append (LC (i.getItem(), 1));
3311
3312 Variable v;
3313 TIMING_START (fac_fq_precompute_leadcoeff);
3314 CFList leadingCoeffs= precomputeLeadingCoeff (LC (A, 1), biFactorsLCs, alpha,
3315 evaluation, Aeval2, lengthAeval2, v);
3316
3317 if (v.level() != 1)
3318 changeSecondVariable (A, biFactors, evaluation, oldAeval, lengthAeval2,
3319 uniFactors, v);
3320
3321 CanonicalForm oldA= A;
3322 CFList oldBiFactors= biFactors;
3323
3324 CanonicalForm LCmultiplier= leadingCoeffs.getFirst();
3325 bool LCmultiplierIsConst= LCmultiplier.inCoeffDomain();
3326 leadingCoeffs.removeFirst();
3327
3328 if (!LCmultiplierIsConst)
3329 distributeLCmultiplier (A, leadingCoeffs, biFactors, evaluation, LCmultiplier);
3330
3331 //prepare leading coefficients
3332 CFList* leadingCoeffs2= new CFList [lengthAeval2];
3333 prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(), leadingCoeffs,
3334 biFactors, evaluation);
3335
3337 CFList bufLeadingCoeffs2= leadingCoeffs2[lengthAeval2-1];
3338 bufBiFactors= biFactors;
3339 bufA= A;
3340 CanonicalForm testVars, bufLCmultiplier= LCmultiplier;
3341 if (!LCmultiplierIsConst)
3342 {
3343 testVars= Variable (2);
3344 for (int i= 0; i < lengthAeval2; i++)
3345 {
3346 if (!oldAeval[i].isEmpty())
3347 testVars *= oldAeval[i].getFirst().mvar();
3348 }
3349 }
3350 TIMING_END_AND_PRINT(fac_fq_precompute_leadcoeff,
3351 "time to precompute LC over Fq: ");
3352
3353 TIMING_START (fac_fq_luckswang);
3354 CFList bufFactors= CFList();
3355 bool LCheuristic= false;
3356 if (LucksWangSparseHeuristic (A, biFactors, 2, leadingCoeffs2[lengthAeval2-1],
3357 factors))
3358 {
3359 int check= biFactors.length();
3360 int * index= new int [factors.length()];
3361 CFList oldFactors= factors;
3362 factors= recoverFactors (A, factors, index);
3363
3364 if (check == factors.length())
3365 {
3366 if (extension)
3367 factors= extNonMonicFactorRecombination (factors, bufA, info);
3368
3369 if (v.level() != 1)
3370 {
3371 for (iter= factors; iter.hasItem(); iter++)
3372 iter.getItem()= swapvar (iter.getItem(), v, y);
3373 }
3374
3375 appendSwapDecompress (factors, contentAFactors, N, swapLevel,
3376 swapLevel2, x);
3377 if (!extension)
3378 normalize (factors);
3379 delete [] index;
3380 delete [] Aeval2;
3381 TIMING_END_AND_PRINT (fac_fq_luckswang,
3382 "time for successful LucksWang over Fq: ");
3383 return factors;
3384 }
3385 else if (factors.length() > 0)
3386 {
3387 int oneCount= 0;
3388 CFList l;
3389 for (int i= 0; i < check; i++)
3390 {
3391 if (index[i] == 1)
3392 {
3393 iter=biFactors;
3394 for (int j=1; j <= i-oneCount; j++)
3395 iter++;
3396 iter.remove (1);
3397 for (int j= 0; j < lengthAeval2; j++)
3398 {
3399 l= leadingCoeffs2[j];
3400 iter= l;
3401 for (int k=1; k <= i-oneCount; k++)
3402 iter++;
3403 iter.remove (1);
3404 leadingCoeffs2[j]=l;
3405 }
3406 oneCount++;
3407 }
3408 }
3409 bufFactors= factors;
3410 factors= CFList();
3411 }
3412 else if (!LCmultiplierIsConst && factors.length() == 0)
3413 {
3414 LCheuristic= true;
3415 factors= oldFactors;
3416 CFList contents, LCs;
3417 bool foundTrueMultiplier= false;
3418 LCHeuristic2 (LCmultiplier, factors, leadingCoeffs2[lengthAeval2-1],
3419 contents, LCs, foundTrueMultiplier);
3420 if (foundTrueMultiplier)
3421 {
3422 A= oldA;
3423 leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
3424 for (int i= lengthAeval2-1; i > -1; i--)
3425 leadingCoeffs2[i]= CFList();
3426 prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(),
3427 leadingCoeffs, biFactors, evaluation);
3428 }
3429 else
3430 {
3431 bool foundMultiplier= false;
3432 LCHeuristic3 (LCmultiplier, factors, oldBiFactors, contents, oldAeval,
3433 A, leadingCoeffs2, lengthAeval2, foundMultiplier);
3434
3435 // coming from above: divide out more LCmultiplier if possible
3436 if (foundMultiplier)
3437 {
3438 foundMultiplier= false;
3439 LCHeuristic4 (oldBiFactors, oldAeval, contents, factors, testVars,
3440 lengthAeval2, leadingCoeffs2, A, LCmultiplier,
3441 foundMultiplier);
3442 }
3443 else
3444 {
3445 LCHeuristicCheck (LCs, contents, A, oldA,
3446 leadingCoeffs2[lengthAeval2-1], foundMultiplier);
3447 if (!foundMultiplier && fdivides (getVars (LCmultiplier), testVars))
3448 {
3449 LCHeuristic (A, LCmultiplier, biFactors, leadingCoeffs2, oldAeval,
3450 lengthAeval2, evaluation, oldBiFactors);
3451 }
3452 }
3453
3454 // patch everything together again
3455 leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
3456 for (int i= lengthAeval2-1; i > -1; i--)
3457 leadingCoeffs2[i]= CFList();
3458 prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(),leadingCoeffs,
3459 biFactors, evaluation);
3460 }
3461 factors= CFList();
3462 if (!fdivides (LC (oldA,1),prod (leadingCoeffs2[lengthAeval2-1])))
3463 {
3464 LCheuristic= false;
3465 A= bufA;
3466 biFactors= bufBiFactors;
3467 leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
3468 LCmultiplier= bufLCmultiplier;
3469 }
3470 }
3471 else
3472 factors= CFList();
3473 delete [] index;
3474 }
3475 TIMING_END_AND_PRINT (fac_fq_luckswang, "time for LucksWang over Fq: ");
3476
3477 TIMING_START (fac_fq_lcheuristic);
3478 if (!LCheuristic && !LCmultiplierIsConst && bufFactors.isEmpty()
3479 && fdivides (getVars (LCmultiplier), testVars))
3480 {
3481 LCheuristic= true;
3482 LCHeuristic (A, LCmultiplier, biFactors, leadingCoeffs2, oldAeval,
3483 lengthAeval2, evaluation, oldBiFactors);
3484
3485 leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
3486 for (int i= lengthAeval2-1; i > -1; i--)
3487 leadingCoeffs2[i]= CFList();
3488 prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(),leadingCoeffs,
3489 biFactors, evaluation);
3490
3491 if (!fdivides (LC (oldA,1),prod (leadingCoeffs2[lengthAeval2-1])))
3492 {
3493 LCheuristic= false;
3494 A= bufA;
3495 biFactors= bufBiFactors;
3496 leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
3497 LCmultiplier= bufLCmultiplier;
3498 }
3499 }
3500 TIMING_END_AND_PRINT (fac_fq_lcheuristic, "time for Lc heuristic over Fq: ");
3501
3502tryAgainWithoutHeu:
3503 TIMING_START (fac_fq_shift_to_zero);
3505
3506 for (iter= biFactors; iter.hasItem(); iter++)
3507 iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
3508
3509 for (int i= 0; i < lengthAeval2-1; i++)
3510 leadingCoeffs2[i]= CFList();
3511 for (iter= leadingCoeffs2[lengthAeval2-1]; iter.hasItem(); iter++)
3512 {
3513 iter.getItem()= shift2Zero (iter.getItem(), list, evaluation);
3514 for (int i= A.level() - 4; i > -1; i--)
3515 {
3516 if (i + 1 == lengthAeval2-1)
3517 leadingCoeffs2[i].append (iter.getItem() (0, i + 4));
3518 else
3519 leadingCoeffs2[i].append (leadingCoeffs2[i+1].getLast() (0, i + 4));
3520 }
3521 }
3522 TIMING_END_AND_PRINT (fac_fq_shift_to_zero,
3523 "time to shift evaluation point to zero: ");
3524
3525 CFArray Pi;
3526 CFList diophant;
3527 int* liftBounds= new int [A.level() - 1];
3528 int liftBoundsLength= A.level() - 1;
3529 for (int i= 0; i < liftBoundsLength; i++)
3530 liftBounds [i]= degree (A, i + 2) + 1;
3531
3532 Aeval.removeFirst();
3533 bool noOneToOne= false;
3534 TIMING_START (fac_fq_hensel_lift);
3535 factors= nonMonicHenselLift (Aeval, biFactors, leadingCoeffs2, diophant,
3536 Pi, liftBounds, liftBoundsLength, noOneToOne);
3537 TIMING_END_AND_PRINT (fac_fq_hensel_lift,
3538 "time for non monic hensel lifting over Fq: ");
3539
3540 if (!noOneToOne)
3541 {
3542 int check= factors.length();
3543 A= oldA;
3544 TIMING_START (fac_fq_recover_factors);
3545 factors= recoverFactors (A, factors, evaluation);
3546 TIMING_END_AND_PRINT (fac_fq_recover_factors,
3547 "time to recover factors over Fq: ");
3548 if (check != factors.length())
3549 noOneToOne= true;
3550 else
3551 factors= Union (factors, bufFactors);
3552
3553 if (extension && !noOneToOne)
3554 factors= extNonMonicFactorRecombination (factors, A, info);
3555 }
3556 if (noOneToOne)
3557 {
3558 if (!LCmultiplierIsConst && LCheuristic)
3559 {
3560 A= bufA;
3561 biFactors= bufBiFactors;
3562 leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
3563 delete [] liftBounds;
3564 LCheuristic= false;
3565 goto tryAgainWithoutHeu;
3566 //something probably went wrong in the heuristic
3567 }
3568
3569 A= shift2Zero (oldA, Aeval, evaluation);
3570 biFactors= oldBiFactors;
3571 for (iter= biFactors; iter.hasItem(); iter++)
3572 iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
3573 CanonicalForm LCA= LC (Aeval.getFirst(), 1);
3574 CanonicalForm yToLift= power (y, lift);
3575 CFListIterator i= biFactors;
3576 lift= degree (i.getItem(), 2) + degree (LC (i.getItem(), 1)) + 1;
3577 i++;
3578
3579 for (; i.hasItem(); i++)
3580 lift= tmax (lift,
3581 degree (i.getItem(), 2) + degree (LC (i.getItem(), 1)) + 1);
3582
3583 lift= tmax (degree (Aeval.getFirst() , 2) + 1, lift);
3584
3585 i= biFactors;
3586 yToLift= power (y, lift);
3587 CanonicalForm dummy;
3588 for (; i.hasItem(); i++)
3589 {
3590 LCA= LC (i.getItem(), 1);
3591 extgcd (LCA, yToLift, LCA, dummy);
3592 i.getItem()= mod (i.getItem()*LCA, yToLift);
3593 }
3594
3595 liftBoundsLength= F.level() - 1;
3596 liftBounds= liftingBounds (A, lift);
3597
3598 CFList MOD;
3599 bool earlySuccess;
3600 CFList earlyFactors, liftedFactors;
3601 TIMING_START (fac_fq_hensel_lift);
3602 liftedFactors= henselLiftAndEarly
3603 (A, MOD, liftBounds, earlySuccess, earlyFactors,
3604 Aeval, biFactors, evaluation, info);
3605 TIMING_END_AND_PRINT (fac_fq_hensel_lift,
3606 "time for hensel lifting over Fq: ");
3607
3608 if (!extension)
3609 {
3610 TIMING_START (fac_fq_factor_recombination);
3611 factors= factorRecombination (A, liftedFactors, MOD);
3612 TIMING_END_AND_PRINT (fac_fq_factor_recombination,
3613 "time for factor recombination: ");
3614 }
3615 else
3616 {
3617 TIMING_START (fac_fq_factor_recombination);
3618 factors= extFactorRecombination (liftedFactors, A, MOD, info, evaluation);
3619 TIMING_END_AND_PRINT (fac_fq_factor_recombination,
3620 "time for factor recombination: ");
3621 }
3622
3623 if (earlySuccess)
3624 factors= Union (factors, earlyFactors);
3625 if (!extension)
3626 {
3627 for (CFListIterator i= factors; i.hasItem(); i++)
3628 {
3629 int kk= Aeval.getLast().level();
3630 for (CFListIterator j= evaluation; j.hasItem(); j++, kk--)
3631 {
3632 if (i.getItem().level() < kk)
3633 continue;
3634 i.getItem()= i.getItem() (Variable (kk) - j.getItem(), kk);
3635 }
3636 }
3637 }
3638 }
3639
3640 if (v.level() != 1)
3641 {
3642 for (CFListIterator iter= factors; iter.hasItem(); iter++)
3643 iter.getItem()= swapvar (iter.getItem(), v, y);
3644 }
3645
3646 swap (factors, swapLevel, swapLevel2, x);
3647 append (factors, contentAFactors);
3648 decompress (factors, N);
3649 if (!extension)
3650 normalize (factors);
3651
3652 delete[] liftBounds;
3653
3654 return factors;
3655}
3656#endif
3657
3658/// multivariate factorization over an extension of the initial field
3659#ifdef HAVE_NTL // multiFactorize
3660CFList
3662{
3663 CanonicalForm A= F;
3664
3665 Variable alpha= info.getAlpha();
3666 Variable beta= info.getBeta();
3667 int k= info.getGFDegree();
3668 char cGFName= info.getGFName();
3669 CanonicalForm delta= info.getDelta();
3670 bool GF= (CFFactory::gettype() == GaloisFieldDomain);
3671 Variable w= Variable (1);
3672
3673 CFList factors;
3674 if (!GF && alpha == w) // we are in F_p
3675 {
3676 CFList factors;
3677 bool extension= true;
3678 int p= getCharacteristic();
3679 if (p < 7)
3680 {
3681 if (p == 2)
3683 else if (p == 3)
3685 else if (p == 5)
3687 ExtensionInfo info= ExtensionInfo (extension);
3688 A= A.mapinto();
3689 factors= multiFactorize (A, info);
3690
3693 Variable vBuf= rootOf (mipo.mapinto());
3694 for (CFListIterator j= factors; j.hasItem(); j++)
3695 j.getItem()= GF2FalphaRep (j.getItem(), vBuf);
3696 prune (vBuf);
3697 }
3698 else if (p >= 7 && p*p < (1<<16)) // pass to GF if possible
3699 {
3701 ExtensionInfo info= ExtensionInfo (extension);
3702 A= A.mapinto();
3703 factors= multiFactorize (A, info);
3704
3707 Variable vBuf= rootOf (mipo.mapinto());
3708 for (CFListIterator j= factors; j.hasItem(); j++)
3709 j.getItem()= GF2FalphaRep (j.getItem(), vBuf);
3710 prune (vBuf);
3711 }
3712 else // not able to pass to GF, pass to F_p(\alpha)
3713 {
3715 Variable v= rootOf (mipo);
3717 factors= multiFactorize (A, info);
3718 prune (v);
3719 }
3720 return factors;
3721 }
3722 else if (!GF && (alpha != w)) // we are in F_p(\alpha)
3723 {
3724 if (k == 1) // need factorization over F_p
3725 {
3726 int extDeg= degree (getMipo (alpha));
3727 extDeg++;
3729 Variable v= rootOf (mipo);
3731 factors= multiFactorize (A, info);
3732 prune (v);
3733 }
3734 else
3735 {
3736 if (beta == w)
3737 {
3739 CanonicalForm primElem, imPrimElem;
3740 bool primFail= false;
3741 Variable vBuf;
3742 primElem= primitiveElement (alpha, vBuf, primFail);
3743 ASSERT (!primFail, "failure in integer factorizer");
3744 if (primFail)
3745 ; //ERROR
3746 else
3747 imPrimElem= mapPrimElem (primElem, alpha, v);
3748
3749 CFList source, dest;
3750 CanonicalForm bufA= mapUp (A, alpha, v, primElem, imPrimElem,
3751 source, dest);
3752 ExtensionInfo info= ExtensionInfo (v, alpha, imPrimElem, primElem);
3753 factors= multiFactorize (bufA, info);
3754 prune (v);
3755 }
3756 else
3757 {
3759 CanonicalForm primElem, imPrimElem;
3760 bool primFail= false;
3761 Variable vBuf;
3762 ASSERT (!primFail, "failure in integer factorizer");
3763 if (primFail)
3764 ; //ERROR
3765 else
3766 imPrimElem= mapPrimElem (delta, beta, v);
3767
3768 CFList source, dest;
3769 CanonicalForm bufA= mapDown (A, info, source, dest);
3770 source= CFList();
3771 dest= CFList();
3772 bufA= mapUp (bufA, beta, v, delta, imPrimElem, source, dest);
3773 ExtensionInfo info= ExtensionInfo (v, beta, imPrimElem, delta);
3774 factors= multiFactorize (bufA, info);
3775 prune (v);
3776 }
3777 }
3778 return factors;
3779 }
3780 else // we are in GF (p^k)
3781 {
3782 int p= getCharacteristic();
3783 int extensionDeg= getGFDegree();
3784 bool extension= true;
3785 if (k == 1) // need factorization over F_p
3786 {
3787 extensionDeg++;
3788 if (pow ((double) p, (double) extensionDeg) < (1<<16))
3789 // pass to GF(p^k+1)
3790 {
3793 Variable vBuf= rootOf (mipo.mapinto());
3794 A= GF2FalphaRep (A, vBuf);
3795 setCharacteristic (p, extensionDeg, 'Z');
3796 ExtensionInfo info= ExtensionInfo (extension);
3797 factors= multiFactorize (A.mapinto(), info);
3798 prune (vBuf);
3799 }
3800 else // not able to pass to another GF, pass to F_p(\alpha)
3801 {
3804 Variable vBuf= rootOf (mipo.mapinto());
3805 A= GF2FalphaRep (A, vBuf);
3806 Variable v= chooseExtension (vBuf, beta, k);
3807 ExtensionInfo info= ExtensionInfo (v, extension);
3808 factors= multiFactorize (A, info);
3809 prune (vBuf);
3810 }
3811 }
3812 else // need factorization over GF (p^k)
3813 {
3814 if (pow ((double) p, (double) 2*extensionDeg) < (1<<16))
3815 // pass to GF(p^2k)
3816 {
3817 setCharacteristic (p, 2*extensionDeg, 'Z');
3818 ExtensionInfo info= ExtensionInfo (k, cGFName, extension);
3819 factors= multiFactorize (GFMapUp (A, extensionDeg), info);
3820 setCharacteristic (p, extensionDeg, cGFName);
3821 }
3822 else // not able to pass to GF (p^2k), pass to F_p (\alpha)
3823 {
3826 Variable v1= rootOf (mipo.mapinto());
3827 A= GF2FalphaRep (A, v1);
3828 Variable v2= chooseExtension (v1, v1, k);
3829 CanonicalForm primElem, imPrimElem;
3830 bool primFail= false;
3831 Variable vBuf;
3832 primElem= primitiveElement (v1, v1, primFail);
3833 if (primFail)
3834 ; //ERROR
3835 else
3836 imPrimElem= mapPrimElem (primElem, v1, v2);
3837 CFList source, dest;
3838 CanonicalForm bufA= mapUp (A, v1, v2, primElem, imPrimElem,
3839 source, dest);
3840 ExtensionInfo info= ExtensionInfo (v2, v1, imPrimElem, primElem);
3841 factors= multiFactorize (bufA, info);
3842 setCharacteristic (p, k, cGFName);
3843 for (CFListIterator i= factors; i.hasItem(); i++)
3844 i.getItem()= Falpha2GFRep (i.getItem());
3845 prune (v1);
3846 }
3847 }
3848 return factors;
3849 }
3850}
3851#endif
3852#endif
Rational pow(const Rational &a, int e)
Definition GMPrat.cc:411
#define swap(_i, _j)
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
CanonicalForm FACTORY_PUBLIC content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition cf_gcd.cc:603
CanonicalForm getVars(const CanonicalForm &f)
CanonicalForm getVars ( const CanonicalForm & f )
Definition cf_ops.cc:350
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition cf_ops.cc:600
int getNumVars(const CanonicalForm &f)
int getNumVars ( const CanonicalForm & f )
Definition cf_ops.cc:314
int ilog2(const CanonicalForm &a)
int * degrees(const CanonicalForm &f, int *degs=0)
int * degrees ( const CanonicalForm & f, int * degs )
Definition cf_ops.cc:493
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
int degree(const CanonicalForm &f)
CanonicalForm deriv(const CanonicalForm &f, const Variable &x)
int getGFDegree()
Definition cf_char.cc:75
Array< CanonicalForm > CFArray
void FACTORY_PUBLIC setCharacteristic(int c)
Definition cf_char.cc:28
ListIterator< CFFactor > CFFListIterator
Matrix< CanonicalForm > CFMatrix
CanonicalForm FACTORY_PUBLIC swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition cf_ops.cc:168
ListIterator< CanonicalForm > CFListIterator
int totaldegree(const CanonicalForm &f)
int totaldegree ( const CanonicalForm & f )
Definition cf_ops.cc:523
List< CFFactor > CFFList
CanonicalForm Lc(const CanonicalForm &f)
Factor< CanonicalForm > CFFactor
int level(const CanonicalForm &f)
List< CanonicalForm > CFList
CanonicalForm LC(const CanonicalForm &f)
int FACTORY_PUBLIC getCharacteristic()
Definition cf_char.cc:70
const CanonicalForm CFMap CFMap & N
Definition cfEzgcd.cc:56
int * degsf
Definition cfEzgcd.cc:59
int l
Definition cfEzgcd.cc:100
int m
Definition cfEzgcd.cc:128
static const double log2exp
Definition cfEzgcd.cc:45
int i
Definition cfEzgcd.cc:132
int k
Definition cfEzgcd.cc:99
Variable x
Definition cfModGcd.cc:4090
static Variable chooseExtension(const Variable &alpha)
Definition cfModGcd.cc:421
int p
Definition cfModGcd.cc:4086
g
Definition cfModGcd.cc:4098
CanonicalForm test
Definition cfModGcd.cc:4104
static void evalPoint(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &FEval, CanonicalForm &GEval, CFGenerator &evalPoint)
CanonicalForm decompress(const CanonicalForm &F, const mpz_t *inverseM, const mpz_t *A)
decompress a bivariate poly
CanonicalForm extgcd(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &a, CanonicalForm &b)
CanonicalForm extgcd ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & a,...
univariate Gcd over finite fields and Z, extended GCD over finite fields and Q
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
CFFList FACTORY_PUBLIC sqrFree(const CanonicalForm &f, bool sort=false)
squarefree factorization
Definition cf_factor.cc:961
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 randomIrredpoly(int i, const Variable &x)
computes a random monic irreducible univariate polynomial in x over Fp of degree i via NTL/FLINT
Definition cf_irred.cc:26
generate random irreducible univariate polynomials
static CanonicalForm bound(const CFMatrix &M)
Definition cf_linsys.cc:460
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m )
Definition cf_map.cc:210
int findItem(const CFList &list, const CanonicalForm &item)
helper function
Definition cf_map_ext.cc:42
CanonicalForm mapPrimElem(const CanonicalForm &primElem, const Variable &alpha, const Variable &beta)
compute the image of a primitive element of in . We assume .
CanonicalForm primitiveElement(const Variable &alpha, Variable &beta, bool &fail)
determine a primitive element of , is a primitive element of a field which is isomorphic to
static CanonicalForm mapDown(const CanonicalForm &F, const Variable &alpha, const CanonicalForm &G, CFList &source, CFList &dest)
the CanonicalForm G is the output of map_up, returns F considered as an element over ,...
CanonicalForm getItem(const CFList &list, const int &pos)
helper function
Definition cf_map_ext.cc:54
static CanonicalForm mapUp(const Variable &alpha, const Variable &beta)
and is a primitive element, returns the image of
Definition cf_map_ext.cc:71
CanonicalForm Falpha2GFRep(const CanonicalForm &F)
change representation by residue classes modulo a Conway polynomial to representation by primitive el...
CanonicalForm GFMapUp(const CanonicalForm &F, int k)
maps a polynomial over to a polynomial over , d needs to be a multiple of k
CanonicalForm GF2FalphaRep(const CanonicalForm &F, const Variable &alpha)
changes representation by primitive element to representation by residue classes modulo a Conway poly...
This file implements functions to map between extensions of finite fields.
generate random integers, random elements of finite fields
generate random elements in F_p(alpha)
Definition cf_random.h:70
CanonicalForm generate() const
Definition cf_random.cc:157
int size() const
static int gettype()
Definition cf_factory.h:28
class to iterate through CanonicalForm's
Definition cf_iter.h:44
class CFMap
Definition cf_map.h:85
factory's main class
CF_NO_INLINE bool isZero() const
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
CF_NO_INLINE bool isOne() const
bool inCoeffDomain() const
int level() const
level() returns the level of CO.
bool isUnivariate() const
ExtensionInfo contains information about extension.
generate random elements in F_p
Definition cf_random.h:44
CanonicalForm generate() const
Definition cf_random.cc:68
T factor() const
generate random elements in GF
Definition cf_random.h:32
CanonicalForm generate() const
Definition cf_random.cc:78
T & getItem() const
T getFirst() const
void removeFirst()
int length() const
void append(const T &)
T getLast() const
void insert(const T &)
int isEmpty() const
void removeLast()
factory's class for variables
Definition factory.h:127
int level() const
Definition factory.h:143
functions to print debug output
CFFListIterator iter
Variable alpha
return result
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
Variable beta
Definition facAbsFact.cc:95
const CanonicalForm & w
Definition facAbsFact.cc:51
CanonicalForm mipo
Definition facAlgExt.cc:57
CFFList append(const CFFList &Inputlist, const CFFactor &TheFactor)
const Variable & v
< [in] a sqrfree bivariate poly
Definition facBivar.h:39
CanonicalForm contentx
CanonicalForm gcd_deriv
CFList LCFeval
CanonicalForm LCF
CanonicalForm deriv_x
bool bad
bool found
CFList & eval
CFList multiFactorize(const CanonicalForm &F, const Variable &v)
Factorization over Q (a)
CFList int & minFactorsLength
[in,out] minimal length of bivariate factors
CFList *& Aeval
<[in] poly
CFList int bool & irred
[in,out] Is A irreducible?
void appendTestMapDown(CFList &factors, const CanonicalForm &f, const ExtensionInfo &info, CFList &source, CFList &dest)
test if g is in a subfield of the current field, if so map it down and append it to factors
const CFList & factors2
void appendSwapDecompress(CFList &factors1, const CFList &factors2, const CFList &factors3, const bool swap1, const bool swap2, const CFMap &N)
first swap Variables in factors1 if necessary, then append factors2 and factors3 on factors1 and fina...
void indexUpdate(int index[], const int &subsetSize, const int &setSize, bool &noSubset)
update index
void appendMapDown(CFList &factors, const CanonicalForm &g, const ExtensionInfo &info, CFList &source, CFList &dest)
map g down into a subfield of the current field and append it to factors
CFArray copy(const CFList &list)
write elements of list into an array
CFList subset(int index[], const int &s, const CFArray &elements, bool &noSubset)
extract a subset given by index of size s from elements, if there is no subset we have not yet consid...
bool isInExtension(const CanonicalForm &F, const CanonicalForm &gamma, const int k, const CanonicalForm &delta, CFList &source, CFList &dest)
tests if F is not contained in a subfield defined by gamma (Fq case) or k (GF case)
else L getLast()(0
CanonicalForm buf2
Definition facFqBivar.cc:76
CFList tmp2
Definition facFqBivar.cc:75
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 ...
CanonicalForm buf1
Definition facFqBivar.cc:76
CFList FqBiSqrfFactorize(const CanonicalForm &G, const Variable &alpha)
factorize a squarefree bivariate polynomial over .
Definition facFqBivar.h:156
CFList biSqrfFactorizeHelper(const CanonicalForm &G, const ExtensionInfo &info)
Definition facFqBivar.h:55
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 recoverFactors(const CanonicalForm &F, const CFList &factors)
divides factors by their content wrt. Variable(1) and checks if these polys divide F
CanonicalForm reverseShift(const CanonicalForm &F, const CFList &evaluation, int l)
reverse shifting the evaluation point to zero
CanonicalForm shift2Zero(const CanonicalForm &F, CFList &Feval, const CFList &evaluation, int l)
shift evaluation point to zero
int * liftingBounds(const CanonicalForm &A, const int &bivarLiftBound)
compute lifting bounds
CFList evaluateAtZero(const CanonicalForm &F)
evaluate F successively n-2 at 0
bool isOnlyLeadingCoeff(const CanonicalForm &F)
check if F consists of more than just the leading coeff wrt. Variable (1)
CFFList sortCFFListByNumOfVars(CFFList &F)
sort CFFList by the number variables in a factor
CanonicalForm myGetVars(const CanonicalForm &F)
like getVars but including multiplicities
CFList evaluateAtEval(const CanonicalForm &F, const CFArray &eval)
evaluate F at evaluation
This file provides utility functions for multivariate factorization.
CFList multiFactorize(const CanonicalForm &F, const ExtensionInfo &info)
CFList factorRecombination(const CanonicalForm &F, const CFList &factors, const CFList &M)
Naive factor recombination for multivariate factorization. No precomputed is used to exclude combinat...
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,...
static CanonicalForm myContent(const CanonicalForm &F)
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.
int testFactors(const CanonicalForm &G, const CFList &uniFactors, const Variable &alpha, CanonicalForm &sqrfPartF, CFList &factors, CFFList *&bufSqrfFactors, CFList &evalSqrfPartF, const CFArray &evalPoint)
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 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....
void checkHelper(const CanonicalForm &f1, CFList &factors1, CFList &factors2, CFList &l1, CFList &l2)
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
CFList checkOneToOne(const CFList &factors1, const CFList &factors2, CFList &factors3, const CanonicalForm &evalPoint, const Variable &x)
check if univariate factors factors2 of factors3 coincide with univariate factors of factors1 and rec...
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
static CanonicalForm prodEval(const CFList &l, const CanonicalForm &evalPoint, const Variable &v)
void factorizationWRTDifferentSecondVars(const CanonicalForm &A, CFList *&Aeval, const ExtensionInfo &info, int &minFactorsLength, bool &irred)
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...
CFList conv(const CFArray &A)
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...
static int newMainVariableSearch(CanonicalForm &A, CFList &Aeval, CFList &evaluation, const Variable &alpha, const int lev, CanonicalForm &g)
CFList extFactorize(const CanonicalForm &F, const ExtensionInfo &info)
multivariate factorization over an extension of the initial field
#define CHAR_THRESHOLD
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...
CFList extNonMonicFactorRecombination(const CFList &factors, const CanonicalForm &F, const ExtensionInfo &info)
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 ...
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...
void refineBiFactors(const CanonicalForm &A, CFList &biFactors, CFList *const &Aeval, const CFList &evaluation, int minFactorsLength)
refine a bivariate factorization of A with l factors to one with minFactorsLength if possible
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....
static CanonicalForm listGCD(const CFList &L)
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 factorizing a multivariate polynomial over , or GF.
CFFList squarefreeFactorization(const CanonicalForm &F, const Variable &alpha)
squarefree factorization over a finite field return a list of squarefree factors with multiplicity
CFList nonMonicHenselLift(const CFList &F, const CFList &factors, const CFList &LCs, CFList &diophant, CFArray &Pi, CFMatrix &M, int lOld, int &lNew, const CFList &MOD, bool &noOneToOne)
int j
Definition facHensel.cc:110
CFList henselLift23(const CFList &eval, const CFList &factors, int *l, CFList &diophant, CFArray &Pi, CFMatrix &M)
Hensel lifting from bivariate to trivariate.
fq_nmod_poly_t prod
Definition facHensel.cc:100
void nonMonicHenselLift12(const CanonicalForm &F, CFList &factors, int l, CFArray &Pi, CFList &diophant, CFMatrix &M, const CFArray &LCs, bool sort)
Hensel lifting from univariate to bivariate, factors need not to be monic.
CFList henselLift(const CFList &F, const CFList &factors, const CFList &MOD, CFList &diophant, CFArray &Pi, CFMatrix &M, int lOld, int lNew)
Hensel lifting.
void henselLiftResume(const CanonicalForm &F, CFList &factors, int start, int end, CFArray &Pi, const CFList &diophant, CFMatrix &M, const CFList &MOD)
resume Hensel lifting.
void sortList(CFList &list, const Variable &x)
sort a list of polynomials by their degree in x.
Definition facHensel.cc:449
This file defines functions for Hensel lifting.
CanonicalForm mulMod(const CanonicalForm &A, const CanonicalForm &B, const CFList &MOD)
Karatsuba style modular multiplication for multivariate polynomials.
Definition facMul.cc:3086
CanonicalForm prodMod(const CFList &L, const CanonicalForm &M)
product of all elements in L modulo M via divide-and-conquer.
Definition facMul.cc:3186
This file defines functions for fast multiplication and division with remainder.
int LucksWangSparseHeuristic(const CanonicalForm &F, const CFList &factors, int level, const CFList &leadingCoeffs, CFList &result)
sparse heuristic lifting by Wang and Lucks
CFList sparseHeuristic(const CanonicalForm &A, const CFList &biFactors, CFList *&moreBiFactors, const CFList &evaluation, int minFactorsLength)
sparse heuristic which patches together bivariate factors of A wrt. different second variables by the...
This file provides functions for sparse heuristic Hensel lifting.
Variable FACTORY_PUBLIC rootOf(const CanonicalForm &, char name='@')
returns a symbolic root of polynomial with name name Use it to define algebraic variables
Definition variable.cc:162
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition variable.cc:207
void FACTORY_PUBLIC prune(Variable &alpha)
Definition variable.cc:261
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
template CanonicalForm tmin(const CanonicalForm &, const CanonicalForm &)
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
template List< Variable > Difference(const List< Variable > &, const List< Variable > &)
template bool find(const List< CanonicalForm > &, const CanonicalForm &)
INST_VAR CanonicalForm gf_mipo
Definition gfops.cc:56
static BOOLEAN length(leftv result, leftv arg)
Definition interval.cc:257
STATIC_VAR jList * T
Definition janet.cc:30
STATIC_VAR TreeM * G
Definition janet.cc:31
STATIC_VAR Poly * h
Definition janet.cc:971
#define info
Definition libparse.cc:1256
VAR int check
Definition libparse.cc:1106
ideal lift(const ideal J, const ring r, const ideal inI, const ring s)
Definition lift.cc:26
int lcm(unsigned long *l, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
Definition minpoly.cc:709
static int index(p_Length length, p_Ord ord)
int status int void size_t count
Definition si_signals.h:69
int status int void * buf
Definition si_signals.h:69
#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
int gcd(int a, int b)