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);
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
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())
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];
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 }
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 {
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 {
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();
2553 {
2554 if (i == w.level())
2555 {
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;
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 {
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
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
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
int totaldegree(const CanonicalForm &f)
int totaldegree ( const CanonicalForm & f )
Definition cf_ops.cc:523
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
CF_NO_INLINE int hasTerms() const
check if iterator has reached the end of CanonicalForm
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.
CanonicalForm mapinto() const
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
generate random elements in GF
Definition cf_random.h:32
CanonicalForm generate() const
Definition cf_random.cc:78
void remove(int moveright)
T & getItem() const
void insert(const T &)
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 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)