My Project
Loading...
Searching...
No Matches
facFqBivar.cc
Go to the documentation of this file.
1/*****************************************************************************\
2 * Computer Algebra System SINGULAR
3\*****************************************************************************/
4/** @file facFqBivar.cc
5 *
6 * This file provides functions for factorizing a bivariate polynomial over
7 * \f$ F_{p} \f$ , \f$ F_{p}(\alpha ) \f$ or GF, based on "Modern Computer
8 * Algebra, Chapter 15" by J. von zur Gathen & J. Gerhard and "Factoring
9 * multivariate polynomials over a finite field" by L. Bernardin.
10 * Factor Recombination is described in "Factoring polynomials over global
11 * fields" by K. Belabas, M. van Hoeij, J. Klueners, A. Steel
12 *
13 *
14 * @author Martin Lee
15 *
16 **/
17/*****************************************************************************/
18
19
20#include "config.h"
21
22#include <math.h>
23
24#include "cf_assert.h"
25#include "cf_util.h"
26#include "debug.h"
27#include "timing.h"
28
29#include "canonicalform.h"
30#include "cf_defs.h"
31#include "cf_map_ext.h"
32#include "cf_random.h"
33#include "facHensel.h"
34#include "facMul.h"
35#include "cf_map.h"
36#include "cf_irred.h"
37#include "facFqBivarUtil.h"
38#include "facFqBivar.h"
39#include "cfNewtonPolygon.h"
40
41#ifdef HAVE_NTL
42#include "NTLconvert.h"
43#endif
44
45#ifdef HAVE_FLINT
46#include "FLINTconvert.h"
47#include "flint/nmod_poly_factor.h"
48#include "flint/fq_nmod_poly_factor.h"
49#endif
50
62
64{
65 if (L.isEmpty())
66 return 1;
67 else if (L.length() == 1)
68 return mod (L.getFirst()(0, 1) , M);
69 else if (L.length() == 2)
70 return mod (mulNTL (L.getFirst()(0, 1),L.getLast()(0, 1), b), M);
71 else
72 {
73 int l= L.length()/2;
77 for (int j= 1; j <= l; j++, i++)
78 tmp1.append (i.getItem());
79 tmp2= Difference (L, tmp1);
80 buf1= prodMod0 (tmp1, M, b);
81 buf2= prodMod0 (tmp2, M, b);
82 return mod (mulNTL (buf1,buf2, b), M);
83 }
84}
85
86#if defined(HAVE_NTL) || defined(HAVE_FLINT)
88 const Variable& alpha, CFList& list, const bool& GF,
89 bool& fail)
90{
91 fail= false;
97 double bound;
98 int p= getCharacteristic ();
99 if (alpha.level() != 1)
100 {
101 mipo= getMipo (alpha);
102 int d= degree (mipo);
103 bound= pow ((double) p, (double) d);
104 }
105 else if (GF)
106 {
107 int d= getGFDegree();
108 bound= ipower (p, d);
109 }
110 else
111 bound= p;
112
113 random= 0;
114 do
115 {
116 if (list.length() >= bound)
117 {
118 fail= true;
119 break;
120 }
121 if (list.isEmpty())
122 random= 0;
123 else if (GF)
124 {
125 if (list.length() == 1)
127 else
128 random= genGF.generate();
129 }
130 else if (list.length() < p || alpha.level() == 1)
131 random= genFF.generate();
132 else if (alpha != x && list.length() >= p)
133 {
134 if (list.length() == p)
135 random= alpha;
136 else
137 {
139 random= genAlgExt.generate();
140 }
141 }
142 if (find (list, random)) continue;
143 eval= F (random, x);
144 if (degree (eval) != degree (F, y))
145 { //leading coeff vanishes
146 if (!find (list, random))
147 list.append (random);
148 continue;
149 }
150 if (degree (gcd (deriv (eval, eval.mvar()), eval), eval.mvar()) > 0)
151 { //evaluated polynomial is not squarefree
152 if (!find (list, random))
153 list.append (random);
154 continue;
155 }
156 } while (find (list, random));
157
158 return random;
159}
160
161#if defined(HAVE_NTL) || defined(HAVE_FLINT)
162CFList
163uniFactorizer (const CanonicalForm& A, const Variable& alpha, const bool& GF)
164{
165 Variable x= A.mvar();
166 if (A.inCoeffDomain())
167 return CFList();
168 ASSERT (A.isUnivariate(),
169 "univariate polynomial expected or constant expected");
171 if (GF)
172 {
173 int k= getGFDegree();
174 char cGFName= gf_name;
179#ifdef HAVE_NTL
180 if (getCharacteristic() > 2)
181#else
182 if (getCharacteristic() > 0)
183#endif
184 {
185#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
190
193
195
198
201
203
205 beta, fq_con);
206
212#else
214 {
216 zz_p::init (getCharacteristic());
217 }
219 zz_pE::init (NTLMipo);
221 MakeMonic (NTLA);
223 zz_pE multi= to_zz_pE (1);
225 x, beta);
226#endif
227 }
228#ifdef HAVE_NTL
229 else
230 {
232 GF2E::init (NTLMipo);
234 MakeMonic (NTLA);
236 GF2E multi= to_GF2E (1);
238 x, beta);
239 }
240#endif
242 for (CFFListIterator i= factorsA; i.hasItem(); i++)
243 {
244 buf= i.getItem().factor();
246 i.getItem()= CFFactor (buf, i.getItem().exp());
247 }
248 prune (beta);
249 }
250 else if (alpha.level() != 1)
251 {
252#ifdef HAVE_NTL
253 if (getCharacteristic() > 2)
254#else
255 if (getCharacteristic() > 0)
256#endif
257 {
258#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
263
266
268
271
274
276
278 alpha, fq_con);
279
285#else
287 {
289 zz_p::init (getCharacteristic());
290 }
292 zz_pE::init (NTLMipo);
294 MakeMonic (NTLA);
296 zz_pE multi= to_zz_pE (1);
298 x, alpha);
299#endif
300 }
301#ifdef HAVE_NTL
302 else
303 {
305 GF2E::init (NTLMipo);
307 MakeMonic (NTLA);
309 GF2E multi= to_GF2E (1);
311 x, alpha);
312 }
313#endif
314 }
315 else
316 {
317#ifdef HAVE_FLINT
318#ifdef HAVE_NTL
319 if (degree (A) < 300)
320#endif
321 {
328 if (factorsA.getFirst().factor().inCoeffDomain())
332 }
333#ifdef HAVE_NTL
334 else
335#endif
336#endif /* HAVE_FLINT */
337#ifdef HAVE_NTL
338 if (getCharacteristic() > 2)
339 {
341 {
343 zz_p::init (getCharacteristic());
344 }
346 MakeMonic (NTLA);
348 zz_p multi= to_zz_p (1);
350 x);
351 }
352 else
353 {
356 GF2 multi= to_GF2 (1);
358 x);
359 }
360#endif
361 }
363 for (CFFListIterator i= factorsA; i.hasItem(); i++)
364 uniFactors.append (i.getItem().factor());
365 return uniFactors;
366}
367#endif
368
369#if defined(HAVE_NTL) || defined(HAVE_FLINT)
370/// naive factor recombination as decribed in "Factoring
371/// multivariate polynomials over a finite field" by L Bernardin.
372CFList
374 const CanonicalForm& N, const ExtensionInfo& info,
375 DegreePattern& degs, const CanonicalForm& eval, int s,
376 int thres)
377{
378 if (factors.length() == 0)
379 {
380 F= 1;
381 return CFList();
382 }
383 if (F.inCoeffDomain())
384 return CFList();
385
386 Variable alpha= info.getAlpha();
387 Variable beta= info.getBeta();
388 CanonicalForm gamma= info.getGamma();
389 CanonicalForm delta= info.getDelta();
390 int k= info.getGFDegree();
391
393 int l= degree (N);
394 Variable y= F.mvar();
395 Variable x= Variable (1);
396 CFList source, dest;
397 if (degs.getLength() <= 1 || factors.length() == 1)
398 {
399 CFList result= CFList(mapDown (F(y-eval, y), info, source, dest));
400 F= 1;
401 return result;
402 }
403
404 DEBOUTLN (cerr, "LC (F, 1)*prodMod (factors, M) == F " <<
405 (mod (LC (F, 1)*prodMod (factors, M), M)/Lc (mod (LC (F, 1)*prodMod (factors, M), M)) == F/Lc (F)));
406 int degMipoBeta= 1;
407 if (!k && beta.level() != 1)
409
410 CFList T, S, Diff;
411 T= factors;
412
415
416 buf= F;
417
419 int * v= new int [T.length()];
420 for (int i= 0; i < T.length(); i++)
421 v[i]= 0;
422
423 CFArray TT;
425 bufDegs1= degs;
426 int subsetDeg;
427 TT= copy (factors);
428 bool nosubset= false;
429 bool recombination= false;
430 bool trueFactor= false;
433 while (T.length() >= 2*s && s <= thres)
434 {
435 while (nosubset == false)
436 {
437 if (T.length() == s)
438 {
439 delete [] v;
440 if (recombination)
441 {
442 T.insert (LCBuf);
443 g= prodMod (T, M);
444 T.removeFirst();
445 g /= content(g);
446 g= g (y - eval, y);
447 g /= Lc (g);
449 F= 1;
450 return result;
451 }
452 else
453 {
454 appendMapDown (result, F (y - eval, y), info, source, dest);
455 F= 1;
456 return result;
457 }
458 }
459 S= subset (v, s, TT, nosubset);
460 if (nosubset) break;
462 // skip those combinations that are not possible
463 if (!degs.find (subsetDeg))
464 continue;
465 else
466 {
467 test= prodMod0 (S, M);
468 test *= LCBuf;
469 test = mod (test, M);
470 if (fdivides (test, buf0))
471 {
472 S.insert (LCBuf);
473 g= prodMod (S, M);
474 S.removeFirst();
475 g /= content (g, x);
476 if (fdivides (g, buf, quot))
477 {
478 buf2= g (y - eval, y);
479 buf2 /= Lc (buf2);
480
481 if (!k && beta.level() == 1)
482 {
483 if (degree (buf2, alpha) < degMipoBeta)
484 {
485 buf= quot;
486 LCBuf= LC (buf, x);
487 recombination= true;
489 trueFactor= true;
490 }
491 }
492 else
493 {
494 if (!isInExtension (buf2, gamma, k, delta, source, dest))
495 {
496 buf= quot;
497 LCBuf= LC (buf, x);
498 recombination= true;
500 trueFactor= true;
501 }
502 }
503 if (trueFactor)
504 {
505 T= Difference (T, S);
506 l -= degree (g);
507 M= power (y, l);
508 buf0= buf (0, x)*LCBuf;
509
510 // compute new possible degree pattern
512 bufDegs1.intersect (bufDegs2);
513 bufDegs1.refine ();
514 if (T.length() < 2*s || T.length() == s ||
515 bufDegs1.getLength() == 1)
516 {
517 delete [] v;
518 if (recombination)
519 {
520 buf= buf (y-eval,y);
521 buf /= Lc (buf);
523 dest);
524 F= 1;
525 return result;
526 }
527 else
528 {
529 appendMapDown (result, F (y - eval, y), info, source, dest);
530 F= 1;
531 return result;
532 }
533 }
534 trueFactor= false;
535 TT= copy (T);
536 indexUpdate (v, s, T.length(), nosubset);
537 if (nosubset) break;
538 }
539 }
540 }
541 }
542 }
543 s++;
544 if (T.length() < 2*s || T.length() == s)
545 {
546 delete [] v;
547 if (recombination)
548 {
549 buf= buf (y-eval,y);
550 buf /= Lc (buf);
552 F= 1;
553 return result;
554 }
555 else
556 {
557 appendMapDown (result, F (y - eval, y), info, source, dest);
558 F= 1;
559 return result;
560 }
561 }
562 for (int i= 0; i < T.length(); i++)
563 v[i]= 0;
564 nosubset= false;
565 }
566 if (T.length() < 2*s)
567 {
568 appendMapDown (result, F (y - eval, y), info, source, dest);
569 F= 1;
570 delete [] v;
571 return result;
572 }
573
574 if (s > thres)
575 {
576 factors= T;
577 F= buf;
578 degs= bufDegs1;
579 }
580
581 delete [] v;
582 return result;
583}
584#endif
585
586/// naive factor recombination as decribed in "Factoring
587/// multivariate polynomials over a finite field" by L Bernardin.
588CFList
590 const CanonicalForm& N, DegreePattern& degs, const
591 CanonicalForm& eval, int s, int thres, const modpk& b,
592 const CanonicalForm& den
593 )
594{
595 if (factors.length() == 0)
596 {
597 F= 1;
598 return CFList ();
599 }
600 if (F.inCoeffDomain())
601 return CFList();
602 Variable y= Variable (2);
603 if (degs.getLength() <= 1 || factors.length() == 1)
604 {
605 CFList result= CFList (F(y-eval,y));
606 F= 1;
607 return result;
608 }
609#ifdef DEBUGOUTPUT
610 if (b.getp() == 0)
611 DEBOUTLN (cerr, "LC (F, 1)*prodMod (factors, N) == F " <<
612 (mod (LC (F, 1)*prodMod (factors, N),N)/Lc (mod (LC (F, 1)*prodMod (factors, N),N)) == F/Lc(F)));
613 else
614 DEBOUTLN (cerr, "LC (F, 1)*prodMod (factors, N) == F " <<
615 (mod (b(LC (F, 1)*prodMod (factors, N)),N)/Lc (mod (b(LC (F, 1)*prodMod (factors, N)),N)) == F/Lc(F)));
616#endif
617
618 CFList T, S;
619
621 int l= degree (N);
622 T= factors;
624 Variable x= Variable (1);
627 CanonicalForm g, quot, buf= F;
628 int * v= new int [T.length()];
629 for (int i= 0; i < T.length(); i++)
630 v[i]= 0;
631 bool nosubset= false;
632 CFArray TT;
634 bufDegs1= degs;
635 int subsetDeg;
636 TT= copy (factors);
637 bool recombination= false;
639 bool isRat= (isOn (SW_RATIONAL) && getCharacteristic() == 0) ||
640 getCharacteristic() > 0;
641 if (!isRat)
642 On (SW_RATIONAL);
644 if (!isRat)
646 while (T.length() >= 2*s && s <= thres)
647 {
648 while (nosubset == false)
649 {
650 if (T.length() == s)
651 {
652 delete [] v;
653 if (recombination)
654 {
655 T.insert (LCBuf);
656 g= prodMod (T, M);
657 if (b.getp() != 0)
658 g= b(g);
659 T.removeFirst();
660 g /= content (g,x);
661 result.append (g(y-eval,y));
662 F= 1;
663 return result;
664 }
665 else
666 {
667 result= CFList (F(y-eval,y));
668 F= 1;
669 return result;
670 }
671 }
672 S= subset (v, s, TT, nosubset);
673 if (nosubset) break;
675 // skip those combinations that are not possible
676 if (!degs.find (subsetDeg))
677 continue;
678 else
679 {
680 if (!isRat)
681 On (SW_RATIONAL);
682 test= prodMod0 (S, M);
683 if (!isRat)
684 {
685 test *= bCommonDen (test);
687 }
688 test= mulNTL (test, LCBuf, b);
689 test= mod (test, M);
690 if (uniFdivides (test, buf0))
691 {
692 if (!isRat)
693 On (SW_RATIONAL);
694 S.insert (LCBuf);
695 g= prodMod (S, M);
696 S.removeFirst();
697 if (!isRat)
698 {
699 g *= bCommonDen(g);
701 }
702 if (b.getp() != 0)
703 g= b(g);
704 if (!isRat)
705 On (SW_RATIONAL);
706 g /= content (g, x);
707 if (!isRat)
708 {
709 On (SW_RATIONAL);
710 if (!Lc (g).inBaseDomain())
711 g /= Lc (g);
712 g *= bCommonDen (g);
714 g /= icontent (g);
715 On (SW_RATIONAL);
716 }
717 if (fdivides (g, buf, quot))
718 {
719 denom *= abs (lc (g));
720 recombination= true;
721 result.append (g (y-eval,y));
722 if (b.getp() != 0)
723 {
727 denom /= gcd (denom, denQuot);
728 On (SW_RATIONAL);
729 }
730 else
731 buf= quot;
732 LCBuf= LC (buf, x)*denom;
733 T= Difference (T, S);
734 l -= degree (g);
735 M= power (y, l);
736 buf0= mulNTL (buf (0, x), LCBuf);
737 if (!isRat)
739 // compute new possible degree pattern
741 bufDegs1.intersect (bufDegs2);
742 bufDegs1.refine ();
743 if (T.length() < 2*s || T.length() == s ||
744 bufDegs1.getLength() == 1)
745 {
746 delete [] v;
747 if (recombination)
748 {
749 result.append (buf (y-eval,y));
750 F= 1;
751 return result;
752 }
753 else
754 {
755 result= CFList (F (y-eval,y));
756 F= 1;
757 return result;
758 }
759 }
760 TT= copy (T);
761 indexUpdate (v, s, T.length(), nosubset);
762 if (nosubset) break;
763 }
764 if (!isRat)
766 }
767 }
768 }
769 s++;
770 if (T.length() < 2*s || T.length() == s)
771 {
772 delete [] v;
773 if (recombination)
774 {
775 result.append (buf(y-eval,y));
776 F= 1;
777 return result;
778 }
779 else
780 {
781 result= CFList (F(y-eval,y));
782 F= 1;
783 return result;
784 }
785 }
786 for (int i= 0; i < T.length(); i++)
787 v[i]= 0;
788 nosubset= false;
789 }
790 delete [] v;
791 if (T.length() < 2*s)
792 {
793 result.append (F(y-eval,y));
794 F= 1;
795 return result;
796 }
797
798 if (s > thres)
799 {
800 factors= T;
801 F= buf;
802 degs= bufDegs1;
803 }
804
805 return result;
806}
807
808#if defined(HAVE_NTL) || defined(HAVE_FLINT)
810{
811 int i=1, m= 2;
812 // extension of F_p needed
813 if (alpha.level() == 1 && beta.level() == 1 && k == 1)
814 {
815 i= 1;
816 m= 2;
817 } //extension of F_p(alpha) needed but want to factorize over F_p
818 else if (alpha.level() != 1 && beta.level() == 1 && k == 1)
819 {
820 i= 1;
821 m= degree (getMipo (alpha)) + 1;
822 } //extension of F_p(alpha) needed for first time
823 else if (alpha.level() != 1 && beta.level() == 1 && k != 1)
824 {
825 i= 2;
826 m= degree (getMipo (alpha));
827 }
828 else if (alpha.level() != 1 && beta.level() != 1 && k != 1)
829 {
830 m= degree (getMipo (beta));
831 i= degree (getMipo (alpha))/m + 1;
832 }
833 #if defined(HAVE_FLINT)
838 #elif defined(HAVE_NTL)
840 {
842 zz_p::init (getCharacteristic());
843 }
847 #else
848 factoryError("NTL/FLINT missing: chooseExtension");
849 #endif
850 return rootOf (newMipo);
851}
852#endif
853
854void
857 DegreePattern& degs, bool& success, int deg, const
859{
864 Variable x= Variable (1);
865 Variable y= Variable (2);
867 CanonicalForm M= power (F.mvar(), deg);
869 int d= degree (F), l= 0;
870 bool isRat= (isOn (SW_RATIONAL) && getCharacteristic() == 0) ||
871 getCharacteristic() > 0;
872 if (!isRat)
873 On (SW_RATIONAL);
874 if (b.getp() != 0)
875 buf *= bCommonDen (buf);
879 if (!isRat)
883
884 for (CFListIterator i= factors; i.hasItem(); i++, l++)
885 {
886 if (!bufDegs1.find (degree (i.getItem(), 1)) || factorsFoundIndex[l] == 1)
887 continue;
888 else
889 {
890 test1= mod (mulNTL (i.getItem() (1,x), LCBuf, b), M);
891 if (uniFdivides (test1, buf1))
892 {
893 test0= mod (mulNTL (i.getItem() (0,x), LCBuf, b), M);
894 if (uniFdivides (test0, buf0))
895 {
896 if (!isRat)
897 On (SW_RATIONAL);
898 g= mulMod2 (i.getItem(), LCBuf, M);
899 if (!isRat)
900 {
901 g *= bCommonDen(g);
903 }
904 if (b.getp() != 0)
905 g= b(g);
906 if (!isRat)
907 On (SW_RATIONAL);
908 g /= content (g, x);
909 if (!isRat)
910 {
911 On (SW_RATIONAL);
912 if (!Lc (g).inBaseDomain())
913 g /= Lc (g);
914 g *= bCommonDen (g);
916 g /= icontent (g);
917 On (SW_RATIONAL);
918 }
919 if (fdivides (g, buf, quot))
920 {
921 den *= abs (lc (g));
924 if (b.getp() != 0)
925 {
929 den /= gcd (den, denQuot);
930 On (SW_RATIONAL);
931 }
932 else
933 buf= quot;
934 d -= degree (g);
935 LCBuf= LC (buf, x)*den;
936 buf0= mulNTL (buf (0,x), LCBuf);
937 buf1= mulNTL (buf (1,x), LCBuf);
938 if (!isRat)
940 T= Difference (T, CFList (i.getItem()));
941 F= buf;
942
943 // compute new possible degree pattern
945 bufDegs1.intersect (bufDegs2);
946 bufDegs1.refine ();
947 if (bufDegs1.getLength() <= 1)
948 {
949 if (!buf.inCoeffDomain())
950 {
952 F= 1;
953 }
954 break;
955 }
956 }
957 if (!isRat)
959 }
960 }
961 }
962 }
963 adaptedLiftBound= d + 1;
964 if (adaptedLiftBound < deg)
965 {
966 degs= bufDegs1;
967 success= true;
968 }
969 if (bufDegs1.getLength() <= 1)
970 degs= bufDegs1;
971}
972
973void
983
984void
987 DegreePattern& degs, bool& success, const
988 ExtensionInfo& info, const CanonicalForm& eval, int deg
989 )
990{
991 Variable alpha= info.getAlpha();
992 Variable beta= info.getBeta();
993 CanonicalForm gamma= info.getGamma();
994 CanonicalForm delta= info.getDelta();
995 int k= info.getGFDegree();
999 Variable y= F.mvar();
1000 Variable x= Variable (1);
1001 CanonicalForm buf= F, LCBuf= LC (buf, x), g, buf2;
1002 CanonicalForm M= power (y, deg);
1004 bool trueFactor= false;
1005 int d= degree (F), l= 0;
1006 CFList source, dest;
1007 int degMipoBeta= 1;
1008 if (!k && beta.level() != 1)
1011 for (CFListIterator i= factors; i.hasItem(); i++, l++)
1012 {
1013 if (!bufDegs1.find (degree (i.getItem(), 1)) || factorsFoundIndex[l] == 1)
1014 continue;
1015 else
1016 {
1017 g= mulMod2 (i.getItem(), LCBuf, M);
1018 g /= content (g, x);
1019 if (fdivides (g, buf, quot))
1020 {
1021 buf2= g (y - eval, y);
1022 buf2 /= Lc (buf2);
1023
1024 if (!k && beta == x)
1025 {
1026 if (degree (buf2, alpha) < degMipoBeta)
1027 {
1029 factorsFoundIndex[l]= 1;
1030 buf= quot;
1031 d -= degree (g);
1032 LCBuf= LC (buf, x);
1033 trueFactor= true;
1034 }
1035 }
1036 else
1037 {
1038 if (!isInExtension (buf2, gamma, k, delta, source, dest))
1039 {
1041 factorsFoundIndex[l]= 1;
1042 buf= quot;
1043 d -= degree (g);
1044 LCBuf= LC (buf, x);
1045 trueFactor= true;
1046 }
1047 }
1048 if (trueFactor)
1049 {
1050 T= Difference (T, CFList (i.getItem()));
1051 F= buf;
1052
1053 // compute new possible degree pattern
1055 bufDegs1.intersect (bufDegs2);
1056 bufDegs1.refine ();
1057 trueFactor= false;
1058 if (bufDegs1.getLength() <= 1)
1059 {
1060 if (!buf.inCoeffDomain())
1061 {
1062 buf= buf (y - eval, y);
1063 buf /= Lc (buf);
1065 F= 1;
1066 }
1067 break;
1068 }
1069 }
1070 }
1071 }
1072 }
1073 adaptedLiftBound= d + 1;
1074 if (adaptedLiftBound < deg)
1075 {
1076 degs= bufDegs1;
1077 success= true;
1078 }
1079 if (bufDegs1.getLength() <= 1)
1080 degs= bufDegs1;
1081}
1082
1083int*
1085 int degreeLC)
1086{
1087 Variable x= Variable (1);
1088 int p= getCharacteristic();
1089 int d= getGFDegree();
1090 char cGFName= gf_name;
1092 CanonicalForm buf= 1;
1093 for (int i= 0; i < sizeOfRightSide; i++)
1094 buf *= (power (x, rightSide [i]) + 1);
1095
1096 int j= 0;
1097 for (CFIterator i= buf; i.hasTerms(); i++, j++)
1098 {
1099 if (i.exp() < degreeLC)
1100 {
1101 j++;
1102 break;
1103 }
1104 }
1105
1106 ASSERT ( j > 1, "j > 1 expected" );
1107
1108 int* result = new int [j - 1];
1109 sizeOfOutput= j - 1;
1110
1111 int i= 0;
1112 for (CFIterator m = buf; i < j - 1; i++, m++)
1113 result [i]= m.exp();
1114
1115 if (d > 1)
1117 else
1119 return result;
1120}
1121
1122int *
1124{
1125 int sizeOfNewtonPoly;
1127 int sizeOfRightSide;
1130 degreeLC);
1131 delete [] rightSide;
1132 for (int i= 0; i < sizeOfNewtonPoly; i++)
1133 delete [] newtonPolyg[i];
1134 delete [] newtonPolyg;
1135 return result;
1136}
1137
1138void
1140{
1141 CFList result;
1142 int i= 0;
1143 for (CFListIterator iter= factors; iter.hasItem(); iter++, i++)
1144 {
1145 if (factorsFoundIndex[i] == 1)
1146 continue;
1147 else
1148 result.append (iter.getItem());
1149 }
1150 factors= result;
1151}
1152
1153#if defined(HAVE_NTL) || defined(HAVE_FLINT) // henselLift12
1154CFList
1157 const CFList& uniFactors, const ExtensionInfo& info,
1159{
1160 Variable alpha= info.getAlpha();
1161 Variable beta= info.getBeta();
1162 CanonicalForm gamma= info.getGamma();
1163 CanonicalForm delta= info.getDelta();
1164 bool extension= info.isInExtension();
1165
1166 int sizeOfLiftPre;
1167 int * liftPre= getLiftPrecisions (A, sizeOfLiftPre, degree (LC (A, 1), 2));
1168
1169 Variable x= Variable (1);
1170 Variable y= Variable (2);
1171 CFArray Pi;
1174 On (SW_RATIONAL);
1176 if (!Lc (A).inBaseDomain())
1177 {
1178 bufA /= Lc (A);
1180 bufA *= denBufA;
1181 Off (SW_RATIONAL);
1182 den /= gcd (den, denBufA);
1183 }
1184 else
1185 {
1186 bufA= A;
1187 Off (SW_RATIONAL);
1188 den /= gcd (den, Lc (A));
1189 }
1191 bool mipoHasDen= false;
1192 if (getCharacteristic() == 0 && b.getp() != 0)
1193 {
1194 if (alpha.level() == 1)
1195 {
1196 lcA0= lc (A (0, 2));
1197 A *= b.inverse (lcA0);
1198 A= b (A);
1200 i.getItem()= b (i.getItem()*b.inverse (lc (i.getItem())));
1201 }
1202 else
1203 {
1204 lcA0= Lc (A (0,2));
1205 On (SW_RATIONAL);
1207 Off (SW_RATIONAL);
1208 CanonicalForm lcA0inverse= b.inverse (lcA0);
1209 A *= lcA0inverse;
1210 A= b (A);
1211 // Lc of bufUniFactors is in Z
1213 i.getItem()= b (i.getItem()*b.inverse (lc (i.getItem())));
1214 }
1215 }
1216 bufUniFactors.insert (LC (A, x));
1218 earlySuccess= false;
1219 int newLiftBound= 0;
1220
1221 int smallFactorDeg= tmin (11, liftPre [sizeOfLiftPre- 1] + 1);//this is a tunable parameter
1222 int dummy;
1223 int * factorsFoundIndex= new int [uniFactors.length()];
1224 for (int i= 0; i < uniFactors.length(); i++)
1225 factorsFoundIndex [i]= 0;
1226
1228 Variable v= alpha;
1229 if (smallFactorDeg >= liftBound || degree (A,y) <= 4)
1231 else if (sizeOfLiftPre > 1 && sizeOfLiftPre < 30)
1232 {
1234 if (mipoHasDen)
1235 {
1236 for (CFListIterator iter= bufUniFactors; iter.hasItem(); iter++)
1237 if (hasFirstAlgVar (iter.getItem(), v))
1238 break;
1239 if (v != alpha)
1240 {
1242 for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
1243 iter.getItem()= replacevar (iter.getItem(), v, alpha);
1244 A= replacevar (A, alpha, v);
1245 }
1246 }
1247
1248 if (!extension)
1249 {
1250 if (v==alpha)
1254 else
1258 }
1259 else
1263 if (degs.getLength() > 1 && !earlySuccess &&
1265 {
1267 {
1268 bufUniFactors.insert (LC (A, x));
1270 liftPre[sizeOfLiftPre-1] + 1, Pi, diophant, M, b);
1271 if (v!=alpha)
1272 {
1274 for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
1275 iter.getItem()= replacevar (iter.getItem(), v, alpha);
1276 }
1277 if (!extension)
1278 {
1279 if (v==alpha)
1282 liftPre[sizeOfLiftPre-1] + 1, eval, b, den);
1283 else
1286 liftPre[sizeOfLiftPre-1] + 1, eval, b, den);
1287 }
1288 else
1291 eval, liftPre[sizeOfLiftPre-1] + 1);
1292 }
1293 }
1294 else if (earlySuccess)
1296
1297 int i= sizeOfLiftPre - 1;
1298 while (degs.getLength() > 1 && !earlySuccess && i - 1 >= 0)
1299 {
1300 if (newLiftBound >= liftPre[i] + 1)
1301 {
1302 bufUniFactors.insert (LC (A, x));
1304 liftPre[i-1] + 1, Pi, diophant, M, b);
1305 if (v!=alpha)
1306 {
1308 for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
1309 iter.getItem()= replacevar (iter.getItem(), v, alpha);
1310 }
1311 if (!extension)
1312 {
1313 if (v==alpha)
1316 liftPre[i-1] + 1, eval, b, den);
1317 else
1320 liftPre[i-1] + 1, eval, b, den);
1321 }
1322 else
1325 eval, liftPre[i-1] + 1);
1326 }
1327 else
1328 {
1330 break;
1331 }
1332 i--;
1333 }
1334 if (earlySuccess)
1336 //after here all factors are lifted to liftPre[sizeOfLiftPre-1]
1337 }
1338 else
1339 {
1341 if (mipoHasDen)
1342 {
1343 for (CFListIterator iter= bufUniFactors; iter.hasItem(); iter++)
1344 if (hasFirstAlgVar (iter.getItem(), v))
1345 break;
1346 if (v != alpha)
1347 {
1349 for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
1350 iter.getItem()= replacevar (iter.getItem(), v, alpha);
1351 A= replacevar (A, alpha, v);
1352 }
1353 }
1354 if (!extension)
1355 {
1356 if (v==alpha)
1360 else
1364 }
1365 else
1369 int i= 1;
1370 while ((degree (A,y)/4)*i + 4 <= smallFactorDeg)
1371 i++;
1372 dummy= tmin (degree (A,y)+1, (degree (A,y)/4)*i+4);
1373 if (degs.getLength() > 1 && !earlySuccess && dummy > smallFactorDeg)
1374 {
1375 bufUniFactors.insert (LC (A, x));
1377 dummy, Pi, diophant, M, b);
1378 if (v!=alpha)
1379 {
1381 for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
1382 iter.getItem()= replacevar (iter.getItem(), v, alpha);
1383 }
1384 if (!extension)
1385 {
1386 if (v==alpha)
1389 b, den);
1390 else
1393 b, den);
1394 }
1395 else
1398 eval, dummy);
1399 }
1400 while (degs.getLength() > 1 && !earlySuccess && i < 4)
1401 {
1402 if (newLiftBound >= dummy)
1403 {
1404 bufUniFactors.insert (LC (A, x));
1405 dummy= tmin (degree (A,y)+1, (degree (A,y)/4)*(i+1)+4);
1407 dummy, Pi, diophant, M, b);
1408 if (v!=alpha)
1409 {
1411 for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
1412 iter.getItem()= replacevar (iter.getItem(), v, alpha);
1413 }
1414 if (!extension)
1415 {
1416 if (v==alpha)
1419 eval, b, den);
1420 else
1423 eval, b, den);
1424 }
1425 else
1428 eval, dummy);
1429 }
1430 else
1431 {
1433 break;
1434 }
1435 i++;
1436 }
1437 if (earlySuccess)
1439 }
1440
1441 A= bufA;
1442 if (earlyFactors.length() > 0 && degs.getLength() > 1)
1443 {
1444 liftBound= degree (A,y) + 1;
1445 earlySuccess= true;
1447 }
1448
1449 delete [] factorsFoundIndex;
1450 delete [] liftPre;
1451
1452 return bufUniFactors;
1453}
1454#endif
1455
1456#ifdef HAVE_NTL // henselLiftAndEarly
1457CFList
1468#endif
1469
1470#ifdef HAVE_NTL
1471long isReduced (const mat_zz_p& M)
1472{
1473 long i, j, nonZero;
1474 for (i = 1; i <= M.NumRows(); i++)
1475 {
1476 nonZero= 0;
1477 for (j = 1; j <= M.NumCols(); j++)
1478 {
1479 if (!IsZero (M (i,j)))
1480 nonZero++;
1481 }
1482 if (nonZero != 1)
1483 return 0;
1484 }
1485 return 1;
1486}
1487#endif
1488
1489#ifdef HAVE_FLINT
1491{
1492 long i, j, nonZero;
1493 for (i = 1; i <= nmod_mat_nrows(M); i++)
1494 {
1495 nonZero= 0;
1496 for (j = 1; j <= nmod_mat_ncols (M); j++)
1497 {
1498 if (!(nmod_mat_entry (M, i-1, j-1)==0))
1499 nonZero++;
1500 }
1501 if (nonZero != 1)
1502 return 0;
1503 }
1504 return 1;
1505}
1506#endif
1507
1508#ifdef HAVE_NTL
1509long isReduced (const mat_zz_pE& M)
1510{
1511 long i, j, nonZero;
1512 for (i = 1; i <= M.NumRows(); i++)
1513 {
1514 nonZero= 0;
1515 for (j = 1; j <= M.NumCols(); j++)
1516 {
1517 if (!IsZero (M (i,j)))
1518 nonZero++;
1519 }
1520 if (nonZero != 1)
1521 return 0;
1522 }
1523 return 1;
1524}
1525#endif
1526
1527#ifdef HAVE_NTL
1529{
1530 long i, j;
1531 bool nonZeroOne= false;
1532 int * result= new int [M.NumCols()];
1533 for (i = 1; i <= M.NumCols(); i++)
1534 {
1535 for (j = 1; j <= M.NumRows(); j++)
1536 {
1537 if (!(IsOne (M (j,i)) || IsZero (M (j,i))))
1538 {
1539 nonZeroOne= true;
1540 break;
1541 }
1542 }
1543 if (!nonZeroOne)
1544 result [i - 1]= 1;
1545 else
1546 result [i - 1]= 0;
1547 nonZeroOne= false;
1548 }
1549 return result;
1550}
1551#endif
1552
1553#ifdef HAVE_FLINT
1555{
1556 long i, j;
1557 bool nonZeroOne= false;
1558 int * result= new int [nmod_mat_ncols (M)];
1559 for (i = 0; i < nmod_mat_ncols (M); i++)
1560 {
1561 for (j = 0; j < nmod_mat_nrows (M); j++)
1562 {
1563 if (!((nmod_mat_entry (M, j, i) == 1) || (nmod_mat_entry (M, j,i) == 0)))
1564 {
1565 nonZeroOne= true;
1566 break;
1567 }
1568 }
1569 if (!nonZeroOne)
1570 result [i]= 1;
1571 else
1572 result [i]= 0;
1573 nonZeroOne= false;
1574 }
1575 return result;
1576}
1577#endif
1578
1579#ifdef HAVE_NTL
1581{
1582 long i, j;
1583 bool nonZeroOne= false;
1584 int * result= new int [M.NumCols()];
1585 for (i = 1; i <= M.NumCols(); i++)
1586 {
1587 for (j = 1; j <= M.NumRows(); j++)
1588 {
1589 if (!(IsOne (M (j,i)) || IsZero (M (j,i))))
1590 {
1591 nonZeroOne= true;
1592 break;
1593 }
1594 }
1595 if (!nonZeroOne)
1596 result [i - 1]= 1;
1597 else
1598 result [i - 1]= 0;
1599 nonZeroOne= false;
1600 }
1601 return result;
1602}
1603#endif
1604
1605#ifdef HAVE_NTL
1606void
1608 factors, const int liftBound, int& factorsFound, int*&
1610 bool beenInThres
1611 )
1612{
1613 Variable y= Variable (2);
1614 Variable x= Variable (1);
1616 CanonicalForm bufF= F (y-eval, y);
1617 if (factors.length() == 2)
1618 {
1621 tmp2= factors.getLast();
1622 tmp1= mulMod2 (tmp1, LC (F,x), yToL);
1623 tmp1 /= content (tmp1, x);
1624 tmp1= tmp1 (y-eval, y);
1625 tmp2= mulMod2 (tmp2, LC (F,x), yToL);
1626 tmp2 /= content (tmp2, x);
1627 tmp2= tmp2 (y-eval, y);
1628 tmp3 = tmp1*tmp2;
1629 if (tmp3/Lc (tmp3) == bufF/Lc (bufF))
1630 {
1631 factorsFound++;
1632 F= 1;
1635 return;
1636 }
1637 }
1640 for (long i= 1; i <= N.NumCols(); i++)
1641 {
1642 if (factorsFoundIndex [i - 1] == 1)
1643 continue;
1644 iter= factors;
1645 if (beenInThres)
1646 {
1647 int count= 1;
1648 while (count < i)
1649 {
1650 count++;
1651 iter++;
1652 }
1653 buf= iter.getItem();
1654 }
1655 else
1656 {
1657 buf= 1;
1658 for (long j= 1; j <= N.NumRows(); j++, iter++)
1659 {
1660 if (!IsZero (N (j,i)))
1661 buf= mulMod2 (buf, iter.getItem(), yToL);
1662 }
1663 }
1664 buf= mulMod2 (buf, LC (F,x), yToL);
1665 buf /= content (buf, x);
1666 buf= buf (y-eval,y);
1667 if (fdivides (buf, bufF, quot))
1668 {
1669 factorsFoundIndex[i - 1]= 1;
1670 factorsFound++;
1671 bufF= quot;
1672 bufF /= Lc (bufF);
1674 }
1675 if (degree (bufF) <= 0)
1676 return;
1677 if (factorsFound + 1 == N.NumCols())
1678 {
1680 F= 1;
1681 return;
1682 }
1683 }
1684 if (reconstructedFactors.length() != 0)
1685 F= bufF (y+eval,y);
1686}
1687#endif
1688
1689#ifdef HAVE_NTL
1690void
1692 factors, const int liftBound, int& factorsFound, int*&
1694 bool beenInThres
1695 )
1696{
1697 Variable y= Variable (2);
1698 Variable x= Variable (1);
1700 CanonicalForm bufF= F (y-eval, y);
1701 if (factors.length() == 2)
1702 {
1705 tmp2= factors.getLast();
1706 tmp1= mulMod2 (tmp1, LC (F,x), yToL);
1707 tmp1 /= content (tmp1, x);
1708 tmp1= tmp1 (y-eval, y);
1709 tmp2= mulMod2 (tmp2, LC (F,x), yToL);
1710 tmp2 /= content (tmp2, x);
1711 tmp2= tmp2 (y-eval,y);
1712 tmp3 = tmp1*tmp2;
1713 if (tmp3/Lc (tmp3) == bufF/Lc (bufF))
1714 {
1715 factorsFound++;
1716 F= 1;
1719 return;
1720 }
1721 }
1724 for (long i= 1; i <= N.NumCols(); i++)
1725 {
1726 if (factorsFoundIndex [i - 1] == 1)
1727 continue;
1728 iter= factors;
1729 if (beenInThres)
1730 {
1731 int count= 1;
1732 while (count < i)
1733 {
1734 count++;
1735 iter++;
1736 }
1737 buf= iter.getItem();
1738 }
1739 else
1740 {
1741 buf= 1;
1742 for (long j= 1; j <= N.NumRows(); j++, iter++)
1743 {
1744 if (!IsZero (N (j,i)))
1745 buf= mulMod2 (buf, iter.getItem(), yToL);
1746 }
1747 }
1748 buf= mulMod2 (buf, LC (F,x), yToL);
1749 buf /= content (buf, x);
1750 buf= buf (y-eval,y);
1751 if (fdivides (buf, bufF, quot))
1752 {
1753 factorsFoundIndex[i - 1]= 1;
1754 factorsFound++;
1755 bufF= quot;
1756 bufF /= Lc (bufF);
1758 }
1759 if (degree (bufF) <= 0)
1760 return;
1761 if (factorsFound + 1 == N.NumCols())
1762 {
1764 F=1;
1765 return;
1766 }
1767 }
1768 if (reconstructedFactors.length() != 0)
1769 F= bufF (y+eval,y);
1770}
1771#endif
1772
1773#ifdef HAVE_FLINT
1774void
1776 factors, const int liftBound, int& factorsFound, int*&
1778 bool beenInThres
1779 )
1780{
1781 Variable y= Variable (2);
1782 Variable x= Variable (1);
1784 CanonicalForm bufF= F (y-eval, y);
1785 if (factors.length() == 2)
1786 {
1789 tmp2= factors.getLast();
1790 tmp1= mulMod2 (tmp1, LC (F,x), yToL);
1791 tmp1 /= content (tmp1, x);
1792 tmp1= tmp1 (y-eval, y);
1793 tmp2= mulMod2 (tmp2, LC (F,x), yToL);
1794 tmp2 /= content (tmp2, x);
1795 tmp2= tmp2 (y-eval, y);
1796 tmp3 = tmp1*tmp2;
1797 if (tmp3/Lc (tmp3) == bufF/Lc (bufF))
1798 {
1799 factorsFound++;
1800 F= 1;
1803 return;
1804 }
1805 }
1808 for (long i= 0; i < nmod_mat_ncols (N); i++)
1809 {
1810 if (factorsFoundIndex [i] == 1)
1811 continue;
1812 iter= factors;
1813 if (beenInThres)
1814 {
1815 int count= 0;
1816 while (count < i)
1817 {
1818 count++;
1819 iter++;
1820 }
1821 buf= iter.getItem();
1822 }
1823 else
1824 {
1825 buf= 1;
1826 for (long j= 0; j < nmod_mat_nrows (N); j++, iter++)
1827 {
1828 if (!(nmod_mat_entry (N, j, i) == 0))
1829 buf= mulMod2 (buf, iter.getItem(), yToL);
1830 }
1831 }
1832 buf= mulMod2 (buf, LC (F,x), yToL);
1833 buf /= content (buf, x);
1834 buf= buf (y-eval,y);
1835 if (fdivides (buf, bufF, quot))
1836 {
1837 factorsFoundIndex[i]= 1;
1838 factorsFound++;
1839 bufF= quot;
1840 bufF /= Lc (bufF);
1842 }
1843 if (degree (F) <= 0)
1844 return;
1845 if (factorsFound + 1 == nmod_mat_ncols (N))
1846 {
1847 F= 1;
1849 return;
1850 }
1851 }
1852 if (reconstructedFactors.length() != 0)
1853 F= bufF (y+eval,y);
1854}
1855#endif
1856
1857#ifdef HAVE_NTL
1858CFList
1860 precision, const mat_zz_pE& N, const CanonicalForm& eval
1861 )
1862{
1863 Variable y= Variable (2);
1864 Variable x= Variable (1);
1865 CanonicalForm F= G;
1871 for (long i= 1; i <= N.NumCols(); i++)
1872 {
1873 if (zeroOneVecs [i - 1] == 0)
1874 continue;
1875 iter= factors;
1876 buf= 1;
1878 for (long j= 1; j <= N.NumRows(); j++, iter++)
1879 {
1880 if (!IsZero (N (j,i)))
1881 {
1882 factorsConsidered.append (iter.getItem());
1883 buf= mulMod2 (buf, iter.getItem(), yToL);
1884 }
1885 }
1886 buf= mulMod2 (buf, LC (F,x), yToL);
1887 buf /= content (buf, x);
1888 if (fdivides (buf, F, quot))
1889 {
1890 F= quot;
1891 F /= Lc (F);
1892 result.append (buf (y-eval,y));
1894 }
1895 if (degree (F) <= 0)
1896 {
1897 G= F;
1899 return result;
1900 }
1901 }
1902 G= F;
1904 return result;
1905}
1906#endif
1907
1908#ifdef HAVE_NTL
1909CFList
1911 int precision, const mat_zz_pE& N
1912 )
1913{
1914 Variable y= Variable (2);
1915 Variable x= Variable (1);
1916 CanonicalForm F= G;
1919 CFList result;
1923 for (long i= 1; i <= N.NumCols(); i++)
1924 {
1925 if (zeroOneVecs [i - 1] == 0)
1926 continue;
1927 iter= factors;
1928 buf= 1;
1930 for (long j= 1; j <= N.NumRows(); j++, iter++)
1931 {
1932 if (!IsZero (N (j,i)))
1933 {
1934 factorsConsidered.append (iter.getItem());
1935 buf= mulMod2 (buf, iter.getItem(), yToL);
1936 }
1937 }
1938 buf2= buf;
1939 buf= mulMod2 (buf, LC (F,x), yToL);
1940 buf /= content (buf, x);
1941 if (fdivides (buf, F, quot))
1942 {
1943 F= quot;
1944 F /= Lc (F);
1945 result.append (buf2);
1947 }
1948 if (degree (F) <= 0)
1949 {
1950 G= F;
1952 return result;
1953 }
1954 }
1955 G= F;
1957 return result;
1958}
1959#endif
1960
1961#ifdef HAVE_NTL
1962CFList
1964 precision, const mat_zz_p& N, const ExtensionInfo& info,
1966 )
1967{
1968 Variable y= Variable (2);
1969 Variable x= Variable (1);
1970 Variable alpha= info.getAlpha();
1971 Variable beta= info.getBeta();
1972 int k= info.getGFDegree();
1973 CanonicalForm gamma= info.getGamma();
1974 CanonicalForm delta= info.getDelta();
1975 CanonicalForm F= G;
1977 CFList result;
1982 for (long i= 1; i <= N.NumCols(); i++)
1983 {
1984 if (zeroOneVecs [i - 1] == 0)
1985 continue;
1986 iter= factors;
1987 buf= 1;
1989 for (long j= 1; j <= N.NumRows(); j++, iter++)
1990 {
1991 if (!IsZero (N (j,i)))
1992 {
1993 factorsConsidered.append (iter.getItem());
1994 buf= mulMod2 (buf, iter.getItem(), yToL);
1995 }
1996 }
1997 buf= mulMod2 (buf, LC (F,x), yToL);
1998 buf /= content (buf, x);
1999 buf2= buf (y-evaluation, y);
2000 buf2 /= Lc (buf2);
2001 if (!k && beta == x)
2002 {
2003 if (degree (buf2, alpha) < 1)
2004 {
2005 if (fdivides (buf, F, quot))
2006 {
2007 F= quot;
2008 F /= Lc (F);
2009 result.append (buf2);
2011 }
2012 }
2013 }
2014 else
2015 {
2016 CFList source, dest;
2017
2018 if (!isInExtension (buf2, gamma, k, delta, source, dest))
2019 {
2020 if (fdivides (buf, F, quot))
2021 {
2022 F= quot;
2023 F /= Lc (F);
2024 result.append (buf2);
2026 }
2027 }
2028 }
2029 if (degree (F) <= 0)
2030 {
2031 G= F;
2033 return result;
2034 }
2035 }
2036 G= F;
2038 return result;
2039}
2040#endif
2041
2042#ifdef HAVE_FLINT
2043CFList
2045 precision, const nmod_mat_t N, const ExtensionInfo& info,
2047 )
2048{
2049 Variable y= Variable (2);
2050 Variable x= Variable (1);
2051 Variable alpha= info.getAlpha();
2052 Variable beta= info.getBeta();
2053 int k= info.getGFDegree();
2054 CanonicalForm gamma= info.getGamma();
2055 CanonicalForm delta= info.getDelta();
2056 CanonicalForm F= G;
2058 CFList result;
2063 for (long i= 0; i < nmod_mat_ncols(N); i++)
2064 {
2065 if (zeroOneVecs [i] == 0)
2066 continue;
2067 iter= factors;
2068 buf= 1;
2070 for (long j= 0; j < nmod_mat_nrows(N); j++, iter++)
2071 {
2072 if (!(nmod_mat_entry (N, j, i) == 0))
2073 {
2074 factorsConsidered.append (iter.getItem());
2075 buf= mulMod2 (buf, iter.getItem(), yToL);
2076 }
2077 }
2078 buf= mulMod2 (buf, LC (F,x), yToL);
2079 buf /= content (buf, x);
2080 buf2= buf (y-evaluation, y);
2081 buf2 /= Lc (buf2);
2082 if (!k && beta == x)
2083 {
2084 if (degree (buf2, alpha) < 1)
2085 {
2086 if (fdivides (buf, F, quot))
2087 {
2088 F= quot;
2089 F /= Lc (F);
2090 result.append (buf2);
2092 }
2093 }
2094 }
2095 else
2096 {
2097 CFList source, dest;
2098
2099 if (!isInExtension (buf2, gamma, k, delta, source, dest))
2100 {
2101 if (fdivides (buf, F, quot))
2102 {
2103 F= quot;
2104 F /= Lc (F);
2105 result.append (buf2);
2107 }
2108 }
2109 }
2110 if (degree (F) <= 0)
2111 {
2112 G= F;
2114 return result;
2115 }
2116 }
2117 G= F;
2119 return result;
2120}
2121#endif
2122
2123#ifdef HAVE_NTL
2124CFList
2126 int precision, const mat_zz_p& N, const CanonicalForm& eval)
2127{
2128 Variable y= Variable (2);
2129 Variable x= Variable (1);
2130 CanonicalForm F= G;
2133 CFList result;
2137 for (long i= 1; i <= N.NumCols(); i++)
2138 {
2139 if (zeroOneVecs [i - 1] == 0)
2140 continue;
2141 iter= factors;
2142 buf= 1;
2144 for (long j= 1; j <= N.NumRows(); j++, iter++)
2145 {
2146 if (!IsZero (N (j,i)))
2147 {
2148 factorsConsidered.append (iter.getItem());
2149 buf= mulMod2 (buf, iter.getItem(), yToL);
2150 }
2151 }
2152 buf= mulMod2 (buf, LC (F,x), yToL);
2153 buf /= content (buf, x);
2154 if (fdivides (buf, F, quot))
2155 {
2156 F= quot;
2157 F /= Lc (F);
2158 result.append (buf (y-eval,y));
2160 }
2161 if (degree (F) <= 0)
2162 {
2163 G= F;
2165 return result;
2166 }
2167 }
2168 G= F;
2170 return result;
2171}
2172#endif
2173
2174#ifdef HAVE_FLINT
2175CFList
2177 int precision, const nmod_mat_t N, const CanonicalForm& eval)
2178{
2179 Variable y= Variable (2);
2180 Variable x= Variable (1);
2181 CanonicalForm F= G;
2184 CFList result;
2188 for (long i= 0; i < nmod_mat_ncols (N); i++)
2189 {
2190 if (zeroOneVecs [i] == 0)
2191 continue;
2192 iter= factors;
2193 buf= 1;
2195 for (long j= 0; j < nmod_mat_nrows (N); j++, iter++)
2196 {
2197 if (!(nmod_mat_entry (N, j, i) == 0))
2198 {
2199 factorsConsidered.append (iter.getItem());
2200 buf= mulMod2 (buf, iter.getItem(), yToL);
2201 }
2202 }
2203 buf= mulMod2 (buf, LC (F,x), yToL);
2204 buf /= content (buf, x);
2205 if (fdivides (buf, F, quot))
2206 {
2207 F= quot;
2208 F /= Lc (F);
2209 result.append (buf (y-eval,y));
2211 }
2212 if (degree (F) <= 0)
2213 {
2214 G= F;
2216 return result;
2217 }
2218 }
2219 G= F;
2221 return result;
2222}
2223#endif
2224
2225#ifdef HAVE_NTL
2226void
2228 CFList& factors, const int liftBound, int& factorsFound,
2231 )
2232{
2233 Variable y= Variable (2);
2234 Variable x= Variable (1);
2235 Variable alpha= info.getAlpha();
2236 Variable beta= info.getBeta();
2237 int k= info.getGFDegree();
2238 CanonicalForm gamma= info.getGamma();
2239 CanonicalForm delta= info.getDelta();
2241 CFList source, dest;
2242 if (factors.length() == 2)
2243 {
2246 tmp2= factors.getLast();
2247 tmp1= mulMod2 (tmp1, LC (F,x), yToL);
2248 tmp1 /= content (tmp1, x);
2249 tmp2= mulMod2 (tmp2, LC (F,x), yToL);
2250 tmp2 /= content (tmp2, x);
2251 tmp3 = tmp1*tmp2;
2252 if (tmp3/Lc (tmp3) == F/Lc (F))
2253 {
2254 tmp1= tmp1 (y - evaluation, y);
2255 tmp2= tmp2 (y - evaluation, y);
2256 tmp1 /= Lc (tmp1);
2257 tmp2 /= Lc (tmp2);
2258 if (!k && beta == x && degree (tmp2, alpha) < 1 &&
2259 degree (tmp1, alpha) < 1)
2260 {
2261 factorsFound++;
2262 F= 1;
2263 tmp1= mapDown (tmp1, info, source, dest);
2264 tmp2= mapDown (tmp2, info, source, dest);
2267 return;
2268 }
2269 else if (!isInExtension (tmp2, gamma, k, delta, source, dest) &&
2270 !isInExtension (tmp1, gamma, k, delta, source, dest))
2271 {
2272 factorsFound++;
2273 F= 1;
2274 tmp1= mapDown (tmp1, info, source, dest);
2275 tmp2= mapDown (tmp2, info, source, dest);
2278 return;
2279 }
2280 }
2281 }
2284 for (long i= 1; i <= N.NumCols(); i++)
2285 {
2286 if (factorsFoundIndex [i - 1] == 1)
2287 continue;
2288 iter= factors;
2289 if (beenInThres)
2290 {
2291 int count= 1;
2292 while (count < i)
2293 {
2294 count++;
2295 iter++;
2296 }
2297 buf= iter.getItem();
2298 }
2299 else
2300 {
2301 buf= 1;
2302 for (long j= 1; j <= N.NumRows(); j++, iter++)
2303 {
2304 if (!IsZero (N (j,i)))
2305 buf= mulMod2 (buf, iter.getItem(), yToL);
2306 }
2307 }
2308 buf= mulMod2 (buf, LC (F,x), yToL);
2309 buf /= content (buf, x);
2310 buf2= buf (y - evaluation, y);
2311 buf2 /= Lc (buf2);
2312 if (!k && beta == x)
2313 {
2314 if (degree (buf2, alpha) < 1)
2315 {
2316 if (fdivides (buf, F, quot))
2317 {
2318 factorsFoundIndex[i - 1]= 1;
2319 factorsFound++;
2320 F= quot;
2321 F /= Lc (F);
2322 buf2= mapDown (buf2, info, source, dest);
2324 }
2325 }
2326 }
2327 else
2328 {
2329 if (!isInExtension (buf2, gamma, k, delta, source, dest))
2330 {
2331 if (fdivides (buf, F, quot))
2332 {
2333 factorsFoundIndex[i - 1]= 1;
2334 factorsFound++;
2335 F= quot;
2336 F /= Lc (F);
2337 buf2= mapDown (buf2, info, source, dest);
2339 }
2340 }
2341 }
2342 if (degree (F) <= 0)
2343 return;
2344 if (factorsFound + 1 == N.NumCols())
2345 {
2346 CanonicalForm tmp= F (y - evaluation, y);
2347 tmp= mapDown (tmp, info, source, dest);
2349 return;
2350 }
2351 }
2352}
2353#endif
2354
2355#ifdef HAVE_FLINT
2356void
2358 CFList& factors, const int liftBound, int& factorsFound,
2361 )
2362{
2363 Variable y= Variable (2);
2364 Variable x= Variable (1);
2365 Variable alpha= info.getAlpha();
2366 Variable beta= info.getBeta();
2367 int k= info.getGFDegree();
2368 CanonicalForm gamma= info.getGamma();
2369 CanonicalForm delta= info.getDelta();
2371 CFList source, dest;
2372 if (factors.length() == 2)
2373 {
2376 tmp2= factors.getLast();
2377 tmp1= mulMod2 (tmp1, LC (F,x), yToL);
2378 tmp1 /= content (tmp1, x);
2379 tmp2= mulMod2 (tmp2, LC (F,x), yToL);
2380 tmp2 /= content (tmp2, x);
2381 tmp3 = tmp1*tmp2;
2382 if (tmp3/Lc (tmp3) == F/Lc (F))
2383 {
2384 tmp1= tmp1 (y - evaluation, y);
2385 tmp2= tmp2 (y - evaluation, y);
2386 tmp1 /= Lc (tmp1);
2387 tmp2 /= Lc (tmp2);
2388 if (!k && beta == x && degree (tmp2, alpha) < 1 &&
2389 degree (tmp1, alpha) < 1)
2390 {
2391 factorsFound++;
2392 F= 1;
2393 tmp1= mapDown (tmp1, info, source, dest);
2394 tmp2= mapDown (tmp2, info, source, dest);
2397 return;
2398 }
2399 else if (!isInExtension (tmp2, gamma, k, delta, source, dest) &&
2400 !isInExtension (tmp1, gamma, k, delta, source, dest))
2401 {
2402 factorsFound++;
2403 F= 1;
2404 tmp1= mapDown (tmp1, info, source, dest);
2405 tmp2= mapDown (tmp2, info, source, dest);
2408 return;
2409 }
2410 }
2411 }
2414 for (long i= 0; i < nmod_mat_ncols (N); i++)
2415 {
2416 if (factorsFoundIndex [i] == 1)
2417 continue;
2418 iter= factors;
2419 if (beenInThres)
2420 {
2421 int count= 0;
2422 while (count < i)
2423 {
2424 count++;
2425 iter++;
2426 }
2427 buf= iter.getItem();
2428 }
2429 else
2430 {
2431 buf= 1;
2432 for (long j= 0; j < nmod_mat_nrows (N); j++, iter++)
2433 {
2434 if (!(nmod_mat_entry (N, j, i) == 0))
2435 buf= mulMod2 (buf, iter.getItem(), yToL);
2436 }
2437 }
2438 buf= mulMod2 (buf, LC (F,x), yToL);
2439 buf /= content (buf, x);
2440 buf2= buf (y - evaluation, y);
2441 buf2 /= Lc (buf2);
2442 if (!k && beta == x)
2443 {
2444 if (degree (buf2, alpha) < 1)
2445 {
2446 if (fdivides (buf, F, quot))
2447 {
2448 factorsFoundIndex[i]= 1;
2449 factorsFound++;
2450 F= quot;
2451 F /= Lc (F);
2452 buf2= mapDown (buf2, info, source, dest);
2454 }
2455 }
2456 }
2457 else
2458 {
2459 if (!isInExtension (buf2, gamma, k, delta, source, dest))
2460 {
2461 if (fdivides (buf, F, quot))
2462 {
2463 factorsFoundIndex[i]= 1;
2464 factorsFound++;
2465 F= quot;
2466 F /= Lc (F);
2467 buf2= mapDown (buf2, info, source, dest);
2469 }
2470 }
2471 }
2472 if (degree (F) <= 0)
2473 return;
2474 if (factorsFound + 1 == nmod_mat_nrows (N))
2475 {
2476 CanonicalForm tmp= F (y - evaluation, y);
2477 tmp= mapDown (tmp, info, source, dest);
2479 return;
2480 }
2481 }
2482}
2483#endif
2484
2485#ifdef HAVE_NTL
2486//over Fp
2487int
2489 start, int liftBound, int minBound, CFList& factors,
2491 Pi, CFArray& bufQ, bool& irreducible
2492 )
2493{
2494 CanonicalForm LCF= LC (F, 1);
2495 CFArray *A= new CFArray [factors.length() - 1];
2496 bool wasInBounds= false;
2497 bool hitBound= false;
2498 int l= (minBound+1)*2;
2499 int stepSize= 2;
2500 int oldL= l/2;
2501 bool reduced= false;
2502 mat_zz_p NTLK, *NTLC;
2503 CFMatrix C;
2504 CFArray buf;
2507 Variable y= F.mvar();
2508 while (l <= liftBound)
2509 {
2511 if (start)
2512 {
2513 henselLiftResume12 (F, factors, start, l, Pi, diophant, M);
2514 start= 0;
2515 }
2516 else
2517 {
2518 if (wasInBounds)
2520 else
2521 henselLift12 (F, factors, l, Pi, diophant, M);
2522 }
2524 "time to lift in compute lattice: ");
2525
2526 factors.insert (LCF);
2527 j= factors;
2528 j++;
2529
2530 truncF= mod (F, power (y, l));
2532 for (int i= 0; i < factors.length() - 1; i++, j++)
2533 {
2534 if (!wasInBounds)
2535 A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ[i]);
2536 else
2537 A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
2538 bufQ[i]);
2539 }
2541 "time to compute logarithmic derivative: ");
2542
2543 for (int i= 0; i < sizeBounds; i++)
2544 {
2545 if (bounds [i] + 1 <= l/2)
2546 {
2547 wasInBounds= true;
2548 int k= tmin (bounds [i] + 1, l/2);
2549 C= CFMatrix (l - k, factors.length() - 1);
2550 for (int ii= 0; ii < factors.length() - 1; ii++)
2551 {
2552 if (A[ii].size() - 1 >= i)
2553 {
2554 buf= getCoeffs (A[ii] [i], k);
2555 writeInMatrix (C, buf, ii + 1, 0);
2556 }
2557 }
2559 NTLK= (*NTLC)*NTLN;
2560 transpose (NTLK, NTLK);
2561 kernel (NTLK, NTLK);
2562 transpose (NTLK, NTLK);
2563 NTLN *= NTLK;
2564 delete NTLC;
2565
2566 if (NTLN.NumCols() == 1)
2567 {
2568 irreducible= true;
2569 break;
2570 }
2571 if (isReduced (NTLN) && l > (minBound+1)*2)
2572 {
2573 reduced= true;
2574 break;
2575 }
2576 }
2577 }
2578
2579 if (irreducible)
2580 break;
2581 if (reduced)
2582 break;
2583 oldL= l;
2584 l += stepSize;
2585 stepSize *= 2;
2586 if (l > liftBound)
2587 {
2588 if (!hitBound)
2589 {
2590 l= liftBound;
2591 hitBound= true;
2592 }
2593 else
2594 break;
2595 }
2596 }
2597 delete [] A;
2598 if (!wasInBounds)
2599 {
2600 if (start)
2601 henselLiftResume12 (F, factors, start, degree (F) + 1, Pi, diophant, M);
2602 else
2603 henselLift12 (F, factors, degree (F) + 1, Pi, diophant, M);
2604 factors.insert (LCF);
2605 }
2606 return l;
2607}
2608#endif
2609
2610#ifdef HAVE_FLINT
2611#ifdef HAVE_NTL // henselLift12
2612int
2614 start, int liftBound, int minBound, CFList& factors,
2616 Pi, CFArray& bufQ, bool& irreducible
2617 )
2618{
2619 CanonicalForm LCF= LC (F, 1);
2620 CFArray *A= new CFArray [factors.length() - 1];
2621 bool wasInBounds= false;
2622 bool hitBound= false;
2623 int l= (minBound+1)*2;
2624 int stepSize= 2;
2625 int oldL= l/2;
2626 bool reduced= false;
2627 long rank;
2629 CFMatrix C;
2630 CFArray buf;
2633 Variable y= F.mvar();
2634 while (l <= liftBound)
2635 {
2637 if (start)
2638 {
2639 henselLiftResume12 (F, factors, start, l, Pi, diophant, M);
2640 start= 0;
2641 }
2642 else
2643 {
2644 if (wasInBounds)
2646 else
2647 henselLift12 (F, factors, l, Pi, diophant, M);
2648 }
2650 "time to lift in compute lattice: ");
2651
2652 factors.insert (LCF);
2653 j= factors;
2654 j++;
2655
2656 truncF= mod (F, power (y, l));
2658 for (int i= 0; i < factors.length() - 1; i++, j++)
2659 {
2660 if (!wasInBounds)
2661 A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ[i]);
2662 else
2663 A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
2664 bufQ[i]);
2665 }
2667 "time to compute logarithmic derivative: ");
2668
2669 for (int i= 0; i < sizeBounds; i++)
2670 {
2671 if (bounds [i] + 1 <= l/2)
2672 {
2673 wasInBounds= true;
2674 int k= tmin (bounds [i] + 1, l/2);
2675 C= CFMatrix (l - k, factors.length() - 1);
2676 for (int ii= 0; ii < factors.length() - 1; ii++)
2677 {
2678 if (A[ii].size() - 1 >= i)
2679 {
2680 buf= getCoeffs (A[ii] [i], k);
2681 writeInMatrix (C, buf, ii + 1, 0);
2682 }
2683 }
2684
2699 nmod_mat_mul (FLINTN, FLINTC, FLINTK); //no aliasing allowed!!
2700
2704 if (nmod_mat_ncols (FLINTN) == 1)
2705 {
2706 irreducible= true;
2707 break;
2708 }
2709 if (isReduced (FLINTN) && l > (minBound+1)*2)
2710 {
2711 reduced= true;
2712 break;
2713 }
2714 }
2715 }
2716
2717 if (irreducible)
2718 break;
2719 if (reduced)
2720 break;
2721 oldL= l;
2722 l += stepSize;
2723 stepSize *= 2;
2724 if (l > liftBound)
2725 {
2726 if (!hitBound)
2727 {
2728 l= liftBound;
2729 hitBound= true;
2730 }
2731 else
2732 break;
2733 }
2734 }
2735 delete [] A;
2736 if (!wasInBounds)
2737 {
2738 if (start)
2739 henselLiftResume12 (F, factors, start, degree (F) + 1, Pi, diophant, M);
2740 else
2741 henselLift12 (F, factors, degree (F) + 1, Pi, diophant, M);
2742 factors.insert (LCF);
2743 }
2744 return l;
2745}
2746#endif
2747#endif
2748
2749#ifdef HAVE_NTL
2750//over field extension
2751int
2753 int liftBound, int minBound, int start, CFList&
2755 CFMatrix& M, CFArray& Pi, CFArray& bufQ, bool&
2756 irreducible, const CanonicalForm& evaluation, const
2758 )
2759{
2761 CanonicalForm LCF= LC (F, 1);
2762 CFArray *A= new CFArray [factors.length() - 1];
2763 bool wasInBounds= false;
2764 bool hitBound= false;
2765 int degMipo;
2767 alpha= info.getAlpha();
2769
2770 Variable gamma= info.getBeta();
2771 CanonicalForm primElemAlpha= info.getGamma();
2773
2774 int stepSize= 2;
2775 int l= ((minBound+1)/degMipo+1)*2;
2776 l= tmax (l, 2);
2777 if (start > l)
2778 l= start;
2779 int oldL= l/2;
2780 bool reduced= false;
2781 Variable y= F.mvar();
2782 Variable x= Variable (1);
2784 CFMatrix Mat, C;
2785 CFArray buf;
2789 while (l <= liftBound)
2790 {
2792 if (start)
2793 {
2794 henselLiftResume12 (F, factors, start, l, Pi, diophant, M);
2795 start= 0;
2796 }
2797 else
2798 {
2799 if (wasInBounds)
2801 else
2802 henselLift12 (F, factors, l, Pi, diophant, M);
2803 }
2805 "time to lift in compute lattice: ");
2806
2807 factors.insert (LCF);
2808
2809 if (GF)
2811
2812 powX= power (y-gamma, l);
2814 for (int i= 0; i < l*degMipo; i++)
2815 {
2816 imBasis= mod (power (y, i), powX);
2817 imBasis= imBasis (power (y, degMipo), y);
2818 imBasis= imBasis (y, gamma);
2819 iter= imBasis;
2820 for (; iter.hasTerms(); iter++)
2821 Mat (iter.exp()+ 1, i+1)= iter.coeff();
2822 }
2823
2825 *NTLMat= inv (*NTLMat);
2826
2827 if (GF)
2829
2830 j= factors;
2831 j++;
2832
2833 truncF= mod (F, power (y, l));
2835 for (int i= 0; i < factors.length() - 1; i++, j++)
2836 {
2837 if (!wasInBounds)
2838 A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ[i]);
2839 else
2840 A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
2841 bufQ[i]);
2842 }
2844 "time to compute logarithmic derivative: ");
2845
2846 for (int i= 0; i < sizeBounds; i++)
2847 {
2848 if (bounds [i] + 1 <= (l/2)*degMipo)
2849 {
2850 wasInBounds= true;
2851 int k= tmin (bounds [i] + 1, (l/2)*degMipo);
2852 C= CFMatrix (l*degMipo - k, factors.length() - 1);
2853
2854 for (int ii= 0; ii < factors.length() - 1; ii++)
2855 {
2856 if (A[ii].size() - 1 >= i)
2857 {
2858 if (GF)
2859 {
2860 A [ii] [i]= A [ii] [i] (y-evaluation, y);
2862 A[ii] [i]= GF2FalphaRep (A[ii] [i], alpha);
2863 if (alpha != gamma)
2865 gamma, source, dest
2866 );
2867 buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, *NTLMat);
2868 }
2869 else
2870 {
2871 A [ii] [i]= A [ii] [i] (y-evaluation, y);
2872 if (alpha != gamma)
2874 gamma, source, dest
2875 );
2876 buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, *NTLMat);
2877 }
2878 writeInMatrix (C, buf, ii + 1, 0);
2879 }
2880 if (GF)
2882 }
2883
2884 if (GF)
2886
2888 NTLK= (*NTLC)*NTLN;
2889 transpose (NTLK, NTLK);
2890 kernel (NTLK, NTLK);
2891 transpose (NTLK, NTLK);
2892 NTLN *= NTLK;
2893 delete NTLC;
2894
2895 if (GF)
2897
2898 if (NTLN.NumCols() == 1)
2899 {
2900 irreducible= true;
2901 break;
2902 }
2903 if (isReduced (NTLN))
2904 {
2905 reduced= true;
2906 break;
2907 }
2908 }
2909 }
2910
2911 delete NTLMat;
2912
2913 if (NTLN.NumCols() == 1)
2914 {
2915 irreducible= true;
2916 break;
2917 }
2918 if (reduced)
2919 break;
2920 oldL= l;
2921 l += stepSize;
2922 stepSize *= 2;
2923 if (l > liftBound)
2924 {
2925 if (!hitBound)
2926 {
2927 l= liftBound;
2928 hitBound= true;
2929 }
2930 else
2931 break;
2932 }
2933 }
2934 delete [] A;
2935 if (!wasInBounds)
2936 {
2937 if (start)
2938 henselLiftResume12 (F, factors, start, degree (F) + 1, Pi, diophant, M);
2939 else
2940 henselLift12 (F, factors, degree (F) + 1, Pi, diophant, M);
2941 factors.insert (LCF);
2942 }
2943 return l;
2944}
2945#endif
2946
2947#ifdef HAVE_FLINT
2948#ifdef HAVE_NTL // henselLift12
2949//over field extension
2950int
2952 int liftBound, int minBound, int start, CFList&
2954 CFMatrix& M, CFArray& Pi, CFArray& bufQ, bool&
2955 irreducible, const CanonicalForm& evaluation, const
2957 )
2958{
2960 CanonicalForm LCF= LC (F, 1);
2961 CFArray *A= new CFArray [factors.length() - 1];
2962 bool wasInBounds= false;
2963 bool hitBound= false;
2964 int degMipo;
2966 alpha= info.getAlpha();
2968
2969 Variable gamma= info.getBeta();
2970 CanonicalForm primElemAlpha= info.getGamma();
2972
2973 int stepSize= 2;
2974 int l= ((minBound+1)/degMipo+1)*2;
2975 l= tmax (l, 2);
2976 if (start > l)
2977 l= start;
2978 int oldL= l/2;
2979 bool reduced= false;
2980 Variable y= F.mvar();
2981 Variable x= Variable (1);
2983 CFMatrix Mat, C;
2984 CFArray buf;
2986 long rank;
2989 while (l <= liftBound)
2990 {
2991 if (start)
2992 {
2993 henselLiftResume12 (F, factors, start, l, Pi, diophant, M);
2994 start= 0;
2995 }
2996 else
2997 {
2998 if (wasInBounds)
3000 else
3001 henselLift12 (F, factors, l, Pi, diophant, M);
3002 }
3003
3004 factors.insert (LCF);
3005
3006 if (GF)
3008
3009 powX= power (y-gamma, l);
3011 for (int i= 0; i < l*degMipo; i++)
3012 {
3013 imBasis= mod (power (y, i), powX);
3014 imBasis= imBasis (power (y, degMipo), y);
3015 imBasis= imBasis (y, gamma);
3016 iter= imBasis;
3017 for (; iter.hasTerms(); iter++)
3018 Mat (iter.exp()+ 1, i+1)= iter.coeff();
3019 }
3020
3025
3026 if (GF)
3028
3029 j= factors;
3030 j++;
3031
3032 truncF= mod (F, power (y, l));
3033 for (int i= 0; i < factors.length() - 1; i++, j++)
3034 {
3035 if (!wasInBounds)
3036 A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ[i]);
3037 else
3038 A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
3039 bufQ[i]);
3040 }
3041
3042 for (int i= 0; i < sizeBounds; i++)
3043 {
3044 if (bounds [i] + 1 <= (l/2)*degMipo)
3045 {
3046 wasInBounds= true;
3047 int k= tmin (bounds [i] + 1, (l/2)*degMipo);
3048 C= CFMatrix (l*degMipo - k, factors.length() - 1);
3049
3050 for (int ii= 0; ii < factors.length() - 1; ii++)
3051 {
3052 if (A[ii].size() - 1 >= i)
3053 {
3054 if (GF)
3055 {
3056 A [ii] [i]= A [ii] [i] (y-evaluation, y);
3058 A[ii] [i]= GF2FalphaRep (A[ii] [i], alpha);
3059 if (alpha != gamma)
3061 gamma, source, dest
3062 );
3063 buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, FLINTMatInv);
3064 }
3065 else
3066 {
3067 A [ii] [i]= A [ii] [i] (y-evaluation, y);
3068 if (alpha != gamma)
3070 gamma, source, dest
3071 );
3072 buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, FLINTMatInv);
3073 }
3074 writeInMatrix (C, buf, ii + 1, 0);
3075 }
3076 if (GF)
3078 }
3079
3080 if (GF)
3082
3097 nmod_mat_mul (FLINTN, FLINTC, FLINTK); //no aliasing allowed!!
3098
3102
3103 if (GF)
3105
3106 if (nmod_mat_ncols (FLINTN) == 1)
3107 {
3108 irreducible= true;
3109 break;
3110 }
3111 if (isReduced (FLINTN))
3112 {
3113 reduced= true;
3114 break;
3115 }
3116 }
3117 }
3118
3121
3122 if (nmod_mat_ncols (FLINTN) == 1)
3123 {
3124 irreducible= true;
3125 break;
3126 }
3127 if (reduced)
3128 break;
3129 oldL= l;
3130 l += stepSize;
3131 stepSize *= 2;
3132 if (l > liftBound)
3133 {
3134 if (!hitBound)
3135 {
3136 l= liftBound;
3137 hitBound= true;
3138 }
3139 else
3140 break;
3141 }
3142 }
3143 delete [] A;
3144 if (!wasInBounds)
3145 {
3146 if (start)
3147 henselLiftResume12 (F, factors, start, degree (F) + 1, Pi, diophant, M);
3148 else
3149 henselLift12 (F, factors, degree (F) + 1, Pi, diophant, M);
3150 factors.insert (LCF);
3151 }
3152 return l;
3153}
3154#endif
3155#endif
3156
3157// over Fq
3158#ifdef HAVE_NTL
3159int
3161 int start, int liftBound, int minBound, CFList& factors,
3163 Pi, CFArray& bufQ, bool& irreducible
3164 )
3165{
3166 CanonicalForm LCF= LC (F, 1);
3167 CFArray *A= new CFArray [factors.length() - 1];
3168 bool wasInBounds= false;
3169 bool hitBound= false;
3170 int l= (minBound+1)*2;
3171 int stepSize= 2;
3172 int oldL= l/2;
3173 bool reduced= false;
3176 CFArray buf;
3177 CFMatrix C;
3178 Variable y= F.mvar();
3180 while (l <= liftBound)
3181 {
3183 if (start)
3184 {
3185 henselLiftResume12 (F, factors, start, l, Pi, diophant, M);
3186 start= 0;
3187 }
3188 else
3189 {
3190 if (wasInBounds)
3192 else
3193 henselLift12 (F, factors, l, Pi, diophant, M);
3194 }
3196 "time to lift in compute lattice: ");
3197
3198 factors.insert (LCF);
3199 j= factors;
3200 j++;
3201
3202 truncF= mod (F, power (y,l));
3204 for (int i= 0; i < factors.length() - 1; i++, j++)
3205 {
3206 if (l == (minBound+1)*2)
3207 {
3208 A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ[i]);
3209 }
3210 else
3211 {
3212 A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
3213 bufQ[i]
3214 );
3215 }
3216 }
3218 "time to compute logarithmic derivative: ");
3219
3220 for (int i= 0; i < sizeBounds; i++)
3221 {
3222 if (bounds [i] + 1 <= l/2)
3223 {
3224 wasInBounds= true;
3225 int k= tmin (bounds [i] + 1, l/2);
3226 C= CFMatrix (l - k, factors.length() - 1);
3227 for (int ii= 0; ii < factors.length() - 1; ii++)
3228 {
3229
3230 if (A[ii].size() - 1 >= i)
3231 {
3232 buf= getCoeffs (A[ii] [i], k);
3233 writeInMatrix (C, buf, ii + 1, 0);
3234 }
3235 }
3236
3238 NTLK= (*NTLC)*NTLN;
3239 transpose (NTLK, NTLK);
3240 kernel (NTLK, NTLK);
3241 transpose (NTLK, NTLK);
3242 NTLN *= NTLK;
3243 delete NTLC;
3244
3245 if (NTLN.NumCols() == 1)
3246 {
3247 irreducible= true;
3248 break;
3249 }
3250 if (isReduced (NTLN) && l > (minBound+1)*2)
3251 {
3252 reduced= true;
3253 break;
3254 }
3255 }
3256 }
3257
3258 if (NTLN.NumCols() == 1)
3259 {
3260 irreducible= true;
3261 break;
3262 }
3263 if (reduced)
3264 break;
3265 oldL= l;
3266 l += stepSize;
3267 stepSize *= 2;
3268 if (l > liftBound)
3269 {
3270 if (!hitBound)
3271 {
3272 l= liftBound;
3273 hitBound= true;
3274 }
3275 else
3276 break;
3277 }
3278 }
3279 delete [] A;
3280 if (!wasInBounds)
3281 {
3282 if (start)
3283 henselLiftResume12 (F, factors, start, degree (F) + 1, Pi, diophant, M);
3284 else
3285 henselLift12 (F, factors, degree (F) + 1, Pi, diophant, M);
3286 factors.insert (LCF);
3287 }
3288 return l;
3289}
3290#endif
3291
3292#ifdef HAVE_NTL // henselLift12
3293#ifdef HAVE_FLINT
3294int
3296 int start, int liftBound, int minBound, CFList&
3298 CFMatrix& M, CFArray& Pi, CFArray& bufQ, bool&
3299 irreducible, const Variable& alpha
3300 )
3301#else
3302int
3304 int start, int liftBound, int minBound, CFList&
3306 M, CFArray& Pi, CFArray& bufQ, bool& irreducible,
3307 const Variable& alpha
3308 )
3309#endif
3310{
3311 CanonicalForm LCF= LC (F, 1);
3312 CFArray *A= new CFArray [factors.length() - 1];
3313 bool wasInBounds= false;
3314 int l= (minBound+1)*2;
3315 int oldL= l/2;
3316 int stepSize= 2;
3317 bool hitBound= false;
3319 bool reduced= false;
3321 CFMatrix C;
3322 CFArray buf;
3323#ifdef HAVE_FLINT
3324 long rank;
3326#else
3327 mat_zz_p* NTLC, NTLK;
3328#endif
3329 Variable y= F.mvar();
3331 while (l <= liftBound)
3332 {
3334 if (start)
3335 {
3336 henselLiftResume12 (F, factors, start, l, Pi, diophant, M);
3337 start= 0;
3338 }
3339 else
3340 {
3341 if (wasInBounds)
3343 else
3344 henselLift12 (F, factors, l, Pi, diophant, M);
3345 }
3347 "time to lift in compute lattice: ");
3348
3349 factors.insert (LCF);
3350 j= factors;
3351 j++;
3352
3353 truncF= mod (F, power (y,l));
3355 for (int i= 0; i < factors.length() - 1; i++, j++)
3356 {
3357 if (l == (minBound+1)*2)
3358 {
3359 A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ[i]);
3360 }
3361 else
3362 {
3363 A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
3364 bufQ[i]
3365 );
3366 }
3367 }
3369 "time to compute logarithmic derivative: ");
3370
3371 for (int i= 0; i < sizeBounds; i++)
3372 {
3373 if (bounds [i] + 1 <= l/2)
3374 {
3375 wasInBounds= true;
3376 int k= tmin (bounds [i] + 1, l/2);
3377 C= CFMatrix ((l - k)*extensionDeg, factors.length() - 1);
3378 for (int ii= 0; ii < factors.length() - 1; ii++)
3379 {
3380 if (A[ii].size() - 1 >= i)
3381 {
3382 buf= getCoeffs (A[ii] [i], k, alpha);
3383 writeInMatrix (C, buf, ii + 1, 0);
3384 }
3385 }
3386
3387#ifdef HAVE_FLINT
3402 nmod_mat_mul (FLINTN, FLINTC, FLINTK); //no aliasing allowed!!
3403
3407#else
3409 NTLK= (*NTLC)*NTLN;
3410 transpose (NTLK, NTLK);
3411 kernel (NTLK, NTLK);
3412 transpose (NTLK, NTLK);
3413 NTLN *= NTLK;
3414 delete NTLC;
3415#endif
3416
3417#ifdef HAVE_FLINT
3418 if (nmod_mat_nrows (FLINTN) == 1)
3419#else
3420 if (NTLN.NumCols() == 1)
3421#endif
3422 {
3423 irreducible= true;
3424 break;
3425 }
3426#ifdef HAVE_FLINT
3427 if (isReduced (FLINTN) && l > (minBound+1)*2)
3428#else
3429 if (isReduced (NTLN) && l > (minBound+1)*2)
3430#endif
3431 {
3432 reduced= true;
3433 break;
3434 }
3435 }
3436 }
3437
3438#ifdef HAVE_FLINT
3439 if (nmod_mat_ncols (FLINTN) == 1)
3440#else
3441 if (NTLN.NumCols() == 1)
3442#endif
3443 {
3444 irreducible= true;
3445 break;
3446 }
3447 if (reduced)
3448 break;
3449 oldL= l;
3450 l += stepSize;
3451 stepSize *= 2;
3452 if (l > liftBound)
3453 {
3454 if (!hitBound)
3455 {
3456 l= liftBound;
3457 hitBound= true;
3458 }
3459 else
3460 break;
3461 }
3462 }
3463 delete [] A;
3464 if (!wasInBounds)
3465 {
3466 if (start)
3467 henselLiftResume12 (F, factors, start, degree (F) + 1, Pi, diophant, M);
3468 else
3469 henselLift12 (F, factors, degree (F) + 1, Pi, diophant, M);
3470 factors.insert (LCF);
3471 }
3472 return l;
3473}
3474#endif
3475
3476#ifdef HAVE_NTL // logarithmicDerivative
3477CFList
3479 int oldNumCols, int oldL, int precision,
3480 const CanonicalForm& eval
3481 )
3482{
3483 int d;
3484 bool isIrreducible= false;
3485 int* bounds= computeBounds (F, d, isIrreducible);
3486 Variable y= F.mvar();
3487 if (isIrreducible)
3488 {
3489 delete [] bounds;
3490 CanonicalForm G= F;
3491 F= 1;
3492 return CFList (G (y-eval, y));
3493 }
3494 CFArray * A= new CFArray [factors.length()];
3496#ifdef HAVE_FLINT
3499 for (long i=factors.length()-1; i >= 0; i--)
3500 nmod_mat_entry (FLINTN, i, i)= 1;
3501#else
3502 mat_zz_p NTLN;
3503 ident (NTLN, factors.length());
3504#endif
3505 int minBound= bounds[0];
3506 for (int i= 1; i < d; i++)
3507 {
3508 if (bounds[i] != 0)
3510 }
3511 int l= tmax (2*(minBound + 1), oldL);
3512 int oldL2= l/2;
3513 int stepSize= 2;
3514 bool useOldQs= false;
3515 bool hitBound= false;
3517 CFMatrix C;
3518 CFArray buf;
3519#ifdef HAVE_FLINT
3520 long rank;
3522#else
3523 mat_zz_p* NTLC, NTLK;
3524#endif
3526 while (l <= precision)
3527 {
3528 j= factors;
3529 truncF= mod (F, power (y,l));
3530 if (useOldQs)
3531 {
3532 for (int i= 0; i < factors.length(); i++, j++)
3533 A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL2, bufQ[i],
3534 bufQ[i]
3535 );
3536 }
3537 else
3538 {
3539 for (int i= 0; i < factors.length(); i++, j++)
3540 A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ [i]);
3541 }
3542 useOldQs= true;
3543 for (int i= 0; i < d; i++)
3544 {
3545 if (bounds [i] + 1 <= l/2)
3546 {
3547 int k= tmin (bounds [i] + 1, l/2);
3548 C= CFMatrix (l - k, factors.length());
3549 for (int ii= 0; ii < factors.length(); ii++)
3550 {
3551 if (A[ii].size() - 1 >= i)
3552 {
3553 buf= getCoeffs (A[ii] [i], k);
3554 writeInMatrix (C, buf, ii + 1, 0);
3555 }
3556 }
3557#ifdef HAVE_FLINT
3572 nmod_mat_mul (FLINTN, FLINTC, FLINTK); //no aliasing allowed!!
3573
3577#else
3579 NTLK= (*NTLC)*NTLN;
3580 transpose (NTLK, NTLK);
3581 kernel (NTLK, NTLK);
3582 transpose (NTLK, NTLK);
3583 NTLN *= NTLK;
3584 delete NTLC;
3585#endif
3586#ifdef HAVE_FLINT
3587 if (nmod_mat_ncols (FLINTN) == 1)
3588 {
3590#else
3591 if (NTLN.NumCols() == 1)
3592 {
3593#endif
3594 delete [] A;
3595 delete [] bounds;
3596 CanonicalForm G= F;
3597 F= 1;
3598 return CFList (G (y-eval,y));
3599 }
3600 }
3601 }
3602
3603#ifdef HAVE_FLINT
3605 {
3606 if (isReduced (FLINTN))
3607 {
3608 int * factorsFoundIndex= new int [nmod_mat_ncols (FLINTN)];
3609 for (long i= 0; i < nmod_mat_ncols (FLINTN); i++)
3610#else
3611 if (NTLN.NumCols() < oldNumCols - factorsFound)
3612 {
3613 if (isReduced (NTLN))
3614 {
3615 int * factorsFoundIndex= new int [NTLN.NumCols()];
3616 for (long i= 0; i < NTLN.NumCols(); i++)
3617#endif
3618 factorsFoundIndex[i]= 0;
3619 int factorsFound2= 0;
3620 CFList result;
3622#ifdef HAVE_FLINT
3625 );
3626 if (result.length() == nmod_mat_ncols (FLINTN))
3627 {
3629#else
3631 factorsFoundIndex, NTLN, eval, false
3632 );
3633 if (result.length() == NTLN.NumCols())
3634 {
3635#endif
3636 delete [] factorsFoundIndex;
3637 delete [] A;
3638 delete [] bounds;
3639 F= 1;
3640 return result;
3641 }
3642 delete [] factorsFoundIndex;
3643 }
3644 else if (l == precision)
3645 {
3647#ifdef HAVE_FLINT
3651#else
3654#endif
3655 F= bufF;
3656 delete [] zeroOne;
3657 delete [] A;
3658 delete [] bounds;
3659 return result;
3660 }
3661 }
3662 oldL2= l;
3663 l += stepSize;
3664 stepSize *= 2;
3665 if (l > precision)
3666 {
3667 if (!hitBound)
3668 {
3669 l= precision;
3670 hitBound= true;
3671 }
3672 else
3673 break;
3674 }
3675 }
3676#ifdef HAVE_FLINT
3678#endif
3679 delete [] bounds;
3680 delete [] A;
3681 return CFList();
3682}
3683#endif
3684
3685#ifdef HAVE_NTL // mat_zz_pE
3686CFList
3688 int oldNumCols, int oldL, const Variable&,
3689 int precision, const CanonicalForm& eval
3690 )
3691{
3692 int d;
3693 bool isIrreducible= false;
3694 Variable y= F.mvar();
3695 int* bounds= computeBounds (F, d, isIrreducible);
3696 if (isIrreducible)
3697 {
3698 delete [] bounds;
3699 CanonicalForm G= F;
3700 F= 1;
3701 return CFList (G (y-eval,y));
3702 }
3703 CFArray * A= new CFArray [factors.length()];
3706 ident (NTLN, factors.length());
3707 int minBound= bounds[0];
3708 for (int i= 1; i < d; i++)
3709 {
3710 if (bounds[i] != 0)
3712 }
3713 int l= tmax (2*(minBound + 1), oldL);
3714 int oldL2= l/2;
3715 int stepSize= 2;
3716 bool useOldQs= false;
3717 bool hitBound= false;
3719 CFMatrix C;
3721 CFArray buf;
3723 while (l <= precision)
3724 {
3725 j= factors;
3726 truncF= mod (F, power (y,l));
3727 if (useOldQs)
3728 {
3729 for (int i= 0; i < factors.length(); i++, j++)
3730 A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL2, bufQ[i],
3731 bufQ[i]
3732 );
3733 }
3734 else
3735 {
3736 for (int i= 0; i < factors.length(); i++, j++)
3737 A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ [i]);
3738 }
3739 useOldQs= true;
3740 for (int i= 0; i < d; i++)
3741 {
3742 if (bounds [i] + 1 <= l/2)
3743 {
3744 int k= tmin (bounds [i] + 1, l/2);
3745 C= CFMatrix (l - k, factors.length());
3746 for (int ii= 0; ii < factors.length(); ii++)
3747 {
3748 if (A[ii].size() - 1 >= i)
3749 {
3750 buf= getCoeffs (A[ii] [i], k);
3751 writeInMatrix (C, buf, ii + 1, 0);
3752 }
3753 }
3755 NTLK= (*NTLC)*NTLN;
3756 transpose (NTLK, NTLK);
3757 kernel (NTLK, NTLK);
3758 transpose (NTLK, NTLK);
3759 NTLN *= NTLK;
3760 delete NTLC;
3761 if (NTLN.NumCols() == 1)
3762 {
3763 delete [] A;
3764 delete [] bounds;
3765 CanonicalForm G= F;
3766 F= 1;
3767 return CFList (G (y-eval,y));
3768 }
3769 }
3770 }
3771
3772 if (NTLN.NumCols() < oldNumCols - factorsFound)
3773 {
3774 if (isReduced (NTLN))
3775 {
3776 int * factorsFoundIndex= new int [NTLN.NumCols()];
3777 for (long i= 0; i < NTLN.NumCols(); i++)
3778 factorsFoundIndex[i]= 0;
3779 int factorsFound2= 0;
3780 CFList result;
3783 factorsFoundIndex, NTLN, eval, false);
3784 if (result.length() == NTLN.NumCols())
3785 {
3786 delete [] factorsFoundIndex;
3787 delete [] A;
3788 delete [] bounds;
3789 F= 1;
3790 return result;
3791 }
3792 delete [] factorsFoundIndex;
3793 }
3794 else if (l == precision)
3795 {
3799 F= bufF;
3800 delete [] zeroOne;
3801 delete [] A;
3802 delete [] bounds;
3803 return result;
3804 }
3805 }
3806 oldL2= l;
3807 l += stepSize;
3808 stepSize *= 2;
3809 if (l > precision)
3810 {
3811 if (!hitBound)
3812 {
3813 l= precision;
3814 hitBound= true;
3815 }
3816 else
3817 break;
3818 }
3819 }
3820 delete [] bounds;
3821 delete [] A;
3822 return CFList();
3823}
3824#endif
3825
3826#ifdef HAVE_NTL // logarithmicDerivative
3827//over field extension
3828CFList
3830 int oldNumCols, int oldL, const CanonicalForm& evaluation,
3831 const ExtensionInfo& info, CFList& source, CFList& dest,
3832 int precision
3833 )
3834{
3836 int degMipo= degree (getMipo (info.getAlpha()));
3837 Variable alpha= info.getAlpha();
3838 int d;
3839 bool isIrreducible= false;
3840 int* bounds= computeBounds (F, d, isIrreducible);
3841 if (isIrreducible)
3842 {
3843 delete [] bounds;
3844 Variable y= Variable (2);
3845 CanonicalForm tmp= F (y - evaluation, y);
3846 CFList source, dest;
3847 tmp= mapDown (tmp, info, source, dest);
3848 F= 1;
3849 return CFList (tmp);
3850 }
3851
3852 CFArray * A= new CFArray [factors.length()];
3854#ifdef HAVE_FLINT
3857 for (long i=factors.length()-1; i >= 0; i--)
3858 nmod_mat_entry (FLINTN, i, i)= 1;
3859#else
3861 {
3863 zz_p::init (getCharacteristic());
3864 }
3865 mat_zz_p NTLN;
3866 ident (NTLN, factors.length());
3867#endif
3868 int minBound= bounds[0];
3869 for (int i= 1; i < d; i++)
3870 {
3871 if (bounds[i] != 0)
3873 }
3874 int l= tmax (oldL, 2*((minBound+1)/degMipo+1));
3875 int oldL2= l/2;
3876 int stepSize= 2;
3877 bool useOldQs= false;
3878 bool hitBound= false;
3879 Variable gamma= info.getBeta();
3880 CanonicalForm primElemAlpha= info.getGamma();
3883 Variable y= F.mvar();
3885 CFMatrix Mat, C;
3887#ifdef HAVE_FLINT
3888 long rank;
3890#else
3892#endif
3893 CFArray buf;
3894 while (l <= precision)
3895 {
3896 j= factors;
3897 if (GF)
3899 powX= power (y-gamma, l);
3901 for (int i= 0; i < l*degMipo; i++)
3902 {
3903 imBasis= mod (power (y, i), powX);
3904 imBasis= imBasis (power (y, degMipo), y);
3905 imBasis= imBasis (y, gamma);
3906 iter= imBasis;
3907 for (; iter.hasTerms(); iter++)
3908 Mat (iter.exp()+ 1, i+1)= iter.coeff();
3909 }
3910
3911#ifdef HAVE_FLINT
3916#else
3918 *NTLMat= inv (*NTLMat);
3919#endif
3920
3921 if (GF)
3923
3924 truncF= mod (F, power (y, l));
3925 if (useOldQs)
3926 {
3927 for (int i= 0; i < factors.length(); i++, j++)
3928 A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL2, bufQ[i],
3929 bufQ[i]
3930 );
3931 }
3932 else
3933 {
3934 for (int i= 0; i < factors.length(); i++, j++)
3935 A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ [i]);
3936 }
3937 useOldQs= true;
3938 for (int i= 0; i < d; i++)
3939 {
3940 if (bounds [i] + 1 <= (l/2)*degMipo)
3941 {
3942 int k= tmin (bounds [i] + 1, (l/2)*degMipo);
3943 C= CFMatrix (l*degMipo - k, factors.length());
3944 for (int ii= 0; ii < factors.length(); ii++)
3945 {
3946 if (A[ii].size() - 1 >= i)
3947 {
3948 if (GF)
3949 {
3950 A[ii] [i]= A [ii] [i] (y-evaluation, y);
3952 A[ii] [i]= GF2FalphaRep (A[ii] [i], alpha);
3953 if (alpha != gamma)
3955 gamma, source, dest
3956 );
3957#ifdef HAVE_FLINT
3958 buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, FLINTMatInv);
3959#else
3960 buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, *NTLMat);
3961#endif
3962 }
3963 else
3964 {
3965 A [ii] [i]= A [ii] [i] (y-evaluation, y);
3966 if (alpha != gamma)
3968 gamma, source, dest
3969 );
3970#ifdef HAVE_FLINT
3971 buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, FLINTMatInv);
3972#else
3973 buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, *NTLMat);
3974#endif
3975 }
3976 writeInMatrix (C, buf, ii + 1, 0);
3977 }
3978 if (GF)
3980 }
3981
3982 if (GF)
3984
3985#ifdef HAVE_FLINT
4000 nmod_mat_mul (FLINTN, FLINTC, FLINTK); //no aliasing allowed!!
4001
4005#else
4007 NTLK= (*NTLC)*NTLN;
4008 transpose (NTLK, NTLK);
4009 kernel (NTLK, NTLK);
4010 transpose (NTLK, NTLK);
4011 NTLN *= NTLK;
4012 delete NTLC;
4013#endif
4014
4015 if (GF)
4017
4018#ifdef HAVE_FLINT
4019 if (nmod_mat_ncols (FLINTN) == 1)
4020 {
4024#else
4025 if (NTLN.NumCols() == 1)
4026 {
4027 delete NTLMat;
4028#endif
4029 Variable y= Variable (2);
4030 CanonicalForm tmp= F (y - evaluation, y);
4031 CFList source, dest;
4032 tmp= mapDown (tmp, info, source, dest);
4033 delete [] A;
4034 delete [] bounds;
4035 F= 1;
4036 return CFList (tmp);
4037 }
4038 }
4039 }
4040
4041#ifdef HAVE_FLINT
4044#else
4045 delete NTLMat;
4046#endif
4047
4048#ifdef HAVE_FLINT
4050 {
4051 if (isReduced (FLINTN))
4052 {
4053 int * factorsFoundIndex= new int [nmod_mat_ncols (FLINTN)];
4054 for (long i= 0; i < nmod_mat_ncols (FLINTN); i++)
4055#else
4056 if (NTLN.NumCols() < oldNumCols - factorsFound)
4057 {
4058 if (isReduced (NTLN))
4059 {
4060 int * factorsFoundIndex= new int [NTLN.NumCols()];
4061 for (long i= 0; i < NTLN.NumCols(); i++)
4062#endif
4063 factorsFoundIndex[i]= 0;
4064 int factorsFound2= 0;
4065 CFList result;
4067#ifdef HAVE_FLINT
4070 );
4071 if (result.length() == nmod_mat_ncols (FLINTN))
4072 {
4074#else
4077 );
4078 if (result.length() == NTLN.NumCols())
4079 {
4080#endif
4081 delete [] factorsFoundIndex;
4082 delete [] A;
4083 delete [] bounds;
4084 F= 1;
4085 return result;
4086 }
4087 delete [] factorsFoundIndex;
4088 }
4089 else if (l == precision)
4090 {
4092#ifdef HAVE_FLINT
4096 );
4098#else
4102 );
4103#endif
4104 F= bufF;
4105 delete [] zeroOne;
4106 delete [] A;
4107 delete [] bounds;
4108 return result;
4109 }
4110 }
4111 oldL2= l;
4112 l += stepSize;
4113 stepSize *= 2;
4114 if (l > precision)
4115 {
4116 if (!hitBound)
4117 {
4118 hitBound= true;
4119 l= precision;
4120 }
4121 else
4122 break;
4123 }
4124 }
4125
4126#ifdef HAVE_FLINT
4128#endif
4129 delete [] bounds;
4130 delete [] A;
4131 return CFList();
4132}
4133#endif
4134
4135#ifdef HAVE_NTL // mat_zz_pE
4136CFList
4138 const Variable& alpha, int precision)
4139{
4140 int d;
4141 bool isIrreducible= false;
4142 int* bounds= computeBounds (F, d, isIrreducible);
4143 if (isIrreducible)
4144 {
4145 delete [] bounds;
4146 return CFList (F);
4147 }
4148 CFArray * A= new CFArray [factors.length()];
4151 {
4153 zz_p::init (getCharacteristic());
4154 }
4156 zz_pE::init (NTLMipo);
4158 ident (NTLN, factors.length());
4159 int minBound= bounds[0];
4160 for (int i= 1; i < d; i++)
4161 {
4162 if (bounds[i] != 0)
4164 }
4165 int l= tmin (2*(minBound + 1), precision);
4166 int oldL= l/2;
4167 int stepSize= 2;
4168 bool useOldQs= false;
4169 bool hitBound= false;
4171 CFMatrix C;
4172 CFArray buf;
4174 Variable y= F.mvar();
4176 while (l <= precision)
4177 {
4178 j= factors;
4179 truncF= mod (F, power (y, l));
4180 if (useOldQs)
4181 {
4182 for (int i= 0; i < factors.length(); i++, j++)
4183 A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i], bufQ[i]);
4184 }
4185 else
4186 {
4187 for (int i= 0; i < factors.length(); i++, j++)
4188 A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ [i]);
4189 }
4190 useOldQs= true;
4191 for (int i= 0; i < d; i++)
4192 {
4193 if (bounds [i] + 1 <= l/2)
4194 {
4195 int k= tmin (bounds [i] + 1, l/2);
4196 C= CFMatrix (l - k, factors.length());
4197 for (int ii= 0; ii < factors.length(); ii++)
4198 {
4199 if (A[ii].size() - 1 >= i)
4200 {
4201 buf= getCoeffs (A[ii] [i], k);
4202 writeInMatrix (C, buf, ii + 1, 0);
4203 }
4204 }
4206 NTLK= (*NTLC)*NTLN;
4207 transpose (NTLK, NTLK);
4208 kernel (NTLK, NTLK);
4209 transpose (NTLK, NTLK);
4210 NTLN *= NTLK;
4211 delete NTLC;
4212
4213 if (NTLN.NumCols() == 1)
4214 {
4215 delete [] A;
4216 delete [] bounds;
4217 return CFList (F);
4218 }
4219 }
4220 }
4221
4222 if (isReduced (NTLN) || l == precision)
4223 {
4228 NTLN
4229 );
4230 if (result.length() != NTLN.NumCols() && l != precision)
4232 if (result.length() == NTLN.NumCols())
4233 {
4234 delete [] zeroOne;
4235 delete [] A;
4236 delete [] bounds;
4237 return result;
4238 }
4239 if (l == precision)
4240 {
4241 delete [] zeroOne;
4242 delete [] A;
4243 delete [] bounds;
4244 return Union (result, factors);
4245 }
4246 delete [] zeroOne;
4247 }
4248 oldL= l;
4249 l += stepSize;
4250 stepSize *= 2;
4251 if (l > precision)
4252 {
4253 if (!hitBound)
4254 {
4255 l= precision;
4256 hitBound= true;
4257 }
4258 else
4259 break;
4260 }
4261 }
4262 delete [] bounds;
4263 delete [] A;
4264 return CFList();
4265}
4266#endif
4267
4268#ifdef HAVE_NTL // logarithmicDerivative
4269CFList
4271 int oldNumCols, int oldL, const Variable& alpha,
4272 int precision, const CanonicalForm& eval
4273 )
4274{
4275 int d;
4276 bool isIrreducible= false;
4277 Variable y= F.mvar();
4278 int* bounds= computeBounds (F, d, isIrreducible);
4279 if (isIrreducible)
4280 {
4281 delete [] bounds;
4282 CanonicalForm G= F;
4283 F= 1;
4284 return CFList (G (y-eval,y));
4285 }
4287 CFArray * A= new CFArray [factors.length()];
4289#ifdef HAVE_FLINT
4292 for (long i=factors.length()-1; i >= 0; i--)
4293 nmod_mat_entry (FLINTN, i, i)= 1;
4294#else
4295 mat_zz_p NTLN;
4296 ident (NTLN, factors.length());
4297#endif
4298 int minBound= bounds[0];
4299 for (int i= 1; i < d; i++)
4300 {
4301 if (bounds[i] != 0)
4303 }
4304 int l= tmax (2*(minBound + 1), oldL);
4305 int oldL2= l/2;
4306 int stepSize= 2;
4307 bool useOldQs= false;
4308 bool hitBound= false;
4310 CFMatrix C;
4311#ifdef HAVE_FLINT
4312 long rank;
4314#else
4315 mat_zz_p* NTLC, NTLK;
4316#endif
4317 CFArray buf;
4319 while (l <= precision)
4320 {
4321 j= factors;
4322 truncF= mod (F, power (y, l));
4323 if (useOldQs)
4324 {
4325 for (int i= 0; i < factors.length(); i++, j++)
4326 A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL2, bufQ[i],
4327 bufQ[i]
4328 );
4329 }
4330 else
4331 {
4332 for (int i= 0; i < factors.length(); i++, j++)
4333 A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ [i]);
4334 }
4335 useOldQs= true;
4336 for (int i= 0; i < d; i++)
4337 {
4338 if (bounds [i] + 1 <= l/2)
4339 {
4340 int k= tmin (bounds [i] + 1, l/2);
4341 C= CFMatrix ((l - k)*extensionDeg, factors.length());
4342 for (int ii= 0; ii < factors.length(); ii++)
4343 {
4344 if (A[ii].size() - 1 >= i)
4345 {
4346 buf= getCoeffs (A[ii] [i], k, alpha);
4347 writeInMatrix (C, buf, ii + 1, 0);
4348 }
4349 }
4350#ifdef HAVE_FLINT
4365 nmod_mat_mul (FLINTN, FLINTC, FLINTK); //no aliasing allowed!!
4366
4370#else
4372 NTLK= (*NTLC)*NTLN;
4373 transpose (NTLK, NTLK);
4374 kernel (NTLK, NTLK);
4375 transpose (NTLK, NTLK);
4376 NTLN *= NTLK;
4377 delete NTLC;
4378#endif
4379#ifdef HAVE_FLINT
4380 if (nmod_mat_ncols (FLINTN) == 1)
4381 {
4383#else
4384 if (NTLN.NumCols() == 1)
4385 {
4386#endif
4387 delete [] A;
4388 delete [] bounds;
4389 CanonicalForm G= F;
4390 F= 1;
4391 return CFList (G (y-eval,y));
4392 }
4393 }
4394 }
4395
4396#ifdef HAVE_FLINT
4398 {
4399 if (isReduced (FLINTN))
4400 {
4401 int * factorsFoundIndex= new int [nmod_mat_ncols (FLINTN)];
4402 for (long i= 0; i < nmod_mat_ncols (FLINTN); i++)
4403#else
4404 if (NTLN.NumCols() < oldNumCols - factorsFound)
4405 {
4406 if (isReduced (NTLN))
4407 {
4408 int * factorsFoundIndex= new int [NTLN.NumCols()];
4409 for (long i= 0; i < NTLN.NumCols(); i++)
4410#endif
4411 factorsFoundIndex[i]= 0;
4412 int factorsFound2= 0;
4413 CFList result;
4415#ifdef HAVE_FLINT
4418 );
4419 if (result.length() == nmod_mat_ncols (FLINTN))
4420 {
4422#else
4424 factorsFoundIndex, NTLN, eval, false
4425 );
4426 if (result.length() == NTLN.NumCols())
4427 {
4428#endif
4429 delete [] factorsFoundIndex;
4430 delete [] A;
4431 delete [] bounds;
4432 F= 1;
4433 return result;
4434 }
4435 delete [] factorsFoundIndex;
4436 }
4437 else if (l == precision)
4438 {
4440#ifdef HAVE_FLINT
4444#else
4447#endif
4448 F= bufF;
4449 delete [] zeroOne;
4450 delete [] A;
4451 delete [] bounds;
4452 return result;
4453 }
4454 }
4455 oldL2= l;
4456 l += stepSize;
4457 stepSize *= 2;
4458 if (l > precision)
4459 {
4460 if (!hitBound)
4461 {
4462 hitBound= true;
4463 l= precision;
4464 }
4465 else
4466 break;
4467 }
4468 }
4469#ifdef HAVE_FLINT
4471#endif
4472 delete [] bounds;
4473 delete [] A;
4474 return CFList();
4475}
4476#endif
4477
4478#ifdef HAVE_NTL // logarithmicDerivative
4479#ifdef HAVE_FLINT
4480CFList
4482 l, int d, int* bounds, CFArray& bufQ, nmod_mat_t FLINTN,
4483 const CanonicalForm& eval
4484 )
4485#else
4486CFList
4488 l, int d, int* bounds, CFArray& bufQ, mat_zz_p& NTLN,
4489 const CanonicalForm& eval
4490 )
4491#endif
4492{
4493 CFList result= CFList();
4494 CFArray * A= new CFArray [factors.length()];
4495 int oldL2= oldL/2;
4496 bool hitBound= false;
4497#ifdef HAVE_FLINT
4498 if (nmod_mat_nrows (FLINTN) != factors.length()) //refined factors
4499 {
4502 for (long i=factors.length()-1; i >= 0; i--)
4503 nmod_mat_entry (FLINTN, i, i)= 1;
4505 }
4506#else
4507 if (NTLN.NumRows() != factors.length()) //refined factors
4508 {
4509 ident (NTLN, factors.length());
4511 }
4512#endif
4513 bool useOldQs= false;
4515 CFMatrix C;
4516 CFArray buf;
4517#ifdef HAVE_FLINT
4518 long rank;
4520#else
4521 mat_zz_p* NTLC, NTLK;
4522#endif
4525 Variable y= F.mvar();
4526 while (oldL <= l)
4527 {
4528 j= factors;
4529 truncF= mod (F, power (y, oldL));
4530 if (useOldQs)
4531 {
4532 for (int i= 0; i < factors.length(); i++, j++)
4533 A[i]= logarithmicDerivative (truncF, j.getItem(), oldL, oldL2, bufQ[i],
4534 bufQ[i]
4535 );
4536 }
4537 else
4538 {
4539 for (int i= 0; i < factors.length(); i++, j++)
4540 A[i]= logarithmicDerivative (truncF, j.getItem(), oldL, bufQ [i]);
4541 }
4542 useOldQs= true;
4543
4544 for (int i= 0; i < d; i++)
4545 {
4546 if (bounds [i] + 1 <= oldL/2)
4547 {
4548 int k= tmin (bounds [i] + 1, oldL/2);
4549 C= CFMatrix (oldL - k, factors.length());
4550 for (int ii= 0; ii < factors.length(); ii++)
4551 {
4552 if (A[ii].size() - 1 >= i)
4553 {
4554 buf= getCoeffs (A[ii] [i], k);
4555 writeInMatrix (C, buf, ii + 1, 0);
4556 }
4557 }
4558#ifdef HAVE_FLINT
4573 nmod_mat_mul (FLINTN, FLINTC, FLINTK); //no aliasing allowed!!
4574
4578#else
4580 NTLK= (*NTLC)*NTLN;
4581 transpose (NTLK, NTLK);
4582 kernel (NTLK, NTLK);
4583 transpose (NTLK, NTLK);
4584 NTLN *= NTLK;
4585 delete NTLC;
4586#endif
4587#ifdef HAVE_FLINT
4588 if (nmod_mat_ncols (FLINTN) == 1)
4589#else
4590 if (NTLN.NumCols() == 1)
4591#endif
4592 {
4593 delete [] A;
4594 return CFList (F (y-eval,y));
4595 }
4596 }
4597 }
4598#ifdef HAVE_FLINT
4599 if (nmod_mat_ncols (FLINTN) == 1)
4600#else
4601 if (NTLN.NumCols() == 1)
4602#endif
4603 {
4604 delete [] A;
4605 return CFList (F (y-eval,y));
4606 }
4607 int * zeroOneVecs;
4608#ifdef HAVE_FLINT
4610#else
4612#endif
4613 bufF= F;
4615#ifdef HAVE_FLINT
4617#else
4619#endif
4620 delete [] zeroOneVecs;
4621 if (degree (bufF) + 1 + degree (LC (bufF, 1)) < oldL && result.length() > 0)
4622 {
4623 F= bufF;
4625 delete [] A;
4626 return result;
4627 }
4628
4629 result= CFList();
4630 oldL2= oldL;
4631 oldL *= 2;
4632 if (oldL > l)
4633 {
4634 if (!hitBound)
4635 {
4636 oldL= l;
4637 hitBound= true;
4638 }
4639 else
4640 break;
4641 }
4642 }
4643 delete [] A;
4644 return result;
4645}
4646#endif
4647
4648#ifdef HAVE_NTL // mat_zz_pE
4649CFList
4651 l, int d, int* bounds, CFArray& bufQ, mat_zz_pE& NTLN,
4652 const CanonicalForm& eval
4653 )
4654{
4655 CFList result= CFList();
4656 CFArray * A= new CFArray [factors.length()];
4657 int oldL2= oldL/2;
4658 bool hitBound= false;
4659 bool useOldQs= false;
4660 if (NTLN.NumRows() != factors.length()) //refined factors
4661 ident (NTLN, factors.length());
4663 CFMatrix C;
4664 CFArray buf;
4668 Variable y= F.mvar();
4669 while (oldL <= l)
4670 {
4671 j= factors;
4672 truncF= mod (F, power (y, oldL));
4673 if (useOldQs)
4674 {
4675 for (int i= 0; i < factors.length(); i++, j++)
4676 A[i]= logarithmicDerivative (truncF, j.getItem(), oldL, oldL2, bufQ[i],
4677 bufQ[i]
4678 );
4679 }
4680 else
4681 {
4682 for (int i= 0; i < factors.length(); i++, j++)
4683 A[i]= logarithmicDerivative (truncF, j.getItem(), oldL, bufQ [i]);
4684 }
4685 useOldQs= true;
4686
4687 for (int i= 0; i < d; i++)
4688 {
4689 if (bounds [i] + 1 <= oldL/2)
4690 {
4691 int k= tmin (bounds [i] + 1, oldL/2);
4692 C= CFMatrix (oldL - k, factors.length());
4693 for (int ii= 0; ii < factors.length(); ii++)
4694 {
4695 if (A[ii].size() - 1 >= i)
4696 {
4697 buf= getCoeffs (A[ii] [i], k);
4698 writeInMatrix (C, buf, ii + 1, 0);
4699 }
4700 }
4702 NTLK= (*NTLC)*NTLN;
4703 transpose (NTLK, NTLK);
4704 kernel (NTLK, NTLK);
4705 transpose (NTLK, NTLK);
4706 NTLN *= NTLK;
4707 delete NTLC;
4708
4709 if (NTLN.NumCols() == 1)
4710 {
4711 delete [] A;
4712 return CFList (F (y-eval,y));
4713 }
4714 }
4715 }
4716 if (NTLN.NumCols() == 1)
4717 {
4718 delete [] A;
4719 return CFList (F (y-eval,y));
4720 }
4721
4722 int * zeroOneVecs;
4724 bufF= F;
4727 delete [] zeroOneVecs;
4728 if (degree (bufF) + 1 + degree (LC (bufF, 1)) < l && result.length() > 0)
4729 {
4730 F= bufF;
4732 delete [] A;
4733 return result;
4734 }
4735
4736 result= CFList();
4737 oldL2= oldL;
4738 oldL *= 2;
4739 if (oldL > l)
4740 {
4741 if (!hitBound)
4742 {
4743 oldL= l;
4744 hitBound= true;
4745 }
4746 else
4747 break;
4748 }
4749 }
4750 delete [] A;
4751 return result;
4752}
4753#endif
4754
4755//over field extension
4756#ifdef HAVE_NTL // logarithmicDerivative
4757#ifdef HAVE_FLINT
4758CFList
4760 int* bounds, CFArray& bufQ, nmod_mat_t FLINTN, const
4762 CFList& source, CFList& dest
4763 )
4764#else
4765CFList
4766extIncreasePrecision (CanonicalForm& F, CFList& factors, int oldL, int l, int d,
4767 int* bounds, CFArray& bufQ, mat_zz_p& NTLN, const
4769 CFList& source, CFList& dest
4770 )
4771#endif
4772{
4773 CFList result= CFList();
4774 CFArray * A= new CFArray [factors.length()];
4775 int oldL2= oldL/2; //be careful
4776 bool hitBound= false;
4777 bool useOldQs= false;
4779 int degMipo= degree (getMipo (info.getAlpha()));
4780 Variable alpha= info.getAlpha();
4781
4782 Variable gamma= info.getBeta();
4783 CanonicalForm primElemAlpha= info.getGamma();
4785#ifdef HAVE_FLINT
4788 for (long i=factors.length()-1; i >= 0; i--)
4789 nmod_mat_entry (FLINTN, i, i)= 1;
4790#else
4791 if (NTLN.NumRows() != factors.length()) //refined factors
4792 ident (NTLN, factors.length());
4793#endif
4794 Variable y= F.mvar();
4797 CFMatrix Mat, C;
4799 CFArray buf;
4800#ifdef HAVE_FLINT
4801 long rank;
4803#else
4805#endif
4807 while (oldL <= l)
4808 {
4809 j= factors;
4810 if (GF)
4812
4813 powX= power (y-gamma, oldL);
4815 for (int i= 0; i < oldL*degMipo; i++)
4816 {
4817 imBasis= mod (power (y, i), powX);
4818 imBasis= imBasis (power (y, degMipo), y);
4819 imBasis= imBasis (y, gamma);
4820 iter= imBasis;
4821 for (; iter.hasTerms(); iter++)
4822 Mat (iter.exp()+ 1, i+1)= iter.coeff();
4823 }
4824
4825#ifdef HAVE_FLINT
4830#else
4832 *NTLMat= inv (*NTLMat);
4833#endif
4834
4835 if (GF)
4837
4838 truncF= mod (F, power (y, oldL));
4839 if (useOldQs)
4840 {
4841 for (int i= 0; i < factors.length(); i++, j++)
4842 A[i]= logarithmicDerivative (truncF, j.getItem(), oldL, oldL2, bufQ[i],
4843 bufQ[i]);
4844 }
4845 else
4846 {
4847 for (int i= 0; i < factors.length(); i++, j++)
4848 A[i]= logarithmicDerivative (truncF, j.getItem(), oldL, bufQ [i]);
4849 }
4850 useOldQs= true;
4851
4852 for (int i= 0; i < d; i++)
4853 {
4854 if (bounds [i] + 1 <= oldL/2)
4855 {
4856 int k= tmin (bounds [i] + 1, oldL/2);
4857 C= CFMatrix (oldL*degMipo - k, factors.length());
4858 for (int ii= 0; ii < factors.length(); ii++)
4859 {
4860 if (A[ii].size() - 1 >= i)
4861 {
4862 if (GF)
4863 {
4864 A [ii] [i]= A [ii] [i] (y-evaluation, y);
4866 A[ii] [i]= GF2FalphaRep (A[ii] [i], alpha);
4867 if (alpha != gamma)
4869 gamma, source, dest
4870 );
4871#ifdef HAVE_FLINT
4872 buf= getCoeffs (A[ii] [i], k, oldL, degMipo, gamma, 0, FLINTMatInv);
4873#else
4874 buf= getCoeffs (A[ii] [i], k, oldL, degMipo, gamma, 0, *NTLMat);
4875#endif
4876 }
4877 else
4878 {
4879 A [ii] [i]= A [ii] [i] (y-evaluation, y);
4880 if (alpha != gamma)
4882 gamma, source, dest
4883 );
4884#ifdef HAVE_FLINT
4885 buf= getCoeffs (A[ii] [i], k, oldL, degMipo, gamma, 0, FLINTMatInv);
4886#else
4887 buf= getCoeffs (A[ii] [i], k, oldL, degMipo, gamma, 0, *NTLMat);
4888#endif
4889 }
4890 writeInMatrix (C, buf, ii + 1, 0);
4891 }
4892 if (GF)
4894 }
4895
4896 if (GF)
4898
4899#ifdef HAVE_FLINT
4914 nmod_mat_mul (FLINTN, FLINTC, FLINTK); //no aliasing allowed!!
4915
4919#else
4921 NTLK= (*NTLC)*NTLN;
4922 transpose (NTLK, NTLK);
4923 kernel (NTLK, NTLK);
4924 transpose (NTLK, NTLK);
4925 NTLN *= NTLK;
4926 delete NTLC;
4927#endif
4928
4929 if (GF)
4931
4932#ifdef HAVE_FLINT
4933 if (nmod_mat_ncols (FLINTN) == 1)
4934 {
4937#else
4938 if (NTLN.NumCols() == 1)
4939 {
4940 delete NTLMat;
4941#endif
4942 Variable y= Variable (2);
4943 CanonicalForm tmp= F (y - evaluation, y);
4944 CFList source, dest;
4945 tmp= mapDown (tmp, info, source, dest);
4946 delete [] A;
4947 return CFList (tmp);
4948 }
4949 }
4950 }
4951
4952#ifdef HAVE_FLINT
4955#else
4956 delete NTLMat;
4957#endif
4958
4959#ifdef HAVE_FLINT
4960 if (nmod_mat_ncols (FLINTN) == 1)
4961#else
4962 if (NTLN.NumCols() == 1)
4963#endif
4964 {
4965 Variable y= Variable (2);
4966 CanonicalForm tmp= F (y - evaluation, y);
4967 CFList source, dest;
4968 tmp= mapDown (tmp, info, source, dest);
4969 delete [] A;
4970 return CFList (tmp);
4971 }
4972
4973 int * zeroOneVecs;
4974 bufF= F;
4976#ifdef HAVE_FLINT
4980 );
4981#else
4985 );
4986#endif
4987 delete [] zeroOneVecs;
4988 if (degree (bufF) + 1 + degree (LC (bufF, 1)) < l && result.length() > 0)
4989 {
4990 F= bufF;
4992 return result;
4993 }
4994
4995 result= CFList();
4996 oldL2= oldL;
4997 oldL *= 2;
4998 if (oldL > l)
4999 {
5000 if (!hitBound)
5001 {
5002 oldL= l;
5003 hitBound= true;
5004 }
5005 else
5006 break;
5007 }
5008 }
5009 delete [] A;
5010 return result;
5011}
5012#endif
5013
5014#ifdef HAVE_NTL // logarithmicDerivative
5015#ifdef HAVE_FLINT
5016CFList
5018 int d, int* bounds, CFArray& bufQ, nmod_mat_t FLINTN,
5019 const Variable& alpha, const CanonicalForm& eval
5020 )
5021#else
5022CFList
5024 int d, int* bounds, CFArray& bufQ, mat_zz_p& NTLN,
5025 const Variable& alpha, const CanonicalForm& eval
5026 )
5027#endif
5028{
5029 CFList result= CFList();
5030 CFArray * A= new CFArray [factors.length()];
5032 int oldL2= oldL/2;
5033 bool hitBound= false;
5034 bool useOldQs= false;
5035#ifdef HAVE_FLINT
5036 if (nmod_mat_nrows (FLINTN) != factors.length()) //refined factors
5037 {
5040 for (long i=factors.length()-1; i >= 0; i--)
5041 nmod_mat_entry (FLINTN, i, i)= 1;
5042 }
5043#else
5044 if (NTLN.NumRows() != factors.length()) //refined factors
5045 ident (NTLN, factors.length());
5046#endif
5048 CFMatrix C;
5049 CFArray buf;
5050#ifdef HAVE_FLINT
5051 long rank;
5053#else
5054 mat_zz_p* NTLC, NTLK;
5055#endif
5058 Variable y= F.mvar();
5059 while (oldL <= l)
5060 {
5061 j= factors;
5062 truncF= mod (F, power (y, oldL));
5063 if (useOldQs)
5064 {
5065 for (int i= 0; i < factors.length(); i++, j++)
5066 A[i]= logarithmicDerivative (truncF, j.getItem(), oldL, oldL2, bufQ[i],
5067 bufQ[i]
5068 );
5069 }
5070 else
5071 {
5072 for (int i= 0; i < factors.length(); i++, j++)
5073 A[i]= logarithmicDerivative (truncF, j.getItem(), oldL, bufQ [i]);
5074 }
5075 useOldQs= true;
5076
5077 for (int i= 0; i < d; i++)
5078 {
5079 if (bounds [i] + 1 <= oldL/2)
5080 {
5081 int k= tmin (bounds [i] + 1, oldL/2);
5083 for (int ii= 0; ii < factors.length(); ii++)
5084 {
5085 if (A[ii].size() - 1 >= i)
5086 {
5087 buf= getCoeffs (A[ii] [i], k, alpha);
5088 writeInMatrix (C, buf, ii + 1, 0);
5089 }
5090 }
5091#ifdef HAVE_FLINT
5106 nmod_mat_mul (FLINTN, FLINTC, FLINTK); //no aliasing allowed!!
5107
5111#else
5113 NTLK= (*NTLC)*NTLN;
5114 transpose (NTLK, NTLK);
5115 kernel (NTLK, NTLK);
5116 transpose (NTLK, NTLK);
5117 NTLN *= NTLK;
5118 delete NTLC;
5119#endif
5120#ifdef HAVE_FLINT
5121 if (nmod_mat_ncols (FLINTN) == 1)
5122#else
5123 if (NTLN.NumCols() == 1)
5124#endif
5125 {
5126 delete [] A;
5127 return CFList (F(y-eval,y));
5128 }
5129 }
5130 }
5131
5132 int * zeroOneVecs;
5133#ifdef HAVE_FLINT
5135#else
5137#endif
5138
5139 bufF= F;
5141#ifdef HAVE_FLINT
5143#else
5145#endif
5146 delete [] zeroOneVecs;
5147 if (degree (bufF) + 1 + degree (LC (bufF, 1)) < l && result.length() > 0)
5148 {
5149 F= bufF;
5151 delete [] A;
5152 return result;
5153 }
5154
5155 result= CFList();
5156 oldL2= oldL;
5157 oldL *= 2;
5158 if (oldL > l)
5159 {
5160 if (!hitBound)
5161 {
5162 oldL= l;
5163 hitBound= true;
5164 }
5165 else
5166 break;
5167 }
5168 }
5169 delete [] A;
5170 return result;
5171}
5172#endif
5173
5174#ifdef HAVE_NTL // logarithmicDerivative
5175#ifdef HAVE_FLINT
5176CFList
5178 factors, int l, int liftBound, int d, int*
5181 const CanonicalForm& eval
5182 )
5183#else
5184CFList
5186 factors, int l, int liftBound, int d, int*
5189 const CanonicalForm& eval
5190 )
5191#endif
5192{
5193 CanonicalForm LCF= LC (F, 1);
5194 CFList result;
5195 bool irreducible= false;
5198 CFArray *A = new CFArray [bufFactors.length()];
5199 bool useOldQs= false;
5200 bool hitBound= false;
5201 int oldL= l;
5202 int stepSize= 8; //TODO choose better step size?
5203 l += tmax (tmin (8, degree (F) + 1 + degree (LC (F, 1))-l), 2);
5204#ifdef HAVE_FLINT
5205 if (nmod_mat_nrows (FLINTN) != factors.length()) //refined factors
5206 {
5209 for (long i=factors.length()-1; i >= 0; i--)
5210 nmod_mat_entry (FLINTN, i, i)= 1;
5211 }
5212#else
5213 if (NTLN.NumRows() != factors.length()) //refined factors
5214 ident (NTLN, factors.length());
5215#endif
5217 CFMatrix C;
5218 CFArray buf;
5219#ifdef HAVE_FLINT
5220 long rank;
5222#else
5223 mat_zz_p* NTLC, NTLK;
5224#endif
5226 Variable y= F.mvar();
5227 while (l <= liftBound)
5228 {
5231 j= bufFactors;
5232 truncF= mod (F, power (y, l));
5233 if (useOldQs)
5234 {
5235 for (int i= 0; i < bufFactors.length(); i++, j++)
5236 A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
5237 bufQ[i]);
5238 }
5239 else
5240 {
5241 for (int i= 0; i < bufFactors.length(); i++, j++)
5242 A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ [i]);
5243 }
5244 for (int i= 0; i < d; i++)
5245 {
5246 if (bounds [i] + 1 <= l/2)
5247 {
5248 int k= tmin (bounds [i] + 1, l/2);
5249 C= CFMatrix (l - k, bufFactors.length());
5250 for (int ii= 0; ii < bufFactors.length(); ii++)
5251 {
5252 if (A[ii].size() - 1 >= i)
5253 {
5254 buf= getCoeffs (A[ii] [i], k);
5255 writeInMatrix (C, buf, ii + 1, 0);
5256 }
5257 }
5258#ifdef HAVE_FLINT
5273 nmod_mat_mul (FLINTN, FLINTC, FLINTK); //no aliasing allowed!!
5274
5278#else
5280 NTLK= (*NTLC)*NTLN;
5281 transpose (NTLK, NTLK);
5282 kernel (NTLK, NTLK);
5283 transpose (NTLK, NTLK);
5284 NTLN *= NTLK;
5285 delete NTLC;
5286#endif
5287#ifdef HAVE_FLINT
5288 if (nmod_mat_ncols (FLINTN) == 1)
5289#else
5290 if (NTLN.NumCols() == 1)
5291#endif
5292 {
5293 irreducible= true;
5294 break;
5295 }
5296 }
5297 }
5298
5299#ifdef HAVE_FLINT
5300 if (nmod_mat_ncols (FLINTN) == 1)
5301#else
5302 if (NTLN.NumCols() == 1)
5303#endif
5304 {
5305 irreducible= true;
5306 break;
5307 }
5308
5309#ifdef HAVE_FLINT
5311#else
5313#endif
5314 bufF= F;
5316#ifdef HAVE_FLINT
5318#else
5320#endif
5321 delete [] zeroOneVecs;
5322 if (result.length() > 0 && degree (bufF) + 1 + degree (LC (bufF, 1)) <= l)
5323 {
5324 F= bufF;
5326 delete [] A;
5327 return result;
5328 }
5329 else
5330 {
5331 bufF= F;
5333 }
5334
5335#ifdef HAVE_FLINT
5336 if (isReduced (FLINTN))
5337#else
5338 if (isReduced (NTLN))
5339#endif
5340 {
5341 int factorsFound= 0;
5342 bufF= F;
5343#ifdef HAVE_FLINT
5344 int* factorsFoundIndex= new int [nmod_mat_ncols (FLINTN)];
5345 for (long i= 0; i < nmod_mat_ncols (FLINTN); i++)
5346#else
5347 int* factorsFoundIndex= new int [NTLN.NumCols()];
5348 for (long i= 0; i < NTLN.NumCols(); i++)
5349#endif
5350 factorsFoundIndex[i]= 0;
5351#ifdef HAVE_FLINT
5352 if (l < liftBound)
5355 );
5356 else
5359 FLINTN, eval, false
5360 );
5361
5363#else
5364 if (l < liftBound)
5366 factorsFoundIndex, NTLN, eval, false
5367 );
5368 else
5371 NTLN, eval, false
5372 );
5373
5374 if (NTLN.NumCols() == result.length())
5375#endif
5376 {
5377 delete [] A;
5378 delete [] factorsFoundIndex;
5379 return result;
5380 }
5381 delete [] factorsFoundIndex;
5382 }
5383 result= CFList();
5384 oldL= l;
5385 stepSize *= 2;
5386 l += stepSize;
5387 if (l > liftBound)
5388 {
5389 if (!hitBound)
5390 {
5391 l= liftBound;
5392 hitBound= true;
5393 }
5394 else
5395 break;
5396 }
5397 }
5398 if (irreducible)
5399 {
5400 delete [] A;
5401 return CFList (F (y-eval,y));
5402 }
5403 delete [] A;
5405 return CFList();
5406}
5407#endif
5408
5409//Fq
5410#ifdef HAVE_NTL
5411CFList
5413 factors, int l, int liftBound, int d, int*
5416 const CanonicalForm& eval
5417 )
5418{
5419 CanonicalForm LCF= LC (F, 1);
5420 CFList result;
5421 bool irreducible= false;
5424 CFArray *A = new CFArray [bufFactors.length()];
5425 bool useOldQs= false;
5426 bool hitBound= false;
5427 int oldL= l;
5428 int stepSize= 8; //TODO choose better step size?
5429 l += tmax (tmin (8, degree (F) + 1 + degree (LC (F, 1))-l), 2);
5430 if (NTLN.NumRows() != factors.length()) //refined factors
5431 ident (NTLN, factors.length());
5433 CFArray buf;
5436 Variable y= F.mvar();
5437 while (l <= liftBound)
5438 {
5441 j= bufFactors;
5442 truncF= mod (F, power (y, l));
5443 if (useOldQs)
5444 {
5445 for (int i= 0; i < bufFactors.length(); i++, j++)
5446 A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
5447 bufQ[i]);
5448 }
5449 else
5450 {
5451 for (int i= 0; i < bufFactors.length(); i++, j++)
5452 A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ [i]);
5453 }
5454 for (int i= 0; i < d; i++)
5455 {
5456 if (bounds [i] + 1 <= l/2)
5457 {
5458 int k= tmin (bounds [i] + 1, l/2);
5460 for (int ii= 0; ii < bufFactors.length(); ii++)
5461 {
5462 if (A[ii].size() - 1 >= i)
5463 {
5464 buf= getCoeffs (A[ii] [i], k);
5465 writeInMatrix (C, buf, ii + 1, 0);
5466 }
5467 }
5469 NTLK= (*NTLC)*NTLN;
5470 transpose (NTLK, NTLK);
5471 kernel (NTLK, NTLK);
5472 transpose (NTLK, NTLK);
5473 NTLN *= NTLK;
5474 delete NTLC;
5475 if (NTLN.NumCols() == 1)
5476 {
5477 irreducible= true;
5478 break;
5479 }
5480 }
5481 }
5482 if (NTLN.NumCols() == 1)
5483 {
5484 irreducible= true;
5485 break;
5486 }
5487
5489 bufF= F;
5492 delete [] zeroOneVecs;
5493 if (result.length() > 0 && degree (bufF) + 1 + degree (LC (bufF, 1)) <= l)
5494 {
5495 F= bufF;
5497 delete [] A;
5498 return result;
5499 }
5500 else
5501 {
5502 bufF= F;
5504 }
5505
5506 if (isReduced (NTLN))
5507 {
5508 int factorsFound= 0;
5509 bufF= F;
5510 int* factorsFoundIndex= new int [NTLN.NumCols()];
5511 for (long i= 0; i < NTLN.NumCols(); i++)
5512 factorsFoundIndex[i]= 0;
5513 if (l < liftBound)
5515 factorsFoundIndex, NTLN, eval, false
5516 );
5517 else
5520 NTLN, eval, false
5521 );
5522 if (NTLN.NumCols() == result.length())
5523 {
5524 delete [] A;
5525 delete [] factorsFoundIndex;
5526 return result;
5527 }
5528 delete [] factorsFoundIndex;
5529 }
5530 result= CFList();
5531 oldL= l;
5532 stepSize *= 2;
5533 l += stepSize;
5534 if (l > liftBound)
5535 {
5536 if (!hitBound)
5537 {
5538 l= liftBound;
5539 hitBound= true;
5540 }
5541 else
5542 break;
5543 }
5544 }
5545 if (irreducible)
5546 {
5547 delete [] A;
5548 return CFList (F (y-eval,y));
5549 }
5550 delete [] A;
5552 return CFList();
5553}
5554#endif
5555
5556//over field extension
5557#ifdef HAVE_NTL // logarithmicDerivative
5558#ifdef HAVE_FLINT
5559CFList
5561 int liftBound, int d, int* bounds,
5564 const CanonicalForm& evaluation, const
5566 CFList& dest
5567 )
5568#else
5569CFList
5571 int liftBound, int d, int* bounds,
5574 const CanonicalForm& evaluation, const
5576 CFList& dest
5577 )
5578#endif
5579{
5580 CanonicalForm LCF= LC (F, 1);
5581 CFList result;
5582 bool irreducible= false;
5585 CFArray *A = new CFArray [bufFactors.length()];
5586 bool useOldQs= false;
5587 bool hitBound= false;
5589 int degMipo= degree (getMipo (info.getAlpha()));
5590 Variable alpha= info.getAlpha();
5591 int oldL= l; //be careful
5592 int stepSize= 8;
5593 l += tmax (tmin (8, degree (F) + 1 + degree (LC (F, 1))-l),2);
5594 Variable gamma= info.getBeta();
5595 CanonicalForm primElemAlpha= info.getGamma();
5597#ifdef HAVE_FLINT
5600 for (long i=factors.length()-1; i >= 0; i--)
5601 nmod_mat_entry (FLINTN, i, i)= 1;
5602#else
5603 if (NTLN.NumRows() != factors.length()) //refined factors
5604 ident (NTLN, factors.length());
5605#endif
5606 Variable y= F.mvar();
5608 CFMatrix Mat, C;
5610#ifdef HAVE_FLINT
5611 long rank;
5613#else
5615#endif
5617 CFArray buf;
5618 while (l <= liftBound)
5619 {
5622
5623 if (GF)
5625
5626 powX= power (y-gamma, l);
5628 for (int i= 0; i < l*degMipo; i++)
5629 {
5630
5631 imBasis= mod (power (y, i), powX);
5632 imBasis= imBasis (power (y, degMipo), y);
5633 imBasis= imBasis (y, gamma);
5634 iter= imBasis;
5635 for (; iter.hasTerms(); iter++)
5636 Mat (iter.exp()+ 1, i+1)= iter.coeff();
5637 }
5638
5639#ifdef HAVE_FLINT
5644#else
5646 *NTLMat= inv (*NTLMat);
5647#endif
5648
5649 if (GF)
5651
5652 j= bufFactors;
5653 truncF= mod (F, power (y, l));
5654 if (useOldQs)
5655 {
5656 for (int i= 0; i < bufFactors.length(); i++, j++)
5657 A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
5658 bufQ[i]);
5659 }
5660 else
5661 {
5662 for (int i= 0; i < bufFactors.length(); i++, j++)
5663 A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ [i]);
5664 }
5665 for (int i= 0; i < d; i++)
5666 {
5667 if (bounds [i] + 1 <= l/2)
5668 {
5669 int k= tmin (bounds [i] + 1, l/2);
5670 C= CFMatrix (l*degMipo - k, bufFactors.length());
5671 for (int ii= 0; ii < bufFactors.length(); ii++)
5672 {
5673 if (A[ii].size() - 1 >= i)
5674 {
5675 if (GF)
5676 {
5677 A [ii] [i]= A [ii] [i] (y-evaluation, y);
5679 A[ii] [i]= GF2FalphaRep (A[ii] [i], alpha);
5680 if (alpha != gamma)
5682 gamma, source, dest
5683 );
5684#ifdef HAVE_FLINT
5685 buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, FLINTMatInv);
5686#else
5687 buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, *NTLMat);
5688#endif
5689 }
5690 else
5691 {
5692 A [ii] [i]= A [ii] [i] (y-evaluation, y);
5693 if (alpha != gamma)
5695 gamma, source, dest
5696 );
5697#ifdef HAVE_FLINT
5698 buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, FLINTMatInv);
5699#else
5700 buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, *NTLMat);
5701#endif
5702 }
5703 writeInMatrix (C, buf, ii + 1, 0);
5704 }
5705 if (GF)
5707 }
5708
5709 if (GF)
5711
5712#ifdef HAVE_FLINT
5727 nmod_mat_mul (FLINTN, FLINTC, FLINTK); //no aliasing allowed!!
5728
5732#else
5734 NTLK= (*NTLC)*NTLN;
5735 transpose (NTLK, NTLK);
5736 kernel (NTLK, NTLK);
5737 transpose (NTLK, NTLK);
5738 NTLN *= NTLK;
5739 delete NTLC;
5740#endif
5741
5742 if (GF)
5744
5745#ifdef HAVE_FLINT
5746 if (nmod_mat_ncols (FLINTN) == 1)
5747#else
5748 if (NTLN.NumCols() == 1)
5749#endif
5750 {
5751 irreducible= true;
5752 break;
5753 }
5754 }
5755 }
5756
5757#ifdef HAVE_FLINT
5760 if (nmod_mat_ncols (FLINTN) == 1)
5761#else
5762 delete NTLMat;
5763 if (NTLN.NumCols() == 1)
5764#endif
5765 {
5766 irreducible= true;
5767 break;
5768 }
5769
5770 bufF= F;
5772#ifdef HAVE_FLINT
5776 );
5777#else
5781 );
5782#endif
5783 delete [] zeroOneVecs;
5784 if (result.length() > 0 && degree (bufF) + 1 + degree (LC (bufF, 1)) <= l)
5785 {
5786 F= bufF;
5788 delete [] A;
5789 return result;
5790 }
5791 else
5792 {
5793 bufF= F;
5795 }
5796
5797#ifdef HAVE_FLINT
5798 if (isReduced (FLINTN))
5799#else
5800 if (isReduced (NTLN))
5801#endif
5802 {
5803 int factorsFound= 0;
5804 bufF= F;
5805#ifdef HAVE_FLINT
5806 int* factorsFoundIndex= new int [nmod_mat_ncols (FLINTN)];
5807 for (long i= 0; i < nmod_mat_ncols (FLINTN); i++)
5808#else
5809 int* factorsFoundIndex= new int [NTLN.NumCols()];
5810 for (long i= 0; i < NTLN.NumCols(); i++)
5811#endif
5812 factorsFoundIndex[i]= 0;
5813#ifdef HAVE_FLINT
5814 if (l < degree (bufF) + 1 + degree (LCF))
5817 );
5818 else
5821 FLINTN, false, info, evaluation
5822 );
5824#else
5825 if (l < degree (bufF) + 1 + degree (LCF))
5828 );
5829 else
5832 NTLN, false, info, evaluation
5833 );
5834 if (NTLN.NumCols() == result.length())
5835#endif
5836 {
5837 delete [] A;
5838 delete [] factorsFoundIndex;
5839 return result;
5840 }
5841 delete [] factorsFoundIndex;
5842 }
5843 result= CFList();
5844 oldL= l;
5845 stepSize *= 2;
5846 l += stepSize;
5847 if (l > liftBound)
5848 {
5849 if (!hitBound)
5850 {
5851 l= liftBound;
5852 hitBound= true;
5853 }
5854 else
5855 break;
5856 }
5857 }
5858 if (irreducible)
5859 {
5860 delete [] A;
5861 Variable y= Variable (2);
5862 CanonicalForm tmp= F (y - evaluation, y);
5863 CFList source, dest;
5864 tmp= mapDown (tmp, info, source, dest);
5865 return CFList (tmp);
5866 }
5867 delete [] A;
5869 return CFList();
5870}
5871#endif
5872
5873#ifdef HAVE_NTL // logarithmicDerivative
5874#ifdef HAVE_FLINT
5875CFList
5877 l, int liftBound, int d, int* bounds,
5880 const Variable& alpha,
5881 const CanonicalForm& eval
5882 )
5883#else
5884CFList
5886 l, int liftBound, int d, int* bounds,
5889 const Variable& alpha,
5890 const CanonicalForm& eval
5891 )
5892#endif
5893{
5894 CanonicalForm LCF= LC (F, 1);
5895 CFList result;
5896 bool irreducible= false;
5899 CFArray *A = new CFArray [bufFactors.length()];
5900 bool useOldQs= false;
5902 bool hitBound= false;
5903 int oldL= l;
5904 int stepSize= 8; //TODO choose better step size?
5905 l += tmax (tmin (8, degree (F) + 1 + degree (LC (F, 1))-l), 2);
5906#ifdef HAVE_FLINT
5907 if (nmod_mat_nrows (FLINTN) != factors.length()) //refined factors
5908 {
5911 for (long i=factors.length()-1; i >= 0; i--)
5912 nmod_mat_entry (FLINTN, i, i)= 1;
5913 }
5914#else
5915 if (NTLN.NumRows() != factors.length()) //refined factors
5916 ident (NTLN, factors.length());
5917#endif
5919 CFMatrix C;
5920#ifdef HAVE_FLINT
5921 long rank;
5923#else
5924 mat_zz_p* NTLC, NTLK;
5925#endif
5927 Variable y= F.mvar();
5928 while (l <= liftBound)
5929 {
5932 j= bufFactors;
5933 truncF= mod (F, power (y, l));
5934 if (useOldQs)
5935 {
5936 for (int i= 0; i < bufFactors.length(); i++, j++)
5937 A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
5938 bufQ[i]);
5939 }
5940 else
5941 {
5942 for (int i= 0; i < bufFactors.length(); i++, j++)
5943 A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ [i]);
5944 }
5945 for (int i= 0; i < d; i++)
5946 {
5947 if (bounds [i] + 1 <= l/2)
5948 {
5949 int k= tmin (bounds [i] + 1, l/2);
5951 for (int ii= 0; ii < bufFactors.length(); ii++)
5952 {
5953 CFArray buf;
5954 if (A[ii].size() - 1 >= i)
5955 {
5956 buf= getCoeffs (A[ii] [i], k, alpha);
5957 writeInMatrix (C, buf, ii + 1, 0);
5958 }
5959 }
5960#ifdef HAVE_FLINT
5975 nmod_mat_mul (FLINTN, FLINTC, FLINTK); //no aliasing allowed!!
5976
5980#else
5982 NTLK= (*NTLC)*NTLN;
5983 transpose (NTLK, NTLK);
5984 kernel (NTLK, NTLK);
5985 transpose (NTLK, NTLK);
5986 NTLN *= NTLK;
5987 delete NTLC;
5988#endif
5989#ifdef HAVE_FLINT
5990 if (nmod_mat_ncols (FLINTN) == 1)
5991#else
5992 if (NTLN.NumCols() == 1)
5993#endif
5994 {
5995 irreducible= true;
5996 break;
5997 }
5998 }
5999 }
6000#ifdef HAVE_FLINT
6001 if (nmod_mat_ncols (FLINTN) == 1)
6002#else
6003 if (NTLN.NumCols() == 1)
6004#endif
6005 {
6006 irreducible= true;
6007 break;
6008 }
6009
6010#ifdef HAVE_FLINT
6012#else
6014#endif
6017#ifdef HAVE_FLINT
6019#else
6021#endif
6022 delete [] zeroOneVecs;
6023 if (result.length() > 0 && degree (bufF) + 1 + degree (LC (bufF, 1)) <= l)
6024 {
6025 F= bufF;
6027 delete [] A;
6028 return result;
6029 }
6030 else
6031 {
6032 bufF= F;
6034 }
6035
6036#ifdef HAVE_FLINT
6037 if (isReduced (FLINTN))
6038#else
6039 if (isReduced (NTLN))
6040#endif
6041 {
6042 int factorsFound= 0;
6043 bufF= F;
6044#ifdef HAVE_FLINT
6045 int* factorsFoundIndex= new int [nmod_mat_ncols (FLINTN)];
6046 for (long i= 0; i < nmod_mat_ncols (FLINTN); i++)
6047#else
6048 int* factorsFoundIndex= new int [NTLN.NumCols()];
6049 for (long i= 0; i < NTLN.NumCols(); i++)
6050#endif
6051 factorsFoundIndex[i]= 0;
6052#ifdef HAVE_FLINT
6053 if (l < degree (bufF) + 1 + degree (LCF))
6056 );
6057 else
6060 FLINTN, eval, false
6061 );
6063#else
6064 if (l < degree (bufF) + 1 + degree (LCF))
6066 factorsFoundIndex, NTLN, eval, false
6067 );
6068 else
6071 NTLN, eval, false
6072 );
6073 if (NTLN.NumCols() == result.length())
6074#endif
6075 {
6076 delete [] A;
6077 delete [] factorsFoundIndex;
6078 return result;
6079 }
6080 delete [] factorsFoundIndex;
6081 }
6082 result= CFList();
6083 oldL= l;
6084 stepSize *= 2;
6085 l += stepSize;
6086 if (l > liftBound)
6087 {
6088 if (!hitBound)
6089 {
6090 l= liftBound;
6091 hitBound= true;
6092 }
6093 else
6094 break;
6095 }
6096 }
6097 if (irreducible)
6098 {
6099 delete [] A;
6100 return CFList (F (y-eval,y));
6101 }
6102 delete [] A;
6104 return CFList();
6105}
6106#endif
6107
6108#ifndef HAVE_FLINT
6109void
6110refineAndRestartLift (const CanonicalForm& F, const mat_zz_p& NTLN, int
6113 )
6114{
6116 Variable y= Variable (2);
6117 CanonicalForm LCF= LC (F, 1);
6120 for (long i= 1; i <= NTLN.NumCols(); i++)
6121 {
6122 iter= factors;
6123 buf= 1;
6124 for (long j= 1; j <= NTLN.NumRows(); j++, iter++)
6125 {
6126 if (!IsZero (NTLN (j,i)))
6127 buf= mulNTL (buf, mod (iter.getItem(), y));
6128 }
6130 }
6133 Pi= CFArray();
6134 diophant= CFList();
6135 factors.insert (LCF);
6136 henselLift12 (F, factors, l, Pi, diophant, M);
6137}
6138#endif
6139
6140#ifdef HAVE_FLINT
6141#ifdef HAVE_NTL // henselLift12
6142void
6146 )
6147{
6149 Variable y= Variable (2);
6150 CanonicalForm LCF= LC (F, 1);
6153 for (long i= 0; i < nmod_mat_ncols (FLINTN); i++)
6154 {
6155 iter= factors;
6156 buf= 1;
6157 for (long j= 0; j < nmod_mat_nrows (FLINTN); j++, iter++)
6158 {
6159 if (!(nmod_mat_entry (FLINTN,j,i) == 0))
6160 buf= mulNTL (buf, mod (iter.getItem(), y));
6161 }
6163 }
6166 Pi= CFArray();
6167 diophant= CFList();
6168 factors.insert (LCF);
6169 henselLift12 (F, factors, l, Pi, diophant, M);
6170}
6171#endif
6172#endif
6173
6174#ifdef HAVE_NTL // mat_zz_pE
6175void
6179 )
6180{
6182 Variable y= Variable (2);
6183 CanonicalForm LCF= LC (F, 1);
6186 for (long i= 1; i <= NTLN.NumCols(); i++)
6187 {
6188 iter= factors;
6189 buf= 1;
6190 for (long j= 1; j <= NTLN.NumRows(); j++, iter++)
6191 {
6192 if (!IsZero (NTLN (j,i)))
6193 buf= mulNTL (buf, mod (iter.getItem(), y));
6194 }
6196 }
6199 Pi= CFArray();
6200 diophant= CFList();
6201 factors.insert (LCF);
6202 henselLift12 (F, factors, l, Pi, diophant, M);
6203}
6204#endif
6205
6206#ifdef HAVE_FLINT
6207CFList
6210 int& factorsFound, bool beenInThres, CFMatrix& M,
6213 )
6214#else
6215CFList
6218 int& factorsFound, bool beenInThres, CFMatrix& M,
6221 )
6222#endif
6223{
6224 int sizeOfLiftPre;
6225 int * liftPre= getLiftPrecisions (F, sizeOfLiftPre, degree (LC (F, 1), 2));
6226
6227 Variable y= F.mvar();
6228 factorsFound= 0;
6229 CanonicalForm LCF= LC (F, 1);
6230 CFList result;
6231 int smallFactorDeg= tmin (11, liftPre [sizeOfLiftPre- 1] + 1);
6232#ifdef HAVE_FLINT
6235 int * factorsFoundIndex= new int [nmod_mat_ncols (FLINTN)];
6236 for (long i= 0; i < nmod_mat_ncols (FLINTN); i++)
6237#else
6238 mat_zz_p NTLN= N;
6239 int * factorsFoundIndex= new int [NTLN.NumCols()];
6240 for (long i= 0; i < NTLN.NumCols(); i++)
6241#endif
6242 factorsFoundIndex [i]= 0;
6243
6244 if (degree (F) + 1 > smallFactorDeg)
6245 {
6246 if (l < smallFactorDeg)
6247 {
6249 factors.insert (LCF);
6251 TIMING_END_AND_PRINT (fac_fq_lift, "time to lift in reconstruction0: ");
6253 }
6254#ifdef HAVE_FLINT
6258 );
6259 TIMING_END_AND_PRINT (fac_fq_reconstruction, "time to reconstruct0: ");
6260 if (result.length() == nmod_mat_ncols (FLINTN))
6261 {
6263#else
6267 );
6268 TIMING_END_AND_PRINT (fac_fq_reconstruction, "time to reconstruct0: ");
6269 if (result.length() == NTLN.NumCols())
6270 {
6271#endif
6272 delete [] liftPre;
6273 delete [] factorsFoundIndex;
6274 return result;
6275 }
6276 }
6277
6278 int i= sizeOfLiftPre - 1;
6279 int dummy= 1;
6280 if (sizeOfLiftPre > 1 && sizeOfLiftPre < 30)
6281 {
6282 while (i > 0)
6283 {
6284 if (l < liftPre[i-1] + 1)
6285 {
6286 factors.insert (LCF);
6288 henselLiftResume12 (F, factors, l, liftPre[i-1] + 1, Pi, diophant, M);
6289 TIMING_END_AND_PRINT (fac_fq_lift, "time to lift in reconstruction1: ");
6290 l= liftPre[i-1] + 1;
6291 }
6292 else
6293 {
6294 i--;
6295 if (i != 0)
6296 continue;
6297 }
6298#ifdef HAVE_FLINT
6302 );
6303 TIMING_END_AND_PRINT (fac_fq_reconstruction, "time to reconstruct1: ");
6304 if (result.length() == nmod_mat_ncols (FLINTN))
6305 {
6307#else
6311 );
6312 TIMING_END_AND_PRINT (fac_fq_reconstruction, "time to reconstruct1: ");
6313 if (result.length() == NTLN.NumCols())
6314 {
6315#endif
6316 delete [] liftPre;
6317 delete [] factorsFoundIndex;
6318 return result;
6319 }
6320 i--;
6321 }
6322 }
6323 else
6324 {
6325 i= 1;
6326 while (((degree (F,y)/4)*i+1) + 4 <= smallFactorDeg)
6327 i++;
6328 while (i < 5)
6329 {
6330 dummy= tmin (degree (F,y)+1, ((degree (F,y)/4)+1)*i+4);
6331 if (l < dummy)
6332 {
6333 factors.insert (LCF);
6336 TIMING_END_AND_PRINT (fac_fq_lift, "time to lift in reconstruction2: ");
6337 l= dummy;
6338 if (i == 1 && degree (F)%4==0 && symmetric && factors.length() == 2 &&
6339 LC (F,1).inCoeffDomain() &&
6340 (degree (factors.getFirst(), 1) == degree (factors.getLast(),1)))
6341 {
6342 Variable x= Variable (1);
6344 int m= degree (F)/4+1;
6345 g= factors.getFirst();
6346 h= factors.getLast();
6347 g= mod (g, power (y,m));
6348 h= mod (h, power (y,m));
6349 g= g (y-evaluation, y);
6350 h= h (y-evaluation, y);
6351 gg= mod (swapvar (g,x,y),power (x,m));
6352 gg= gg (y + evaluation, y);
6353 multiplier1= factors.getLast()[m-1][0]/gg[m-1][0];
6354 gg= div (gg, power (y,m));
6355 gg= gg*power (y,m);
6356 hh= mod (swapvar (h,x,y),power (x,m));
6357 hh= hh (y + evaluation, y);
6358 multiplier2= factors.getFirst()[m-1][0]/hh[m-1][0];
6359 hh= div (hh, power (y,m));
6360 hh= hh*power (y,m);
6363 check1= gg (y-evaluation,y);
6364 check2= hh (y-evaluation,y);
6366 check1= swapvar (check1, x, y);
6367 if (check1/Lc (check1) == check2/Lc (check2))
6368 {
6369#ifdef HAVE_FLINT
6371#endif
6372 result.append (oldcheck1);
6373 result.append (check2);
6374 delete [] liftPre;
6375 delete [] factorsFoundIndex;
6376 return result;
6377 }
6378 }
6379 }
6380 else
6381 {
6382 i++;
6383 if (i < 5)
6384 continue;
6385 }
6386#ifdef HAVE_FLINT
6390 );
6391 TIMING_END_AND_PRINT (fac_fq_reconstruction, "time to reconstruct2: ");
6392 if (result.length() == nmod_mat_ncols (FLINTN))
6393 {
6395#else
6399 );
6400 TIMING_END_AND_PRINT (fac_fq_reconstruction, "time to reconstruct2: ");
6401 if (result.length() == NTLN.NumCols())
6402 {
6403#endif
6404 delete [] liftPre;
6405 delete [] factorsFoundIndex;
6406 return result;
6407 }
6408 i++;
6409 }
6410 }
6411
6412#ifdef HAVE_FLINT
6414#endif
6415 delete [] liftPre;
6416 delete [] factorsFoundIndex;
6417 return result;
6418}
6419
6420#ifdef HAVE_NTL // mat_zz_pE
6421CFList
6424 int& factorsFound, bool beenInThres, CFMatrix& M,
6427 )
6428{
6429 int sizeOfLiftPre;
6430 int * liftPre= getLiftPrecisions (F, sizeOfLiftPre, degree (LC (F, 1), 2));
6431 Variable y= F.mvar();
6432 factorsFound= 0;
6433 CanonicalForm LCF= LC (F, 1);
6434 CFList result;
6435 int smallFactorDeg= 11;
6436 mat_zz_pE NTLN= N;
6437 int * factorsFoundIndex= new int [NTLN.NumCols()];
6438 for (long i= 0; i < NTLN.NumCols(); i++)
6439 factorsFoundIndex [i]= 0;
6440
6441 if (degree (F) + 1 > smallFactorDeg)
6442 {
6443 if (l < smallFactorDeg)
6444 {
6446 factors.insert (LCF);
6448 TIMING_END_AND_PRINT (fac_fq_lift, "time to lift in reconstruction0: ");
6450 }
6454 );
6455 TIMING_END_AND_PRINT (fac_fq_reconstruction, "time to reconstruct0: ");
6456 if (result.length() == NTLN.NumCols())
6457 {
6458 delete [] liftPre;
6459 delete [] factorsFoundIndex;
6460 return result;
6461 }
6462 }
6463
6464 int i= sizeOfLiftPre - 1;
6465 int dummy= 1;
6466 if (sizeOfLiftPre > 1 && sizeOfLiftPre < 30)
6467 {
6468 while (i > 0)
6469 {
6470 if (l < liftPre[i-1] + 1)
6471 {
6472 factors.insert (LCF);
6474 henselLiftResume12 (F, factors, l, liftPre[i-1] + 1, Pi, diophant, M);
6475 TIMING_END_AND_PRINT (fac_fq_lift, "time to lift in reconstruction1: ");
6476 l= liftPre[i-1] + 1;
6477 }
6478 else
6479 {
6480 i--;
6481 if (i != 0)
6482 continue;
6483 }
6487 );
6488 TIMING_END_AND_PRINT (fac_fq_reconstruction, "time to reconstruct1: ");
6489 if (result.length() == NTLN.NumCols())
6490 {
6491 delete [] liftPre;
6492 delete [] factorsFoundIndex;
6493 return result;
6494 }
6495 i--;
6496 }
6497 }
6498 else
6499 {
6500 i= 1;
6501 while ((degree (F,y)/4+1)*i + 4 <= smallFactorDeg)
6502 i++;
6503 while (i < 5)
6504 {
6505 dummy= tmin (degree (F,y)+1, (degree (F,y)/4+1)*i+4);
6506 if (l < dummy)
6507 {
6508 factors.insert (LCF);
6511 TIMING_END_AND_PRINT (fac_fq_lift, "time to lift in reconstruction2: ");
6512 l= dummy;
6513 if (i == 1 && degree (F)%4==0 && symmetric && factors.length() == 2 &&
6514 LC (F,1).inCoeffDomain() &&
6515 (degree (factors.getFirst(), 1) == degree (factors.getLast(),1)))
6516 {
6517 Variable x= Variable (1);
6519 int m= degree (F)/4+1;
6520 g= factors.getFirst();
6521 h= factors.getLast();
6522 g= mod (g, power (y,m));
6523 h= mod (h, power (y,m));
6524 g= g (y-evaluation, y);
6525 h= h (y-evaluation, y);
6526 gg= mod (swapvar (g,x,y),power (x,m));
6527 gg= gg (y + evaluation, y);
6528 multiplier1= factors.getLast()[m-1][0]/gg[m-1][0];
6529 gg= div (gg, power (y,m));
6530 gg= gg*power (y,m);
6531 hh= mod (swapvar (h,x,y),power (x,m));
6532 hh= hh (y + evaluation, y);
6533 multiplier2= factors.getFirst()[m-1][0]/hh[m-1][0];
6534 hh= div (hh, power (y,m));
6535 hh= hh*power (y,m);
6538 check1= gg (y-evaluation,y);
6539 check2= hh (y-evaluation,y);
6541 check1= swapvar (check1, x, y);
6542 if (check1/Lc (check1) == check2/Lc (check2))
6543 {
6544 result.append (oldcheck1);
6545 result.append (check2);
6546 delete [] liftPre;
6547 delete [] factorsFoundIndex;
6548 return result;
6549 }
6550 }
6551 }
6552 else
6553 {
6554 i++;
6555 if (i < 5)
6556 continue;
6557 }
6561 );
6562 TIMING_END_AND_PRINT (fac_fq_reconstruction, "time to reconstruct2: ");
6563 if (result.length() == NTLN.NumCols())
6564 {
6565 delete [] liftPre;
6566 delete [] factorsFoundIndex;
6567 return result;
6568 }
6569 i++;
6570 }
6571 }
6572
6573 delete [] liftPre;
6574 delete [] factorsFoundIndex;
6575 return result;
6576}
6577#endif
6578
6579//over field extension
6580#ifdef HAVE_FLINT
6581CFList
6584 int& factorsFound, bool beenInThres, CFMatrix&
6585 M, CFArray& Pi, CFList& diophant, const
6588 )
6589#else
6590CFList
6593 int& factorsFound, bool beenInThres, CFMatrix&
6594 M, CFArray& Pi, CFList& diophant, const
6597 )
6598#endif
6599{
6600 int sizeOfLiftPre;
6601 int * liftPre= getLiftPrecisions (F, sizeOfLiftPre, degree (LC (F, 1), 2));
6602 Variable y= F.mvar();
6603 factorsFound= 0;
6604 CanonicalForm LCF= LC (F, 1);
6605 CFList result;
6606 int smallFactorDeg= 11;
6607#ifdef HAVE_FLINT
6610 int * factorsFoundIndex= new int [nmod_mat_ncols (FLINTN)];
6611 for (long i= 0; i < nmod_mat_ncols (FLINTN); i++)
6612#else
6613 mat_zz_p NTLN= N;
6614 int * factorsFoundIndex= new int [NTLN.NumCols()];
6615 for (long i= 0; i < NTLN.NumCols(); i++)
6616#endif
6617 factorsFoundIndex [i]= 0;
6618
6619 if (degree (F) + 1 > smallFactorDeg)
6620 {
6621 if (l < smallFactorDeg)
6622 {
6624 factors.insert (LCF);
6626 TIMING_END_AND_PRINT (fac_fq_lift, "time to lift in reconstruction0: ");
6628 }
6630#ifdef HAVE_FLINT
6634 );
6635#else
6639 );
6640#endif
6641 TIMING_END_AND_PRINT (fac_fq_reconstruction, "time to reconstruct0: ");
6642#ifdef HAVE_FLINT
6643 if (result.length() == nmod_mat_ncols (FLINTN))
6644 {
6646#else
6647 if (result.length() == NTLN.NumCols())
6648 {
6649#endif
6650 delete [] liftPre;
6651 delete [] factorsFoundIndex;
6652 return result;
6653 }
6654 }
6655
6656 int i= sizeOfLiftPre - 1;
6657 int dummy= 1;
6658 if (sizeOfLiftPre > 1 && sizeOfLiftPre < 30)
6659 {
6660 while (i > 0)
6661 {
6662 if (l < liftPre[i-1] + 1)
6663 {
6664 factors.insert (LCF);
6666 henselLiftResume12 (F, factors, l, liftPre[i-1] + 1, Pi, diophant, M);
6667 TIMING_END_AND_PRINT (fac_fq_lift, "time to lift in reconstruction1: ");
6668 l= liftPre[i-1] + 1;
6669 }
6670 else
6671 {
6672 i--;
6673 if (i != 0)
6674 continue;
6675 }
6677#ifdef HAVE_FLINT
6681 );
6682#else
6686 );
6687#endif
6688 TIMING_END_AND_PRINT (fac_fq_reconstruction, "time to reconstruct1: ");
6689#ifdef HAVE_FLINT
6690 if (result.length() == nmod_mat_ncols (FLINTN))
6691 {
6693#else
6694 if (result.length() == NTLN.NumCols())
6695 {
6696#endif
6697 delete [] liftPre;
6698 delete [] factorsFoundIndex;
6699 return result;
6700 }
6701 i--;
6702 }
6703 }
6704 else
6705 {
6706 i= 1;
6707 while ((degree (F,y)/4+1)*i + 4 <= smallFactorDeg)
6708 i++;
6709 while (i < 5)
6710 {
6711 dummy= tmin (degree (F,y)+1, (degree (F,y)/4+1)*i+4);
6712 if (l < dummy)
6713 {
6714 factors.insert (LCF);
6717 TIMING_END_AND_PRINT (fac_fq_lift, "time to lift in reconstruction2: ");
6718 l= dummy;
6719 }
6720 else
6721 {
6722 i++;
6723 if (i < 5)
6724 continue;
6725 }
6727#ifdef HAVE_FLINT
6731 );
6732#else
6736 );
6737#endif
6738 TIMING_END_AND_PRINT (fac_fq_reconstruction, "time to reconstruct2: ");
6739#ifdef HAVE_FLINT
6740 if (result.length() == nmod_mat_ncols (FLINTN))
6741 {
6743#else
6744 if (result.length() == NTLN.NumCols())
6745 {
6746#endif
6747 delete [] liftPre;
6748 delete [] factorsFoundIndex;
6749 return result;
6750 }
6751 i++;
6752 }
6753 }
6754
6755#ifdef HAVE_FLINT
6757#endif
6758 delete [] liftPre;
6759 delete [] factorsFoundIndex;
6760 return result;
6761}
6762
6763#ifdef HAVE_NTL // henselLift12
6764CFList
6767 CFMatrix& M, bool& success, int d, const CanonicalForm& eval
6768 )
6769{
6770 CanonicalForm F= G;
6772 bufUniFactors.insert (LC (F, 1));
6773 int smallFactorDeg= d;
6776 int adaptedLiftBound;
6777 success= false;
6778 int * factorsFoundIndex= new int [uniFactors.length()];
6779 for (int i= 0; i < uniFactors.length(); i++)
6780 factorsFoundIndex [i]= 0;
6784 delete [] factorsFoundIndex;
6785 if (degs.getLength() == 1)
6786 {
6787 degPat= degs;
6788 return earlyFactors;
6789 }
6790 if (success)
6791 {
6792 H= F;
6793 return earlyFactors;
6794 }
6795 int sizeOldF= size (G);
6796 if (size (F) < sizeOldF)
6797 {
6798 H= F;
6799 success= true;
6800 return earlyFactors;
6801 }
6802 else
6803 {
6805 return CFList();
6806 }
6807}
6808#endif
6809
6810#ifdef HAVE_NTL // henselLift12
6811CFList
6814 CFMatrix& M, bool& success, int d, const CanonicalForm&
6816 )
6817{
6818 CanonicalForm F= G;
6820 bufUniFactors.insert (LC (F, 1));
6821 int smallFactorDeg= d;
6824 int adaptedLiftBound;
6825 success= false;
6826 int * factorsFoundIndex= new int [uniFactors.length()];
6827 for (int i= 0; i < uniFactors.length(); i++)
6828 factorsFoundIndex [i]= 0;
6833 delete [] factorsFoundIndex;
6834 if (degs.getLength() == 1)
6835 {
6836 degPat= degs;
6837 return earlyFactors;
6838 }
6839 if (success)
6840 {
6841 H= F;
6842 return earlyFactors;
6843 }
6844 Variable y= F.mvar();
6845 int sizeOldF= size (G);
6846 if (size (F) < sizeOldF)
6847 {
6848 H= F;
6849 success= true;
6850 return earlyFactors;
6851 }
6852 else
6853 {
6855 return CFList();
6856 }
6857}
6858#endif
6859
6860#ifdef HAVE_NTL // matrix Fq
6861CFList
6863 const Variable& alpha, const DegreePattern& degPat,
6864 bool symmetric, const CanonicalForm& eval
6865 )
6866{
6868 CanonicalForm F= G;
6869 CanonicalForm LCF= LC (F, 1);
6870 Variable y= F.mvar();
6871 Variable x= Variable (1);
6872 int d;
6873 bool isIrreducible= false;
6874 int* bounds= computeBounds (F, d, isIrreducible);
6875 if (isIrreducible)
6876 {
6877 delete [] bounds;
6878 return CFList (G);
6879 }
6880 int minBound= bounds[0];
6881 for (int i= 1; i < d; i++)
6882 {
6883 if (bounds[i] != 0)
6885 }
6886
6888 CFArray Pi;
6890 int liftBound= 2*totaldegree (F) - 1;
6892
6895 bool success= false;
6897 success, minBound + 1, eval
6898 );
6899
6900 if (smallFactors.length() > 0)
6901 {
6902 if (smallFactors.length() == 1)
6903 {
6904 if (smallFactors.getFirst() == F)
6905 {
6906 delete [] bounds;
6907 return CFList (G (y-eval,y));
6908 }
6909 }
6910 if (degs.getLength() <= 1)
6911 {
6912 delete [] bounds;
6913 return smallFactors;
6914 }
6915 }
6916
6917 int index;
6919 for (CFListIterator i= smallFactors; i.hasItem(); i++)
6920 {
6921 index= 1;
6922 tmp1= mod (i.getItem(),y-eval);
6923 tmp1 /= Lc (tmp1);
6924 for (CFListIterator j= bufUniFactors; j.hasItem(); j++, index++)
6925 {
6926 tmp2= mod (j.getItem(), y);
6927 tmp2 /= Lc (tmp2);
6928 if (tmp1 == tmp2)
6929 {
6930 index++;
6931 j.remove(index);
6932 break;
6933 }
6934 }
6935 }
6936
6937 if (bufUniFactors.isEmpty())
6938 {
6939 delete [] bounds;
6940 return smallFactors;
6941 }
6942
6943 if (success)
6944 {
6945 F= H;
6946 delete [] bounds;
6948 if (isIrreducible)
6949 {
6950 smallFactors.append (F (y-eval,y));
6951 delete [] bounds;
6952 return smallFactors;
6953 }
6954 LCF= LC (F, 1);
6955
6956 minBound= bounds[0];
6957 for (int i= 1; i < d; i++)
6958 {
6959 if (bounds[i] != 0)
6961 }
6962 Pi= CFArray();
6963 diophant= CFList();
6964 liftBound= 2*totaldegree (F) - 1;
6967 degs.intersect (bufDegs);
6968 degs.refine();
6969 if (degs.getLength() <= 1)
6970 {
6971 smallFactors.append (F (y-eval,y));
6972 delete [] bounds;
6973 return smallFactors;
6974 }
6975 }
6976
6977 bool reduceFq2Fp= (degree (F) > getCharacteristic());
6979 int l= 1;
6980
6981#ifdef HAVE_FLINT
6983#endif
6984
6986 {
6988 zz_p::init (getCharacteristic());
6989 }
6990 mat_zz_p NTLN;
6991
6992 if (alpha.level() != 1)
6993 {
6995 zz_pE::init (NTLMipo);
6996 }
6998
6999 if (alpha.level() == 1)
7000 {
7001#ifdef HAVE_FLINT
7003 for (long i= bufUniFactors.length()-2; i >= 0; i--)
7004 nmod_mat_entry (FLINTN, i, i)= 1;
7005#else
7006 ident (NTLN, bufUniFactors.length() - 1);
7007#endif
7008 }
7009 else
7010 {
7011 if (reduceFq2Fp)
7012#ifdef HAVE_FLINT
7013 {
7015 for (long i= bufUniFactors.length()-2; i >= 0; i--)
7016 nmod_mat_entry (FLINTN, i, i)= 1;
7017 }
7018#else
7019 ident (NTLN, bufUniFactors.length() - 1);
7020#endif
7021 else
7023 }
7024 bool irreducible= false;
7026
7027 int oldL;
7029 if (success)
7030 {
7031 int start= 0;
7032 if (alpha.level() == 1)
7036#else
7038#endif
7040 );
7041 else
7042 {
7043 if (reduceFq2Fp)
7047#else
7049#endif
7051 alpha
7052 );
7053 else
7057 );
7058 }
7059 }
7060 else
7061 {
7062 if (alpha.level() == 1)
7063 {
7067#else
7069#endif
7071 );
7072 }
7073 else
7074 {
7075 if (reduceFq2Fp)
7079 FLINTN, diophant, M, Pi, bufQ,
7080#else
7081 NTLN, diophant, M, Pi, bufQ,
7082#endif
7084 );
7085 else
7088 M, Pi, bufQ, irreducible
7089 );
7090 }
7091 }
7092
7094 "time to compute a reduced lattice: ");
7096 if (oldL > liftBound)
7097 {
7098#ifdef HAVE_FLINT
7099 if (alpha.level() == 1 || (alpha.level() != 1 && reduceFq2Fp))
7101#endif
7102 delete [] bounds;
7103 return Union (smallFactors,
7105 power (y, degree (F) + 1),
7106 degs, eval, 1, bufUniFactors.length()/2
7107 )
7108 );
7109 }
7110
7111 l= oldL;
7112 if (irreducible)
7113 {
7114#ifdef HAVE_FLINT
7115 if (alpha.level() == 1 || (alpha.level() != 1 && reduceFq2Fp))
7117#endif
7118 delete [] bounds;
7119 return Union (CFList (F(y-eval,y)), smallFactors);
7120 }
7121
7123
7124 CFList result;
7125 if (l >= degree (F) + 1)
7126 {
7127 int * factorsFoundIndex;
7128 if (alpha.level() == 1 || (alpha.level() != 1 && reduceFq2Fp))
7129 {
7130#ifdef HAVE_FLINT
7132 for (long i= 0; i < nmod_mat_ncols (FLINTN); i++)
7133#else
7134 factorsFoundIndex= new int [NTLN.NumCols()];
7135 for (long i= 0; i < NTLN.NumCols(); i++)
7136#endif
7137 factorsFoundIndex[i]= 0;
7138 }
7139 else
7140 {
7141 factorsFoundIndex= new int [NTLNe.NumCols()];
7142 for (long i= 0; i < NTLNe.NumCols(); i++)
7143 factorsFoundIndex[i]= 0;
7144 }
7145 int factorsFound= 0;
7147 if (alpha.level() == 1 || (alpha.level() != 1 && reduceFq2Fp))
7151#else
7153#endif
7154 );
7155 else
7158 );
7159 if (alpha.level() == 1 || (alpha.level() != 1 && reduceFq2Fp))
7160 {
7161#ifdef HAVE_FLINT
7162 if (result.length() == nmod_mat_ncols (FLINTN))
7163 {
7164 if (alpha.level() == 1 || (alpha.level() != 1 && reduceFq2Fp))
7166#else
7167 if (result.length() == NTLN.NumCols())
7168 {
7169#endif
7170 delete [] factorsFoundIndex;
7171 delete [] bounds;
7172 return Union (result, smallFactors);
7173 }
7174 }
7175 else
7176 {
7177 if (result.length() == NTLNe.NumCols())
7178 {
7179 delete [] factorsFoundIndex;
7180 delete [] bounds;
7181 return Union (result, smallFactors);
7182 }
7183 }
7184 delete [] factorsFoundIndex;
7185 }
7186 if (l >= liftBound)
7187 {
7188 int * factorsFoundIndex;
7189 if (alpha.level() == 1 || (alpha.level() != 1 && reduceFq2Fp))
7190 {
7191#ifdef HAVE_FLINT
7193 for (long i= 0; i < nmod_mat_ncols (FLINTN); i++)
7194#else
7195 factorsFoundIndex= new int [NTLN.NumCols()];
7196 for (long i= 0; i < NTLN.NumCols(); i++)
7197#endif
7198 factorsFoundIndex[i]= 0;
7199 }
7200 else
7201 {
7202 factorsFoundIndex= new int [NTLNe.NumCols()];
7203 for (long i= 0; i < NTLNe.NumCols(); i++)
7204 factorsFoundIndex[i]= 0;
7205 }
7207 int factorsFound= 0;
7208 if (alpha.level() == 1 || (alpha.level() != 1 && reduceFq2Fp))
7212#else
7214#endif
7215 );
7216 else
7219 );
7220 if (alpha.level() == 1 || (alpha.level() != 1 && reduceFq2Fp))
7221 {
7222#ifdef HAVE_FLINT
7223 if (result.length() == nmod_mat_ncols(FLINTN))
7224 {
7226#else
7227 if (result.length() == NTLN.NumCols())
7228 {
7229#endif
7230 delete [] factorsFoundIndex;
7231 delete [] bounds;
7232 return Union (result, smallFactors);
7233 }
7234 }
7235 else
7236 {
7237 if (result.length() == NTLNe.NumCols())
7238 {
7239 delete [] factorsFoundIndex;
7240 delete [] bounds;
7241 return Union (result, smallFactors);
7242 }
7243 }
7244 delete [] factorsFoundIndex;
7245 }
7246
7247 result= CFList();
7248 bool beenInThres= false;
7249 int thres= 100;
7250 if (l <= thres)
7251 {
7252 if (alpha.level() == 1 || (alpha.level() != 1 && reduceFq2Fp))
7253 {
7254#ifdef HAVE_FLINT
7256 {
7258#else
7259 if (NTLN.NumCols() < bufUniFactors.length())
7260 {
7261 refineAndRestartLift (F, NTLN, liftBound, l, bufUniFactors, M, Pi,
7262#endif
7263 diophant
7264 );
7265 beenInThres= true;
7266 }
7267 }
7268 else
7269 {
7270 if (NTLNe.NumCols() < bufUniFactors.length())
7271 {
7272 refineAndRestartLift (F, NTLNe, liftBound, l, bufUniFactors, M, Pi,
7273 diophant
7274 );
7275 beenInThres= true;
7276 }
7277 }
7278 }
7279
7281 int factorsFound= 0;
7282 if (alpha.level() == 1 || (alpha.level() != 1 && reduceFq2Fp))
7283 {
7284#ifdef HAVE_FLINT
7285 result= earlyReconstructionAndLifting (F, FLINTN, bufF, bufUniFactors, l,
7286#else
7287 result= earlyReconstructionAndLifting (F, NTLN, bufF, bufUniFactors, l,
7288#endif
7289 factorsFound, beenInThres, M, Pi,
7290 diophant, symmetric, eval
7291 );
7292
7293#ifdef HAVE_FLINT
7294 if (result.length() == nmod_mat_ncols (FLINTN))
7295 {
7296 nmod_mat_clear (FLINTN);
7297#else
7298 if (result.length() == NTLN.NumCols())
7299 {
7300#endif
7301 delete [] bounds;
7302 return Union (result, smallFactors);
7303 }
7304 }
7305 else
7306 {
7307 result= earlyReconstructionAndLifting (F, NTLNe, bufF, bufUniFactors, l,
7308 factorsFound, beenInThres, M, Pi,
7309 diophant, symmetric, eval
7310 );
7311
7312 if (result.length() == NTLNe.NumCols())
7313 {
7314 delete [] bounds;
7315 return Union (result, smallFactors);
7316 }
7317 }
7318
7319 if (result.length() > 0)
7320 {
7321 if (beenInThres)
7322 {
7323 int index;
7324 for (CFListIterator i= result; i.hasItem(); i++)
7325 {
7326 index= 1;
7327 tmp1= mod (i.getItem(), y-eval);
7328 tmp1 /= Lc (tmp1);
7329 for (CFListIterator j= bufUniFactors; j.hasItem(); j++, index++)
7330 {
7331 tmp2= mod (j.getItem(), y);
7332 tmp2 /= Lc (tmp2);
7333 if (tmp1 == tmp2)
7334 {
7335 index++;
7336 j.remove(index);
7337 break;
7338 }
7339 }
7340 }
7341 }
7342 else
7343 {
7344 int * zeroOne;
7345 long numCols, numRows;
7346 if (alpha.level() == 1 || (alpha.level() != 1 && reduceFq2Fp))
7347 {
7348#ifdef HAVE_FLINT
7349 numCols= nmod_mat_ncols (FLINTN);
7350 numRows= nmod_mat_nrows (FLINTN);
7351 zeroOne= extractZeroOneVecs (FLINTN);
7352#else
7353 numCols= NTLN.NumCols();
7354 numRows= NTLN.NumRows();
7355 zeroOne= extractZeroOneVecs (NTLN);
7356#endif
7357 }
7358 else
7359 {
7360 numCols= NTLNe.NumCols();
7361 numRows= NTLNe.NumRows();
7362 zeroOne= extractZeroOneVecs (NTLNe);
7363 }
7369 for (int i= 0; i < numCols; i++)
7370 {
7371 if (zeroOne [i] == 0)
7372 continue;
7374 buf= 1;
7376 for (int j= 0; j < numRows; j++, iter++)
7377 {
7378 if (alpha.level() == 1 || (alpha.level() != 1 && reduceFq2Fp))
7379 {
7380#ifdef HAVE_FLINT
7381 if (!(nmod_mat_entry (FLINTN, j,i) == 0))
7382#else
7383 if (!IsZero (NTLN (j + 1,i + 1)))
7384#endif
7385 {
7386 factorsConsidered.append (iter.getItem());
7387 buf *= mod (iter.getItem(), y);
7388 }
7389 }
7390 else
7391 {
7392 if (!IsZero (NTLNe (j + 1,i + 1)))
7393 {
7394 factorsConsidered.append (iter.getItem());
7395 buf *= mod (iter.getItem(), y);
7396 }
7397 }
7398 }
7399 buf /= Lc (buf);
7400 for (iter2= result; iter2.hasItem(); iter2++)
7401 {
7402 tmp= mod (iter2.getItem(), y-eval);
7403 tmp /= Lc (tmp);
7404 if (tmp == buf)
7405 {
7407 break;
7408 }
7409 }
7410 }
7412 delete [] zeroOne;
7413 }
7414
7415 int oldNumCols;
7417 irreducible= false;
7418
7419 if (alpha.level() == 1)
7420 {
7421#ifdef HAVE_FLINT
7423#else
7424 oldNumCols= NTLN.NumCols();
7425#endif
7428 );
7429 }
7430 else
7431 {
7432 if (reduceFq2Fp)
7433 {
7434#ifdef HAVE_FLINT
7436#else
7437 oldNumCols= NTLN.NumCols();
7438#endif
7439
7442 );
7443 }
7444 else
7445 {
7446 oldNumCols= NTLNe.NumCols();
7447
7450 );
7451 }
7452 }
7453
7454 if (bufUniFactors.isEmpty() || degree (bufF) <= 0)
7455 {
7456#ifdef HAVE_FLINT
7457 if (alpha.level() == 1 || (alpha.level() != 1 && reduceFq2Fp))
7459#endif
7460 delete [] bounds;
7462 return Union (result, smallFactors);
7463 }
7464
7466 i.getItem()= mod (i.getItem(), y);
7467
7470 delete [] bounds;
7472 degs.intersect (bufDegs);
7473 degs.refine();
7474 if (degs.getLength() == 1 || bufUniFactors.length() == 1)
7475 {
7476#ifdef HAVE_FLINT
7477 if (alpha.level() == 1 || (alpha.level() != 1 && reduceFq2Fp))
7479#endif
7480 result.append (bufF (y-eval,y));
7481 return result;
7482 }
7483#ifdef HAVE_FLINT
7484 if (alpha.level() == 1 || (alpha.level() != 1 && reduceFq2Fp))
7486#endif
7489 eval
7490 )
7491 );
7492 }
7493
7494 if (l < liftBound)
7495 {
7496 if (alpha.level() == 1)
7497 {
7500 FLINTN, eval
7501#else
7502 NTLN, eval
7503#endif
7504 );
7505 }
7506 else
7507 {
7508 if (reduceFq2Fp)
7509 {
7513#else
7514 bufQ, NTLN, alpha, eval
7515#endif
7516 );
7517 }
7518 else
7519 {
7521 NTLNe, eval
7522 );
7523 }
7524 }
7525 if (alpha.level() == 1 || (alpha.level() != 1 && reduceFq2Fp))
7526 {
7527#ifdef HAVE_FLINT
7528 if (result.length()== nmod_mat_ncols (FLINTN))
7529 {
7531#else
7532 if (result.length()== NTLN.NumCols())
7533 {
7534#endif
7535 delete [] bounds;
7537 return result;
7538 }
7539 }
7540 else
7541 {
7542 if (result.length()== NTLNe.NumCols())
7543 {
7544 delete [] bounds;
7546 return result;
7547 }
7548 }
7549
7550 if (result.isEmpty())
7551 {
7552 if (alpha.level() == 1)
7556#else
7557 liftBound, d, bounds, NTLN,
7558#endif
7559 diophant, M, Pi, bufQ, eval
7560 );
7561 else
7562 {
7563 if (reduceFq2Fp)
7565 liftBound, d, bounds,
7567 FLINTN, diophant, M,
7568#else
7569 NTLN, diophant, M,
7570#endif
7571 Pi, bufQ, alpha, eval
7572 );
7573 else
7575 liftBound, d, bounds,
7576 NTLNe, diophant, M,
7577 Pi, bufQ, eval
7578 );
7579 }
7580
7581 if (alpha.level() == 1 || (alpha.level() != 1 && reduceFq2Fp))
7582 {
7583#ifdef HAVE_FLINT
7584 if (result.length() == nmod_mat_ncols (FLINTN))
7585 {
7587#else
7588 if (result.length() == NTLN.NumCols())
7589 {
7590#endif
7591 delete [] bounds;
7593 return result;
7594 }
7595 }
7596 else
7597 {
7598 if (result.length() == NTLNe.NumCols())
7599 {
7600 delete [] bounds;
7602 return result;
7603 }
7604 }
7605 }
7606 }
7607
7608 DEBOUTLN (cerr, "lattice recombination failed");
7609
7611 degs.intersect (bufDegs);
7612 degs.refine();
7613
7614 delete [] bounds;
7616#ifdef HAVE_FLINT
7617 if (alpha.level() == 1 || (alpha.level() != 1 && reduceFq2Fp))
7619#endif
7620 if (isIrreducible)
7621 {
7622 delete [] bounds;
7624 result.append (F (y-eval,y));
7625 return result;
7626 }
7627 minBound= bounds[0];
7628 for (int i= 1; i < d; i++)
7629 {
7630 if (bounds[i] != 0)
7632 }
7633
7634 if (minBound > 16 || result.length() == 0)
7635 {
7637 CanonicalForm MODl= power (y, degree (F) + 1);
7638 delete [] bounds;
7640 eval, 1, bufUniFactors.length()/2
7641 )
7642 );
7643 }
7644 else
7645 {
7648 i.getItem()= mod (i.getItem(), y);
7649 delete [] bounds;
7652 )
7653 );
7654 }
7655}
7656#endif
7657
7658#ifdef HAVE_NTL // findMinPoly
7661 int& degMipo
7662 )
7663{
7665 Variable alpha= info.getAlpha();
7666 if (GF)
7667 {
7671 GFMipo.mapinto();
7672 alpha= rootOf (GFMipo);
7674 }
7675 else
7676 {
7677 alpha= info.getAlpha();
7679 }
7680
7683 if ((!GF && evaluation != alpha) || (GF && evaluation != getGFGenerator()))
7684 {
7686 if (GF)
7687 {
7690 }
7691 else
7694 gamma= rootOf (mipo);
7696 bool fail= false;
7699
7700 if (GF)
7702 }
7703 else
7704 gamma= alpha;
7706 imPrimElemAlpha, 1, info.getGFName(), true
7707 );
7708
7709 return info2;
7710}
7711#endif
7712
7713#ifdef HAVE_NTL // extSieveSmallFactors,...
7714CFList
7716 const ExtensionInfo& extInfo, const
7718 )
7719{
7724 CanonicalForm F= G;
7725 Variable x= Variable (1);
7726 Variable y= F.mvar();
7728
7729
7730 int degMipo;
7732
7733 CFList source, dest;
7734 CanonicalForm LCF= LC (F, 1);
7735
7736 int d;
7737 bool isIrreducible= false;
7738 int* bounds= computeBounds (F, d, isIrreducible);
7739 if (isIrreducible)
7740 {
7741 delete [] bounds;
7742 CFList source, dest;
7744 tmp= mapDown (tmp, info, source, dest);
7745 return CFList (tmp);
7746 }
7747 int minBound= bounds[0];
7748 for (int i= 1; i < d; i++)
7749 {
7750 if (bounds[i] != 0)
7752 }
7753
7754
7755 CFArray Pi;
7757 int liftBound= tmax ((2*totaldegree (F) - 1)/degMipo + 1, degree (F) + 1 +
7758 degree (LC (F, 1)));
7760
7763 bool success= false;
7765 M, success, minBound + 1, evaluation, info
7766 );
7767
7768 if (smallFactors.length() > 0)
7769 {
7770 if (smallFactors.length() == 1)
7771 {
7772 if (smallFactors.getFirst() == F)
7773 {
7774 delete [] bounds;
7775 CFList source, dest;
7777 tmp= mapDown (tmp, info, source, dest);
7778 return CFList (tmp);
7779 }
7780 }
7781 if (degs.getLength() <= 1)
7782 {
7783 delete [] bounds;
7784 return smallFactors;
7785 }
7786 }
7787
7788 int index;
7790 for (CFListIterator i= smallFactors; i.hasItem(); i++)
7791 {
7792 index= 1;
7793 tmp1= mod (i.getItem(), y - evaluation);
7794 tmp1 /= Lc (tmp1);
7795 for (CFListIterator j= bufUniFactors; j.hasItem(); j++, index++)
7796 {
7797 tmp2= mod (j.getItem(), y);
7798 tmp2 /= Lc (tmp2);
7799 if (tmp1 == tmp2)
7800 {
7801 index++;
7802 j.remove(index);
7803 break;
7804 }
7805 }
7806 }
7807
7808 if (bufUniFactors.isEmpty())
7809 {
7810 delete [] bounds;
7811 return smallFactors;
7812 }
7813
7814 if (success)
7815 {
7816 F= H/Lc(H);
7817 delete [] bounds;
7819 if (isIrreducible)
7820 {
7821 delete [] bounds;
7822 CFList source, dest;
7823 CanonicalForm tmp= F (y - evaluation, y);
7824 tmp= mapDown (tmp, info, source, dest);
7826 return smallFactors;
7827 }
7828 LCF= LC (F, 1);
7829
7830 minBound= bounds[0];
7831 for (int i= 1; i < d; i++)
7832 {
7833 if (bounds[i] != 0)
7835 }
7836 Pi= CFArray();
7837 diophant= CFList();
7838 liftBound=tmax ((2*totaldegree (F) - 1)/degMipo + 1, degree (F) + 1 +
7839 degree (LC (F, 1)));
7842 degs.intersect (bufDegs);
7843 degs.refine();
7844 if (degs.getLength() <= 1)
7845 {
7846 delete [] bounds;
7847 CFList source, dest;
7848 CanonicalForm tmp= F (y - evaluation, y);
7849 tmp= mapDown (tmp, info, source, dest);
7851 return smallFactors;
7852 }
7853 }
7854
7856 int l= 1;
7857
7858#ifdef HAVE_FLINT
7862 for (long i= bufUniFactors.length()-2; i >= 0; i--)
7863 nmod_mat_entry (FLINTN, i, i)= 1;
7864#else
7866 {
7868 zz_p::init (getCharacteristic());
7869 }
7870 zz_pX NTLMipo;
7871 mat_zz_p NTLN;
7872
7873 ident (NTLN, bufUniFactors.length() - 1);
7874#endif
7875 bool irreducible= false;
7877
7878 int oldL;
7880 if (success)
7881 {
7882 int start= 0;
7883#ifdef HAVE_FLINT
7887 );
7888#else
7892 );
7893#endif
7894 }
7895 else
7896 {
7897#ifdef HAVE_FLINT
7901 source, dest
7902 );
7903#else
7907 source, dest
7908 );
7909#endif
7910 }
7912 "time to compute a reduced lattice: ");
7913
7915 if (oldL > liftBound)
7916 {
7917#ifdef HAVE_FLINT
7919#endif
7920 delete [] bounds;
7922 (bufUniFactors, F,
7923 power (y, degree (F) + 1),info,
7925 )
7926 );
7927 }
7928
7929 l= oldL;
7930 if (irreducible)
7931 {
7932#ifdef HAVE_FLINT
7934#endif
7935 delete [] bounds;
7936 CFList source, dest;
7937 CanonicalForm tmp= F (y - evaluation, y);
7938 tmp= mapDown (tmp, info, source, dest);
7939 return Union (CFList (tmp), smallFactors);
7940 }
7941
7943
7944 CFList result;
7945 if (l >= degree (F) + 1)
7946 {
7947 int * factorsFoundIndex;
7948
7949#ifdef HAVE_FLINT
7951 for (long i= 0; i < nmod_mat_ncols (FLINTN); i++)
7952#else
7953 factorsFoundIndex= new int [NTLN.NumCols()];
7954 for (long i= 0; i < NTLN.NumCols(); i++)
7955#endif
7956 factorsFoundIndex[i]= 0;
7957
7958 int factorsFound= 0;
7960
7961#ifdef HAVE_FLINT
7965 );
7966
7967 if (result.length() == nmod_mat_ncols (FLINTN))
7968 {
7970#else
7974 );
7975
7976 if (result.length() == NTLN.NumCols())
7977 {
7978#endif
7979 delete [] factorsFoundIndex;
7980 delete [] bounds;
7981 return Union (result, smallFactors);
7982 }
7983
7984 delete [] factorsFoundIndex;
7985 }
7986 if (l >= liftBound)
7987 {
7988 int * factorsFoundIndex;
7989#ifdef HAVE_FLINT
7991 for (long i= 0; i < nmod_mat_ncols (FLINTN); i++)
7992#else
7993 factorsFoundIndex= new int [NTLN.NumCols()];
7994 for (long i= 0; i < NTLN.NumCols(); i++)
7995#endif
7996 factorsFoundIndex[i]= 0;
7998 int factorsFound= 0;
7999
8000#ifdef HAVE_FLINT
8004 );
8005
8006 if (result.length() == nmod_mat_ncols (FLINTN))
8007 {
8009#else
8013 );
8014
8015 if (result.length() == NTLN.NumCols())
8016 {
8017#endif
8018 delete [] factorsFoundIndex;
8019 delete [] bounds;
8020 return Union (result, smallFactors);
8021 }
8022 delete [] factorsFoundIndex;
8023 }
8024
8025 result= CFList();
8026 bool beenInThres= false;
8027 int thres= 100;
8028#ifdef HAVE_FLINT
8030 {
8032 diophant
8033 );
8034#else
8035 if (l <= thres && bufUniFactors.length() > NTLN.NumCols())
8036 {
8038 diophant
8039 );
8040#endif
8041 beenInThres= true;
8042 }
8043
8044
8046 int factorsFound= 0;
8047
8048#ifdef HAVE_FLINT
8052 );
8053
8054 if (result.length() == nmod_mat_ncols (FLINTN))
8055 {
8057#else
8061 );
8062
8063 if (result.length() == NTLN.NumCols())
8064 {
8065#endif
8066 delete [] bounds;
8067 return Union (result, smallFactors);
8068 }
8069
8070 if (result.length() > 0)
8071 {
8072 if (beenInThres)
8073 {
8074 int index;
8075 for (CFListIterator i= result; i.hasItem(); i++)
8076 {
8077 index= 1;
8078 tmp1= mod (i.getItem(), y-evaluation);
8079 tmp1 /= Lc (tmp1);
8080 for (CFListIterator j= bufUniFactors; j.hasItem(); j++, index++)
8081 {
8082 tmp2= mod (j.getItem(), y);
8083 tmp2 /= Lc (tmp2);
8084 if (tmp1 == tmp2)
8085 {
8086 index++;
8087 j.remove(index);
8088 break;
8089 }
8090 }
8091 }
8092 }
8093 else
8094 {
8095#ifdef HAVE_FLINT
8097#else
8099#endif
8104#ifdef HAVE_FLINT
8105 for (int i= 0; i < nmod_mat_ncols (FLINTN); i++)
8106#else
8107 for (int i= 0; i < NTLN.NumCols(); i++)
8108#endif
8109 {
8110 if (zeroOne [i] == 0)
8111 continue;
8113 buf= 1;
8115#ifdef HAVE_FLINT
8116 for (int j= 0; j < nmod_mat_nrows (FLINTN); j++, iter++)
8117 {
8118 if (!(nmod_mat_entry (FLINTN, j, i) == 0))
8119#else
8120 for (int j= 0; j < NTLN.NumRows(); j++, iter++)
8121 {
8122 if (!IsZero (NTLN (j + 1,i + 1)))
8123#endif
8124 {
8125 factorsConsidered.append (iter.getItem());
8126 buf *= mod (iter.getItem(), y);
8127 }
8128 }
8129 buf /= Lc (buf);
8130 for (iter2= result; iter2.hasItem(); iter2++)
8131 {
8132 CanonicalForm tmp= mod (iter2.getItem(), y - evaluation);
8133 tmp /= Lc (tmp);
8134 if (tmp == buf)
8135 {
8137 break;
8138 }
8139 }
8140 }
8142 delete [] zeroOne;
8143 }
8144
8145 int oldNumCols;
8147 irreducible= false;
8148
8149#ifdef HAVE_FLINT //TODO
8153 source, dest, l
8154 );
8156#else
8157 oldNumCols= NTLN.NumCols();
8160 source, dest, l
8161 );
8162#endif
8163 if (bufUniFactors.isEmpty() || degree (bufF) <= 0)
8164 {
8165 delete [] bounds;
8167 return Union (result, smallFactors);
8168 }
8169
8171 i.getItem()= mod (i.getItem(), y);
8172
8173 delete [] bounds;
8176 degs.intersect (bufDegs);
8177 degs.refine();
8179 if (degs.getLength() == 1 || bufUniFactors.length() == 1)
8180 {
8181 CFList source, dest;
8183 tmp= mapDown (tmp, info, source, dest);
8184 result.append (tmp);
8185 return result;
8186 }
8189 )
8190 );
8191 }
8192
8193 if (l/degMipo < liftBound)
8194 {
8195#ifdef HAVE_FLINT
8197 FLINTN, evaluation, info2, source, dest
8198 );
8199
8200 if (result.length()== nmod_mat_ncols (FLINTN))
8201 {
8203#else
8205 NTLN, evaluation, info2, source, dest
8206 );
8207
8208 if (result.length()== NTLN.NumCols())
8209 {
8210#endif
8211 delete [] bounds;
8213 return result;
8214 }
8215
8216 if (result.isEmpty())
8217 {
8218#ifdef HAVE_FLINT
8221 diophant, M, Pi, bufQ,
8223 dest
8224 );
8225 if (result.length()== nmod_mat_ncols (FLINTN))
8226 {
8228#else
8230 liftBound, d, bounds, NTLN,
8231 diophant, M, Pi, bufQ,
8233 dest
8234 );
8235 if (result.length()== NTLN.NumCols())
8236 {
8237#endif
8238 delete [] bounds;
8240 return result;
8241 }
8242 }
8243 }
8244
8245#ifdef HAVE_FLINT
8247#endif
8248
8249 DEBOUTLN (cerr, "lattice recombination failed");
8250
8252 degs.intersect (bufDegs);
8253 degs.refine();
8254
8255 delete [] bounds;
8257 if (isIrreducible)
8258 {
8259 delete [] bounds;
8260 CFList source, dest;
8261 CanonicalForm tmp= F (y - evaluation, y);
8262 tmp= mapDown (tmp, info, source, dest);
8265 return result;
8266 }
8267 minBound= bounds[0];
8268 for (int i= 1; i < d; i++)
8269 {
8270 if (bounds[i] != 0)
8272 }
8273
8274 if (minBound > 16 || result.length() == 0)
8275 {
8277 CanonicalForm MODl= power (y, degree (F) + 1);
8278 delete [] bounds;
8280 degs, evaluation, 1,
8282 )
8283 );
8284 }
8285 else
8286 {
8289 i.getItem()= mod (i.getItem(), y);
8290 delete [] bounds;
8293 )
8294 );
8295 }
8296}
8297#endif
8298
8299#ifdef HAVE_NTL // henselLiftAndLatticeRecombi
8300CFList
8302
8303/// bivariate factorization over finite fields as decribed in "Factoring
8304/// multivariate polynomials over a finite field" by L Bernardin.
8305CFList
8307{
8308 if (F.inCoeffDomain())
8309 return CFList(F);
8310
8311 CanonicalForm A= F;
8313
8314 Variable alpha= info.getAlpha();
8315 Variable beta= info.getBeta();
8316 CanonicalForm gamma= info.getGamma();
8317 CanonicalForm delta= info.getDelta();
8318 int k= info.getGFDegree();
8319 bool extension= info.isInExtension();
8320 if (A.isUnivariate())
8321 {
8322 if (extension == false)
8323 return uniFactorizer (F, alpha, GF);
8324 else
8325 {
8326 CFList source, dest;
8327 A= mapDown (A, info, source, dest);
8328 return uniFactorizer (A, beta, GF);
8329 }
8330 }
8331
8332 CFMap N;
8333 A= compress (A, N);
8334 Variable y= A.mvar();
8335
8336 if (y.level() > 2) return CFList (F);
8337 Variable x= Variable (1);
8338
8339 //remove and factorize content
8342
8345
8346 if (!extension)
8347 {
8350 }
8351
8352 //trivial case
8354 if (A.inCoeffDomain())
8355 {
8358 decompress (factors, N);
8359 return factors;
8360 }
8361 else if (A.isUnivariate())
8362 {
8366 decompress (factors, N);
8367 return factors;
8368 }
8369
8370
8371 //check trivial case
8372 if (degree (A) == 1 || degree (A, 1) == 1 ||
8373 (size (A) == 2 && igcd (degree (A), degree (A,1))==1))
8374 {
8375 factors.append (A);
8376
8378 false, false, N);
8379
8380 if (!extension)
8382 return factors;
8383 }
8384
8385 // check derivatives
8386 bool derivXZero= false;
8389 if (derivX.isZero())
8390 derivXZero= true;
8391 else
8392 {
8393 gcdDerivX= gcd (A, derivX);
8394 if (degree (gcdDerivX) > 0)
8395 {
8402 if (!extension)
8404 return factorsG;
8405 }
8406 }
8407 bool derivYZero= false;
8410 if (derivY.isZero())
8411 derivYZero= true;
8412 else
8413 {
8414 gcdDerivY= gcd (A, derivY);
8415 if (degree (gcdDerivY) > 0)
8416 {
8423 if (!extension)
8425 return factorsG;
8426 }
8427 }
8428 //main variable is chosen s.t. the degree in x is minimal
8429 bool swap= false;
8430 if ((degree (A) > degree (A, x)) || derivXZero)
8431 {
8432 if (!derivYZero)
8433 {
8434 A= swapvar (A, y, x);
8438 swap= true;
8439 }
8440 }
8441
8442 int boundsLength;
8443 bool isIrreducible= false;
8445 if (isIrreducible)
8446 {
8447 delete [] bounds;
8448 factors.append (A);
8449
8451 swap, false, N);
8452
8453 if (!extension)
8455 return factors;
8456 }
8457
8458 int minBound= bounds[0];
8459 for (int i= 1; i < boundsLength; i++)
8460 {
8461 if (bounds[i] != 0)
8463 }
8464
8465 int boundsLength2;
8467 int minBound2= bounds2[0];
8468 for (int i= 1; i < boundsLength2; i++)
8469 {
8470 if (bounds2[i] != 0)
8472 }
8473
8474
8475 bool fail= false;
8480
8481 bool fail2= false;
8486 bool swap2= false;
8487
8488 // several univariate factorizations to obtain more information about the
8489 // degree pattern therefore usually less combinations have to be tried during
8490 // the recombination process
8491 int factorNums= 3;
8492 int subCheck1= substituteCheck (A, x);
8493 int subCheck2= substituteCheck (A, y);
8494 bool symmetric= false;
8495
8497 for (int i= 0; i < factorNums; i++)
8498 {
8499 bufAeval= A;
8502 TIMING_END_AND_PRINT (fac_fq_bi_evaluation, "time to find eval point: ");
8503 if (!derivXZero && !fail2 && !symmetric)
8504 {
8505 if (i == 0)
8506 {
8507 buf= swapvar (A, x, y);
8508 symmetric= (A/Lc (A) == buf/Lc (buf));
8509 }
8510 bufAeval2= buf;
8514 "time to find eval point wrt y: ");
8515 }
8516 // first try to change main variable if there is no valid evaluation point
8517 if (fail && (i == 0))
8518 {
8519 if (!derivXZero && !fail2 && !symmetric)
8520 {
8522 int dummy= subCheck2;
8525 tmp= A;
8526 A= buf;
8527 buf= tmp;
8529 swap2= true;
8530 fail= false;
8531 }
8532 else
8533 fail= true;
8534 }
8535
8536 // if there is no valid evaluation point pass to a field extension
8537 if (fail && (i == 0))
8538 {
8541 swap, swap2, N);
8543 delete [] bounds;
8544 delete [] bounds2;
8545 return factors;
8546 }
8547
8548 // there is at least one valid evaluation point
8549 // but we do not compute more univariate factorization over an extension
8550 if (fail && (i != 0))
8551 break;
8552
8553 // univariate factorization
8557 "time for univariate factorization over Fq: ");
8558 DEBOUTLN (cerr, "Lc (bufAeval)*prod (bufUniFactors)== bufAeval " <<
8560
8561 if (!derivXZero && !fail2 && !symmetric)
8562 {
8566 "time for univariate factorization in y over Fq: ");
8567 DEBOUTLN (cerr, "Lc (bufAeval2)*prod (bufUniFactors2)== bufAeval2 " <<
8569 }
8570
8571 if (bufUniFactors.length() == 1 ||
8572 (!fail2 && !derivXZero && !symmetric && (bufUniFactors2.length() == 1)))
8573 {
8574 if (extension)
8575 {
8576 CFList source, dest;
8577 appendMapDown (factors, A, info, source, dest);
8578 }
8579 else
8580 factors.append (A);
8581
8583 swap, swap2, N);
8584
8585 if (!extension)
8587 delete [] bounds;
8588 delete [] bounds2;
8589 return factors;
8590 }
8591
8592 if (i == 0 && !extension)
8593 {
8594 if (subCheck1 > 0)
8595 {
8597
8598 if (subCheck > 1 && (subCheck1%subCheck == 0))
8599 {
8601 subst (bufA, bufA, subCheck, x);
8605 swap, swap2, N);
8606 if (!extension)
8608 delete [] bounds;
8609 delete [] bounds2;
8610 return factors;
8611 }
8612 }
8613
8614 if (!derivXZero && !fail2 && !symmetric && subCheck2 > 0)
8615 {
8617
8618 if (subCheck > 1 && (subCheck2%subCheck == 0))
8619 {
8621 subst (bufA, bufA, subCheck, y);
8625 swap, swap2, N);
8626 if (!extension)
8628 delete [] bounds;
8629 delete [] bounds2;
8630 return factors;
8631 }
8632 }
8633 }
8634
8635 // degree analysis
8637 if (!derivXZero && !fail2 && !symmetric)
8639
8640 if (i == 0)
8641 {
8642 Aeval= bufAeval;
8645 degs= bufDegs;
8646 if (!derivXZero && !fail2 && !symmetric)
8647 {
8651 degs2= bufDegs2;
8652 }
8653 }
8654 else
8655 {
8656 degs.intersect (bufDegs);
8657 if (!derivXZero && !fail2 && !symmetric)
8658 {
8659 degs2.intersect (bufDegs2);
8661 {
8665 }
8666 }
8668 {
8670 Aeval= bufAeval;
8672 }
8673 }
8674 list.append (bufEvaluation);
8675 if (!derivXZero && !fail2 && !symmetric)
8677 }
8679 "total time for univariate factorizations: ");
8680
8681 if (!derivXZero && !fail2 && !symmetric)
8682 {
8685 && degs.getLength() > degs2.getLength() && minBound2 <= minBound))
8686 {
8687 degs= degs2;
8690 Aeval= Aeval2;
8691 A= buf;
8692 swap2= true;
8693 }
8694 }
8695
8696 if (degs.getLength() == 1) // A is irreducible
8697 {
8698 if (extension)
8699 {
8700 CFList source, dest;
8701 appendMapDown (factors, A, info, source, dest);
8702 }
8703 else
8704 factors.append (A);
8706 swap, swap2, N);
8707 if (!extension)
8709 delete [] bounds;
8710 delete [] bounds2;
8711 return factors;
8712 }
8713
8714 int liftBound= degree (A, y) + 1;
8715
8716 if (swap2)
8717 {
8718 delete [] bounds;
8719 bounds= bounds2;
8721 }
8722
8724 A= A (y + evaluation, y);
8726 "time to shift eval to zero: ");
8727
8728 int degMipo= 1;
8729 if (extension && alpha.level() != 1 && k==1)
8731
8732 DEBOUTLN (cerr, "uniFactors= " << uniFactors);
8733
8734 if ((GF && !extension) || (GF && extension && k != 1))
8735 {
8736 bool earlySuccess= false;
8743 "time for bivariate hensel lifting over Fq: ");
8744 DEBOUTLN (cerr, "lifted factors= " << uniFactors);
8745
8747
8749 if (extension)
8751 evaluation, 1, uniFactors.length()/2);
8752 else
8754 uniFactors.length()/2);
8756 "time for naive bivariate factor recombi over Fq: ");
8757
8758 if (earlySuccess)
8760 else if (!earlySuccess && degs.getLength() == 1)
8762 }
8763 else if (degree (A) > 4 && beta.level() == 1 && (2*minBound)/degMipo < 32)
8764 {
8766 if (extension)
8767 {
8770 );
8772 }
8773 else if (alpha.level() == 1 && !GF)
8774 {
8778 }
8779 else if (!extension && (alpha != x || GF))
8780 {
8784 }
8786 "time to bivar lift and LLL recombi over Fq: ");
8787 DEBOUTLN (cerr, "lifted factors= " << uniFactors);
8788 }
8789 else
8790 {
8791 bool earlySuccess= false;
8798 "time for bivar hensel lifting over Fq: ");
8799 DEBOUTLN (cerr, "lifted factors= " << uniFactors);
8800
8802 if (!extension)
8803 {
8807 "time for small subset naive recombi over Fq: ");
8808
8810 if (degree (A) > 0)
8811 {
8812 CFList tmp;
8814 if (alpha.level() == 1)
8817 );
8818 else
8819 {
8820 if (degree (A) > getCharacteristic())
8823 );
8824 else
8827 );
8828 }
8830 "time to increase precision: ");
8832 if (tmp.length() == 0 || (tmp.length() > 0 && uniFactors.length() != 0
8834 )
8835 {
8837 degs.intersect (bufDegs);
8838 degs.refine ();
8840 degs, evaluation, 4,
8841 uniFactors.length()/2
8842 )
8843 );
8844 }
8845 }
8846 }
8847 else
8848 {
8849 if (beta.level() != 1 || k > 1)
8850 {
8851 if (k > 1)
8852 {
8855 );
8856 }
8857 else
8858 {
8860 evaluation, 1, 3
8861 );
8862 if (degree (A) > 0)
8863 {
8866 degs.intersect (bufDegs);
8867 degs.refine ();
8870 1, tmp.length()/2
8871 )
8872 );
8873 }
8874 }
8875 }
8876 else
8877 {
8879 evaluation, 1, 3
8880 );
8882 if (degree (A) > 0)
8883 {
8884 int degMipo;
8886
8887 CFList source, dest;
8890 info2, source, dest, liftBound
8891 );
8893 if (tmp.length() == 0 || (tmp.length() > 0 && uniFactors.length() != 0
8895 )
8896 {
8898 degs.intersect (bufDegs);
8899 degs.refine ();
8902 4, uniFactors.length()/2
8903 )
8904 );
8905 }
8906 }
8907 }
8908 }
8909
8910 if (earlySuccess)
8912 else if (!earlySuccess && degs.getLength() == 1)
8914 }
8915
8916 if (!swap2)
8917 delete [] bounds2;
8918 delete [] bounds;
8919
8921 swap, swap2, N);
8922 if (!extension)
8924
8925 return factors;
8926}
8927#endif
8928
8929#ifdef HAVE_NTL // biFactorize
8930CFList
8932{
8933
8934 CanonicalForm A= F;
8935 Variable alpha= info.getAlpha();
8936 Variable beta= info.getBeta();
8937 int k= info.getGFDegree();
8938 char cGFName= info.getGFName();
8939 CanonicalForm delta= info.getDelta();
8940
8942 Variable x= Variable (1);
8944 if (!GF && alpha == x) // we are in F_p
8945 {
8946 bool extension= true;
8947 int p= getCharacteristic();
8948 if (p*p < (1<<16)) // pass to GF if possible
8949 {
8951 A= A.mapinto();
8954
8958 for (CFListIterator j= factors; j.hasItem(); j++)
8959 j.getItem()= GF2FalphaRep (j.getItem(), vBuf);
8960 prune (vBuf);
8961 }
8962 else // not able to pass to GF, pass to F_p(\alpha)
8963 {
8965 Variable v= rootOf (mipo);
8968 prune (v);
8969 }
8970 return factors;
8971 }
8972 else if (!GF && (alpha != x)) // we are in F_p(\alpha)
8973 {
8974 if (k == 1) // need factorization over F_p
8975 {
8976 int extDeg= degree (getMipo (alpha));
8977 extDeg++;
8979 Variable v= rootOf (mipo);
8982 prune (v);
8983 }
8984 else
8985 {
8986 if (beta == x)
8987 {
8990 bool primFail= false;
8991 Variable vBuf;
8993 ASSERT (!primFail, "failure in integer factorizer");
8994 if (primFail)
8995 ; //ERROR
8996 else
8998
8999 CFList source, dest;
9001 source, dest);
9004 prune (v);
9005 }
9006 else
9007 {
9010 bool primFail= false;
9011 Variable vBuf;
9012 ASSERT (!primFail, "failure in integer factorizer");
9013 if (primFail)
9014 ; //ERROR
9015 else
9016 imPrimElem= mapPrimElem (delta, beta, v);
9017
9018 CFList source, dest;
9020 source= CFList();
9021 dest= CFList();
9022 bufA= mapUp (bufA, beta, v, delta, imPrimElem, source, dest);
9025 prune (v);
9026 }
9027 }
9028 return factors;
9029 }
9030 else // we are in GF (p^k)
9031 {
9032 int p= getCharacteristic();
9034 bool extension= true;
9035 if (k == 1) // need factorization over F_p
9036 {
9037 extensionDeg++;
9038 if (ipower (p, extensionDeg) < (1<<16))
9039 // pass to GF(p^k+1)
9040 {
9044 A= GF2FalphaRep (A, vBuf);
9047 factors= biFactorize (A.mapinto(), info2);
9048 prune (vBuf);
9049 }
9050 else // not able to pass to another GF, pass to F_p(\alpha)
9051 {
9055 A= GF2FalphaRep (A, vBuf);
9059 prune (vBuf);
9060 }
9061 }
9062 else // need factorization over GF (p^k)
9063 {
9064 if (ipower (p, 2*extensionDeg) < (1<<16))
9065 // pass to GF (p^2k)
9066 {
9071 }
9072 else // not able to pass to GF (p^2k), pass to F_p (\alpha)
9073 {
9077 A= GF2FalphaRep (A, v1);
9080 bool primFail= false;
9081 Variable vBuf;
9083 ASSERT (!primFail, "failure in integer factorizer");
9084 if (primFail)
9085 ; //ERROR
9086 else
9088
9089 CFList source, dest;
9091 source, dest);
9095 for (CFListIterator i= factors; i.hasItem(); i++)
9097 prune (v1);
9098 }
9099 }
9100 return factors;
9101 }
9102}
9103#endif
9104#endif
void convertFacCFMatrix2nmod_mat_t(nmod_mat_t M, const CFMatrix &m)
conversion of a factory matrix over Z/p to a nmod_mat_t
CFFList convertFLINTFq_nmod_poly_factor2FacCFFList(const fq_nmod_poly_factor_t fac, const Variable &x, const Variable &alpha, const fq_nmod_ctx_t fq_con)
conversion of a FLINT factorization over Fq (for word size p) to a CFFList
CanonicalForm convertnmod_poly_t2FacCF(const nmod_poly_t poly, const Variable &x)
conversion of a FLINT poly over Z/p to CanonicalForm
void convertFacCF2Fq_nmod_poly_t(fq_nmod_poly_t result, const CanonicalForm &f, const fq_nmod_ctx_t ctx)
conversion of a factory univariate poly over F_q to a FLINT fq_nmod_poly_t
CFFList convertFLINTnmod_poly_factor2FacCFFList(const nmod_poly_factor_t fac, const mp_limb_t leadingCoeff, const Variable &x)
conversion of a FLINT factorization over Z/p (for word size p) to a CFFList
This file defines functions for conversion to FLINT (www.flintlib.org) and back.
Rational pow(const Rational &a, int e)
Definition GMPrat.cc:411
Rational abs(const Rational &a)
Definition GMPrat.cc:436
CFFList convertNTLvec_pair_GF2X_long2FacCFFList(const vec_pair_GF2X_long &e, GF2, const Variable &x)
NAME: convertNTLvec_pair_GF2X_long2FacCFFList.
zz_pEX convertFacCF2NTLzz_pEX(const CanonicalForm &f, const zz_pX &mipo)
CFFList convertNTLvec_pair_zzpEX_long2FacCFFList(const vec_pair_zz_pEX_long &e, const zz_pE &cont, const Variable &x, const Variable &alpha)
CFFList convertNTLvec_pair_GF2EX_long2FacCFFList(const vec_pair_GF2EX_long &e, const GF2E &cont, const Variable &x, const Variable &alpha)
NAME: convertNTLvec_pair_GF2EX_long2FacCFFList.
CanonicalForm convertNTLzzpX2CF(const zz_pX &poly, const Variable &x)
CFFList convertNTLvec_pair_zzpX_long2FacCFFList(const vec_pair_zz_pX_long &e, const zz_p cont, const Variable &x)
mat_zz_pE * convertFacCFMatrix2NTLmat_zz_pE(const CFMatrix &m)
GF2EX convertFacCF2NTLGF2EX(const CanonicalForm &f, const GF2X &mipo)
CanonicalForm in Z_2(a)[X] to NTL GF2EX.
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
mat_zz_p * convertFacCFMatrix2NTLmat_zz_p(const CFMatrix &m)
VAR long fac_NTL_char
Definition NTLconvert.cc:46
GF2X convertFacCF2NTLGF2X(const CanonicalForm &f)
NAME: convertFacCF2NTLGF2X.
Conversion to and from NTL.
#define swap(_i, _j)
bool isOn(int sw)
switches
void On(int sw)
switches
void Off(int sw)
switches
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Header for factory's main class CanonicalForm.
CanonicalForm FACTORY_PUBLIC content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition cf_gcd.cc:603
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition cf_ops.cc:600
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm div(const CanonicalForm &, const CanonicalForm &)
CanonicalForm lc(const CanonicalForm &f)
CanonicalForm FACTORY_PUBLIC icontent(const CanonicalForm &f)
CanonicalForm icontent ( const CanonicalForm & f )
Definition cf_gcd.cc:74
CanonicalForm FACTORY_PUBLIC replacevar(const CanonicalForm &, const Variable &, const Variable &)
CanonicalForm replacevar ( const CanonicalForm & f, const Variable & x1, const Variable & x2 )
Definition cf_ops.cc:271
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
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition cf_ops.cc:679
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
CanonicalForm den(const CanonicalForm &f)
int totaldegree(const CanonicalForm &f)
int totaldegree ( const CanonicalForm & f )
Definition cf_ops.cc:523
CanonicalForm Lc(const CanonicalForm &f)
CanonicalForm getGFGenerator()
Definition cf_char.cc:81
Factor< CanonicalForm > CFFactor
List< CanonicalForm > CFList
CanonicalForm LC(const CanonicalForm &f)
int FACTORY_PUBLIC getCharacteristic()
Definition cf_char.cc:70
static bool irreducible(const CFList &AS)
const CanonicalForm CFMap CFMap & N
Definition cfEzgcd.cc:56
int l
Definition cfEzgcd.cc:100
int m
Definition cfEzgcd.cc:128
int k
Definition cfEzgcd.cc:99
Variable x
Definition cfModGcd.cc:4090
int p
Definition cfModGcd.cc:4086
g
Definition cfModGcd.cc:4098
CanonicalForm test
Definition cfModGcd.cc:4104
int * getRightSide(int **polygon, int sizeOfPolygon, int &sizeOfOutput)
get the y-direction slopes of all edges with positive slope in y-direction of a convex polygon with a...
CanonicalForm decompress(const CanonicalForm &F, const mpz_t *inverseM, const mpz_t *A)
decompress a bivariate poly
int ** newtonPolygon(const CanonicalForm &F, int &sizeOfNewtonPoly)
compute the Newton polygon of a bivariate polynomial
This file provides functions to compute the Newton polygon of a bivariate polynomial.
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
assertions for Factory
#define ASSERT(expression, message)
Definition cf_assert.h:99
factory switches.
static const int SW_RATIONAL
set to 1 for computations over Q
Definition cf_defs.h:31
#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
map polynomials
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
CanonicalForm findMinPoly(const CanonicalForm &F, const Variable &alpha)
compute minimal polynomial of via NTL
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 ,...
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...
CanonicalForm map(const CanonicalForm &primElem, const Variable &alpha, const CanonicalForm &F, const Variable &beta)
map from to such that is mapped onto
This file implements functions to map between extensions of finite fields.
GLOBAL_VAR flint_rand_t FLINTrandom
Definition cf_random.cc:25
generate random integers, random elements of finite fields
VAR void(* factoryError)(const char *s)
Definition cf_util.cc:80
int igcd(int a, int b)
Definition cf_util.cc:56
int ipower(int b, int m)
int ipower ( int b, int m )
Definition cf_util.cc:27
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.
CF_NO_INLINE bool isOne() const
bool inCoeffDomain() const
int level() const
level() returns the level of CO.
CanonicalForm mapinto() const
DegreePattern provides a functionality to create, intersect and refine degree patterns.
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
void append(const T &)
T & getItem() const
T getFirst() const
void removeFirst()
int length() const
void append(const T &)
T getLast() const
void insert(const T &)
int isEmpty() const
factory's class for variables
Definition factory.h:127
int level() const
Definition factory.h:143
class to do operations mod p^k for int's p and k
Definition fac_util.h:23
functions to print debug output
#define DEBOUTLN(stream, objects)
Definition debug.h:49
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
CanonicalForm H
Definition facAbsFact.cc:60
CanonicalForm mipo
Definition facAlgExt.cc:57
CFFList append(const CFFList &Inputlist, const CFFactor &TheFactor)
CanonicalForm subst(const CanonicalForm &f, const CFList &a, const CFList &b, const CanonicalForm &Rstar, bool isFunctionField)
return modpk(p, k)
const Variable & v
< [in] a sqrfree bivariate poly
Definition facBivar.h:39
CanonicalForm LCF
CFList & eval
CFList *& Aeval
<[in] poly
int subsetDegree(const CFList &S)
compute the sum of degrees in Variable(1) of elements in S
CFArray logarithmicDerivative(const CanonicalForm &F, const CanonicalForm &G, int l, CanonicalForm &Q)
compute the coefficients of the logarithmic derivative of G mod Variable (2)^l over Fq
int * computeBounds(const CanonicalForm &F, int &n, bool &isIrreducible)
compute bounds for logarithmic derivative as described in K. Belabas, M. van Hoeij,...
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
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
CanonicalForm reverseSubst(const CanonicalForm &F, const int d, const Variable &x)
reverse a substitution x^d->x
CFArray getCoeffs(const CanonicalForm &F, const int k)
extract coefficients of for where is a variable of level 1
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)
void writeInMatrix(CFMatrix &M, const CFArray &A, const int column, const int startIndex)
write A into M starting at row startIndex
int substituteCheck(const CanonicalForm &F, const Variable &x)
check if a substitution x^n->x is possible
int * computeBoundsWrtDiffMainvar(const CanonicalForm &F, int &n, bool &isIrreducible)
as above just wrt to the other variable
This file provides utility functions for bivariate factorization.
CFList biFactorize(const CanonicalForm &F, const ExtensionInfo &info)
bivariate factorization over finite fields as decribed in "Factoring multivariate polynomials over a ...
void extEarlyFactorDetection(CFList &reconstructedFactors, CanonicalForm &F, CFList &factors, int &adaptedLiftBound, int *&factorsFoundIndex, DegreePattern &degs, bool &success, const ExtensionInfo &info, const CanonicalForm &eval, int deg)
detects factors of F at stage deg of Hensel lifting. No combinations of more than one factor are test...
CFList increasePrecision(CanonicalForm &F, CFList &factors, int factorsFound, int oldNumCols, int oldL, int precision, const CanonicalForm &eval)
CFList extFurtherLiftingAndIncreasePrecision(CanonicalForm &F, CFList &factors, int l, int liftBound, int d, int *bounds, nmod_mat_t FLINTN, CFList &diophant, CFMatrix &M, CFArray &Pi, CFArray &bufQ, const CanonicalForm &evaluation, const ExtensionInfo &info, CFList &source, CFList &dest)
return mod(mulNTL(buf1, buf2, b), M)
CFList extHenselLiftAndLatticeRecombi(const CanonicalForm &G, const CFList &uniFactors, const ExtensionInfo &extInfo, const DegreePattern &degPat, const CanonicalForm &eval)
CFList tmp1
Definition facFqBivar.cc:75
int * getCombinations(int *rightSide, int sizeOfRightSide, int &sizeOfOutput, int degreeLC)
CFList furtherLiftingAndIncreasePrecision(CanonicalForm &F, CFList &factors, int l, int liftBound, int d, int *bounds, nmod_mat_t FLINTN, CFList &diophant, CFMatrix &M, CFArray &Pi, CFArray &bufQ, const CanonicalForm &eval)
void deleteFactors(CFList &factors, int *factorsFoundIndex)
void extReconstructionTry(CFList &reconstructedFactors, CanonicalForm &F, const CFList &factors, const int liftBound, int &factorsFound, int *&factorsFoundIndex, mat_zz_p &N, bool beenInThres, const ExtensionInfo &info, const CanonicalForm &evaluation)
CanonicalForm buf2
Definition facFqBivar.cc:76
CFList extBiFactorize(const CanonicalForm &F, const ExtensionInfo &info)
Factorization over an extension of initial field.
int * getLiftPrecisions(const CanonicalForm &F, int &sizeOfOutput, int degreeLC)
compute lifting precisions from the shape of the Newton polygon of F
int liftAndComputeLatticeFq2Fp(const CanonicalForm &F, int *bounds, int sizeBounds, int start, int liftBound, int minBound, CFList &factors, nmod_mat_t FLINTN, CFList &diophant, CFMatrix &M, CFArray &Pi, CFArray &bufQ, bool &irreducible, const Variable &alpha)
CFList extReconstruction(CanonicalForm &G, CFList &factors, int *zeroOneVecs, int precision, const mat_zz_p &N, const ExtensionInfo &info, const CanonicalForm &evaluation)
int liftAndComputeLattice(const CanonicalForm &F, int *bounds, int sizeBounds, int start, int liftBound, int minBound, CFList &factors, mat_zz_p &NTLN, CFList &diophant, CFMatrix &M, CFArray &Pi, CFArray &bufQ, bool &irreducible)
CFList extEarlyReconstructionAndLifting(const CanonicalForm &F, const nmod_mat_t N, CanonicalForm &bufF, CFList &factors, int &l, int &factorsFound, bool beenInThres, CFMatrix &M, CFArray &Pi, CFList &diophant, const ExtensionInfo &info, const CanonicalForm &evaluation)
int * extractZeroOneVecs(const mat_zz_p &M)
CFList increasePrecisionFq2Fp(CanonicalForm &F, CFList &factors, int factorsFound, int oldNumCols, int oldL, const Variable &alpha, int precision, const CanonicalForm &eval)
CFList tmp2
Definition facFqBivar.cc:75
CFList extIncreasePrecision(CanonicalForm &F, CFList &factors, int factorsFound, int oldNumCols, int oldL, const CanonicalForm &evaluation, const ExtensionInfo &info, CFList &source, CFList &dest, int precision)
CFList monicReconstruction(CanonicalForm &G, CFList &factors, int *zeroOneVecs, int precision, const mat_zz_pE &N)
CFList henselLiftAndLatticeRecombi(const CanonicalForm &G, const CFList &uniFactors, const Variable &alpha, const DegreePattern &degPat, bool symmetric, const CanonicalForm &eval)
CFList reconstruction(CanonicalForm &G, CFList &factors, int *zeroOneVecs, int precision, const mat_zz_pE &N, const CanonicalForm &eval)
CFListIterator i
Definition facFqBivar.cc:74
CFList extSieveSmallFactors(const CanonicalForm &G, CFList &uniFactors, DegreePattern &degPat, CanonicalForm &H, CFList &diophant, CFArray &Pi, CFMatrix &M, bool &success, int d, const CanonicalForm &evaluation, const ExtensionInfo &info)
CFList extFactorRecombination(CFList &factors, CanonicalForm &F, const CanonicalForm &N, const ExtensionInfo &info, DegreePattern &degs, const CanonicalForm &eval, int s, int thres)
naive factor recombination as decribed in "Factoring multivariate polynomials over a finite field" by...
CanonicalForm evalPoint(const CanonicalForm &F, CanonicalForm &eval, const Variable &alpha, CFList &list, const bool &GF, bool &fail)
find an evaluation point p, s.t. F(p,y) is squarefree and .
Definition facFqBivar.cc:87
CFList henselLiftAndEarly(CanonicalForm &A, bool &earlySuccess, CFList &earlyFactors, DegreePattern &degs, int &liftBound, const CFList &uniFactors, const ExtensionInfo &info, const CanonicalForm &eval, modpk &b, CanonicalForm &den)
hensel Lifting and early factor detection
CFList sieveSmallFactors(const CanonicalForm &G, CFList &uniFactors, DegreePattern &degPat, CanonicalForm &H, CFList &diophant, CFArray &Pi, CFMatrix &M, bool &success, int d, const CanonicalForm &eval)
const CanonicalForm & M
Definition facFqBivar.cc:63
void refineAndRestartLift(const CanonicalForm &F, const nmod_mat_t FLINTN, int liftBound, int l, CFList &factors, CFMatrix &M, CFArray &Pi, CFList &diophant)
void reconstructionTry(CFList &reconstructedFactors, CanonicalForm &F, const CFList &factors, const int liftBound, int &factorsFound, int *&factorsFoundIndex, mat_zz_pE &N, const CanonicalForm &eval, bool beenInThres)
void earlyFactorDetection(CFList &reconstructedFactors, CanonicalForm &F, CFList &factors, int &adaptedLiftBound, int *&factorsFoundIndex, DegreePattern &degs, bool &success, int deg, const CanonicalForm &eval, const modpk &b, CanonicalForm &den)
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 ...
long isReduced(const mat_zz_p &M)
Variable chooseExtension(const Variable &alpha, const Variable &beta, int k)
chooses a field extension.
CFList factorRecombination(CFList &factors, CanonicalForm &F, const CanonicalForm &N, DegreePattern &degs, const CanonicalForm &eval, int s, int thres, const modpk &b, const CanonicalForm &den)
naive factor recombination as decribed in "Factoring multivariate polynomials over a finite field" by...
CFList earlyReconstructionAndLifting(const CanonicalForm &F, const nmod_mat_t N, CanonicalForm &bufF, CFList &factors, int &l, int &factorsFound, bool beenInThres, CFMatrix &M, CFArray &Pi, CFList &diophant, bool symmetric, const CanonicalForm &evaluation)
int extLiftAndComputeLattice(const CanonicalForm &F, int *bounds, int sizeBounds, int liftBound, int minBound, int start, CFList &factors, mat_zz_p &NTLN, CFList &diophant, CFMatrix &M, CFArray &Pi, CFArray &bufQ, bool &irreducible, const CanonicalForm &evaluation, const ExtensionInfo &info, CFList &source, CFList &dest)
CanonicalForm buf1
Definition facFqBivar.cc:76
ExtensionInfo init4ext(const ExtensionInfo &info, const CanonicalForm &evaluation, int &degMipo)
const CanonicalForm const modpk & b
Definition facFqBivar.cc:64
CFList increasePrecision2(const CanonicalForm &F, CFList &factors, const Variable &alpha, int precision)
CFList furtherLiftingAndIncreasePrecisionFq2Fp(CanonicalForm &F, CFList &factors, int l, int liftBound, int d, int *bounds, nmod_mat_t FLINTN, CFList &diophant, CFMatrix &M, CFArray &Pi, CFArray &bufQ, const Variable &alpha, const CanonicalForm &eval)
This file provides functions for factorizing a bivariate polynomial over , or GF.
CanonicalForm prodMod0(const CFList &L, const CanonicalForm &M, const modpk &b=modpk())
via divide-and-conquer
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...
fq_nmod_ctx_t fq_con
Definition facHensel.cc:99
int j
Definition facHensel.cc:110
fq_nmod_ctx_clear(fq_con)
nmod_poly_init(FLINTmipo, getCharacteristic())
fq_nmod_ctx_init_modulus(fq_con, FLINTmipo, "Z")
fq_nmod_poly_t prod
Definition facHensel.cc:100
void henselLift12(const CanonicalForm &F, CFList &factors, int l, CFArray &Pi, CFList &diophant, CFMatrix &M, modpk &b, bool sort)
Hensel lift from univariate to bivariate.
convertFacCF2nmod_poly_t(FLINTmipo, M)
void henselLiftResume12(const CanonicalForm &F, CFList &factors, int start, int end, CFArray &Pi, const CFList &diophant, CFMatrix &M, const modpk &b)
resume Hensel lift from univariate to bivariate. Assumes factors are lifted to precision Variable (2)...
nmod_poly_clear(FLINTmipo)
fq_nmod_poly_clear(prod, fq_con)
This file defines functions for Hensel lifting.
CanonicalForm mulNTL(const CanonicalForm &F, const CanonicalForm &G, const modpk &b)
multiplication of univariate polys using FLINT/NTL over F_p, F_q, Z/p^k, Z/p^k[t]/(f),...
Definition facMul.cc:416
bool uniFdivides(const CanonicalForm &A, const CanonicalForm &B)
divisibility test for univariate polys
Definition facMul.cc:3764
CanonicalForm mulMod2(const CanonicalForm &A, const CanonicalForm &B, const CanonicalForm &M)
Karatsuba style modular multiplication for bivariate polynomials.
Definition facMul.cc:2991
CanonicalForm prodMod(const CFList &L, const CanonicalForm &M)
product of all elements in L modulo M via divide-and-conquer.
Definition facMul.cc:3185
This file defines functions for fast multiplication and division with remainder.
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
#define const
Definition fegetopt.c:39
static BOOLEAN IsOne(number a, const coeffs)
Definition flintcf_Q.cc:388
static BOOLEAN IsZero(number a, const coeffs)
Definition flintcf_Q.cc:384
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 &)
bool isIrreducible(const CanonicalForm &f)
bool isIrreducible ( const CanonicalForm & f )
VAR char gf_name
Definition gfops.cc:52
INST_VAR CanonicalForm gf_mipo
Definition gfops.cc:56
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
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
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)