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
22#include "cf_assert.h"
23#include "debug.h"
24#include "timing.h"
25
26#include "facFqFactorizeUtil.h"
27#include "facFqFactorize.h"
28#include "cf_random.h"
29#include "facHensel.h"
30#include "cf_irred.h"
31#include "cf_map_ext.h"
32#include "facSparseHensel.h"
33#include "facMul.h"
34#include "cfUnivarGcd.h"
35
50
51
52static inline
54listGCD (const CFList& L);
55
56static inline
59{
60 Variable x= Variable (1);
61 CanonicalForm G= swapvar (F, F.mvar(), x);
62 CFList L;
63 for (CFIterator i= G; i.hasTerms(); i++)
64 L.append (i.coeff());
65 if (L.length() == 2)
66 return swapvar (gcd (L.getFirst(), L.getLast()), F.mvar(), x);
67 if (L.length() == 1)
68 return LC (F, x);
69 return swapvar (listGCD (L), F.mvar(), x);
70}
71
72static inline
74listGCD (const CFList& L)
75{
76 if (L.length() == 0)
77 return 0;
78 if (L.length() == 1)
79 return L.getFirst();
80 if (L.length() == 2)
81 return gcd (L.getFirst(), L.getLast());
82 else
83 {
84 CFList lHi, lLo;
86 int length= L.length()/2;
87 int j= 0;
88 for (CFListIterator i= L; j < length; i++, j++)
89 lHi.append (i.getItem());
90 lLo= Difference (L, lHi);
93 if (resultHi.isOne() || resultLo.isOne())
94 return 1;
95 return gcd (resultHi, resultLo);
96 }
97}
98
99static inline
102{
103 if (degree (F, x) <= 0)
104 return 1;
105 CanonicalForm G= F;
106 bool swap= false;
107 if (x != F.mvar())
108 {
109 swap= true;
110 G= swapvar (F, x, F.mvar());
111 }
112 CFList L;
114 for (CFIterator i= G; i.hasTerms(); i++)
115 L.append (i.coeff());
116 if (L.length() == 2)
117 {
118 if (swap)
119 return swapvar (gcd (L.getFirst(), L.getLast()), F.mvar(), x);
120 else
121 return gcd (L.getFirst(), L.getLast());
122 }
123 if (L.length() == 1)
124 {
125 return LC (F, x);
126 }
127 if (swap)
128 return swapvar (listGCD (L), F.mvar(), x);
129 else
130 return listGCD (L);
131}
132
134{
135 int n= F.level();
136 int * degsf= NEW_ARRAY(int,n + 1);
137 int ** swap= new int* [n + 1];
138 for (int i= 0; i <= n; i++)
139 {
140 degsf[i]= 0;
141 swap [i]= new int [3];
142 swap [i] [0]= 0;
143 swap [i] [1]= 0;
144 swap [i] [2]= 0;
145 }
146 int i= 1;
147 n= 1;
148 degsf= degrees (F, degsf);
149
151 while ( i <= F.level() )
152 {
153 while( degsf[i] == 0 ) i++;
154 swap[n][0]= i;
155 swap[n][1]= size (LC (F,i));
156 swap[n][2]= degsf [i];
157 if (i != n)
159 n++; i++;
160 }
161
162 int buf1, buf2, buf3;
163 n--;
164
165 for (i= 1; i < n; i++)
166 {
167 for (int j= 1; j < n - i + 1; j++)
168 {
169 if (swap[j][1] > swap[j + 1][1])
170 {
171 buf1= swap [j + 1] [0];
172 buf2= swap [j + 1] [1];
173 buf3= swap [j + 1] [2];
174 swap[j + 1] [0]= swap[j] [0];
175 swap[j + 1] [1]= swap[j] [1];
176 swap[j + 1] [2]= swap[j] [2];
177 swap[j][0]= buf1;
178 swap[j][1]= buf2;
179 swap[j][2]= buf3;
180 result= swapvar (result, Variable (j + 1), Variable (j));
181 }
182 else if (swap[j][1] == swap[j + 1][1] && swap[j][2] < swap[j + 1][2])
183 {
184 buf1= swap [j + 1] [0];
185 buf2= swap [j + 1] [1];
186 buf3= swap [j + 1] [2];
187 swap[j + 1] [0]= swap[j] [0];
188 swap[j + 1] [1]= swap[j] [1];
189 swap[j + 1] [2]= swap[j] [2];
190 swap[j][0]= buf1;
191 swap[j][1]= buf2;
192 swap[j][2]= buf3;
193 result= swapvar (result, Variable (j + 1), Variable (j));
194 }
195 }
196 }
197
198 for (i= n; i > 0; i--)
199 {
200 if (i != swap[i] [0])
201 N.newpair (Variable (i), Variable (swap[i] [0]));
202 }
203
204 for (i= F.level(); i >=0 ; i--)
205 delete [] swap[i];
206 delete [] swap;
207
209
210 return result;
211}
212
213#if defined(HAVE_NTL) || defined(HAVE_FLINT)
214CFList
216 const CFList& M, const ExtensionInfo& info,
217 const CFList& evaluation)
218{
219 Variable alpha= info.getAlpha();
220 Variable beta= info.getBeta();
221 CanonicalForm gamma= info.getGamma();
222 CanonicalForm delta= info.getDelta();
223 int k= info.getGFDegree();
224 CFList source, dest;
225 if (factors.length() == 1)
226 {
228 return CFList (mapDown (buf, info, source, dest));
229 }
230 if (factors.length() < 1)
231 return CFList();
232
233 int degMipoBeta= 1;
234 if (!k && beta.level() != 1)
236
237 CFList T, S;
238 T= factors;
239
240 int s= 1;
243
244 buf= F;
245
246 Variable x= Variable (1);
249 int * v= new int [T.length()];
250 for (int i= 0; i < T.length(); i++)
251 v[i]= 0;
252 bool noSubset= false;
253 CFArray TT;
254 TT= copy (factors);
255 bool recombination= false;
256 bool trueFactor= false;
257 while (T.length() >= 2*s)
258 {
259 while (noSubset == false)
260 {
261 if (T.length() == s)
262 {
263 delete [] v;
264 if (recombination)
265 {
266 T.insert (LCBuf);
267 g= prodMod (T, M);
268 T.removeFirst();
269 result.append (g/myContent (g));
271 g /= Lc (g);
273 return result;
274 }
275 else
276 {
278 return CFList (buf);
279 }
280 }
281
282 S= subset (v, s, TT, noSubset);
283 if (noSubset) break;
284
285 S.insert (LCBuf);
286 g= prodMod (S, M);
287 S.removeFirst();
288 g /= myContent (g);
289 if (fdivides (g, buf, quot))
290 {
292 buf2 /= Lc (buf2);
293 if (!k && beta == x)
294 {
295 if (degree (buf2, alpha) < degMipoBeta)
296 {
298 buf= quot;
299 LCBuf= LC (buf, x);
300 recombination= true;
301 trueFactor= true;
302 }
303 }
304 else
305 {
306 if (!isInExtension (buf2, gamma, k, delta, source, dest))
307 {
309 buf /= g;
310 LCBuf= LC (buf, x);
311 recombination= true;
312 trueFactor= true;
313 }
314 }
315
316 if (trueFactor)
317 {
318 T= Difference (T, S);
319
320 if (T.length() < 2*s || T.length() == s)
321 {
323 buf /= Lc (buf);
325 delete [] v;
326 return result;
327 }
328 trueFactor= false;
329 TT= copy (T);
330 indexUpdate (v, s, T.length(), noSubset);
331 if (noSubset) break;
332 }
333 }
334 }
335 s++;
336 if (T.length() < 2*s || T.length() == s)
337 {
340 delete [] v;
341 return result;
342 }
343 for (int i= 0; i < T.length(); i++)
344 v[i]= 0;
345 noSubset= false;
346 }
347 if (T.length() < 2*s)
348 {
351 }
352
353 delete [] v;
354 return result;
355}
356#endif
357
358#if defined(HAVE_NTL) || defined(HAVE_FLINT)
359CFList
361 const CFList& M)
362{
363 if (factors.length() == 1)
364 return CFList(F);
365 if (factors.length() < 1)
366 return CFList();
367
368 CFList T, S;
369
370 T= factors;
371
372 int s= 1;
374 CanonicalForm LCBuf= LC (F, Variable (1));
375 CanonicalForm g, buf= F;
376 int * v= new int [T.length()];
377 for (int i= 0; i < T.length(); i++)
378 v[i]= 0;
379 bool noSubset= false;
380 CFArray TT;
381 TT= copy (factors);
382 Variable y= F.level() - 1;
383 bool recombination= false;
385 while (T.length() >= 2*s)
386 {
387 while (noSubset == false)
388 {
389 if (T.length() == s)
390 {
391 delete [] v;
392 if (recombination)
393 {
394 T.insert (LC (buf));
395 g= prodMod (T, M);
396 result.append (g/myContent (g));
397 return result;
398 }
399 else
400 return CFList (F);
401 }
402 S= subset (v, s, TT, noSubset);
403 if (noSubset) break;
404 S.insert (LCBuf);
405 g= prodMod (S, M);
406 S.removeFirst();
407 g /= myContent (g);
408 if (fdivides (g, buf, quot))
409 {
410 recombination= true;
411 result.append (g);
412 buf= quot;
413 LCBuf= LC (buf, Variable(1));
414 T= Difference (T, S);
415 if (T.length() < 2*s || T.length() == s)
416 {
417 result.append (buf);
418 delete [] v;
419 return result;
420 }
421 TT= copy (T);
422 indexUpdate (v, s, T.length(), noSubset);
423 if (noSubset) break;
424 }
425 }
426 s++;
427 if (T.length() < 2*s || T.length() == s)
428 {
429 result.append (buf);
430 delete [] v;
431 return result;
432 }
433 for (int i= 0; i < T.length(); i++)
434 v[i]= 0;
435 noSubset= false;
436 }
437 if (T.length() < 2*s)
438 result.append (F);
439
440 delete [] v;
441 return result;
442}
443#endif
444
445#if defined(HAVE_NTL) || defined(HAVE_FLINT)
446int
448 success, const int deg, const CFList& MOD, const int bound)
449{
450 int adaptedLiftBound= 0;
452 Variable y= F.mvar();
453 Variable x= Variable (1);
456 CFList M= MOD;
457 M.append (power (y, deg));
458 int d= bound;
459 int e= 0;
460 int nBuf;
461 for (CFListIterator i= factors; i.hasItem(); i++)
462 {
463 g= mulMod (i.getItem(), LCBuf, M);
464 g /= myContent (g);
465 if (fdivides (g, buf, quot))
466 {
467 nBuf= degree (g, y) + degree (LC (g, 1), y);
468 d -= nBuf;
469 e= tmax (e, nBuf);
470 buf= quot;
471 LCBuf= LC (buf, x);
472 }
473 }
475
476 if (adaptedLiftBound < deg)
477 {
478 if (adaptedLiftBound < degree (F) + 1)
479 {
480 if (d == 1)
481 {
482 if (e + 1 > deg)
483 {
484 adaptedLiftBound= deg;
485 success= false;
486 }
487 else
488 {
489 success= true;
490 if (e + 1 < degree (F) + 1)
491 adaptedLiftBound= deg;
492 else
493 adaptedLiftBound= e + 1;
494 }
495 }
496 else
497 {
498 success= true;
499 adaptedLiftBound= deg;
500 }
501 }
502 else
503 {
504 success= true;
505 }
506 }
507 return adaptedLiftBound;
508}
509#endif
510
511#if defined(HAVE_NTL) || defined(HAVE_FLINT)
512int
514 success, const ExtensionInfo& info, const CFList& eval,
515 const int deg, const CFList& MOD, const int bound)
516{
517 Variable alpha= info.getAlpha();
518 Variable beta= info.getBeta();
519 CanonicalForm gamma= info.getGamma();
520 CanonicalForm delta= info.getDelta();
521 int k= info.getGFDegree();
522 int adaptedLiftBound= 0;
524 Variable y= F.mvar();
525 Variable x= Variable (1);
528 CFList M= MOD;
529 M.append (power (y, deg));
531 int d= bound;
532 int e= 0;
533 int nBuf;
534 int degMipoBeta= 1;
535 if (!k && beta.level() != 1)
537
538 CFList source, dest;
539 for (CFListIterator i= factors; i.hasItem(); i++)
540 {
541 g= mulMod (i.getItem(), LCBuf, M);
542 g /= myContent (g);
543 if (fdivides (g, buf, quot))
544 {
545 gg= reverseShift (g, eval);
546 gg /= Lc (gg);
547 if (!k && beta == x)
548 {
549 if (degree (gg, alpha) < degMipoBeta)
550 {
551 buf= quot;
552 nBuf= degree (g, y) + degree (LC (g, x), y);
553 d -= nBuf;
554 e= tmax (e, nBuf);
555 LCBuf= LC (buf, x);
556 }
557 }
558 else
559 {
560 if (!isInExtension (gg, gamma, k, delta, source, dest))
561 {
562 buf= quot;
563 nBuf= degree (g, y) + degree (LC (g, x), y);
564 d -= nBuf;
565 e= tmax (e, nBuf);
566 LCBuf= LC (buf, x);
567 }
568 }
569 }
570 }
572
573 if (adaptedLiftBound < deg)
574 {
575 if (adaptedLiftBound < degree (F) + 1)
576 {
577 if (d == 1)
578 {
579 if (e + 1 > deg)
580 {
581 adaptedLiftBound= deg;
582 success= false;
583 }
584 else
585 {
586 success= true;
587 if (e + 1 < degree (F) + 1)
588 adaptedLiftBound= deg;
589 else
590 adaptedLiftBound= e + 1;
591 }
592 }
593 else
594 {
595 success= true;
596 adaptedLiftBound= deg;
597 }
598 }
599 else
600 {
601 success= true;
602 }
603 }
604
605 return adaptedLiftBound;
606}
607#endif
608
609#if defined(HAVE_NTL) || defined(HAVE_FLINT)
610CFList
612 bool& success, const int deg, const CFList& MOD,
613 const int bound)
614{
618 Variable y= F.mvar();
619 Variable x= Variable (1);
622 CFList M= MOD;
623 M.append (power (y, deg));
625 int d= bound;
626 int e= 0;
627 int nBuf;
628 for (CFListIterator i= factors; i.hasItem(); i++)
629 {
630 g= mulMod (i.getItem(), LCBuf, M);
631 g /= myContent (g);
632 if (fdivides (g, buf, quot))
633 {
634 result.append (g);
635 nBuf= degree (g, y) + degree (LC (g, x), y);
636 d -= nBuf;
637 e= tmax (e, nBuf);
638 buf= quot;
639 LCBuf= LC (buf, x);
640 T= Difference (T, CFList (i.getItem()));
641 }
642 }
644
645 if (adaptedLiftBound < deg)
646 {
647 if (adaptedLiftBound < degree (F) + 1)
648 {
649 if (d == 1)
650 adaptedLiftBound= tmin (e + 1, deg);
651 else
652 adaptedLiftBound= deg;
653 }
654 factors= T;
655 F= buf;
656 success= true;
657 }
658 return result;
659}
660#endif
661
662#if defined(HAVE_NTL) || defined(HAVE_FLINT)
663CFList
665 bool& success, const ExtensionInfo& info, const CFList&
666 eval, const int deg, const CFList& MOD, const int bound)
667{
668 Variable alpha= info.getAlpha();
669 Variable beta= info.getBeta();
670 CanonicalForm gamma= info.getGamma();
671 CanonicalForm delta= info.getDelta();
672 int k= info.getGFDegree();
676 Variable y= F.mvar();
677 Variable x= Variable (1);
680 CFList M= MOD;
681 M.append (power (y, deg));
683 int d= bound;
684 int e= 0;
685 int nBuf;
686 CFList source, dest;
687
688 int degMipoBeta= 1;
689 if (!k && beta.level() != 1)
691
692 for (CFListIterator i= factors; i.hasItem(); i++)
693 {
694 g= mulMod (i.getItem(), LCBuf, M);
695 g /= myContent (g);
696 if (fdivides (g, buf, quot))
697 {
698 gg= reverseShift (g, eval);
699 gg /= Lc (gg);
700 if (!k && beta == x)
701 {
702 if (degree (gg, alpha) < degMipoBeta)
703 {
705 buf= quot;
706 nBuf= degree (g, y) + degree (LC (g, x), y);
707 d -= nBuf;
708 e= tmax (e, nBuf);
709 LCBuf= LC (buf, x);
710 T= Difference (T, CFList (i.getItem()));
711 }
712 }
713 else
714 {
715 if (!isInExtension (gg, gamma, k, delta, source, dest))
716 {
718 buf= quot;
719 nBuf= degree (g, y) + degree (LC (g, x), y);
720 d -= nBuf;
721 e= tmax (e, nBuf);
722 LCBuf= LC (buf, x);
723 T= Difference (T, CFList (i.getItem()));
724 }
725 }
726 }
727 }
729
730 if (adaptedLiftBound < deg)
731 {
732 if (adaptedLiftBound < degree (F) + 1)
733 {
734 if (d == 1)
735 adaptedLiftBound= tmin (e + 1, deg);
736 else
737 adaptedLiftBound= deg;
738 }
739 success= true;
740 factors= T;
741 F= buf;
742 }
743 return result;
744}
745#endif
746
747#if defined(HAVE_NTL) || defined(HAVE_FLINT)
748#define CHAR_THRESHOLD 8
749CFList
751 CFList& list, const bool& GF, bool& fail)
752{
753 int k= F.level() - 1;
754 Variable x= Variable (1);
755 CanonicalForm LCF=LC (F, x);
757
761 int p= getCharacteristic ();
762 if (p < CHAR_THRESHOLD)
763 {
764 if (!GF && alpha.level() == 1)
765 {
766 fail= true;
767 return CFList();
768 }
769 else if (!GF && alpha.level() != 1)
770 {
771 if ((p == 2 && degree (getMipo (alpha)) < 6) ||
772 (p == 3 && degree (getMipo (alpha)) < 4) ||
773 (p == 5 && degree (getMipo (alpha)) < 3))
774 {
775 fail= true;
776 return CFList();
777 }
778 }
779 }
780 double bound;
781 if (alpha != x)
782 {
783 bound= pow ((double) p, (double) degree (getMipo(alpha)));
784 bound *= (double) k;
785 }
786 else if (GF)
787 {
788 bound= pow ((double) p, (double) getGFDegree());
789 bound *= (double) k;
790 }
791 else
792 bound= pow ((double) p, (double) k);
793
796 do
797 {
798 random= 0;
799 // possible overflow if list.length() does not fit into a int
800 if (list.length() >= bound)
801 {
802 fail= true;
803 break;
804 }
805 for (int i= 0; i < k; i++)
806 {
807 if (list.isEmpty())
808 result.append (0);
809 else if (GF)
810 {
811 result.append (genGF.generate());
812 random += result.getLast()*power (x, i);
813 }
814 else if (alpha.level() != 1)
815 {
817 result.append (genAlgExt.generate());
818 random += result.getLast()*power (x, i);
819 }
820 else
821 {
822 result.append (genFF.generate());
823 random += result.getLast()*power (x, i);
824 }
825 }
826 if (find (list, random))
827 {
828 result= CFList();
829 continue;
830 }
831 int l= F.level();
832 eval.insert (F);
834 bool bad= false;
835 for (CFListIterator i= result; i.hasItem(); i++, l--)
836 {
837 eval.insert (eval.getFirst()(i.getItem(), l));
838 LCFeval.insert (LCFeval.getFirst()(i.getItem(), l));
839 if (degree (eval.getFirst(), l - 1) != degree (F, l - 1))
840 {
841 if (!find (list, random))
842 list.append (random);
843 result= CFList();
844 eval= CFList();
845 LCFeval= CFList();
846 bad= true;
847 break;
848 }
849 if ((l != 2) && (degree (LCFeval.getFirst(), l-1) != degree (LCF, l-1)))
850 {
851 if (!find (list, random))
852 list.append (random);
853 result= CFList();
854 eval= CFList();
855 LCFeval= CFList();
856 bad= true;
857 break;
858 }
859 }
860
861 if (bad)
862 continue;
863
864 if (degree (eval.getFirst()) != degree (F, 1))
865 {
866 if (!find (list, random))
867 list.append (random);
868 result= CFList();
869 LCFeval= CFList();
870 eval= CFList();
871 continue;
872 }
873
876 if (degree (gcd_deriv) > 0)
877 {
878 if (!find (list, random))
879 list.append (random);
880 result= CFList();
881 LCFeval= CFList();
882 eval= CFList();
883 continue;
884 }
886 i++;
887 CanonicalForm contentx= content (i.getItem(), x);
888 if (degree (contentx) > 0)
889 {
890 if (!find (list, random))
891 list.append (random);
892 result= CFList();
893 LCFeval= CFList();
894 eval= CFList();
895 continue;
896 }
897
898 contentx= content (i.getItem());
899 if (degree (contentx) > 0)
900 {
901 if (!find (list, random))
902 list.append (random);
903 result= CFList();
904 LCFeval= CFList();
905 eval= CFList();
906 continue;
907 }
908
909 if (list.length() >= bound)
910 {
911 fail= true;
912 break;
913 }
914 } while (find (list, random));
915
916 if (!eval.isEmpty())
918
919 return result;
920}
921#endif
922
923static inline
925 evaluation, const Variable& alpha, const int lev,
927 )
928{
929 Variable x= Variable (1);
932 int swapLevel= 0;
933 CFList list;
934 bool fail= false;
935 buf= A;
936 Aeval= CFList();
938 for (int i= lev; i <= A.level(); i++)
939 {
940 derivI= deriv (buf, Variable (i));
941 if (!derivI.isZero())
942 {
943 g= gcd (buf, derivI);
944 if (degree (g) > 0)
945 return -1;
946
947 buf= swapvar (buf, x, Variable (i));
948 Aeval= CFList();
950 fail= false;
952 if (!fail)
953 {
954 A= buf;
955 swapLevel= i;
956 break;
957 }
958 else
959 buf= A;
960 }
961 }
962 return swapLevel;
963}
964
966{
967 int i= A.level();
970 buf /= contentAi.getLast();
971 contentAi.append (content (buf, i - 1));
973 for (i= i - 2; i > 0; i--)
974 {
976 buf /= contentAi.getLast();
978 }
979 return result;
980}
981
982#if defined(HAVE_NTL) || defined(HAVE_FLINT) // henselLift23
983CFList
986 const CFList& biFactors, const CFList& evaluation,
987 const ExtensionInfo& info)
988{
989 bool extension= info.isInExtension();
992
994
996 CFArray Pi;
997 int smallFactorDeg= 11; //tunable parameter
999 int adaptedLiftBound= 0;
1000 int liftBound= liftBounds[1];
1001
1002 earlySuccess= false;
1005 j++;
1006 CanonicalForm buf= j.getItem();
1008 MOD= CFList (power (Variable (2), liftBounds[0]));
1010 {
1012 }
1013 else if (smallFactorDeg >= degree (buf) + 1)
1014 {
1015 liftBounds[1]= degree (buf) + 1;
1017 if (Aeval.length() == 2)
1018 {
1019 if (!extension)
1022 degree (buf) + 1, MOD, liftBound);
1023 else
1027 (buf) + 1, MOD, liftBound);
1028 }
1029 else
1030 {
1031 if (!extension)
1033 degree (buf) + 1, MOD, liftBound);
1034 else
1036 evaluation, degree (buf) + 1,
1037 MOD, liftBound);
1038 }
1039 if (!earlySuccess)
1040 {
1041 result.insert (LC (buf, 1));
1045 Pi, diophant, Mat, MOD);
1046 }
1047 else
1049 }
1050 else if (smallFactorDeg < degree (buf) + 1)
1051 {
1054 if (Aeval.length() == 2)
1055 {
1056 if (!extension)
1059 liftBound);
1060 else
1064 }
1065 else
1066 {
1067 if (!extension)
1070 else
1073 liftBound);
1074 }
1075
1076 if (!earlySuccess)
1077 {
1078 result.insert (LC (buf, 1));
1080 Pi, diophant, Mat, MOD);
1081 if (Aeval.length() == 2)
1082 {
1083 if (!extension)
1085 earlySuccess, degree (buf) + 1,
1086 MOD, liftBound);
1087 else
1090 degree (buf) + 1, MOD,
1091 liftBound);
1092 }
1093 else
1094 {
1095 if (!extension)
1097 degree (buf) + 1, MOD,liftBound);
1098 else
1101 degree (buf) + 1, MOD,
1102 liftBound);
1103 }
1104 if (!earlySuccess)
1105 {
1106 result.insert (LC (buf, 1));
1110 Pi, diophant, Mat, MOD);
1111 }
1112 else
1114 }
1115 else
1117 }
1118
1119 MOD.append (power (Variable (3), liftBounds[1]));
1120
1121 if (Aeval.length() > 2)
1122 {
1124 j++;
1126 bufEval.append (j.getItem());
1127 j++;
1128 int liftBoundsLength= Aeval.getLast().level() - 1;
1129 for (int i= 2; i <= liftBoundsLength && j.hasItem(); i++, j++)
1130 {
1131 earlySuccess= false;
1132 result.insert (LC (bufEval.getFirst(), 1));
1133 bufEval.append (j.getItem());
1135 Mat= CFMatrix (liftBounds[i], result.length() - 1);
1136
1137 buf= j.getItem();
1140 liftBounds[i - 1], liftBounds[i]);
1141 else if (smallFactorDeg >= degree (buf) + 1)
1142 {
1144 liftBounds[i - 1], degree (buf) + 1);
1145
1146 if (Aeval.length() == i + 1)
1147 {
1148 if (!extension)
1151 degree (buf) + 1, MOD, liftBound);
1152 else
1156 }
1157 else
1158 {
1159 if (!extension)
1162 + 1, MOD, liftBound);
1163 else
1166 degree (buf) + 1, MOD, liftBound);
1167 }
1168
1169 if (!earlySuccess)
1170 {
1171 result.insert (LC (buf, 1));
1175 Pi, diophant, Mat, MOD);
1176 }
1177 else
1178 {
1180 }
1181 }
1182 else if (smallFactorDeg < degree (buf) + 1)
1183 {
1186
1187 if (Aeval.length() == i + 1)
1188 {
1189 if (!extension)
1193 else
1197 }
1198 else
1199 {
1200 if (!extension)
1204 else
1208 }
1209
1210 if (!earlySuccess)
1211 {
1212 result.insert (LC (buf, 1));
1214 degree (buf) + 1, Pi, diophant, Mat, MOD);
1215 if (Aeval.length() == i + 1)
1216 {
1217 if (!extension)
1220 degree (buf) + 1, MOD, liftBound);
1221 else
1224 info, evaluation, degree (buf) + 1, MOD,
1225 liftBound);
1226 }
1227 else
1228 {
1229 if (!extension)
1232 (buf) + 1, MOD, liftBound);
1233 else
1236 degree (buf) + 1, MOD, liftBound);
1237 }
1238
1239 if (!earlySuccess)
1240 {
1241 result.insert (LC (buf, 1));
1245 Pi, diophant, Mat, MOD);
1246 }
1247 else
1249 }
1250 else
1252 }
1253 MOD.append (power (Variable (i + 2), liftBounds[i]));
1255 }
1257 }
1258 else
1260
1261 if (earlySuccess)
1262 A= buf;
1263 return result;
1264}
1265#endif
1266
1267void
1269{
1271 int k= factors1.length();
1272 int l= factors2.length();
1273 int n= 0;
1274 int m;
1276 for (CFFListIterator i= factors1; (n < k && i.hasItem()); i++, n++)
1277 {
1278 m= 0;
1279 for (j= factors2; (m < l && j.hasItem()); j++, m++)
1280 {
1281 g= gcd (i.getItem().factor(), j.getItem().factor());
1282 if (degree (g,1) > 0)
1283 {
1284 j.getItem()= CFFactor (j.getItem().factor()/g, j.getItem().exp());
1285 i.getItem()= CFFactor (i.getItem().factor()/g, i.getItem().exp());
1286 factors1.append (CFFactor (g, i.getItem().exp()));
1287 factors2.append (CFFactor (g, j.getItem().exp()));
1288 }
1289 }
1290 }
1291}
1292
1293CFList
1295 int length
1296 )
1297{
1298 CFList l= L;
1300
1301 if (content.inCoeffDomain())
1302 return l;
1303
1304 if (l.length() == 1)
1305 {
1306 CFList result;
1307 for (int i= 0; i < length; i++)
1308 {
1309 if (differentSecondVarFactors[i].isEmpty())
1310 continue;
1311 if (result.isEmpty())
1312 {
1314 for (CFListIterator iter= result; iter.hasItem(); iter++)
1315 content /= iter.getItem();
1316 }
1317 else
1318 {
1321 iter2++, iter1++)
1322 {
1323 iter1.getItem() *= iter2.getItem();
1324 content /= iter2.getItem();
1325 }
1326 }
1327 }
1329 return result;
1330 }
1331
1332 Variable v;
1336 for (int i= 0; i < length; i++)
1337 {
1338 if (differentSecondVarFactors[i].isEmpty())
1339 continue;
1340 iter1= l;
1341 iter1++;
1342
1343 tmp= 1;
1344 for (iter2= differentSecondVarFactors[i]; iter2.hasItem();
1345 iter2++, iter1++)
1346 {
1347 if (iter2.getItem().inCoeffDomain())
1348 {
1349 multiplier.append (1);
1350 continue;
1351 }
1352 v= iter2.getItem().mvar();
1353 if (degree (iter2.getItem()) == degree (iter1.getItem(),v))
1354 {
1355 multiplier.append (1);
1356 continue;
1357 }
1358 g= gcd (iter2.getItem(), content);
1359 if (!g.inCoeffDomain())
1360 {
1361 tmp *= g;
1363 }
1364 else
1365 multiplier.append (1);
1366 }
1367 if (!tmp.isOne() && fdivides (tmp, content))
1368 {
1369 iter1= l;
1370 iter1++;
1371 content /= tmp;
1372 for (iter2= multiplier; iter2.hasItem(); iter1++, iter2++)
1373 iter1.getItem() *= iter2.getItem();
1374 }
1375 multiplier= CFList();
1376 }
1377
1378 l.removeFirst();
1379 l.insert (content);
1380 return l;
1381}
1382
1383int
1387 const CFArray& evalPoint)
1388{
1389 CanonicalForm F= G;
1391 if (getCharacteristic() > 0)
1393 else
1395
1396 sqrfPartF= 1;
1397 for (CFFListIterator i= sqrfFactorization; i.hasItem(); i++)
1398 sqrfPartF *= i.getItem().factor();
1399
1401
1403
1404 if (degree (test) != degree (sqrfPartF, 1) || test.inCoeffDomain())
1405 return 0;
1406
1409 CFList tmp2;
1410 int k= 0;
1413 for (CFListIterator i= factors; i.hasItem(); i++, k++)
1414 {
1415 tmp= 1;
1416 if (getCharacteristic() > 0)
1418 else
1419 sqrfFactors= sqrFree (i.getItem());
1420
1421 for (iter= sqrfFactors; iter.hasItem(); iter++)
1422 {
1423 tmp2.append (iter.getItem().factor());
1424 tmp *= iter.getItem().factor();
1425 }
1426 i.getItem()= tmp/Lc(tmp);
1428 }
1429
1430 for (int i= 0; i < factors.length() - 1; i++)
1431 {
1432 for (k= i + 1; k < factors.length(); k++)
1433 {
1435 }
1436 }
1437
1438 factors= CFList();
1439 for (int i= 0; i < uniFactors.length(); i++)
1440 {
1441 if (i == 0)
1442 {
1443 for (iter= bufSqrfFactors [i]; iter.hasItem(); iter++)
1444 {
1445 if (iter.getItem().factor().inCoeffDomain())
1446 continue;
1447 iter.getItem()= CFFactor (iter.getItem().factor()/
1448 Lc (iter.getItem().factor()),
1449 iter.getItem().exp());
1450 factors.append (iter.getItem().factor());
1451 }
1452 }
1453 else
1454 {
1455 for (iter= bufSqrfFactors [i]; iter.hasItem(); iter++)
1456 {
1457 if (iter.getItem().factor().inCoeffDomain())
1458 continue;
1459 iter.getItem()= CFFactor (iter.getItem().factor()/
1460 Lc (iter.getItem().factor()),
1461 iter.getItem().exp());
1462 if (!find (factors, iter.getItem().factor()))
1463 factors.append (iter.getItem().factor());
1464 }
1465 }
1466 }
1467
1468 test= prod (factors);
1470 if (test/Lc (test) != tmp/Lc (tmp))
1471 return 0;
1472 else
1473 return 1;
1474}
1475
1476#if defined(HAVE_NTL) || defined(HAVE_FLINT) // nonMonicHenselLift12
1477CFList
1479 const Variable& alpha, const CFList& evaluation,
1481 Variable& y
1482 )
1483{
1484 y= Variable (1);
1485 if (LCF.inCoeffDomain())
1486 {
1487 CFList result;
1488 for (int i= 1; i <= LCFFactors.length() + 1; i++)
1489 result.append (1);
1490 return result;
1491 }
1492
1493 CFMap N, M;
1494 CFArray dummy= CFArray (2);
1495 dummy [0]= LCF;
1496 dummy [1]= Variable (2);
1497 compress (dummy, M, N);
1498 CanonicalForm F= M (LCF);
1499 if (LCF.isUnivariate())
1500 {
1501 CFList result;
1502 int LCFLevel= LCF.level();
1503 bool found= false;
1504 if (LCFLevel == 2)
1505 {
1506 //bivariate leading coefficients are already the true leading coefficients
1508 found= true;
1509 }
1510 else
1511 {
1513 for (int i= 0; i < lSecondVarLCs; i++)
1514 {
1515 for (j= differentSecondVarLCs[i]; j.hasItem(); j++)
1516 {
1517 if (j.getItem().level() == LCFLevel)
1518 {
1519 found= true;
1520 break;
1521 }
1522 }
1523 if (found)
1524 {
1526 break;
1527 }
1528 }
1529 if (!found)
1531 }
1532 if (found)
1533 result.insert (Lc (LCF));
1534 else
1535 result.insert (LCF);
1536
1537 return result;
1538 }
1539
1541
1542 for (CFListIterator i= factors; i.hasItem(); i++)
1543 i.getItem()= M (i.getItem());
1544
1548 CFArray evalPoint= CFArray (evaluation.length() - 1);
1549 CFArray buf= CFArray (evaluation.length());
1550 CFArray swap= CFArray (evaluation.length());
1553 for (int i= evaluation.length() +1; i > 1; i--, iter++)
1554 {
1555 buf[i-2]=iter.getItem();
1556 if (degree (vars, i) > 0)
1557 swap[M(Variable (i)).level()-1]=buf[i-2];
1558 }
1559 buf= swap;
1560 for (int i= 0; i < evaluation.length() - 1; i++)
1561 evalPoint[i]= buf[i+1];
1562
1565
1566 bool foundDifferent= false;
1567 Variable z, x= y;
1568 int j= 0;
1569 if (!pass)
1570 {
1571 int lev= 0;
1572 // LCF is non-constant here
1575 for (int i= 0; i < lSecondVarLCs; i++)
1576 {
1577 if (!differentSecondVarLCs [i].isEmpty())
1578 {
1579 bool allConstant= true;
1580 for (iter= differentSecondVarLCs[i]; iter.hasItem(); iter++)
1581 {
1582 if (!iter.getItem().inCoeffDomain())
1583 {
1584 allConstant= false;
1585 y= Variable (iter.getItem().level());
1586 lev= M(y).level();
1587 }
1588 }
1589 if (allConstant)
1590 continue;
1591
1593 for (iter= bufFactors; iter.hasItem(); iter++)
1594 iter.getItem()= swapvar (iter.getItem(), x, y);
1595 bufF= F;
1596 z= Variable (lev);
1597 bufF= swapvar (bufF, x, z);
1599 evalPoint= CFArray (evaluation.length() - 1);
1600 for (int k= 1; k < evaluation.length(); k++)
1601 {
1602 if (N (Variable (k+1)).level() != y.level())
1603 evalPoint[k-1]= buf[k];
1604 else
1605 evalPoint[k-1]= buf[0];
1606 }
1609 if (pass)
1610 {
1611 foundDifferent= true;
1612 F= bufF;
1613 CFList l= factors;
1614 for (iter= l; iter.hasItem(); iter++)
1615 iter.getItem()= swapvar (iter.getItem(), x, y);
1617 j= i;
1618 break;
1619 }
1620 if (!pass && i == lSecondVarLCs - 1)
1621 {
1622 CFList result;
1623 result.append (LCF);
1624 for (int j= 1; j <= factors.length(); j++)
1625 result.append (1);
1627 y= Variable (1);
1628 delete [] bufSqrfFactors;
1629 return result;
1630 }
1631 }
1632 }
1633 }
1634 if (!pass)
1635 {
1636 CFList result;
1637 result.append (LCF);
1638 for (int j= 1; j <= factors.length(); j++)
1639 result.append (1);
1641 y= Variable (1);
1642 delete [] bufSqrfFactors;
1643 return result;
1644 }
1645 else
1647
1649
1650 CFMap MM, NN;
1651 dummy [0]= sqrfPartF;
1652 dummy [1]= 1;
1653 compress (dummy, MM, NN);
1656 for (CFListIterator iter= factors; iter.hasItem(); iter++)
1657 iter.getItem()= MM (iter.getItem());
1658
1660 for (int i= 2; i <= varsSqrfPartF.level(); i++)
1662
1666 if (factors.length() > 1)
1667 {
1670 for (int i= 0; i < factors.length(); i++)
1672
1675 for (CFListIterator i= oldFactors; i.hasItem(); i++)
1676 i.getItem() *= LC1eval.getFirst()/Lc (i.getItem());
1677
1678 bool success= false;
1684 {
1687 success= true;
1688 }
1689 if (!success)
1690 {
1691 LC1= LC (evalSqrfPartF.getFirst(), 1);
1692
1694 for (int i= 0; i < factors.length(); i++)
1696
1697 for (CFListIterator i= factors; i.hasItem(); i++)
1698 i.getItem() *= LC1 (0,2)/Lc (i.getItem());
1699 factors.insert (1);
1700
1703
1704 int liftBound= degree (newSqrfPartF,2) + 1;
1705
1707 CFArray Pi;
1710 leadingCoeffs, false);
1711
1712 if (sqrfPartF.level() > 2)
1713 {
1714 int* liftBounds= new int [sqrfPartF.level() - 1];
1715 bool noOneToOne= false;
1716 CFList *leadingCoeffs2= new CFList [sqrfPartF.level()-2];
1717 LC1= LC (evalSqrfPartF.getLast(), 1);
1718 CFList LCs;
1719 for (int i= 0; i < factors.length(); i++)
1720 LCs.append (LC1);
1721 leadingCoeffs2 [sqrfPartF.level() - 3]= LCs;
1722 for (int i= sqrfPartF.level() - 1; i > 2; i--)
1723 {
1724 for (CFListIterator j= LCs; j.hasItem(); j++)
1725 j.getItem()= j.getItem() (0, i + 1);
1726 leadingCoeffs2 [i - 3]= LCs;
1727 }
1728 sqrfPartF *= power (LC1, factors.length()-1);
1729
1730 int liftBoundsLength= sqrfPartF.level() - 1;
1731 for (int i= 0; i < liftBoundsLength; i++)
1732 liftBounds [i]= degree (sqrfPartF, i + 2) + 1;
1736 diophant, Pi, liftBounds, sqrfPartF.level() - 1, noOneToOne);
1737 delete [] leadingCoeffs2;
1738 delete [] liftBounds;
1739 }
1740 for (CFListIterator iter= factors; iter.hasItem(); iter++)
1741 iter.getItem()= reverseShift (iter.getItem(), evaluation2);
1742
1745 factors);
1746 }
1747 }
1748 else
1749 {
1753 }
1754
1755 for (CFListIterator iter= interMedResult; iter.hasItem(); iter++)
1756 iter.getItem()= NN (iter.getItem());
1757
1758 CFList result;
1760 for (int i= 0; i < LCFFactors.length(); i++)
1761 {
1762 CanonicalForm tmp= 1;
1763 for (k= bufSqrfFactors[i]; k.hasItem(); k++)
1764 {
1765 int pos= findItem (bufFactors, k.getItem().factor());
1766 if (pos)
1767 tmp *= power (getItem (interMedResult, pos), k.getItem().exp());
1768 }
1769 result.append (tmp);
1770 }
1771
1772 for (CFListIterator i= result; i.hasItem(); i++)
1773 {
1774 F /= i.getItem();
1775 if (foundDifferent)
1776 i.getItem()= swapvar (i.getItem(), x, z);
1777 i.getItem()= N (i.getItem());
1778 }
1779
1780 if (foundDifferent)
1781 {
1783 for (CFListIterator i= l; i.hasItem(); i++)
1784 i.getItem()= swapvar (i.getItem(), y, z);
1786 F= swapvar (F, x, z);
1787 }
1788
1789 result.insert (N (F));
1790
1792
1793 if (!result.getFirst().inCoeffDomain())
1794 {
1795 // prepare input for recursion
1796 if (foundDifferent)
1797 {
1798 for (CFListIterator i= result; i.hasItem(); i++)
1799 i.getItem()= swapvar (i.getItem(), Variable (2), y);
1801 for (CFListIterator i= l; i.hasItem(); i++)
1802 i.getItem()= swapvar (i.getItem(), y, z);
1804 }
1805
1806 F= result.getFirst();
1807 int level= 0;
1808 if (foundDifferent)
1809 {
1810 level= y.level() - 2;
1811 for (int i= y.level(); i > 1; i--)
1812 {
1813 if (degree (F,i) > 0)
1814 {
1815 if (y.level() == 3)
1816 level= 0;
1817 else
1818 level= i-3;
1819 }
1820 }
1821 }
1822lcretry:
1823 if (lSecondVarLCs - level > 0)
1824 {
1826 int j= lSecondVarLCs+2;
1829 for (i= evaluation2; i.hasItem(); i++, j--)
1830 {
1831 if (j==y.level())
1832 {
1833 swap= i.getItem();
1834 i.getItem()= evaluation2.getLast();
1837 }
1838 }
1839
1841 if (newLCs.isEmpty())
1842 {
1843 if (degree (F, level+3) > 0)
1844 {
1845 delete [] bufSqrfFactors;
1846 return result; //TODO handle this case
1847 }
1848 level=level+1;
1849 goto lcretry;
1850 }
1851 i= newLCs;
1853 iter++;
1855 for (;iter.hasItem(); iter++, i++)
1856 {
1857 swap= iter.getItem();
1858 if (degree (swap, level+3) > 0)
1859 {
1860 int count= evaluation.length()+1;
1861 for (CFListIterator iter2= evaluation2; iter2.hasItem(); iter2++,
1862 count--)
1863 {
1864 if (count != level+3)
1865 swap= swap (iter2.getItem(), count);
1866 }
1867 if (fdivides (swap, i.getItem(), quot))
1868 i.getItem()= quot;
1869 }
1870 }
1872 for (int j= level+1; j < lSecondVarLCs; j++)
1873 {
1874 if (degree (F, j+3) > 0)
1875 {
1876 if (!differentSecondVarLCs[j].isEmpty())
1877 {
1880 iter=result;
1881 iter++;
1882 for (;iter.hasItem(); iter++, i++)
1883 {
1884 swap= iter.getItem();
1885 if (degree (swap, j+3) > 0)
1886 {
1887 int count= evaluation.length()+1;
1888 for (CFListIterator iter2= evaluation2; iter2.hasItem();iter2++,
1889 count--)
1890 {
1891 if (count != j+3)
1892 swap= swap (iter2.getItem(), count);
1893 }
1894 if (fdivides (swap, i.getItem(), quot))
1895 i.getItem()= quot;
1896 }
1897 }
1898 }
1899 }
1900 }
1901
1902 for (int j= 0; j < level+1; j++)
1905
1908 for (i=newLCs; i.hasItem(); i++)
1909 i.getItem()= swapvar (i.getItem(), Variable (2), Variable (level+3));
1910 for (int j= 1; j < lSecondVarLCs-level;j++)
1911 {
1912 for (i= differentSecondVarLCs2[j-1]; i.hasItem(); i++)
1913 i.getItem()= swapvar (i.getItem(), Variable (2+j),
1914 Variable (level+3+j));
1916 }
1917
1921 dummyvar);
1922
1923 if (dummyvar.level() != 1)
1924 {
1925 for (i= recursiveResult; i.hasItem(); i++)
1926 i.getItem()= swapvar (i.getItem(), Variable (2), dummyvar);
1927 }
1928 for (i= recursiveResult; i.hasItem(); i++)
1929 {
1930 for (int j= lSecondVarLCs-level-1; j > 0; j--)
1931 i.getItem()=swapvar (i.getItem(), Variable (2+j),
1932 Variable (level+3+j));
1933 i.getItem()= swapvar (i.getItem(), Variable (2), Variable (level+3));
1934 }
1935
1936 if (recursiveResult.getFirst() == result.getFirst())
1937 {
1938 delete [] bufSqrfFactors;
1939 delete [] differentSecondVarLCs2;
1940 return result;
1941 }
1942 else
1943 {
1945 i= result;
1946 i.getItem()= iter.getItem();
1947 i++;
1948 iter++;
1949 for (; i.hasItem(); i++, iter++)
1950 i.getItem() *= iter.getItem();
1951 delete [] differentSecondVarLCs2;
1952 }
1953 }
1954 }
1955 else
1956 y= Variable (1);
1957
1958 delete [] bufSqrfFactors;
1959
1960 return result;
1961}
1962#endif
1963
1964void
1966 const CanonicalForm& A)
1967{
1969 CFList tmp2;
1971 bool preserveDegree= true;
1972 Variable x= Variable (1);
1973 int j, degAi, degA1= degree (A,1);
1974 for (int i= A.level(); i > 2; i--)
1975 {
1976 tmp= A;
1977 tmp2= CFList();
1979 preserveDegree= true;
1980 degAi= degree (A,i);
1981 for (j= A.level(); j > 1; j--, iter++)
1982 {
1983 if (j == i)
1984 continue;
1985 else
1986 {
1987 tmp= tmp (iter.getItem(), j);
1988 tmp2.insert (tmp);
1989 if ((degree (tmp, i) != degAi) ||
1990 (degree (tmp, 1) != degA1))
1991 {
1992 preserveDegree= false;
1993 break;
1994 }
1995 }
1996 }
1997 if (!content(tmp,1).inCoeffDomain())
1998 preserveDegree= false;
1999 if (!content(tmp).inCoeffDomain())
2000 preserveDegree= false;
2001 if (!(gcd (deriv (tmp,x), tmp)).inCoeffDomain())
2002 preserveDegree= false;
2003 if (preserveDegree)
2004 Aeval [i - 3]= tmp2;
2005 else
2006 Aeval [i - 3]= CFList();
2007 }
2008}
2009
2010static inline
2012 const Variable& v)
2013{
2015 for (CFListIterator i= l; i.hasItem(); i++)
2016 result *= i.getItem() (evalPoint, v);
2017 return result;
2018}
2019
2020void
2022 CFList& l1, CFList& l2)
2023{
2024 CanonicalForm g1= f1, g2;
2026 for (; iter1.hasItem(); iter1++, iter2++)
2027 {
2028 g2= gcd (g1, iter1.getItem());
2029 if (!g2.inCoeffDomain())
2030 {
2031 l1.append (iter1.getItem());
2032 l2.append (iter2.getItem());
2033 g1 /= g2;
2034 }
2035 }
2038}
2039
2040/// check if univariate factors @a factors2 of @a factors3 coincide with
2041/// univariate factors of @a factors1 and recombine if necessary.
2042/// The recombined factors of @a factors1 are returned and @a factors3 is
2043/// recombined accordingly.
2044CFList
2046 const CanonicalForm& evalPoint, const Variable& x)
2047{
2053 int pos;
2054
2055 for (iter= factors1; iter.hasItem(); iter++)
2056 {
2057 tmp= iter.getItem() (evalPoint, x);
2058 tmp /= Lc (tmp);
2059 if ((pos= findItem (factors2, tmp)))
2060 {
2061 result2.append (getItem (factors3, pos));
2062 result.append (iter.getItem());
2064 }
2065 else
2067 }
2068
2069 CFList bad2, bad3;
2072 CFList tmp2, tmp3;
2073 CanonicalForm g1, g2, g3, g4;
2074
2075 while (!uniFactorsOfFactors1.isEmpty())
2076 {
2079 g1= prod (tmp2);
2080 g2= prod (tmp3);
2081 tmp2= CFList();
2082 tmp3= CFList();
2084 g3= prod (tmp2);
2085 g4= prod (tmp3);
2086 tmp2= CFList();
2087 tmp3= CFList();
2088 do
2089 {
2091 g1 *= prod (tmp2);
2092 g2 *= prod (tmp3);
2093 tmp2= CFList();
2094 tmp3= CFList();
2096 g3 *= prod (tmp2);
2097 g4 *= prod (tmp3);
2098 tmp2= CFList();
2099 tmp3= CFList();
2100 } while (!bad2.isEmpty() && !bad3.isEmpty());
2101 result.append (g4);
2102 result2.append (g2);
2103 }
2104
2105 if (factors3.length() != result2.length())
2107 return result;
2108}
2109
2110//recombine bivariate factors in case one bivariate factorization yields less
2111// factors than the other
2112CFList
2114 const CanonicalForm& evalPoint, const Variable& x)
2115{
2116 CFList T, S;
2117
2118 T= factors1;
2119 CFList result;
2121 int * v= new int [T.length()];
2122 for (int i= 0; i < T.length(); i++)
2123 v[i]= 0;
2124 bool nosubset= false;
2125 CFArray TT;
2126 TT= copy (factors1);
2127 int recombinations= 0;
2128 while (T.length() >= 2*s && s <= thres)
2129 {
2130 while (nosubset == false)
2131 {
2132 if (T.length() == s)
2133 {
2134 delete [] v;
2135 if (recombinations == factors2.length() - 1)
2136 result.append (prod (T));
2137 else
2138 result= Union (result, T);
2139 return result;
2140 }
2141 S= subset (v, s, TT, nosubset);
2142 if (nosubset) break;
2143 buf= prodEval (S, evalPoint, x);
2144 buf /= Lc (buf);
2145 if (find (factors2, buf))
2146 {
2148 T= Difference (T, S);
2149 result.append (prod (S));
2150 TT= copy (T);
2151 indexUpdate (v, s, T.length(), nosubset);
2152 if (nosubset) break;
2153 }
2154 }
2155 s++;
2156 if (T.length() < 2*s || T.length() == s)
2157 {
2158 if (recombinations == factors2.length() - 1)
2159 result.append (prod (T));
2160 else
2161 result= Union (result, T);
2162 delete [] v;
2163 return result;
2164 }
2165 for (int i= 0; i < T.length(); i++)
2166 v[i]= 0;
2167 nosubset= false;
2168 }
2169
2170 delete [] v;
2171 if (T.length() < 2*s)
2172 {
2173 result= Union (result, T);
2174 return result;
2175 }
2176
2177 return result;
2178}
2179
2180#if defined(HAVE_NTL) || defined(HAVE_FLINT)
2181#ifdef HAVE_NTL // GFBiSqrfFactorize
2182void
2184 const ExtensionInfo& info,
2185 int& minFactorsLength, bool& irred)
2186{
2187 Variable x= Variable (1);
2189 irred= false;
2191 Variable v;
2192 for (int j= 0; j < A.level() - 2; j++)
2193 {
2194 if (!Aeval[j].isEmpty())
2195 {
2196 v= Variable (Aeval[j].getFirst().level());
2198 factors= GFBiSqrfFactorize (Aeval[j].getFirst());
2199 else if (info.getAlpha().level() == 1)
2200 factors= FpBiSqrfFactorize (Aeval[j].getFirst());
2201 else
2202 factors= FqBiSqrfFactorize (Aeval[j].getFirst(), info.getAlpha());
2203
2205 if (minFactorsLength == 0)
2207 else
2209
2210 if (factors.length() == 1)
2211 {
2212 irred= true;
2213 return;
2214 }
2215 sortList (factors, x);
2216 Aeval [j]= factors;
2217 }
2218 }
2219}
2220#endif
2221#endif
2222
2224{
2225 CFList result;
2226 for (int i= A.max(); i >= A.min(); i--)
2227 result.insert (A[i]);
2228 return result;
2229}
2230
2231
2233 )
2234{
2236 CFList LCs;
2237 for (int j= 0; j < A.level() - 2; j++)
2238 {
2239 if (!Aeval[j].isEmpty())
2240 {
2241 LCs= CFList();
2242 for (iter= Aeval[j]; iter.hasItem(); iter++)
2243 LCs.append (LC (iter.getItem(), 1));
2244 //normalize (LCs);
2245 Aeval[j]= LCs;
2246 }
2247 }
2248}
2249
2252 const CFList& evaluation
2253 )
2254{
2256 int i;
2258 Variable v;
2259 CFList LCs, buf;
2260 CFArray l;
2261 int pos, index, checklength;
2262 bool leaveLoop=false;
2263recurse:
2264 for (int j= 0; j < AevalLength; j++)
2265 {
2266 if (!Aeval[j].isEmpty())
2267 {
2268 i= evaluation.length() + 1;
2269 for (iter= evaluation; iter.hasItem(); iter++, i--)
2270 {
2271 for (iter2= Aeval[j]; iter2.hasItem(); iter2++)
2272 {
2273 if (i == iter2.getItem().level())
2274 {
2275 evalPoint= iter.getItem();
2276 leaveLoop= true;
2277 break;
2278 }
2279 }
2280 if (leaveLoop)
2281 {
2282 leaveLoop= false;
2283 break;
2284 }
2285 }
2286
2287 v= Variable (i);
2288 if (Aeval[j].length() > uniFactors.length())
2290 Aeval[j].length() - uniFactors.length() + 1,
2291 evalPoint, v);
2292
2296 {
2298 Variable (2));
2299 goto recurse;
2300 }
2301
2304 index= 1;
2305 for (iter= buf; iter.hasItem(); iter++, index++)
2306 {
2307 pos= findItem (uniFactors, iter.getItem());
2308 if (pos)
2309 l[pos-1]= getItem (Aeval[j], index);
2310 }
2311 buf= conv (l);
2312 Aeval [j]= buf;
2313
2315 }
2316 }
2317}
2318
2319CFList
2321 const Variable& y)
2322{
2323 CFList result;
2325 for (CFListIterator i= biFactors; i.hasItem(); i++)
2326 {
2327 tmp= mod (i.getItem(), y - evalPoint);
2328 tmp /= Lc (tmp);
2329 result.append (tmp);
2330 }
2331 return result;
2332}
2333
2335 CFList* const& Aeval, const CFList& evaluation,
2336 int minFactorsLength)
2337{
2340 int i;
2341 Variable v;
2342 Variable y= Variable (2);
2343 CFList list;
2344 bool leaveLoop= false;
2345 for (int j= 0; j < A.level() - 2; j++)
2346 {
2347 if (Aeval[j].length() == minFactorsLength)
2348 {
2349 i= A.level();
2350
2351 for (iter= evaluation; iter.hasItem(); iter++, i--)
2352 {
2353 for (iter2= Aeval[j]; iter2.hasItem(); iter2++)
2354 {
2355 if (i == iter2.getItem().level())
2356 {
2357 evalPoint= iter.getItem();
2358 leaveLoop= true;
2359 break;
2360 }
2361 }
2362 if (leaveLoop)
2363 {
2364 leaveLoop= false;
2365 break;
2366 }
2367 }
2368
2369 v= Variable (i);
2370 list= buildUniFactors (Aeval[j], evalPoint, v);
2371
2373 biFactors.length() - list.length() + 1,
2374 evaluation.getLast(), y);
2375 return;
2376 }
2377 }
2378}
2379
2380void
2382 const CFList& leadingCoeffs, const CFList& biFactors,
2383 const CFList& evaluation)
2384{
2386 LCs [n-3]= l;
2389 for (int i= n - 1; i > 2; i--, iter++)
2390 {
2391 for (j= l; j.hasItem(); j++)
2392 j.getItem()= j.getItem() (iter.getItem(), i + 1);
2393 LCs [i - 3]= l;
2394 }
2395 l= LCs [0];
2396 for (CFListIterator i= l; i.hasItem(); i++)
2397 i.getItem()= i.getItem() (iter.getItem(), 3);
2400 for (CFListIterator i= l; i.hasItem(); i++, ii++)
2401 normalizeFactor.append (Lc (LC (ii.getItem(), 1))/Lc (i.getItem()));
2402 for (int i= 0; i < n-2; i++)
2403 {
2405 for (j= LCs [i]; j.hasItem(); j++, ii++)
2406 j.getItem() *= ii.getItem();
2407 }
2408
2410
2412
2413 for (iter= Aeval; iter.hasItem(); iter++)
2414 iter.getItem() *= hh;
2415
2416 A *= hh;
2417}
2418
2419CFList
2421 const ExtensionInfo& info)
2422{
2423 Variable alpha= info.getAlpha();
2424 Variable beta= info.getBeta();
2425 CanonicalForm gamma= info.getGamma();
2426 CanonicalForm delta= info.getDelta();
2427 int k= info.getGFDegree();
2428 CFList source, dest;
2429
2430 int degMipoBeta= 1;
2431 if (!k && beta != Variable(1))
2433
2434 CFList T, S;
2435 T= factors;
2436 int s= 1;
2437 CFList result;
2439
2442 int * v= new int [T.length()];
2443 for (int i= 0; i < T.length(); i++)
2444 v[i]= 0;
2445 bool noSubset= false;
2446 CFArray TT;
2447 TT= copy (factors);
2448 bool recombination= false;
2449 bool trueFactor= false;
2450 while (T.length() >= 2*s)
2451 {
2452 while (noSubset == false)
2453 {
2454 if (T.length() == s)
2455 {
2456 delete [] v;
2457 if (recombination)
2458 {
2459 g= prod (T);
2460 T.removeFirst();
2461 g /= myContent (g);
2462 g /= Lc (g);
2464 return result;
2465 }
2466 else
2467 return CFList (buf/myContent(buf));
2468 }
2469
2470 S= subset (v, s, TT, noSubset);
2471 if (noSubset) break;
2472
2473 g= prod (S);
2474 g /= myContent (g);
2475 if (fdivides (g, buf, quot))
2476 {
2477 buf2= g;
2478 buf2 /= Lc (buf2);
2479 if (!k && beta.level() == 1)
2480 {
2481 if (degree (buf2, alpha) < degMipoBeta)
2482 {
2484 buf= quot;
2485 recombination= true;
2486 trueFactor= true;
2487 }
2488 }
2489 else
2490 {
2491 if (!isInExtension (buf2, gamma, k, delta, source, dest))
2492 {
2494 buf= quot;
2495 recombination= true;
2496 trueFactor= true;
2497 }
2498 }
2499 if (trueFactor)
2500 {
2501 T= Difference (T, S);
2502
2503 if (T.length() < 2*s || T.length() == s)
2504 {
2505 delete [] v;
2506 buf /= myContent (buf);
2507 buf /= Lc (buf);
2509 return result;
2510 }
2511 trueFactor= false;
2512 TT= copy (T);
2513 indexUpdate (v, s, T.length(), noSubset);
2514 if (noSubset) break;
2515 }
2516 }
2517 }
2518 s++;
2519 if (T.length() < 2*s || T.length() == s)
2520 {
2521 delete [] v;
2522 buf /= myContent (buf);
2523 buf /= Lc (buf);
2525 return result;
2526 }
2527 for (int i= 0; i < T.length(); i++)
2528 v[i]= 0;
2529 noSubset= false;
2530 }
2531 if (T.length() < 2*s)
2532 {
2533 buf= F/myContent (F);
2534 buf /= Lc (buf);
2535 appendMapDown (result, buf, info, source, dest);
2536 }
2537
2538 delete [] v;
2539 return result;
2540}
2541
2542void
2545 const CFList& uniFactors, const Variable& w)
2546{
2547 Variable y= Variable (2);
2548 A= swapvar (A, y, w);
2549 int i= A.level();
2551 for (CFListIterator iter= evaluation; iter.hasItem(); iter++, i--)
2552 {
2553 if (i == w.level())
2554 {
2555 evalPoint= iter.getItem();
2556 iter.getItem()= evaluation.getLast();
2557 evaluation.removeLast();
2558 evaluation.append (evalPoint);
2559 break;
2560 }
2561 }
2562 for (i= 0; i < lengthAeval2; i++)
2563 {
2564 if (oldAeval[i].isEmpty())
2565 continue;
2566 if (oldAeval[i].getFirst().level() == w.level())
2567 {
2570 for (CFListIterator iter= oldAeval[i]; iter.hasItem(); iter++)
2571 iter.getItem()= swapvar (iter.getItem(), w, y);
2572 for (int ii= 0; ii < tmp.size(); ii++)
2573 tmp[ii]= swapvar (tmp[ii], w, y);
2574 CFArray tmp2= CFArray (tmp.size());
2576 for (int ii= 0; ii < tmp.size(); ii++)
2577 {
2578 buf= tmp[ii] (evaluation.getLast(),y);
2579 buf /= Lc (buf);
2581 }
2582 biFactors= CFList();
2583 for (int j= 0; j < tmp2.size(); j++)
2585 }
2586 }
2587}
2588
2589void
2593{
2595 A *= tmp;
2598 for (;iter.hasItem(); iter++)
2599 iter.getItem() *= LCmultipler;
2601 for (int i= A.level(); i > 2; i--, iter++)
2602 tmp= tmp (iter.getItem(), i);
2603 if (!tmp.inCoeffDomain())
2604 {
2605 for (CFListIterator i= biFactors; i.hasItem(); i++)
2606 {
2607 i.getItem() *= tmp/LC (i.getItem(), 1);
2608 i.getItem() /= Lc (i.getItem());
2609 }
2610 }
2611}
2612
2613void
2616 int lengthAeval, const CFList& evaluation,
2617 const CFList& oldBiFactors)
2618{
2620 int index;
2621 Variable xx;
2622 CFList vars1;
2624 if (sqrfMultiplier.getFirst().factor().inCoeffDomain())
2627 xx= Variable (2);
2628 for (iter= oldBiFactors; iter.hasItem(); iter++)
2629 vars1.append (power (xx, degree (LC (iter.getItem(),1), xx)));
2630 for (int i= 0; i < lengthAeval; i++)
2631 {
2632 if (oldAeval[i].isEmpty())
2633 continue;
2634 xx= oldAeval[i].getFirst().mvar();
2635 iter2= vars1;
2636 for (iter= oldAeval[i]; iter.hasItem(); iter++, iter2++)
2637 iter2.getItem() *= power (xx, degree (LC (iter.getItem(),1), xx));
2638 }
2640 iter2= vars1;
2641 for (iter= leadingCoeffs[lengthAeval-1]; iter.hasItem(); iter++, iter2++)
2642 {
2643 tmp= iter.getItem()/LCmultiplier;
2644 for (int i=1; i <= tmp.level(); i++)
2645 {
2646 if (degree (tmp,i) > 0 && (degree (iter2.getItem(),i) > degree (tmp,i)))
2647 iter2.getItem() /= power (Variable (i), degree (tmp,i));
2648 }
2649 }
2650 int multi;
2651 for (CFFListIterator ii= sqrfMultiplier; ii.hasItem(); ii++)
2652 {
2653 multi= 0;
2654 for (iter= vars1; iter.hasItem(); iter++)
2655 {
2656 tmp= iter.getItem();
2657 while (fdivides (myGetVars (ii.getItem().factor()), tmp))
2658 {
2659 multi++;
2660 tmp /= myGetVars (ii.getItem().factor());
2661 }
2662 }
2663 if (multi == ii.getItem().exp())
2664 {
2665 index= 1;
2666 for (iter= vars1; iter.hasItem(); iter++, index++)
2667 {
2668 while (fdivides (myGetVars (ii.getItem().factor()), iter.getItem()))
2669 {
2670 int index2= 1;
2671 for (iter2= leadingCoeffs[lengthAeval-1]; iter2.hasItem();iter2++,
2672 index2++)
2673 {
2674 if (index2 == index)
2675 continue;
2676 else
2677 {
2678 tmp= ii.getItem().factor();
2679 if (fdivides (tmp, iter2.getItem(), quot1))
2680 {
2682 for (int jj= A.level(); jj > 2; jj--, iter3++)
2683 tmp= tmp (iter3.getItem(), jj);
2684 if (!tmp.inCoeffDomain())
2685 {
2686 int index3= 1;
2687 for (iter3= biFactors; iter3.hasItem(); iter3++, index3++)
2688 {
2689 if (index3 == index2)
2690 {
2691 if (fdivides (tmp, iter3.getItem(), quot2))
2692 {
2693 if (fdivides (ii.getItem().factor(), A, quot3))
2694 {
2695 A = quot3;
2696 iter2.getItem() = quot2;
2697 iter3.getItem() = quot3;
2698 iter3.getItem() /= Lc (iter3.getItem());
2699 break;
2700 }
2701 }
2702 }
2703 }
2704 }
2705 }
2706 }
2707 }
2708 iter.getItem() /= getVars (ii.getItem().factor());
2709 }
2710 }
2711 }
2712 else
2713 {
2714 index= 1;
2715 for (iter= vars1; iter.hasItem(); iter++, index++)
2716 {
2717 if (!fdivides (myGetVars (ii.getItem().factor()), iter.getItem()))
2718 {
2719 int index2= 1;
2720 for (iter2= leadingCoeffs[lengthAeval-1];iter2.hasItem();iter2++,
2721 index2++)
2722 {
2723 if (index2 == index)
2724 {
2725 tmp= power (ii.getItem().factor(), ii.getItem().exp());
2726 if (fdivides (tmp, A, quot1))
2727 {
2728 if (fdivides (tmp, iter2.getItem()))
2729 {
2731 for (int jj= A.level(); jj > 2; jj--, iter3++)
2732 tmp= tmp (iter3.getItem(), jj);
2733 if (!tmp.inCoeffDomain())
2734 {
2735 int index3= 1;
2736 for (iter3= biFactors; iter3.hasItem(); iter3++, index3++)
2737 {
2738 if (index3 == index2)
2739 {
2740 if (fdivides (tmp, iter3.getItem(), quot3))
2741 {
2742 A = quot1;
2743 iter2.getItem() = quot2;
2744 iter3.getItem() = quot3;
2745 iter3.getItem() /= Lc (iter3.getItem());
2746 break;
2747 }
2748 }
2749 }
2750 }
2751 }
2752 }
2753 }
2754 }
2755 }
2756 }
2757 }
2758 }
2759}
2760
2761void
2764 bool& foundTrueMultiplier)
2765{
2767 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
2768 {
2769 A= oldA;
2771 for (CFListIterator iter= contents; iter.hasItem(); iter++, iter2++)
2772 iter2.getItem() /= iter.getItem();
2773 foundTrueMultiplier= true;
2774 }
2775}
2776
2777void
2780 bool& foundTrueMultiplier)
2781{
2783 int index= 1;
2785 for (CFListIterator iter= factors; iter.hasItem(); iter++, index++)
2786 {
2787 cont= content (iter.getItem(), 1);
2790 if (cont.inCoeffDomain()) // trivial content->LCmultiplier needs to go there
2791 {
2792 foundTrueMultiplier= true;
2793 int index2= 1;
2794 for (iter2= leadingCoeffs; iter2.hasItem(); iter2++, index2++)
2795 {
2796 if (index2 == index)
2797 continue;
2798 iter2.getItem() /= LCmultiplier;
2799 }
2800 break;
2801 }
2802 else
2803 LCs.append (LC (iter.getItem()/cont, 1));
2804 }
2805}
2806
2807void
2809 const CFList& oldBiFactors, const CFList& contents,
2811 int lengthAeval, bool& foundMultiplier)
2812{
2813 int index= 1;
2815 for (iter= contents; iter.hasItem(); iter++, iter2++, index++)
2816 {
2817 if (fdivides (iter.getItem(), LCmultiplier))
2818 {
2819 if ((LCmultiplier/iter.getItem()).inCoeffDomain() &&
2820 !isOnlyLeadingCoeff(iter2.getItem())) //content divides LCmultiplier completely and factor consists of more terms than just the leading coeff
2821 {
2822 Variable xx= Variable (2);
2825 xx));
2826 for (int i= 0; i < lengthAeval; i++)
2827 {
2828 if (oldAeval[i].isEmpty())
2829 continue;
2830 xx= oldAeval[i].getFirst().mvar();
2831 vars *= power (xx, degree (LC (getItem(oldAeval[i], index),1),
2832 xx));
2833 }
2834 if (vars.level() <= 2)
2835 {
2836 int index2= 1;
2838 iter3.hasItem(); iter3++, index2++)
2839 {
2840 if (index2 == index)
2841 {
2842 iter3.getItem() /= LCmultiplier;
2843 break;
2844 }
2845 }
2846 A /= LCmultiplier;
2847 foundMultiplier= true;
2848 iter.getItem()= 1;
2849 }
2850 }
2851 }
2852 }
2853}
2854
2855void
2857 const CFList& contents, const CFList& factors,
2861{
2862 int index=1;
2864 for (iter= contents; iter.hasItem(); iter++, iter2++, index++)
2865 {
2866 if (!iter.getItem().isOne() &&
2867 fdivides (iter.getItem(), LCmultiplier))
2868 {
2869 if (!isOnlyLeadingCoeff (iter2.getItem())) // factor is more than just leading coeff
2870 {
2871 int index2= 1;
2872 for (iter2= leadingCoeffs[lengthAeval-1]; iter2.hasItem();
2873 iter2++, index2++)
2874 {
2875 if (index2 == index)
2876 {
2877 iter2.getItem() /= iter.getItem();
2878 foundMultiplier= true;
2879 break;
2880 }
2881 }
2882 A /= iter.getItem();
2883 LCmultiplier /= iter.getItem();
2884 iter.getItem()= 1;
2885 }
2886 else if (fdivides (getVars (LCmultiplier), testVars))//factor consists of just leading coeff
2887 {
2888 Variable xx= Variable (2);
2891 xx));
2892 for (int i= 0; i < lengthAeval; i++)
2893 {
2894 if (oldAeval[i].isEmpty())
2895 continue;
2896 xx= oldAeval[i].getFirst().mvar();
2897 vars *= power (xx, degree (LC (getItem(oldAeval[i], index),1),
2898 xx));
2899 }
2902 {
2903 int index2= 1;
2904 for (iter2= leadingCoeffs[lengthAeval-1]; iter2.hasItem();
2905 iter2++, index2++)
2906 {
2907 if (index2 == index)
2908 {
2909 iter2.getItem() /= LCmultiplier;
2910 foundMultiplier= true;
2911 break;
2912 }
2913 }
2914 A /= LCmultiplier;
2915 iter.getItem()= 1;
2916 }
2917 }
2918 }
2919 }
2920}
2921
2922#if defined(HAVE_NTL) || defined(HAVE_FLINT)
2923#ifdef HAVE_NTL // biSqrfFactorizeHelper
2924CFList
2925extFactorize (const CanonicalForm& F, const ExtensionInfo& info);
2926
2927CFList
2929{
2930 if (F.inCoeffDomain())
2931 return CFList (F);
2932
2934 // compress and find main Variable
2935 CFMap N;
2938 TIMING_END_AND_PRINT (fac_fq_compress, "time to compress poly over Fq: ")
2939
2940 A /= Lc (A); // make monic
2941
2942 Variable alpha= info.getAlpha();
2943 Variable beta= info.getBeta();
2944 CanonicalForm gamma= info.getGamma();
2945 CanonicalForm delta= info.getDelta();
2946 bool extension= info.isInExtension();
2948 //univariate case
2949 if (F.isUnivariate())
2950 {
2951 if (extension == false)
2952 return uniFactorizer (F, alpha, GF);
2953 else
2954 {
2955 CFList source, dest;
2956 A= mapDown (F, info, source, dest);
2957 return uniFactorizer (A, beta, GF);
2958 }
2959 }
2960
2961 //bivariate case
2962 if (A.level() == 2)
2963 {
2965 if (buf.getFirst().inCoeffDomain())
2966 buf.removeFirst();
2967 return buf;
2968 }
2969
2970 Variable x= Variable (1);
2971 Variable y= Variable (2);
2972
2973 // remove content
2977 A /= lcmCont;
2978 TIMING_END_AND_PRINT (fac_fq_content, "time to extract content over Fq: ");
2979
2980 // trivial after content removal
2982 if (A.inCoeffDomain())
2983 {
2984 for (CFListIterator i= contentAi; i.hasItem(); i++)
2985 {
2986 if (i.getItem().inCoeffDomain())
2987 continue;
2988 else
2989 {
2990 lcmCont /= i.getItem();
2993 multiFactorize (i.getItem(), info));
2994 break;
2995 }
2996 }
2998 if (!extension)
3000 return contentAFactors;
3001 }
3002
3003 // factorize content
3006 TIMING_END_AND_PRINT (fac_fq_content, "time to factor content over Fq: ");
3007
3008 // univariate after content removal
3010 if (A.isUnivariate ())
3011 {
3014 decompress (factors, N);
3015 return factors;
3016 }
3017
3018 // check main variable
3020 int swapLevel= 0;
3024 Variable z;
3025 for (int i= 1; i <= A.level(); i++)
3026 {
3027 z= Variable (i);
3028 derivZ= deriv (bufA, z);
3029 if (derivZ.isZero())
3030 {
3031 if (i == 1)
3032 swapLevel= 1;
3033 else
3034 continue;
3035 }
3036 else
3037 {
3039 if (degree (gcdDerivZ) > 0 && !derivZ.isZero())
3040 {
3046 if (!extension)
3048 return factorsG;
3049 }
3050 else
3051 {
3052 if (swapLevel == 1)
3053 {
3054 swapLevel= i;
3055 bufA= swapvar (A, x, z);
3056 }
3057 A= bufA;
3058 break;
3059 }
3060 }
3061 }
3063 "time to check main var over Fq: ");
3065 "time to preprocess poly and extract content over Fq: ");
3066
3068 bool fail= false;
3069 int swapLevel2= 0;
3070 //int level;
3071 int factorNums= 3;
3074 int lift, bufLift, lengthAeval2= A.level()-2;
3075 double logarithm= (double) ilog2 (totaldegree (A));
3076 logarithm /= log2exp;
3077 logarithm= ceil (logarithm);
3078 if (factorNums < (int) logarithm)
3082 int counter;
3083 int differentSecondVar= 0;
3084 // several bivariate factorizations
3086 for (int i= 0; i < factorNums; i++)
3087 {
3088 counter= 0;
3089 bufA= A;
3090 bufAeval= CFList();
3094 "time to find evaluation point over Fq: ");
3095 evalPoly= 0;
3096
3097 if (fail && (i == 0))
3098 {
3099 /*if (!swapLevel) //uncomment to reenable search for new main variable
3100 level= 2;
3101 else
3102 level= swapLevel + 1;*/
3103
3104 //CanonicalForm g;
3105 //swapLevel2= newMainVariableSearch (A, Aeval, evaluation, alpha, level, g);
3106
3107 /*if (!swapLevel2) // need to pass to an extension
3108 {*/
3112 delete [] bufAeval2;
3113 delete [] Aeval2;
3114 return factors;
3115 /*}
3116 else
3117 {
3118 if (swapLevel2 == -1)
3119 {
3120 CFList factorsG=
3121 Union (multiFactorize (g, info),
3122 multiFactorize (A/g, info));
3123 appendSwapDecompress (factorsG, contentAFactors, N, swapLevel, x);
3124 if (!extension)
3125 normalize (factorsG);
3126 delete [] bufAeval2;
3127 delete [] Aeval2;
3128 return factorsG;
3129 }
3130 fail= false;
3131 bufAeval= Aeval;
3132 bufA= A;
3133 bufEvaluation= evaluation;
3134 }*/ //end uncomment
3135 }
3136 else if (fail && (i > 0))
3137 break;
3138
3142 "time for evaluation wrt diff second vars over Fq: ");
3143
3144 for (int j= 0; j < lengthAeval2; j++)
3145 {
3146 if (!bufAeval2[j].isEmpty())
3147 counter++;
3148 }
3149
3150 bufLift= degree (A, y) + 1 + degree (LC(A, x), y);
3151
3153 if (!GF && alpha.level() == 1)
3155 else if (GF)
3157 else
3160 "time for bivariate factorization: ");
3162
3163 if (bufBiFactors.length() == 1)
3164 {
3165 if (extension)
3166 {
3167 CFList source, dest;
3168 A= mapDown (A, info, source, dest);
3169 }
3170 factors.append (A);
3172 swapLevel2, x);
3173 if (!extension)
3175 delete [] bufAeval2;
3176 delete [] Aeval2;
3177 return factors;
3178 }
3179
3180 if (i == 0)
3181 {
3182 Aeval= bufAeval;
3185 lift= bufLift;
3186 for (int j= 0; j < lengthAeval2; j++)
3187 Aeval2 [j]= bufAeval2 [j];
3188 differentSecondVar= counter;
3189 }
3190 else
3191 {
3192 if (bufBiFactors.length() < biFactors.length() ||
3193 ((bufLift < lift) && (bufBiFactors.length() == biFactors.length())) ||
3194 counter > differentSecondVar)
3195 {
3196 Aeval= bufAeval;
3199 lift= bufLift;
3200 for (int j= 0; j < lengthAeval2; j++)
3201 Aeval2 [j]= bufAeval2 [j];
3202 differentSecondVar= counter;
3203 }
3204 }
3205 int k= 0;
3206 for (CFListIterator j= bufEvaluation; j.hasItem(); j++, k++)
3207 evalPoly += j.getItem()*power (x, k);
3208 list.append (evalPoly);
3209 }
3210
3211 delete [] bufAeval2;
3212
3213 sortList (biFactors, x);
3214
3215 int minFactorsLength;
3216 bool irred= false;
3220 "time for bivariate factorization wrt diff second vars over Fq: ");
3221
3223 "total time for eval and bivar factors over Fq: ");
3224 if (irred)
3225 {
3226 if (extension)
3227 {
3228 CFList source, dest;
3229 A= mapDown (A, info, source, dest);
3230 }
3231 factors.append (A);
3233 swapLevel2, x);
3234 if (!extension)
3236 delete [] Aeval2;
3237 return factors;
3238 }
3239
3240 if (minFactorsLength == 0)
3242 else if (biFactors.length() > minFactorsLength)
3245
3247
3249
3251
3252 if (minFactorsLength == 1)
3253 {
3254 if (extension)
3255 {
3256 CFList source, dest;
3257 A= mapDown (A, info, source, dest);
3258 }
3259 factors.append (A);
3261 swapLevel2, x);
3262 if (!extension)
3264 delete [] Aeval2;
3265 return factors;
3266 }
3267
3269 {
3270 bool zeroOccured= false;
3271 for (CFListIterator iter= evaluation; iter.hasItem(); iter++)
3272 {
3273 if (iter.getItem().isZero())
3274 {
3275 zeroOccured= true;
3276 break;
3277 }
3278 }
3279 if (!zeroOccured)
3280 {
3283 if (factors.length() == biFactors.length())
3284 {
3285 if (extension)
3287
3289 swapLevel2, x);
3290 if (!extension)
3292 delete [] Aeval2;
3293 return factors;
3294 }
3295 else
3296 factors= CFList();
3297 //TODO case where factors.length() > 0
3298 }
3299 }
3300
3301 CFList * oldAeval= new CFList [lengthAeval2]; //TODO use bufAeval2 for this
3302 for (int i= 0; i < lengthAeval2; i++)
3303 oldAeval[i]= Aeval2[i];
3304
3306
3308 for (CFListIterator i= biFactors; i.hasItem(); i++)
3309 biFactorsLCs.append (LC (i.getItem(), 1));
3310
3311 Variable v;
3315
3316 if (v.level() != 1)
3318 uniFactors, v);
3319
3322
3324 bool LCmultiplierIsConst= LCmultiplier.inCoeffDomain();
3326
3329
3330 //prepare leading coefficients
3334
3338 bufA= A;
3341 {
3342 testVars= Variable (2);
3343 for (int i= 0; i < lengthAeval2; i++)
3344 {
3345 if (!oldAeval[i].isEmpty())
3346 testVars *= oldAeval[i].getFirst().mvar();
3347 }
3348 }
3350 "time to precompute LC over Fq: ");
3351
3354 bool LCheuristic= false;
3356 factors))
3357 {
3358 int check= biFactors.length();
3359 int * index= new int [factors.length()];
3362
3363 if (check == factors.length())
3364 {
3365 if (extension)
3367
3368 if (v.level() != 1)
3369 {
3370 for (iter= factors; iter.hasItem(); iter++)
3371 iter.getItem()= swapvar (iter.getItem(), v, y);
3372 }
3373
3375 swapLevel2, x);
3376 if (!extension)
3378 delete [] index;
3379 delete [] Aeval2;
3381 "time for successful LucksWang over Fq: ");
3382 return factors;
3383 }
3384 else if (factors.length() > 0)
3385 {
3386 int oneCount= 0;
3387 CFList l;
3388 for (int i= 0; i < check; i++)
3389 {
3390 if (index[i] == 1)
3391 {
3393 for (int j=1; j <= i-oneCount; j++)
3394 iter++;
3395 iter.remove (1);
3396 for (int j= 0; j < lengthAeval2; j++)
3397 {
3398 l= leadingCoeffs2[j];
3399 iter= l;
3400 for (int k=1; k <= i-oneCount; k++)
3401 iter++;
3402 iter.remove (1);
3404 }
3405 oneCount++;
3406 }
3407 }
3409 factors= CFList();
3410 }
3411 else if (!LCmultiplierIsConst && factors.length() == 0)
3412 {
3413 LCheuristic= true;
3416 bool foundTrueMultiplier= false;
3420 {
3421 A= oldA;
3423 for (int i= lengthAeval2-1; i > -1; i--)
3427 }
3428 else
3429 {
3430 bool foundMultiplier= false;
3433
3434 // coming from above: divide out more LCmultiplier if possible
3435 if (foundMultiplier)
3436 {
3437 foundMultiplier= false;
3441 }
3442 else
3443 {
3447 {
3450 }
3451 }
3452
3453 // patch everything together again
3455 for (int i= lengthAeval2-1; i > -1; i--)
3459 }
3460 factors= CFList();
3462 {
3463 LCheuristic= false;
3464 A= bufA;
3468 }
3469 }
3470 else
3471 factors= CFList();
3472 delete [] index;
3473 }
3474 TIMING_END_AND_PRINT (fac_fq_luckswang, "time for LucksWang over Fq: ");
3475
3479 {
3480 LCheuristic= true;
3483
3485 for (int i= lengthAeval2-1; i > -1; i--)
3489
3491 {
3492 LCheuristic= false;
3493 A= bufA;
3497 }
3498 }
3499 TIMING_END_AND_PRINT (fac_fq_lcheuristic, "time for Lc heuristic over Fq: ");
3500
3504
3505 for (iter= biFactors; iter.hasItem(); iter++)
3506 iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
3507
3508 for (int i= 0; i < lengthAeval2-1; i++)
3510 for (iter= leadingCoeffs2[lengthAeval2-1]; iter.hasItem(); iter++)
3511 {
3512 iter.getItem()= shift2Zero (iter.getItem(), list, evaluation);
3513 for (int i= A.level() - 4; i > -1; i--)
3514 {
3515 if (i + 1 == lengthAeval2-1)
3516 leadingCoeffs2[i].append (iter.getItem() (0, i + 4));
3517 else
3518 leadingCoeffs2[i].append (leadingCoeffs2[i+1].getLast() (0, i + 4));
3519 }
3520 }
3522 "time to shift evaluation point to zero: ");
3523
3524 CFArray Pi;
3526 int* liftBounds= new int [A.level() - 1];
3527 int liftBoundsLength= A.level() - 1;
3528 for (int i= 0; i < liftBoundsLength; i++)
3529 liftBounds [i]= degree (A, i + 2) + 1;
3530
3532 bool noOneToOne= false;
3537 "time for non monic hensel lifting over Fq: ");
3538
3539 if (!noOneToOne)
3540 {
3541 int check= factors.length();
3542 A= oldA;
3546 "time to recover factors over Fq: ");
3547 if (check != factors.length())
3548 noOneToOne= true;
3549 else
3551
3552 if (extension && !noOneToOne)
3554 }
3555 if (noOneToOne)
3556 {
3558 {
3559 A= bufA;
3562 delete [] liftBounds;
3563 LCheuristic= false;
3564 goto tryAgainWithoutHeu;
3565 //something probably went wrong in the heuristic
3566 }
3567
3570 for (iter= biFactors; iter.hasItem(); iter++)
3571 iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
3575 lift= degree (i.getItem(), 2) + degree (LC (i.getItem(), 1)) + 1;
3576 i++;
3577
3578 for (; i.hasItem(); i++)
3579 lift= tmax (lift,
3580 degree (i.getItem(), 2) + degree (LC (i.getItem(), 1)) + 1);
3581
3582 lift= tmax (degree (Aeval.getFirst() , 2) + 1, lift);
3583
3584 i= biFactors;
3585 yToLift= power (y, lift);
3587 for (; i.hasItem(); i++)
3588 {
3589 LCA= LC (i.getItem(), 1);
3590 extgcd (LCA, yToLift, LCA, dummy);
3591 i.getItem()= mod (i.getItem()*LCA, yToLift);
3592 }
3593
3594 liftBoundsLength= F.level() - 1;
3596
3597 CFList MOD;
3598 bool earlySuccess;
3605 "time for hensel lifting over Fq: ");
3606
3607 if (!extension)
3608 {
3612 "time for factor recombination: ");
3613 }
3614 else
3615 {
3619 "time for factor recombination: ");
3620 }
3621
3622 if (earlySuccess)
3624 if (!extension)
3625 {
3626 for (CFListIterator i= factors; i.hasItem(); i++)
3627 {
3628 int kk= Aeval.getLast().level();
3629 for (CFListIterator j= evaluation; j.hasItem(); j++, kk--)
3630 {
3631 if (i.getItem().level() < kk)
3632 continue;
3633 i.getItem()= i.getItem() (Variable (kk) - j.getItem(), kk);
3634 }
3635 }
3636 }
3637 }
3638
3639 if (v.level() != 1)
3640 {
3641 for (CFListIterator iter= factors; iter.hasItem(); iter++)
3642 iter.getItem()= swapvar (iter.getItem(), v, y);
3643 }
3644
3647 decompress (factors, N);
3648 if (!extension)
3650
3651 delete[] liftBounds;
3652
3653 return factors;
3654}
3655#endif
3656
3657/// multivariate factorization over an extension of the initial field
3658#ifdef HAVE_NTL // multiFactorize
3659CFList
3661{
3662 CanonicalForm A= F;
3663
3664 Variable alpha= info.getAlpha();
3665 Variable beta= info.getBeta();
3666 int k= info.getGFDegree();
3667 char cGFName= info.getGFName();
3668 CanonicalForm delta= info.getDelta();
3670 Variable w= Variable (1);
3671
3673 if (!GF && alpha == w) // we are in F_p
3674 {
3676 bool extension= true;
3677 int p= getCharacteristic();
3678 if (p < 7)
3679 {
3680 if (p == 2)
3682 else if (p == 3)
3684 else if (p == 5)
3687 A= A.mapinto();
3689
3693 for (CFListIterator j= factors; j.hasItem(); j++)
3694 j.getItem()= GF2FalphaRep (j.getItem(), vBuf);
3695 prune (vBuf);
3696 }
3697 else if (p >= 7 && p*p < (1<<16)) // pass to GF if possible
3698 {
3701 A= A.mapinto();
3703
3707 for (CFListIterator j= factors; j.hasItem(); j++)
3708 j.getItem()= GF2FalphaRep (j.getItem(), vBuf);
3709 prune (vBuf);
3710 }
3711 else // not able to pass to GF, pass to F_p(\alpha)
3712 {
3714 Variable v= rootOf (mipo);
3717 prune (v);
3718 }
3719 return factors;
3720 }
3721 else if (!GF && (alpha != w)) // we are in F_p(\alpha)
3722 {
3723 if (k == 1) // need factorization over F_p
3724 {
3725 int extDeg= degree (getMipo (alpha));
3726 extDeg++;
3728 Variable v= rootOf (mipo);
3731 prune (v);
3732 }
3733 else
3734 {
3735 if (beta == w)
3736 {
3739 bool primFail= false;
3740 Variable vBuf;
3742 ASSERT (!primFail, "failure in integer factorizer");
3743 if (primFail)
3744 ; //ERROR
3745 else
3747
3748 CFList source, dest;
3750 source, dest);
3753 prune (v);
3754 }
3755 else
3756 {
3759 bool primFail= false;
3760 Variable vBuf;
3761 ASSERT (!primFail, "failure in integer factorizer");
3762 if (primFail)
3763 ; //ERROR
3764 else
3765 imPrimElem= mapPrimElem (delta, beta, v);
3766
3767 CFList source, dest;
3769 source= CFList();
3770 dest= CFList();
3771 bufA= mapUp (bufA, beta, v, delta, imPrimElem, source, dest);
3774 prune (v);
3775 }
3776 }
3777 return factors;
3778 }
3779 else // we are in GF (p^k)
3780 {
3781 int p= getCharacteristic();
3783 bool extension= true;
3784 if (k == 1) // need factorization over F_p
3785 {
3786 extensionDeg++;
3787 if (pow ((double) p, (double) extensionDeg) < (1<<16))
3788 // pass to GF(p^k+1)
3789 {
3793 A= GF2FalphaRep (A, vBuf);
3796 factors= multiFactorize (A.mapinto(), info);
3797 prune (vBuf);
3798 }
3799 else // not able to pass to another GF, pass to F_p(\alpha)
3800 {
3804 A= GF2FalphaRep (A, vBuf);
3808 prune (vBuf);
3809 }
3810 }
3811 else // need factorization over GF (p^k)
3812 {
3813 if (pow ((double) p, (double) 2*extensionDeg) < (1<<16))
3814 // pass to GF(p^2k)
3815 {
3820 }
3821 else // not able to pass to GF (p^2k), pass to F_p (\alpha)
3822 {
3826 A= GF2FalphaRep (A, v1);
3829 bool primFail= false;
3830 Variable vBuf;
3832 if (primFail)
3833 ; //ERROR
3834 else
3836 CFList source, dest;
3838 source, dest);
3842 for (CFListIterator i= factors; i.hasItem(); i++)
3843 i.getItem()= Falpha2GFRep (i.getItem());
3844 prune (v1);
3845 }
3846 }
3847 return factors;
3848 }
3849}
3850#endif
3851#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:4082
static Variable chooseExtension(const Variable &alpha)
Definition cfModGcd.cc:420
int p
Definition cfModGcd.cc:4078
g
Definition cfModGcd.cc:4090
CanonicalForm test
Definition cfModGcd.cc:4096
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
static int gettype()
Definition cf_factory.h:28
class to iterate through CanonicalForm's
Definition cf_iter.h:44
class CFMap
Definition cf_map.h:85
factory's main class
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
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
generate random elements in GF
Definition cf_random.h:32
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:75
CFList tmp2
Definition facFqBivar.cc:74
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:75
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:3084
CanonicalForm prodMod(const CFList &L, const CanonicalForm &M)
product of all elements in L modulo M via divide-and-conquer.
Definition facMul.cc:3184
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:59
int status int void * buf
Definition si_signals.h:59
#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)