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
23#include "cf_assert.h"
24#include "cf_util.h"
25#include "debug.h"
26#include "timing.h"
27
28#include "canonicalform.h"
29#include "cf_defs.h"
30#include "cf_map_ext.h"
31#include "cf_random.h"
32#include "facHensel.h"
33#include "facMul.h"
34#include "cf_map.h"
35#include "cf_irred.h"
36#include "facFqBivarUtil.h"
37#include "facFqBivar.h"
38#include "cfNewtonPolygon.h"
39
40#ifdef HAVE_NTL
41#include "NTLconvert.h"
42#endif
43
44#ifdef HAVE_FLINT
45#include "FLINTconvert.h"
46#include "flint/nmod_poly_factor.h"
47#include "flint/fq_nmod_poly_factor.h"
48#endif
49
61
63{
64 if (L.isEmpty())
65 return 1;
66 else if (L.length() == 1)
67 return mod (L.getFirst()(0, 1) , M);
68 else if (L.length() == 2)
69 return mod (mulNTL (L.getFirst()(0, 1),L.getLast()(0, 1), b), M);
70 else
71 {
72 int l= L.length()/2;
76 for (int j= 1; j <= l; j++, i++)
77 tmp1.append (i.getItem());
78 tmp2= Difference (L, tmp1);
79 buf1= prodMod0 (tmp1, M, b);
80 buf2= prodMod0 (tmp2, M, b);
81 return mod (mulNTL (buf1,buf2, b), M);
82 }
83}
84
85#if defined(HAVE_NTL) || defined(HAVE_FLINT)
87 const Variable& alpha, CFList& list, const bool& GF,
88 bool& fail)
89{
90 fail= false;
96 double bound;
97 int p= getCharacteristic ();
98 if (alpha.level() != 1)
99 {
100 mipo= getMipo (alpha);
101 int d= degree (mipo);
102 bound= pow ((double) p, (double) d);
103 }
104 else if (GF)
105 {
106 int d= getGFDegree();
107 bound= ipower (p, d);
108 }
109 else
110 bound= p;
111
112 random= 0;
113 do
114 {
115 if (list.length() >= bound)
116 {
117 fail= true;
118 break;
119 }
120 if (list.isEmpty())
121 random= 0;
122 else if (GF)
123 {
124 if (list.length() == 1)
126 else
127 random= genGF.generate();
128 }
129 else if (list.length() < p || alpha.level() == 1)
130 random= genFF.generate();
131 else if (alpha != x && list.length() >= p)
132 {
133 if (list.length() == p)
134 random= alpha;
135 else
136 {
138 random= genAlgExt.generate();
139 }
140 }
141 if (find (list, random)) continue;
142 eval= F (random, x);
143 if (degree (eval) != degree (F, y))
144 { //leading coeff vanishes
145 if (!find (list, random))
146 list.append (random);
147 continue;
148 }
149 if (degree (gcd (deriv (eval, eval.mvar()), eval), eval.mvar()) > 0)
150 { //evaluated polynomial is not squarefree
151 if (!find (list, random))
152 list.append (random);
153 continue;
154 }
155 } while (find (list, random));
156
157 return random;
158}
159
160#if defined(HAVE_NTL) || defined(HAVE_FLINT)
161CFList
162uniFactorizer (const CanonicalForm& A, const Variable& alpha, const bool& GF)
163{
164 Variable x= A.mvar();
165 if (A.inCoeffDomain())
166 return CFList();
167 ASSERT (A.isUnivariate(),
168 "univariate polynomial expected or constant expected");
170 if (GF)
171 {
172 int k= getGFDegree();
173 char cGFName= gf_name;
178#ifdef HAVE_NTL
179 if (getCharacteristic() > 2)
180#else
181 if (getCharacteristic() > 0)
182#endif
183 {
184#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
189
192
194
197
200
202
204 beta, fq_con);
205
211#else
213 {
215 zz_p::init (getCharacteristic());
216 }
218 zz_pE::init (NTLMipo);
220 MakeMonic (NTLA);
222 zz_pE multi= to_zz_pE (1);
224 x, beta);
225#endif
226 }
227#ifdef HAVE_NTL
228 else
229 {
231 GF2E::init (NTLMipo);
233 MakeMonic (NTLA);
235 GF2E multi= to_GF2E (1);
237 x, beta);
238 }
239#endif
241 for (CFFListIterator i= factorsA; i.hasItem(); i++)
242 {
243 buf= i.getItem().factor();
245 i.getItem()= CFFactor (buf, i.getItem().exp());
246 }
247 prune (beta);
248 }
249 else if (alpha.level() != 1)
250 {
251#ifdef HAVE_NTL
252 if (getCharacteristic() > 2)
253#else
254 if (getCharacteristic() > 0)
255#endif
256 {
257#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
262
265
267
270
273
275
277 alpha, fq_con);
278
284#else
286 {
288 zz_p::init (getCharacteristic());
289 }
291 zz_pE::init (NTLMipo);
293 MakeMonic (NTLA);
295 zz_pE multi= to_zz_pE (1);
297 x, alpha);
298#endif
299 }
300#ifdef HAVE_NTL
301 else
302 {
304 GF2E::init (NTLMipo);
306 MakeMonic (NTLA);
308 GF2E multi= to_GF2E (1);
310 x, alpha);
311 }
312#endif
313 }
314 else
315 {
316#ifdef HAVE_FLINT
317#ifdef HAVE_NTL
318 if (degree (A) < 300)
319#endif
320 {
327 if (factorsA.getFirst().factor().inCoeffDomain())
331 }
332#ifdef HAVE_NTL
333 else
334#endif
335#endif /* HAVE_FLINT */
336#ifdef HAVE_NTL
337 if (getCharacteristic() > 2)
338 {
340 {
342 zz_p::init (getCharacteristic());
343 }
345 MakeMonic (NTLA);
347 zz_p multi= to_zz_p (1);
349 x);
350 }
351 else
352 {
355 GF2 multi= to_GF2 (1);
357 x);
358 }
359#endif
360 }
362 for (CFFListIterator i= factorsA; i.hasItem(); i++)
363 uniFactors.append (i.getItem().factor());
364 return uniFactors;
365}
366#endif
367
368#if defined(HAVE_NTL) || defined(HAVE_FLINT)
369/// naive factor recombination as decribed in "Factoring
370/// multivariate polynomials over a finite field" by L Bernardin.
371CFList
373 const CanonicalForm& N, const ExtensionInfo& info,
374 DegreePattern& degs, const CanonicalForm& eval, int s,
375 int thres)
376{
377 if (factors.length() == 0)
378 {
379 F= 1;
380 return CFList();
381 }
382 if (F.inCoeffDomain())
383 return CFList();
384
385 Variable alpha= info.getAlpha();
386 Variable beta= info.getBeta();
387 CanonicalForm gamma= info.getGamma();
388 CanonicalForm delta= info.getDelta();
389 int k= info.getGFDegree();
390
392 int l= degree (N);
393 Variable y= F.mvar();
394 Variable x= Variable (1);
395 CFList source, dest;
396 if (degs.getLength() <= 1 || factors.length() == 1)
397 {
398 CFList result= CFList(mapDown (F(y-eval, y), info, source, dest));
399 F= 1;
400 return result;
401 }
402
403 DEBOUTLN (cerr, "LC (F, 1)*prodMod (factors, M) == F " <<
404 (mod (LC (F, 1)*prodMod (factors, M), M)/Lc (mod (LC (F, 1)*prodMod (factors, M), M)) == F/Lc (F)));
405 int degMipoBeta= 1;
406 if (!k && beta.level() != 1)
408
409 CFList T, S, Diff;
410 T= factors;
411
414
415 buf= F;
416
418 int * v= new int [T.length()];
419 for (int i= 0; i < T.length(); i++)
420 v[i]= 0;
421
422 CFArray TT;
424 bufDegs1= degs;
425 int subsetDeg;
426 TT= copy (factors);
427 bool nosubset= false;
428 bool recombination= false;
429 bool trueFactor= false;
432 while (T.length() >= 2*s && s <= thres)
433 {
434 while (nosubset == false)
435 {
436 if (T.length() == s)
437 {
438 delete [] v;
439 if (recombination)
440 {
441 T.insert (LCBuf);
442 g= prodMod (T, M);
443 T.removeFirst();
444 g /= content(g);
445 g= g (y - eval, y);
446 g /= Lc (g);
448 F= 1;
449 return result;
450 }
451 else
452 {
453 appendMapDown (result, F (y - eval, y), info, source, dest);
454 F= 1;
455 return result;
456 }
457 }
458 S= subset (v, s, TT, nosubset);
459 if (nosubset) break;
461 // skip those combinations that are not possible
462 if (!degs.find (subsetDeg))
463 continue;
464 else
465 {
466 test= prodMod0 (S, M);
467 test *= LCBuf;
468 test = mod (test, M);
469 if (fdivides (test, buf0))
470 {
471 S.insert (LCBuf);
472 g= prodMod (S, M);
473 S.removeFirst();
474 g /= content (g, x);
475 if (fdivides (g, buf, quot))
476 {
477 buf2= g (y - eval, y);
478 buf2 /= Lc (buf2);
479
480 if (!k && beta.level() == 1)
481 {
482 if (degree (buf2, alpha) < degMipoBeta)
483 {
484 buf= quot;
485 LCBuf= LC (buf, x);
486 recombination= true;
488 trueFactor= true;
489 }
490 }
491 else
492 {
493 if (!isInExtension (buf2, gamma, k, delta, source, dest))
494 {
495 buf= quot;
496 LCBuf= LC (buf, x);
497 recombination= true;
499 trueFactor= true;
500 }
501 }
502 if (trueFactor)
503 {
504 T= Difference (T, S);
505 l -= degree (g);
506 M= power (y, l);
507 buf0= buf (0, x)*LCBuf;
508
509 // compute new possible degree pattern
511 bufDegs1.intersect (bufDegs2);
512 bufDegs1.refine ();
513 if (T.length() < 2*s || T.length() == s ||
514 bufDegs1.getLength() == 1)
515 {
516 delete [] v;
517 if (recombination)
518 {
519 buf= buf (y-eval,y);
520 buf /= Lc (buf);
522 dest);
523 F= 1;
524 return result;
525 }
526 else
527 {
528 appendMapDown (result, F (y - eval, y), info, source, dest);
529 F= 1;
530 return result;
531 }
532 }
533 trueFactor= false;
534 TT= copy (T);
535 indexUpdate (v, s, T.length(), nosubset);
536 if (nosubset) break;
537 }
538 }
539 }
540 }
541 }
542 s++;
543 if (T.length() < 2*s || T.length() == s)
544 {
545 delete [] v;
546 if (recombination)
547 {
548 buf= buf (y-eval,y);
549 buf /= Lc (buf);
551 F= 1;
552 return result;
553 }
554 else
555 {
556 appendMapDown (result, F (y - eval, y), info, source, dest);
557 F= 1;
558 return result;
559 }
560 }
561 for (int i= 0; i < T.length(); i++)
562 v[i]= 0;
563 nosubset= false;
564 }
565 if (T.length() < 2*s)
566 {
567 appendMapDown (result, F (y - eval, y), info, source, dest);
568 F= 1;
569 delete [] v;
570 return result;
571 }
572
573 if (s > thres)
574 {
575 factors= T;
576 F= buf;
577 degs= bufDegs1;
578 }
579
580 delete [] v;
581 return result;
582}
583#endif
584
585/// naive factor recombination as decribed in "Factoring
586/// multivariate polynomials over a finite field" by L Bernardin.
587CFList
589 const CanonicalForm& N, DegreePattern& degs, const
590 CanonicalForm& eval, int s, int thres, const modpk& b,
591 const CanonicalForm& den
592 )
593{
594 if (factors.length() == 0)
595 {
596 F= 1;
597 return CFList ();
598 }
599 if (F.inCoeffDomain())
600 return CFList();
601 Variable y= Variable (2);
602 if (degs.getLength() <= 1 || factors.length() == 1)
603 {
604 CFList result= CFList (F(y-eval,y));
605 F= 1;
606 return result;
607 }
608#ifdef DEBUGOUTPUT
609 if (b.getp() == 0)
610 DEBOUTLN (cerr, "LC (F, 1)*prodMod (factors, N) == F " <<
611 (mod (LC (F, 1)*prodMod (factors, N),N)/Lc (mod (LC (F, 1)*prodMod (factors, N),N)) == F/Lc(F)));
612 else
613 DEBOUTLN (cerr, "LC (F, 1)*prodMod (factors, N) == F " <<
614 (mod (b(LC (F, 1)*prodMod (factors, N)),N)/Lc (mod (b(LC (F, 1)*prodMod (factors, N)),N)) == F/Lc(F)));
615#endif
616
617 CFList T, S;
618
620 int l= degree (N);
621 T= factors;
623 Variable x= Variable (1);
626 CanonicalForm g, quot, buf= F;
627 int * v= new int [T.length()];
628 for (int i= 0; i < T.length(); i++)
629 v[i]= 0;
630 bool nosubset= false;
631 CFArray TT;
633 bufDegs1= degs;
634 int subsetDeg;
635 TT= copy (factors);
636 bool recombination= false;
638 bool isRat= (isOn (SW_RATIONAL) && getCharacteristic() == 0) ||
639 getCharacteristic() > 0;
640 if (!isRat)
641 On (SW_RATIONAL);
643 if (!isRat)
645 while (T.length() >= 2*s && s <= thres)
646 {
647 while (nosubset == false)
648 {
649 if (T.length() == s)
650 {
651 delete [] v;
652 if (recombination)
653 {
654 T.insert (LCBuf);
655 g= prodMod (T, M);
656 if (b.getp() != 0)
657 g= b(g);
658 T.removeFirst();
659 g /= content (g,x);
660 result.append (g(y-eval,y));
661 F= 1;
662 return result;
663 }
664 else
665 {
666 result= CFList (F(y-eval,y));
667 F= 1;
668 return result;
669 }
670 }
671 S= subset (v, s, TT, nosubset);
672 if (nosubset) break;
674 // skip those combinations that are not possible
675 if (!degs.find (subsetDeg))
676 continue;
677 else
678 {
679 if (!isRat)
680 On (SW_RATIONAL);
681 test= prodMod0 (S, M);
682 if (!isRat)
683 {
684 test *= bCommonDen (test);
686 }
687 test= mulNTL (test, LCBuf, b);
688 test= mod (test, M);
689 if (uniFdivides (test, buf0))
690 {
691 if (!isRat)
692 On (SW_RATIONAL);
693 S.insert (LCBuf);
694 g= prodMod (S, M);
695 S.removeFirst();
696 if (!isRat)
697 {
698 g *= bCommonDen(g);
700 }
701 if (b.getp() != 0)
702 g= b(g);
703 if (!isRat)
704 On (SW_RATIONAL);
705 g /= content (g, x);
706 if (!isRat)
707 {
708 On (SW_RATIONAL);
709 if (!Lc (g).inBaseDomain())
710 g /= Lc (g);
711 g *= bCommonDen (g);
713 g /= icontent (g);
714 On (SW_RATIONAL);
715 }
716 if (fdivides (g, buf, quot))
717 {
718 denom *= abs (lc (g));
719 recombination= true;
720 result.append (g (y-eval,y));
721 if (b.getp() != 0)
722 {
726 denom /= gcd (denom, denQuot);
727 On (SW_RATIONAL);
728 }
729 else
730 buf= quot;
731 LCBuf= LC (buf, x)*denom;
732 T= Difference (T, S);
733 l -= degree (g);
734 M= power (y, l);
735 buf0= mulNTL (buf (0, x), LCBuf);
736 if (!isRat)
738 // compute new possible degree pattern
740 bufDegs1.intersect (bufDegs2);
741 bufDegs1.refine ();
742 if (T.length() < 2*s || T.length() == s ||
743 bufDegs1.getLength() == 1)
744 {
745 delete [] v;
746 if (recombination)
747 {
748 result.append (buf (y-eval,y));
749 F= 1;
750 return result;
751 }
752 else
753 {
754 result= CFList (F (y-eval,y));
755 F= 1;
756 return result;
757 }
758 }
759 TT= copy (T);
760 indexUpdate (v, s, T.length(), nosubset);
761 if (nosubset) break;
762 }
763 if (!isRat)
765 }
766 }
767 }
768 s++;
769 if (T.length() < 2*s || T.length() == s)
770 {
771 delete [] v;
772 if (recombination)
773 {
774 result.append (buf(y-eval,y));
775 F= 1;
776 return result;
777 }
778 else
779 {
780 result= CFList (F(y-eval,y));
781 F= 1;
782 return result;
783 }
784 }
785 for (int i= 0; i < T.length(); i++)
786 v[i]= 0;
787 nosubset= false;
788 }
789 delete [] v;
790 if (T.length() < 2*s)
791 {
792 result.append (F(y-eval,y));
793 F= 1;
794 return result;
795 }
796
797 if (s > thres)
798 {
799 factors= T;
800 F= buf;
801 degs= bufDegs1;
802 }
803
804 return result;
805}
806
807#if defined(HAVE_NTL) || defined(HAVE_FLINT)
809{
810 int i=1, m= 2;
811 // extension of F_p needed
812 if (alpha.level() == 1 && beta.level() == 1 && k == 1)
813 {
814 i= 1;
815 m= 2;
816 } //extension of F_p(alpha) needed but want to factorize over F_p
817 else if (alpha.level() != 1 && beta.level() == 1 && k == 1)
818 {
819 i= 1;
820 m= degree (getMipo (alpha)) + 1;
821 } //extension of F_p(alpha) needed for first time
822 else if (alpha.level() != 1 && beta.level() == 1 && k != 1)
823 {
824 i= 2;
825 m= degree (getMipo (alpha));
826 }
827 else if (alpha.level() != 1 && beta.level() != 1 && k != 1)
828 {
829 m= degree (getMipo (beta));
830 i= degree (getMipo (alpha))/m + 1;
831 }
832 #if defined(HAVE_FLINT)
837 #elif defined(HAVE_NTL)
839 {
841 zz_p::init (getCharacteristic());
842 }
846 #else
847 factoryError("NTL/FLINT missing: chooseExtension");
848 #endif
849 return rootOf (newMipo);
850}
851#endif
852
853void
856 DegreePattern& degs, bool& success, int deg, const
858{
863 Variable x= Variable (1);
864 Variable y= Variable (2);
866 CanonicalForm M= power (F.mvar(), deg);
868 int d= degree (F), l= 0;
869 bool isRat= (isOn (SW_RATIONAL) && getCharacteristic() == 0) ||
870 getCharacteristic() > 0;
871 if (!isRat)
872 On (SW_RATIONAL);
873 if (b.getp() != 0)
874 buf *= bCommonDen (buf);
878 if (!isRat)
882
883 for (CFListIterator i= factors; i.hasItem(); i++, l++)
884 {
885 if (!bufDegs1.find (degree (i.getItem(), 1)) || factorsFoundIndex[l] == 1)
886 continue;
887 else
888 {
889 test1= mod (mulNTL (i.getItem() (1,x), LCBuf, b), M);
890 if (uniFdivides (test1, buf1))
891 {
892 test0= mod (mulNTL (i.getItem() (0,x), LCBuf, b), M);
893 if (uniFdivides (test0, buf0))
894 {
895 if (!isRat)
896 On (SW_RATIONAL);
897 g= mulMod2 (i.getItem(), LCBuf, M);
898 if (!isRat)
899 {
900 g *= bCommonDen(g);
902 }
903 if (b.getp() != 0)
904 g= b(g);
905 if (!isRat)
906 On (SW_RATIONAL);
907 g /= content (g, x);
908 if (!isRat)
909 {
910 On (SW_RATIONAL);
911 if (!Lc (g).inBaseDomain())
912 g /= Lc (g);
913 g *= bCommonDen (g);
915 g /= icontent (g);
916 On (SW_RATIONAL);
917 }
918 if (fdivides (g, buf, quot))
919 {
920 den *= abs (lc (g));
923 if (b.getp() != 0)
924 {
928 den /= gcd (den, denQuot);
929 On (SW_RATIONAL);
930 }
931 else
932 buf= quot;
933 d -= degree (g);
934 LCBuf= LC (buf, x)*den;
935 buf0= mulNTL (buf (0,x), LCBuf);
936 buf1= mulNTL (buf (1,x), LCBuf);
937 if (!isRat)
939 T= Difference (T, CFList (i.getItem()));
940 F= buf;
941
942 // compute new possible degree pattern
944 bufDegs1.intersect (bufDegs2);
945 bufDegs1.refine ();
946 if (bufDegs1.getLength() <= 1)
947 {
948 if (!buf.inCoeffDomain())
949 {
951 F= 1;
952 }
953 break;
954 }
955 }
956 if (!isRat)
958 }
959 }
960 }
961 }
962 adaptedLiftBound= d + 1;
963 if (adaptedLiftBound < deg)
964 {
965 degs= bufDegs1;
966 success= true;
967 }
968 if (bufDegs1.getLength() <= 1)
969 degs= bufDegs1;
970}
971
972void
982
983void
986 DegreePattern& degs, bool& success, const
987 ExtensionInfo& info, const CanonicalForm& eval, int deg
988 )
989{
990 Variable alpha= info.getAlpha();
991 Variable beta= info.getBeta();
992 CanonicalForm gamma= info.getGamma();
993 CanonicalForm delta= info.getDelta();
994 int k= info.getGFDegree();
998 Variable y= F.mvar();
999 Variable x= Variable (1);
1000 CanonicalForm buf= F, LCBuf= LC (buf, x), g, buf2;
1001 CanonicalForm M= power (y, deg);
1003 bool trueFactor= false;
1004 int d= degree (F), l= 0;
1005 CFList source, dest;
1006 int degMipoBeta= 1;
1007 if (!k && beta.level() != 1)
1010 for (CFListIterator i= factors; i.hasItem(); i++, l++)
1011 {
1012 if (!bufDegs1.find (degree (i.getItem(), 1)) || factorsFoundIndex[l] == 1)
1013 continue;
1014 else
1015 {
1016 g= mulMod2 (i.getItem(), LCBuf, M);
1017 g /= content (g, x);
1018 if (fdivides (g, buf, quot))
1019 {
1020 buf2= g (y - eval, y);
1021 buf2 /= Lc (buf2);
1022
1023 if (!k && beta == x)
1024 {
1025 if (degree (buf2, alpha) < degMipoBeta)
1026 {
1028 factorsFoundIndex[l]= 1;
1029 buf= quot;
1030 d -= degree (g);
1031 LCBuf= LC (buf, x);
1032 trueFactor= true;
1033 }
1034 }
1035 else
1036 {
1037 if (!isInExtension (buf2, gamma, k, delta, source, dest))
1038 {
1040 factorsFoundIndex[l]= 1;
1041 buf= quot;
1042 d -= degree (g);
1043 LCBuf= LC (buf, x);
1044 trueFactor= true;
1045 }
1046 }
1047 if (trueFactor)
1048 {
1049 T= Difference (T, CFList (i.getItem()));
1050 F= buf;
1051
1052 // compute new possible degree pattern
1054 bufDegs1.intersect (bufDegs2);
1055 bufDegs1.refine ();
1056 trueFactor= false;
1057 if (bufDegs1.getLength() <= 1)
1058 {
1059 if (!buf.inCoeffDomain())
1060 {
1061 buf= buf (y - eval, y);
1062 buf /= Lc (buf);
1064 F= 1;
1065 }
1066 break;
1067 }
1068 }
1069 }
1070 }
1071 }
1072 adaptedLiftBound= d + 1;
1073 if (adaptedLiftBound < deg)
1074 {
1075 degs= bufDegs1;
1076 success= true;
1077 }
1078 if (bufDegs1.getLength() <= 1)
1079 degs= bufDegs1;
1080}
1081
1082int*
1084 int degreeLC)
1085{
1086 Variable x= Variable (1);
1087 int p= getCharacteristic();
1088 int d= getGFDegree();
1089 char cGFName= gf_name;
1091 CanonicalForm buf= 1;
1092 for (int i= 0; i < sizeOfRightSide; i++)
1093 buf *= (power (x, rightSide [i]) + 1);
1094
1095 int j= 0;
1096 for (CFIterator i= buf; i.hasTerms(); i++, j++)
1097 {
1098 if (i.exp() < degreeLC)
1099 {
1100 j++;
1101 break;
1102 }
1103 }
1104
1105 ASSERT ( j > 1, "j > 1 expected" );
1106
1107 int* result = new int [j - 1];
1108 sizeOfOutput= j - 1;
1109
1110 int i= 0;
1111 for (CFIterator m = buf; i < j - 1; i++, m++)
1112 result [i]= m.exp();
1113
1114 if (d > 1)
1116 else
1118 return result;
1119}
1120
1121int *
1123{
1124 int sizeOfNewtonPoly;
1126 int sizeOfRightSide;
1129 degreeLC);
1130 delete [] rightSide;
1131 for (int i= 0; i < sizeOfNewtonPoly; i++)
1132 delete [] newtonPolyg[i];
1133 delete [] newtonPolyg;
1134 return result;
1135}
1136
1137void
1139{
1140 CFList result;
1141 int i= 0;
1142 for (CFListIterator iter= factors; iter.hasItem(); iter++, i++)
1143 {
1144 if (factorsFoundIndex[i] == 1)
1145 continue;
1146 else
1147 result.append (iter.getItem());
1148 }
1149 factors= result;
1150}
1151
1152#if defined(HAVE_NTL) || defined(HAVE_FLINT) // henselLift12
1153CFList
1156 const CFList& uniFactors, const ExtensionInfo& info,
1158{
1159 Variable alpha= info.getAlpha();
1160 Variable beta= info.getBeta();
1161 CanonicalForm gamma= info.getGamma();
1162 CanonicalForm delta= info.getDelta();
1163 bool extension= info.isInExtension();
1164
1165 int sizeOfLiftPre;
1166 int * liftPre= getLiftPrecisions (A, sizeOfLiftPre, degree (LC (A, 1), 2));
1167
1168 Variable x= Variable (1);
1169 Variable y= Variable (2);
1170 CFArray Pi;
1173 On (SW_RATIONAL);
1175 if (!Lc (A).inBaseDomain())
1176 {
1177 bufA /= Lc (A);
1179 bufA *= denBufA;
1180 Off (SW_RATIONAL);
1181 den /= gcd (den, denBufA);
1182 }
1183 else
1184 {
1185 bufA= A;
1186 Off (SW_RATIONAL);
1187 den /= gcd (den, Lc (A));
1188 }
1190 bool mipoHasDen= false;
1191 if (getCharacteristic() == 0 && b.getp() != 0)
1192 {
1193 if (alpha.level() == 1)
1194 {
1195 lcA0= lc (A (0, 2));
1196 A *= b.inverse (lcA0);
1197 A= b (A);
1199 i.getItem()= b (i.getItem()*b.inverse (lc (i.getItem())));
1200 }
1201 else
1202 {
1203 lcA0= Lc (A (0,2));
1204 On (SW_RATIONAL);
1206 Off (SW_RATIONAL);
1207 CanonicalForm lcA0inverse= b.inverse (lcA0);
1208 A *= lcA0inverse;
1209 A= b (A);
1210 // Lc of bufUniFactors is in Z
1212 i.getItem()= b (i.getItem()*b.inverse (lc (i.getItem())));
1213 }
1214 }
1215 bufUniFactors.insert (LC (A, x));
1217 earlySuccess= false;
1218 int newLiftBound= 0;
1219
1220 int smallFactorDeg= tmin (11, liftPre [sizeOfLiftPre- 1] + 1);//this is a tunable parameter
1221 int dummy;
1222 int * factorsFoundIndex= new int [uniFactors.length()];
1223 for (int i= 0; i < uniFactors.length(); i++)
1224 factorsFoundIndex [i]= 0;
1225
1227 Variable v= alpha;
1228 if (smallFactorDeg >= liftBound || degree (A,y) <= 4)
1230 else if (sizeOfLiftPre > 1 && sizeOfLiftPre < 30)
1231 {
1233 if (mipoHasDen)
1234 {
1235 for (CFListIterator iter= bufUniFactors; iter.hasItem(); iter++)
1236 if (hasFirstAlgVar (iter.getItem(), v))
1237 break;
1238 if (v != alpha)
1239 {
1241 for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
1242 iter.getItem()= replacevar (iter.getItem(), v, alpha);
1243 A= replacevar (A, alpha, v);
1244 }
1245 }
1246
1247 if (!extension)
1248 {
1249 if (v==alpha)
1253 else
1257 }
1258 else
1262 if (degs.getLength() > 1 && !earlySuccess &&
1264 {
1266 {
1267 bufUniFactors.insert (LC (A, x));
1269 liftPre[sizeOfLiftPre-1] + 1, Pi, diophant, M, b);
1270 if (v!=alpha)
1271 {
1273 for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
1274 iter.getItem()= replacevar (iter.getItem(), v, alpha);
1275 }
1276 if (!extension)
1277 {
1278 if (v==alpha)
1281 liftPre[sizeOfLiftPre-1] + 1, eval, b, den);
1282 else
1285 liftPre[sizeOfLiftPre-1] + 1, eval, b, den);
1286 }
1287 else
1290 eval, liftPre[sizeOfLiftPre-1] + 1);
1291 }
1292 }
1293 else if (earlySuccess)
1295
1296 int i= sizeOfLiftPre - 1;
1297 while (degs.getLength() > 1 && !earlySuccess && i - 1 >= 0)
1298 {
1299 if (newLiftBound >= liftPre[i] + 1)
1300 {
1301 bufUniFactors.insert (LC (A, x));
1303 liftPre[i-1] + 1, Pi, diophant, M, b);
1304 if (v!=alpha)
1305 {
1307 for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
1308 iter.getItem()= replacevar (iter.getItem(), v, alpha);
1309 }
1310 if (!extension)
1311 {
1312 if (v==alpha)
1315 liftPre[i-1] + 1, eval, b, den);
1316 else
1319 liftPre[i-1] + 1, eval, b, den);
1320 }
1321 else
1324 eval, liftPre[i-1] + 1);
1325 }
1326 else
1327 {
1329 break;
1330 }
1331 i--;
1332 }
1333 if (earlySuccess)
1335 //after here all factors are lifted to liftPre[sizeOfLiftPre-1]
1336 }
1337 else
1338 {
1340 if (mipoHasDen)
1341 {
1342 for (CFListIterator iter= bufUniFactors; iter.hasItem(); iter++)
1343 if (hasFirstAlgVar (iter.getItem(), v))
1344 break;
1345 if (v != alpha)
1346 {
1348 for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
1349 iter.getItem()= replacevar (iter.getItem(), v, alpha);
1350 A= replacevar (A, alpha, v);
1351 }
1352 }
1353 if (!extension)
1354 {
1355 if (v==alpha)
1359 else
1363 }
1364 else
1368 int i= 1;
1369 while ((degree (A,y)/4)*i + 4 <= smallFactorDeg)
1370 i++;
1371 dummy= tmin (degree (A,y)+1, (degree (A,y)/4)*i+4);
1372 if (degs.getLength() > 1 && !earlySuccess && dummy > smallFactorDeg)
1373 {
1374 bufUniFactors.insert (LC (A, x));
1376 dummy, Pi, diophant, M, b);
1377 if (v!=alpha)
1378 {
1380 for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
1381 iter.getItem()= replacevar (iter.getItem(), v, alpha);
1382 }
1383 if (!extension)
1384 {
1385 if (v==alpha)
1388 b, den);
1389 else
1392 b, den);
1393 }
1394 else
1397 eval, dummy);
1398 }
1399 while (degs.getLength() > 1 && !earlySuccess && i < 4)
1400 {
1401 if (newLiftBound >= dummy)
1402 {
1403 bufUniFactors.insert (LC (A, x));
1404 dummy= tmin (degree (A,y)+1, (degree (A,y)/4)*(i+1)+4);
1406 dummy, Pi, diophant, M, b);
1407 if (v!=alpha)
1408 {
1410 for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
1411 iter.getItem()= replacevar (iter.getItem(), v, alpha);
1412 }
1413 if (!extension)
1414 {
1415 if (v==alpha)
1418 eval, b, den);
1419 else
1422 eval, b, den);
1423 }
1424 else
1427 eval, dummy);
1428 }
1429 else
1430 {
1432 break;
1433 }
1434 i++;
1435 }
1436 if (earlySuccess)
1438 }
1439
1440 A= bufA;
1441 if (earlyFactors.length() > 0 && degs.getLength() > 1)
1442 {
1443 liftBound= degree (A,y) + 1;
1444 earlySuccess= true;
1446 }
1447
1448 delete [] factorsFoundIndex;
1449 delete [] liftPre;
1450
1451 return bufUniFactors;
1452}
1453#endif
1454
1455#ifdef HAVE_NTL // henselLiftAndEarly
1456CFList
1467#endif
1468
1469#ifdef HAVE_NTL
1470long isReduced (const mat_zz_p& M)
1471{
1472 long i, j, nonZero;
1473 for (i = 1; i <= M.NumRows(); i++)
1474 {
1475 nonZero= 0;
1476 for (j = 1; j <= M.NumCols(); j++)
1477 {
1478 if (!IsZero (M (i,j)))
1479 nonZero++;
1480 }
1481 if (nonZero != 1)
1482 return 0;
1483 }
1484 return 1;
1485}
1486#endif
1487
1488#ifdef HAVE_FLINT
1490{
1491 long i, j, nonZero;
1492 for (i = 1; i <= nmod_mat_nrows(M); i++)
1493 {
1494 nonZero= 0;
1495 for (j = 1; j <= nmod_mat_ncols (M); j++)
1496 {
1497 if (!(nmod_mat_entry (M, i-1, j-1)==0))
1498 nonZero++;
1499 }
1500 if (nonZero != 1)
1501 return 0;
1502 }
1503 return 1;
1504}
1505#endif
1506
1507#ifdef HAVE_NTL
1508long isReduced (const mat_zz_pE& M)
1509{
1510 long i, j, nonZero;
1511 for (i = 1; i <= M.NumRows(); i++)
1512 {
1513 nonZero= 0;
1514 for (j = 1; j <= M.NumCols(); j++)
1515 {
1516 if (!IsZero (M (i,j)))
1517 nonZero++;
1518 }
1519 if (nonZero != 1)
1520 return 0;
1521 }
1522 return 1;
1523}
1524#endif
1525
1526#ifdef HAVE_NTL
1528{
1529 long i, j;
1530 bool nonZeroOne= false;
1531 int * result= new int [M.NumCols()];
1532 for (i = 1; i <= M.NumCols(); i++)
1533 {
1534 for (j = 1; j <= M.NumRows(); j++)
1535 {
1536 if (!(IsOne (M (j,i)) || IsZero (M (j,i))))
1537 {
1538 nonZeroOne= true;
1539 break;
1540 }
1541 }
1542 if (!nonZeroOne)
1543 result [i - 1]= 1;
1544 else
1545 result [i - 1]= 0;
1546 nonZeroOne= false;
1547 }
1548 return result;
1549}
1550#endif
1551
1552#ifdef HAVE_FLINT
1554{
1555 long i, j;
1556 bool nonZeroOne= false;
1557 int * result= new int [nmod_mat_ncols (M)];
1558 for (i = 0; i < nmod_mat_ncols (M); i++)
1559 {
1560 for (j = 0; j < nmod_mat_nrows (M); j++)
1561 {
1562 if (!((nmod_mat_entry (M, j, i) == 1) || (nmod_mat_entry (M, j,i) == 0)))
1563 {
1564 nonZeroOne= true;
1565 break;
1566 }
1567 }
1568 if (!nonZeroOne)
1569 result [i]= 1;
1570 else
1571 result [i]= 0;
1572 nonZeroOne= false;
1573 }
1574 return result;
1575}
1576#endif
1577
1578#ifdef HAVE_NTL
1580{
1581 long i, j;
1582 bool nonZeroOne= false;
1583 int * result= new int [M.NumCols()];
1584 for (i = 1; i <= M.NumCols(); i++)
1585 {
1586 for (j = 1; j <= M.NumRows(); j++)
1587 {
1588 if (!(IsOne (M (j,i)) || IsZero (M (j,i))))
1589 {
1590 nonZeroOne= true;
1591 break;
1592 }
1593 }
1594 if (!nonZeroOne)
1595 result [i - 1]= 1;
1596 else
1597 result [i - 1]= 0;
1598 nonZeroOne= false;
1599 }
1600 return result;
1601}
1602#endif
1603
1604#ifdef HAVE_NTL
1605void
1607 factors, const int liftBound, int& factorsFound, int*&
1609 bool beenInThres
1610 )
1611{
1612 Variable y= Variable (2);
1613 Variable x= Variable (1);
1615 CanonicalForm bufF= F (y-eval, y);
1616 if (factors.length() == 2)
1617 {
1620 tmp2= factors.getLast();
1621 tmp1= mulMod2 (tmp1, LC (F,x), yToL);
1622 tmp1 /= content (tmp1, x);
1623 tmp1= tmp1 (y-eval, y);
1624 tmp2= mulMod2 (tmp2, LC (F,x), yToL);
1625 tmp2 /= content (tmp2, x);
1626 tmp2= tmp2 (y-eval, y);
1627 tmp3 = tmp1*tmp2;
1628 if (tmp3/Lc (tmp3) == bufF/Lc (bufF))
1629 {
1630 factorsFound++;
1631 F= 1;
1634 return;
1635 }
1636 }
1639 for (long i= 1; i <= N.NumCols(); i++)
1640 {
1641 if (factorsFoundIndex [i - 1] == 1)
1642 continue;
1643 iter= factors;
1644 if (beenInThres)
1645 {
1646 int count= 1;
1647 while (count < i)
1648 {
1649 count++;
1650 iter++;
1651 }
1652 buf= iter.getItem();
1653 }
1654 else
1655 {
1656 buf= 1;
1657 for (long j= 1; j <= N.NumRows(); j++, iter++)
1658 {
1659 if (!IsZero (N (j,i)))
1660 buf= mulMod2 (buf, iter.getItem(), yToL);
1661 }
1662 }
1663 buf= mulMod2 (buf, LC (F,x), yToL);
1664 buf /= content (buf, x);
1665 buf= buf (y-eval,y);
1666 if (fdivides (buf, bufF, quot))
1667 {
1668 factorsFoundIndex[i - 1]= 1;
1669 factorsFound++;
1670 bufF= quot;
1671 bufF /= Lc (bufF);
1673 }
1674 if (degree (bufF) <= 0)
1675 return;
1676 if (factorsFound + 1 == N.NumCols())
1677 {
1679 F= 1;
1680 return;
1681 }
1682 }
1683 if (reconstructedFactors.length() != 0)
1684 F= bufF (y+eval,y);
1685}
1686#endif
1687
1688#ifdef HAVE_NTL
1689void
1691 factors, const int liftBound, int& factorsFound, int*&
1693 bool beenInThres
1694 )
1695{
1696 Variable y= Variable (2);
1697 Variable x= Variable (1);
1699 CanonicalForm bufF= F (y-eval, y);
1700 if (factors.length() == 2)
1701 {
1704 tmp2= factors.getLast();
1705 tmp1= mulMod2 (tmp1, LC (F,x), yToL);
1706 tmp1 /= content (tmp1, x);
1707 tmp1= tmp1 (y-eval, y);
1708 tmp2= mulMod2 (tmp2, LC (F,x), yToL);
1709 tmp2 /= content (tmp2, x);
1710 tmp2= tmp2 (y-eval,y);
1711 tmp3 = tmp1*tmp2;
1712 if (tmp3/Lc (tmp3) == bufF/Lc (bufF))
1713 {
1714 factorsFound++;
1715 F= 1;
1718 return;
1719 }
1720 }
1723 for (long i= 1; i <= N.NumCols(); i++)
1724 {
1725 if (factorsFoundIndex [i - 1] == 1)
1726 continue;
1727 iter= factors;
1728 if (beenInThres)
1729 {
1730 int count= 1;
1731 while (count < i)
1732 {
1733 count++;
1734 iter++;
1735 }
1736 buf= iter.getItem();
1737 }
1738 else
1739 {
1740 buf= 1;
1741 for (long j= 1; j <= N.NumRows(); j++, iter++)
1742 {
1743 if (!IsZero (N (j,i)))
1744 buf= mulMod2 (buf, iter.getItem(), yToL);
1745 }
1746 }
1747 buf= mulMod2 (buf, LC (F,x), yToL);
1748 buf /= content (buf, x);
1749 buf= buf (y-eval,y);
1750 if (fdivides (buf, bufF, quot))
1751 {
1752 factorsFoundIndex[i - 1]= 1;
1753 factorsFound++;
1754 bufF= quot;
1755 bufF /= Lc (bufF);
1757 }
1758 if (degree (bufF) <= 0)
1759 return;
1760 if (factorsFound + 1 == N.NumCols())
1761 {
1763 F=1;
1764 return;
1765 }
1766 }
1767 if (reconstructedFactors.length() != 0)
1768 F= bufF (y+eval,y);
1769}
1770#endif
1771
1772#ifdef HAVE_FLINT
1773void
1775 factors, const int liftBound, int& factorsFound, int*&
1777 bool beenInThres
1778 )
1779{
1780 Variable y= Variable (2);
1781 Variable x= Variable (1);
1783 CanonicalForm bufF= F (y-eval, y);
1784 if (factors.length() == 2)
1785 {
1788 tmp2= factors.getLast();
1789 tmp1= mulMod2 (tmp1, LC (F,x), yToL);
1790 tmp1 /= content (tmp1, x);
1791 tmp1= tmp1 (y-eval, y);
1792 tmp2= mulMod2 (tmp2, LC (F,x), yToL);
1793 tmp2 /= content (tmp2, x);
1794 tmp2= tmp2 (y-eval, y);
1795 tmp3 = tmp1*tmp2;
1796 if (tmp3/Lc (tmp3) == bufF/Lc (bufF))
1797 {
1798 factorsFound++;
1799 F= 1;
1802 return;
1803 }
1804 }
1807 for (long i= 0; i < nmod_mat_ncols (N); i++)
1808 {
1809 if (factorsFoundIndex [i] == 1)
1810 continue;
1811 iter= factors;
1812 if (beenInThres)
1813 {
1814 int count= 0;
1815 while (count < i)
1816 {
1817 count++;
1818 iter++;
1819 }
1820 buf= iter.getItem();
1821 }
1822 else
1823 {
1824 buf= 1;
1825 for (long j= 0; j < nmod_mat_nrows (N); j++, iter++)
1826 {
1827 if (!(nmod_mat_entry (N, j, i) == 0))
1828 buf= mulMod2 (buf, iter.getItem(), yToL);
1829 }
1830 }
1831 buf= mulMod2 (buf, LC (F,x), yToL);
1832 buf /= content (buf, x);
1833 buf= buf (y-eval,y);
1834 if (fdivides (buf, bufF, quot))
1835 {
1836 factorsFoundIndex[i]= 1;
1837 factorsFound++;
1838 bufF= quot;
1839 bufF /= Lc (bufF);
1841 }
1842 if (degree (F) <= 0)
1843 return;
1844 if (factorsFound + 1 == nmod_mat_ncols (N))
1845 {
1846 F= 1;
1848 return;
1849 }
1850 }
1851 if (reconstructedFactors.length() != 0)
1852 F= bufF (y+eval,y);
1853}
1854#endif
1855
1856#ifdef HAVE_NTL
1857CFList
1859 precision, const mat_zz_pE& N, const CanonicalForm& eval
1860 )
1861{
1862 Variable y= Variable (2);
1863 Variable x= Variable (1);
1864 CanonicalForm F= G;
1870 for (long i= 1; i <= N.NumCols(); i++)
1871 {
1872 if (zeroOneVecs [i - 1] == 0)
1873 continue;
1874 iter= factors;
1875 buf= 1;
1877 for (long j= 1; j <= N.NumRows(); j++, iter++)
1878 {
1879 if (!IsZero (N (j,i)))
1880 {
1881 factorsConsidered.append (iter.getItem());
1882 buf= mulMod2 (buf, iter.getItem(), yToL);
1883 }
1884 }
1885 buf= mulMod2 (buf, LC (F,x), yToL);
1886 buf /= content (buf, x);
1887 if (fdivides (buf, F, quot))
1888 {
1889 F= quot;
1890 F /= Lc (F);
1891 result.append (buf (y-eval,y));
1893 }
1894 if (degree (F) <= 0)
1895 {
1896 G= F;
1898 return result;
1899 }
1900 }
1901 G= F;
1903 return result;
1904}
1905#endif
1906
1907#ifdef HAVE_NTL
1908CFList
1910 int precision, const mat_zz_pE& N
1911 )
1912{
1913 Variable y= Variable (2);
1914 Variable x= Variable (1);
1915 CanonicalForm F= G;
1918 CFList result;
1922 for (long i= 1; i <= N.NumCols(); i++)
1923 {
1924 if (zeroOneVecs [i - 1] == 0)
1925 continue;
1926 iter= factors;
1927 buf= 1;
1929 for (long j= 1; j <= N.NumRows(); j++, iter++)
1930 {
1931 if (!IsZero (N (j,i)))
1932 {
1933 factorsConsidered.append (iter.getItem());
1934 buf= mulMod2 (buf, iter.getItem(), yToL);
1935 }
1936 }
1937 buf2= buf;
1938 buf= mulMod2 (buf, LC (F,x), yToL);
1939 buf /= content (buf, x);
1940 if (fdivides (buf, F, quot))
1941 {
1942 F= quot;
1943 F /= Lc (F);
1944 result.append (buf2);
1946 }
1947 if (degree (F) <= 0)
1948 {
1949 G= F;
1951 return result;
1952 }
1953 }
1954 G= F;
1956 return result;
1957}
1958#endif
1959
1960#ifdef HAVE_NTL
1961CFList
1963 precision, const mat_zz_p& N, const ExtensionInfo& info,
1965 )
1966{
1967 Variable y= Variable (2);
1968 Variable x= Variable (1);
1969 Variable alpha= info.getAlpha();
1970 Variable beta= info.getBeta();
1971 int k= info.getGFDegree();
1972 CanonicalForm gamma= info.getGamma();
1973 CanonicalForm delta= info.getDelta();
1974 CanonicalForm F= G;
1976 CFList result;
1981 for (long i= 1; i <= N.NumCols(); i++)
1982 {
1983 if (zeroOneVecs [i - 1] == 0)
1984 continue;
1985 iter= factors;
1986 buf= 1;
1988 for (long j= 1; j <= N.NumRows(); j++, iter++)
1989 {
1990 if (!IsZero (N (j,i)))
1991 {
1992 factorsConsidered.append (iter.getItem());
1993 buf= mulMod2 (buf, iter.getItem(), yToL);
1994 }
1995 }
1996 buf= mulMod2 (buf, LC (F,x), yToL);
1997 buf /= content (buf, x);
1998 buf2= buf (y-evaluation, y);
1999 buf2 /= Lc (buf2);
2000 if (!k && beta == x)
2001 {
2002 if (degree (buf2, alpha) < 1)
2003 {
2004 if (fdivides (buf, F, quot))
2005 {
2006 F= quot;
2007 F /= Lc (F);
2008 result.append (buf2);
2010 }
2011 }
2012 }
2013 else
2014 {
2015 CFList source, dest;
2016
2017 if (!isInExtension (buf2, gamma, k, delta, source, dest))
2018 {
2019 if (fdivides (buf, F, quot))
2020 {
2021 F= quot;
2022 F /= Lc (F);
2023 result.append (buf2);
2025 }
2026 }
2027 }
2028 if (degree (F) <= 0)
2029 {
2030 G= F;
2032 return result;
2033 }
2034 }
2035 G= F;
2037 return result;
2038}
2039#endif
2040
2041#ifdef HAVE_FLINT
2042CFList
2044 precision, const nmod_mat_t N, const ExtensionInfo& info,
2046 )
2047{
2048 Variable y= Variable (2);
2049 Variable x= Variable (1);
2050 Variable alpha= info.getAlpha();
2051 Variable beta= info.getBeta();
2052 int k= info.getGFDegree();
2053 CanonicalForm gamma= info.getGamma();
2054 CanonicalForm delta= info.getDelta();
2055 CanonicalForm F= G;
2057 CFList result;
2062 for (long i= 0; i < nmod_mat_ncols(N); i++)
2063 {
2064 if (zeroOneVecs [i] == 0)
2065 continue;
2066 iter= factors;
2067 buf= 1;
2069 for (long j= 0; j < nmod_mat_nrows(N); j++, iter++)
2070 {
2071 if (!(nmod_mat_entry (N, j, i) == 0))
2072 {
2073 factorsConsidered.append (iter.getItem());
2074 buf= mulMod2 (buf, iter.getItem(), yToL);
2075 }
2076 }
2077 buf= mulMod2 (buf, LC (F,x), yToL);
2078 buf /= content (buf, x);
2079 buf2= buf (y-evaluation, y);
2080 buf2 /= Lc (buf2);
2081 if (!k && beta == x)
2082 {
2083 if (degree (buf2, alpha) < 1)
2084 {
2085 if (fdivides (buf, F, quot))
2086 {
2087 F= quot;
2088 F /= Lc (F);
2089 result.append (buf2);
2091 }
2092 }
2093 }
2094 else
2095 {
2096 CFList source, dest;
2097
2098 if (!isInExtension (buf2, gamma, k, delta, source, dest))
2099 {
2100 if (fdivides (buf, F, quot))
2101 {
2102 F= quot;
2103 F /= Lc (F);
2104 result.append (buf2);
2106 }
2107 }
2108 }
2109 if (degree (F) <= 0)
2110 {
2111 G= F;
2113 return result;
2114 }
2115 }
2116 G= F;
2118 return result;
2119}
2120#endif
2121
2122#ifdef HAVE_NTL
2123CFList
2125 int precision, const mat_zz_p& N, const CanonicalForm& eval)
2126{
2127 Variable y= Variable (2);
2128 Variable x= Variable (1);
2129 CanonicalForm F= G;
2132 CFList result;
2136 for (long i= 1; i <= N.NumCols(); i++)
2137 {
2138 if (zeroOneVecs [i - 1] == 0)
2139 continue;
2140 iter= factors;
2141 buf= 1;
2143 for (long j= 1; j <= N.NumRows(); j++, iter++)
2144 {
2145 if (!IsZero (N (j,i)))
2146 {
2147 factorsConsidered.append (iter.getItem());
2148 buf= mulMod2 (buf, iter.getItem(), yToL);
2149 }
2150 }
2151 buf= mulMod2 (buf, LC (F,x), yToL);
2152 buf /= content (buf, x);
2153 if (fdivides (buf, F, quot))
2154 {
2155 F= quot;
2156 F /= Lc (F);
2157 result.append (buf (y-eval,y));
2159 }
2160 if (degree (F) <= 0)
2161 {
2162 G= F;
2164 return result;
2165 }
2166 }
2167 G= F;
2169 return result;
2170}
2171#endif
2172
2173#ifdef HAVE_FLINT
2174CFList
2176 int precision, const nmod_mat_t N, const CanonicalForm& eval)
2177{
2178 Variable y= Variable (2);
2179 Variable x= Variable (1);
2180 CanonicalForm F= G;
2183 CFList result;
2187 for (long i= 0; i < nmod_mat_ncols (N); i++)
2188 {
2189 if (zeroOneVecs [i] == 0)
2190 continue;
2191 iter= factors;
2192 buf= 1;
2194 for (long j= 0; j < nmod_mat_nrows (N); j++, iter++)
2195 {
2196 if (!(nmod_mat_entry (N, j, i) == 0))
2197 {
2198 factorsConsidered.append (iter.getItem());
2199 buf= mulMod2 (buf, iter.getItem(), yToL);
2200 }
2201 }
2202 buf= mulMod2 (buf, LC (F,x), yToL);
2203 buf /= content (buf, x);
2204 if (fdivides (buf, F, quot))
2205 {
2206 F= quot;
2207 F /= Lc (F);
2208 result.append (buf (y-eval,y));
2210 }
2211 if (degree (F) <= 0)
2212 {
2213 G= F;
2215 return result;
2216 }
2217 }
2218 G= F;
2220 return result;
2221}
2222#endif
2223
2224#ifdef HAVE_NTL
2225void
2227 CFList& factors, const int liftBound, int& factorsFound,
2230 )
2231{
2232 Variable y= Variable (2);
2233 Variable x= Variable (1);
2234 Variable alpha= info.getAlpha();
2235 Variable beta= info.getBeta();
2236 int k= info.getGFDegree();
2237 CanonicalForm gamma= info.getGamma();
2238 CanonicalForm delta= info.getDelta();
2240 CFList source, dest;
2241 if (factors.length() == 2)
2242 {
2245 tmp2= factors.getLast();
2246 tmp1= mulMod2 (tmp1, LC (F,x), yToL);
2247 tmp1 /= content (tmp1, x);
2248 tmp2= mulMod2 (tmp2, LC (F,x), yToL);
2249 tmp2 /= content (tmp2, x);
2250 tmp3 = tmp1*tmp2;
2251 if (tmp3/Lc (tmp3) == F/Lc (F))
2252 {
2253 tmp1= tmp1 (y - evaluation, y);
2254 tmp2= tmp2 (y - evaluation, y);
2255 tmp1 /= Lc (tmp1);
2256 tmp2 /= Lc (tmp2);
2257 if (!k && beta == x && degree (tmp2, alpha) < 1 &&
2258 degree (tmp1, alpha) < 1)
2259 {
2260 factorsFound++;
2261 F= 1;
2262 tmp1= mapDown (tmp1, info, source, dest);
2263 tmp2= mapDown (tmp2, info, source, dest);
2266 return;
2267 }
2268 else if (!isInExtension (tmp2, gamma, k, delta, source, dest) &&
2269 !isInExtension (tmp1, gamma, k, delta, source, dest))
2270 {
2271 factorsFound++;
2272 F= 1;
2273 tmp1= mapDown (tmp1, info, source, dest);
2274 tmp2= mapDown (tmp2, info, source, dest);
2277 return;
2278 }
2279 }
2280 }
2283 for (long i= 1; i <= N.NumCols(); i++)
2284 {
2285 if (factorsFoundIndex [i - 1] == 1)
2286 continue;
2287 iter= factors;
2288 if (beenInThres)
2289 {
2290 int count= 1;
2291 while (count < i)
2292 {
2293 count++;
2294 iter++;
2295 }
2296 buf= iter.getItem();
2297 }
2298 else
2299 {
2300 buf= 1;
2301 for (long j= 1; j <= N.NumRows(); j++, iter++)
2302 {
2303 if (!IsZero (N (j,i)))
2304 buf= mulMod2 (buf, iter.getItem(), yToL);
2305 }
2306 }
2307 buf= mulMod2 (buf, LC (F,x), yToL);
2308 buf /= content (buf, x);
2309 buf2= buf (y - evaluation, y);
2310 buf2 /= Lc (buf2);
2311 if (!k && beta == x)
2312 {
2313 if (degree (buf2, alpha) < 1)
2314 {
2315 if (fdivides (buf, F, quot))
2316 {
2317 factorsFoundIndex[i - 1]= 1;
2318 factorsFound++;
2319 F= quot;
2320 F /= Lc (F);
2321 buf2= mapDown (buf2, info, source, dest);
2323 }
2324 }
2325 }
2326 else
2327 {
2328 if (!isInExtension (buf2, gamma, k, delta, source, dest))
2329 {
2330 if (fdivides (buf, F, quot))
2331 {
2332 factorsFoundIndex[i - 1]= 1;
2333 factorsFound++;
2334 F= quot;
2335 F /= Lc (F);
2336 buf2= mapDown (buf2, info, source, dest);
2338 }
2339 }
2340 }
2341 if (degree (F) <= 0)
2342 return;
2343 if (factorsFound + 1 == N.NumCols())
2344 {
2345 CanonicalForm tmp= F (y - evaluation, y);
2346 tmp= mapDown (tmp, info, source, dest);
2348 return;
2349 }
2350 }
2351}
2352#endif
2353
2354#ifdef HAVE_FLINT
2355void
2357 CFList& factors, const int liftBound, int& factorsFound,
2360 )
2361{
2362 Variable y= Variable (2);
2363 Variable x= Variable (1);
2364 Variable alpha= info.getAlpha();
2365 Variable beta= info.getBeta();
2366 int k= info.getGFDegree();
2367 CanonicalForm gamma= info.getGamma();
2368 CanonicalForm delta= info.getDelta();
2370 CFList source, dest;
2371 if (factors.length() == 2)
2372 {
2375 tmp2= factors.getLast();
2376 tmp1= mulMod2 (tmp1, LC (F,x), yToL);
2377 tmp1 /= content (tmp1, x);
2378 tmp2= mulMod2 (tmp2, LC (F,x), yToL);
2379 tmp2 /= content (tmp2, x);
2380 tmp3 = tmp1*tmp2;
2381 if (tmp3/Lc (tmp3) == F/Lc (F))
2382 {
2383 tmp1= tmp1 (y - evaluation, y);
2384 tmp2= tmp2 (y - evaluation, y);
2385 tmp1 /= Lc (tmp1);
2386 tmp2 /= Lc (tmp2);
2387 if (!k && beta == x && degree (tmp2, alpha) < 1 &&
2388 degree (tmp1, alpha) < 1)
2389 {
2390 factorsFound++;
2391 F= 1;
2392 tmp1= mapDown (tmp1, info, source, dest);
2393 tmp2= mapDown (tmp2, info, source, dest);
2396 return;
2397 }
2398 else if (!isInExtension (tmp2, gamma, k, delta, source, dest) &&
2399 !isInExtension (tmp1, gamma, k, delta, source, dest))
2400 {
2401 factorsFound++;
2402 F= 1;
2403 tmp1= mapDown (tmp1, info, source, dest);
2404 tmp2= mapDown (tmp2, info, source, dest);
2407 return;
2408 }
2409 }
2410 }
2413 for (long i= 0; i < nmod_mat_ncols (N); i++)
2414 {
2415 if (factorsFoundIndex [i] == 1)
2416 continue;
2417 iter= factors;
2418 if (beenInThres)
2419 {
2420 int count= 0;
2421 while (count < i)
2422 {
2423 count++;
2424 iter++;
2425 }
2426 buf= iter.getItem();
2427 }
2428 else
2429 {
2430 buf= 1;
2431 for (long j= 0; j < nmod_mat_nrows (N); j++, iter++)
2432 {
2433 if (!(nmod_mat_entry (N, j, i) == 0))
2434 buf= mulMod2 (buf, iter.getItem(), yToL);
2435 }
2436 }
2437 buf= mulMod2 (buf, LC (F,x), yToL);
2438 buf /= content (buf, x);
2439 buf2= buf (y - evaluation, y);
2440 buf2 /= Lc (buf2);
2441 if (!k && beta == x)
2442 {
2443 if (degree (buf2, alpha) < 1)
2444 {
2445 if (fdivides (buf, F, quot))
2446 {
2447 factorsFoundIndex[i]= 1;
2448 factorsFound++;
2449 F= quot;
2450 F /= Lc (F);
2451 buf2= mapDown (buf2, info, source, dest);
2453 }
2454 }
2455 }
2456 else
2457 {
2458 if (!isInExtension (buf2, gamma, k, delta, source, dest))
2459 {
2460 if (fdivides (buf, F, quot))
2461 {
2462 factorsFoundIndex[i]= 1;
2463 factorsFound++;
2464 F= quot;
2465 F /= Lc (F);
2466 buf2= mapDown (buf2, info, source, dest);
2468 }
2469 }
2470 }
2471 if (degree (F) <= 0)
2472 return;
2473 if (factorsFound + 1 == nmod_mat_nrows (N))
2474 {
2475 CanonicalForm tmp= F (y - evaluation, y);
2476 tmp= mapDown (tmp, info, source, dest);
2478 return;
2479 }
2480 }
2481}
2482#endif
2483
2484#ifdef HAVE_NTL
2485//over Fp
2486int
2488 start, int liftBound, int minBound, CFList& factors,
2490 Pi, CFArray& bufQ, bool& irreducible
2491 )
2492{
2493 CanonicalForm LCF= LC (F, 1);
2494 CFArray *A= new CFArray [factors.length() - 1];
2495 bool wasInBounds= false;
2496 bool hitBound= false;
2497 int l= (minBound+1)*2;
2498 int stepSize= 2;
2499 int oldL= l/2;
2500 bool reduced= false;
2501 mat_zz_p NTLK, *NTLC;
2502 CFMatrix C;
2503 CFArray buf;
2506 Variable y= F.mvar();
2507 while (l <= liftBound)
2508 {
2510 if (start)
2511 {
2512 henselLiftResume12 (F, factors, start, l, Pi, diophant, M);
2513 start= 0;
2514 }
2515 else
2516 {
2517 if (wasInBounds)
2519 else
2520 henselLift12 (F, factors, l, Pi, diophant, M);
2521 }
2523 "time to lift in compute lattice: ");
2524
2525 factors.insert (LCF);
2526 j= factors;
2527 j++;
2528
2529 truncF= mod (F, power (y, l));
2531 for (int i= 0; i < factors.length() - 1; i++, j++)
2532 {
2533 if (!wasInBounds)
2534 A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ[i]);
2535 else
2536 A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
2537 bufQ[i]);
2538 }
2540 "time to compute logarithmic derivative: ");
2541
2542 for (int i= 0; i < sizeBounds; i++)
2543 {
2544 if (bounds [i] + 1 <= l/2)
2545 {
2546 wasInBounds= true;
2547 int k= tmin (bounds [i] + 1, l/2);
2548 C= CFMatrix (l - k, factors.length() - 1);
2549 for (int ii= 0; ii < factors.length() - 1; ii++)
2550 {
2551 if (A[ii].size() - 1 >= i)
2552 {
2553 buf= getCoeffs (A[ii] [i], k);
2554 writeInMatrix (C, buf, ii + 1, 0);
2555 }
2556 }
2558 NTLK= (*NTLC)*NTLN;
2559 transpose (NTLK, NTLK);
2560 kernel (NTLK, NTLK);
2561 transpose (NTLK, NTLK);
2562 NTLN *= NTLK;
2563 delete NTLC;
2564
2565 if (NTLN.NumCols() == 1)
2566 {
2567 irreducible= true;
2568 break;
2569 }
2570 if (isReduced (NTLN) && l > (minBound+1)*2)
2571 {
2572 reduced= true;
2573 break;
2574 }
2575 }
2576 }
2577
2578 if (irreducible)
2579 break;
2580 if (reduced)
2581 break;
2582 oldL= l;
2583 l += stepSize;
2584 stepSize *= 2;
2585 if (l > liftBound)
2586 {
2587 if (!hitBound)
2588 {
2589 l= liftBound;
2590 hitBound= true;
2591 }
2592 else
2593 break;
2594 }
2595 }
2596 delete [] A;
2597 if (!wasInBounds)
2598 {
2599 if (start)
2600 henselLiftResume12 (F, factors, start, degree (F) + 1, Pi, diophant, M);
2601 else
2602 henselLift12 (F, factors, degree (F) + 1, Pi, diophant, M);
2603 factors.insert (LCF);
2604 }
2605 return l;
2606}
2607#endif
2608
2609#ifdef HAVE_FLINT
2610#ifdef HAVE_NTL // henselLift12
2611int
2613 start, int liftBound, int minBound, CFList& factors,
2615 Pi, CFArray& bufQ, bool& irreducible
2616 )
2617{
2618 CanonicalForm LCF= LC (F, 1);
2619 CFArray *A= new CFArray [factors.length() - 1];
2620 bool wasInBounds= false;
2621 bool hitBound= false;
2622 int l= (minBound+1)*2;
2623 int stepSize= 2;
2624 int oldL= l/2;
2625 bool reduced= false;
2626 long rank;
2628 CFMatrix C;
2629 CFArray buf;
2632 Variable y= F.mvar();
2633 while (l <= liftBound)
2634 {
2636 if (start)
2637 {
2638 henselLiftResume12 (F, factors, start, l, Pi, diophant, M);
2639 start= 0;
2640 }
2641 else
2642 {
2643 if (wasInBounds)
2645 else
2646 henselLift12 (F, factors, l, Pi, diophant, M);
2647 }
2649 "time to lift in compute lattice: ");
2650
2651 factors.insert (LCF);
2652 j= factors;
2653 j++;
2654
2655 truncF= mod (F, power (y, l));
2657 for (int i= 0; i < factors.length() - 1; i++, j++)
2658 {
2659 if (!wasInBounds)
2660 A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ[i]);
2661 else
2662 A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
2663 bufQ[i]);
2664 }
2666 "time to compute logarithmic derivative: ");
2667
2668 for (int i= 0; i < sizeBounds; i++)
2669 {
2670 if (bounds [i] + 1 <= l/2)
2671 {
2672 wasInBounds= true;
2673 int k= tmin (bounds [i] + 1, l/2);
2674 C= CFMatrix (l - k, factors.length() - 1);
2675 for (int ii= 0; ii < factors.length() - 1; ii++)
2676 {
2677 if (A[ii].size() - 1 >= i)
2678 {
2679 buf= getCoeffs (A[ii] [i], k);
2680 writeInMatrix (C, buf, ii + 1, 0);
2681 }
2682 }
2683
2698 nmod_mat_mul (FLINTN, FLINTC, FLINTK); //no aliasing allowed!!
2699
2703 if (nmod_mat_ncols (FLINTN) == 1)
2704 {
2705 irreducible= true;
2706 break;
2707 }
2708 if (isReduced (FLINTN) && l > (minBound+1)*2)
2709 {
2710 reduced= true;
2711 break;
2712 }
2713 }
2714 }
2715
2716 if (irreducible)
2717 break;
2718 if (reduced)
2719 break;
2720 oldL= l;
2721 l += stepSize;
2722 stepSize *= 2;
2723 if (l > liftBound)
2724 {
2725 if (!hitBound)
2726 {
2727 l= liftBound;
2728 hitBound= true;
2729 }
2730 else
2731 break;
2732 }
2733 }
2734 delete [] A;
2735 if (!wasInBounds)
2736 {
2737 if (start)
2738 henselLiftResume12 (F, factors, start, degree (F) + 1, Pi, diophant, M);
2739 else
2740 henselLift12 (F, factors, degree (F) + 1, Pi, diophant, M);
2741 factors.insert (LCF);
2742 }
2743 return l;
2744}
2745#endif
2746#endif
2747
2748#ifdef HAVE_NTL
2749//over field extension
2750int
2752 int liftBound, int minBound, int start, CFList&
2754 CFMatrix& M, CFArray& Pi, CFArray& bufQ, bool&
2755 irreducible, const CanonicalForm& evaluation, const
2757 )
2758{
2760 CanonicalForm LCF= LC (F, 1);
2761 CFArray *A= new CFArray [factors.length() - 1];
2762 bool wasInBounds= false;
2763 bool hitBound= false;
2764 int degMipo;
2766 alpha= info.getAlpha();
2768
2769 Variable gamma= info.getBeta();
2770 CanonicalForm primElemAlpha= info.getGamma();
2772
2773 int stepSize= 2;
2774 int l= ((minBound+1)/degMipo+1)*2;
2775 l= tmax (l, 2);
2776 if (start > l)
2777 l= start;
2778 int oldL= l/2;
2779 bool reduced= false;
2780 Variable y= F.mvar();
2781 Variable x= Variable (1);
2783 CFMatrix Mat, C;
2784 CFArray buf;
2788 while (l <= liftBound)
2789 {
2791 if (start)
2792 {
2793 henselLiftResume12 (F, factors, start, l, Pi, diophant, M);
2794 start= 0;
2795 }
2796 else
2797 {
2798 if (wasInBounds)
2800 else
2801 henselLift12 (F, factors, l, Pi, diophant, M);
2802 }
2804 "time to lift in compute lattice: ");
2805
2806 factors.insert (LCF);
2807
2808 if (GF)
2810
2811 powX= power (y-gamma, l);
2813 for (int i= 0; i < l*degMipo; i++)
2814 {
2815 imBasis= mod (power (y, i), powX);
2816 imBasis= imBasis (power (y, degMipo), y);
2817 imBasis= imBasis (y, gamma);
2818 iter= imBasis;
2819 for (; iter.hasTerms(); iter++)
2820 Mat (iter.exp()+ 1, i+1)= iter.coeff();
2821 }
2822
2824 *NTLMat= inv (*NTLMat);
2825
2826 if (GF)
2828
2829 j= factors;
2830 j++;
2831
2832 truncF= mod (F, power (y, l));
2834 for (int i= 0; i < factors.length() - 1; i++, j++)
2835 {
2836 if (!wasInBounds)
2837 A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ[i]);
2838 else
2839 A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
2840 bufQ[i]);
2841 }
2843 "time to compute logarithmic derivative: ");
2844
2845 for (int i= 0; i < sizeBounds; i++)
2846 {
2847 if (bounds [i] + 1 <= (l/2)*degMipo)
2848 {
2849 wasInBounds= true;
2850 int k= tmin (bounds [i] + 1, (l/2)*degMipo);
2851 C= CFMatrix (l*degMipo - k, factors.length() - 1);
2852
2853 for (int ii= 0; ii < factors.length() - 1; ii++)
2854 {
2855 if (A[ii].size() - 1 >= i)
2856 {
2857 if (GF)
2858 {
2859 A [ii] [i]= A [ii] [i] (y-evaluation, y);
2861 A[ii] [i]= GF2FalphaRep (A[ii] [i], alpha);
2862 if (alpha != gamma)
2864 gamma, source, dest
2865 );
2866 buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, *NTLMat);
2867 }
2868 else
2869 {
2870 A [ii] [i]= A [ii] [i] (y-evaluation, y);
2871 if (alpha != gamma)
2873 gamma, source, dest
2874 );
2875 buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, *NTLMat);
2876 }
2877 writeInMatrix (C, buf, ii + 1, 0);
2878 }
2879 if (GF)
2881 }
2882
2883 if (GF)
2885
2887 NTLK= (*NTLC)*NTLN;
2888 transpose (NTLK, NTLK);
2889 kernel (NTLK, NTLK);
2890 transpose (NTLK, NTLK);
2891 NTLN *= NTLK;
2892 delete NTLC;
2893
2894 if (GF)
2896
2897 if (NTLN.NumCols() == 1)
2898 {
2899 irreducible= true;
2900 break;
2901 }
2902 if (isReduced (NTLN))
2903 {
2904 reduced= true;
2905 break;
2906 }
2907 }
2908 }
2909
2910 delete NTLMat;
2911
2912 if (NTLN.NumCols() == 1)
2913 {
2914 irreducible= true;
2915 break;
2916 }
2917 if (reduced)
2918 break;
2919 oldL= l;
2920 l += stepSize;
2921 stepSize *= 2;
2922 if (l > liftBound)
2923 {
2924 if (!hitBound)
2925 {
2926 l= liftBound;
2927 hitBound= true;
2928 }
2929 else
2930 break;
2931 }
2932 }
2933 delete [] A;
2934 if (!wasInBounds)
2935 {
2936 if (start)
2937 henselLiftResume12 (F, factors, start, degree (F) + 1, Pi, diophant, M);
2938 else
2939 henselLift12 (F, factors, degree (F) + 1, Pi, diophant, M);
2940 factors.insert (LCF);
2941 }
2942 return l;
2943}
2944#endif
2945
2946#ifdef HAVE_FLINT
2947#ifdef HAVE_NTL // henselLift12
2948//over field extension
2949int
2951 int liftBound, int minBound, int start, CFList&
2953 CFMatrix& M, CFArray& Pi, CFArray& bufQ, bool&
2954 irreducible, const CanonicalForm& evaluation, const
2956 )
2957{
2959 CanonicalForm LCF= LC (F, 1);
2960 CFArray *A= new CFArray [factors.length() - 1];
2961 bool wasInBounds= false;
2962 bool hitBound= false;
2963 int degMipo;
2965 alpha= info.getAlpha();
2967
2968 Variable gamma= info.getBeta();
2969 CanonicalForm primElemAlpha= info.getGamma();
2971
2972 int stepSize= 2;
2973 int l= ((minBound+1)/degMipo+1)*2;
2974 l= tmax (l, 2);
2975 if (start > l)
2976 l= start;
2977 int oldL= l/2;
2978 bool reduced= false;
2979 Variable y= F.mvar();
2980 Variable x= Variable (1);
2982 CFMatrix Mat, C;
2983 CFArray buf;
2985 long rank;
2988 while (l <= liftBound)
2989 {
2990 if (start)
2991 {
2992 henselLiftResume12 (F, factors, start, l, Pi, diophant, M);
2993 start= 0;
2994 }
2995 else
2996 {
2997 if (wasInBounds)
2999 else
3000 henselLift12 (F, factors, l, Pi, diophant, M);
3001 }
3002
3003 factors.insert (LCF);
3004
3005 if (GF)
3007
3008 powX= power (y-gamma, l);
3010 for (int i= 0; i < l*degMipo; i++)
3011 {
3012 imBasis= mod (power (y, i), powX);
3013 imBasis= imBasis (power (y, degMipo), y);
3014 imBasis= imBasis (y, gamma);
3015 iter= imBasis;
3016 for (; iter.hasTerms(); iter++)
3017 Mat (iter.exp()+ 1, i+1)= iter.coeff();
3018 }
3019
3024
3025 if (GF)
3027
3028 j= factors;
3029 j++;
3030
3031 truncF= mod (F, power (y, l));
3032 for (int i= 0; i < factors.length() - 1; i++, j++)
3033 {
3034 if (!wasInBounds)
3035 A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ[i]);
3036 else
3037 A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
3038 bufQ[i]);
3039 }
3040
3041 for (int i= 0; i < sizeBounds; i++)
3042 {
3043 if (bounds [i] + 1 <= (l/2)*degMipo)
3044 {
3045 wasInBounds= true;
3046 int k= tmin (bounds [i] + 1, (l/2)*degMipo);
3047 C= CFMatrix (l*degMipo - k, factors.length() - 1);
3048
3049 for (int ii= 0; ii < factors.length() - 1; ii++)
3050 {
3051 if (A[ii].size() - 1 >= i)
3052 {
3053 if (GF)
3054 {
3055 A [ii] [i]= A [ii] [i] (y-evaluation, y);
3057 A[ii] [i]= GF2FalphaRep (A[ii] [i], alpha);
3058 if (alpha != gamma)
3060 gamma, source, dest
3061 );
3062 buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, FLINTMatInv);
3063 }
3064 else
3065 {
3066 A [ii] [i]= A [ii] [i] (y-evaluation, y);
3067 if (alpha != gamma)
3069 gamma, source, dest
3070 );
3071 buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, FLINTMatInv);
3072 }
3073 writeInMatrix (C, buf, ii + 1, 0);
3074 }
3075 if (GF)
3077 }
3078
3079 if (GF)
3081
3096 nmod_mat_mul (FLINTN, FLINTC, FLINTK); //no aliasing allowed!!
3097
3101
3102 if (GF)
3104
3105 if (nmod_mat_ncols (FLINTN) == 1)
3106 {
3107 irreducible= true;
3108 break;
3109 }
3110 if (isReduced (FLINTN))
3111 {
3112 reduced= true;
3113 break;
3114 }
3115 }
3116 }
3117
3120
3121 if (nmod_mat_ncols (FLINTN) == 1)
3122 {
3123 irreducible= true;
3124 break;
3125 }
3126 if (reduced)
3127 break;
3128 oldL= l;
3129 l += stepSize;
3130 stepSize *= 2;
3131 if (l > liftBound)
3132 {
3133 if (!hitBound)
3134 {
3135 l= liftBound;
3136 hitBound= true;
3137 }
3138 else
3139 break;
3140 }
3141 }
3142 delete [] A;
3143 if (!wasInBounds)
3144 {
3145 if (start)
3146 henselLiftResume12 (F, factors, start, degree (F) + 1, Pi, diophant, M);
3147 else
3148 henselLift12 (F, factors, degree (F) + 1, Pi, diophant, M);
3149 factors.insert (LCF);
3150 }
3151 return l;
3152}
3153#endif
3154#endif
3155
3156// over Fq
3157#ifdef HAVE_NTL
3158int
3160 int start, int liftBound, int minBound, CFList& factors,
3162 Pi, CFArray& bufQ, bool& irreducible
3163 )
3164{
3165 CanonicalForm LCF= LC (F, 1);
3166 CFArray *A= new CFArray [factors.length() - 1];
3167 bool wasInBounds= false;
3168 bool hitBound= false;
3169 int l= (minBound+1)*2;
3170 int stepSize= 2;
3171 int oldL= l/2;
3172 bool reduced= false;
3175 CFArray buf;
3176 CFMatrix C;
3177 Variable y= F.mvar();
3179 while (l <= liftBound)
3180 {
3182 if (start)
3183 {
3184 henselLiftResume12 (F, factors, start, l, Pi, diophant, M);
3185 start= 0;
3186 }
3187 else
3188 {
3189 if (wasInBounds)
3191 else
3192 henselLift12 (F, factors, l, Pi, diophant, M);
3193 }
3195 "time to lift in compute lattice: ");
3196
3197 factors.insert (LCF);
3198 j= factors;
3199 j++;
3200
3201 truncF= mod (F, power (y,l));
3203 for (int i= 0; i < factors.length() - 1; i++, j++)
3204 {
3205 if (l == (minBound+1)*2)
3206 {
3207 A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ[i]);
3208 }
3209 else
3210 {
3211 A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
3212 bufQ[i]
3213 );
3214 }
3215 }
3217 "time to compute logarithmic derivative: ");
3218
3219 for (int i= 0; i < sizeBounds; i++)
3220 {
3221 if (bounds [i] + 1 <= l/2)
3222 {
3223 wasInBounds= true;
3224 int k= tmin (bounds [i] + 1, l/2);
3225 C= CFMatrix (l - k, factors.length() - 1);
3226 for (int ii= 0; ii < factors.length() - 1; ii++)
3227 {
3228
3229 if (A[ii].size() - 1 >= i)
3230 {
3231 buf= getCoeffs (A[ii] [i], k);
3232 writeInMatrix (C, buf, ii + 1, 0);
3233 }
3234 }
3235
3237 NTLK= (*NTLC)*NTLN;
3238 transpose (NTLK, NTLK);
3239 kernel (NTLK, NTLK);
3240 transpose (NTLK, NTLK);
3241 NTLN *= NTLK;
3242 delete NTLC;
3243
3244 if (NTLN.NumCols() == 1)
3245 {
3246 irreducible= true;
3247 break;
3248 }
3249 if (isReduced (NTLN) && l > (minBound+1)*2)
3250 {
3251 reduced= true;
3252 break;
3253 }
3254 }
3255 }
3256
3257 if (NTLN.NumCols() == 1)
3258 {
3259 irreducible= true;
3260 break;
3261 }
3262 if (reduced)
3263 break;
3264 oldL= l;
3265 l += stepSize;
3266 stepSize *= 2;
3267 if (l > liftBound)
3268 {
3269 if (!hitBound)
3270 {
3271 l= liftBound;
3272 hitBound= true;
3273 }
3274 else
3275 break;
3276 }
3277 }
3278 delete [] A;
3279 if (!wasInBounds)
3280 {
3281 if (start)
3282 henselLiftResume12 (F, factors, start, degree (F) + 1, Pi, diophant, M);
3283 else
3284 henselLift12 (F, factors, degree (F) + 1, Pi, diophant, M);
3285 factors.insert (LCF);
3286 }
3287 return l;
3288}
3289#endif
3290
3291#ifdef HAVE_NTL // henselLift12
3292#ifdef HAVE_FLINT
3293int
3295 int start, int liftBound, int minBound, CFList&
3297 CFMatrix& M, CFArray& Pi, CFArray& bufQ, bool&
3298 irreducible, const Variable& alpha
3299 )
3300#else
3301int
3303 int start, int liftBound, int minBound, CFList&
3305 M, CFArray& Pi, CFArray& bufQ, bool& irreducible,
3306 const Variable& alpha
3307 )
3308#endif
3309{
3310 CanonicalForm LCF= LC (F, 1);
3311 CFArray *A= new CFArray [factors.length() - 1];
3312 bool wasInBounds= false;
3313 int l= (minBound+1)*2;
3314 int oldL= l/2;
3315 int stepSize= 2;
3316 bool hitBound= false;
3318 bool reduced= false;
3320 CFMatrix C;
3321 CFArray buf;
3322#ifdef HAVE_FLINT
3323 long rank;
3325#else
3326 mat_zz_p* NTLC, NTLK;
3327#endif
3328 Variable y= F.mvar();
3330 while (l <= liftBound)
3331 {
3333 if (start)
3334 {
3335 henselLiftResume12 (F, factors, start, l, Pi, diophant, M);
3336 start= 0;
3337 }
3338 else
3339 {
3340 if (wasInBounds)
3342 else
3343 henselLift12 (F, factors, l, Pi, diophant, M);
3344 }
3346 "time to lift in compute lattice: ");
3347
3348 factors.insert (LCF);
3349 j= factors;
3350 j++;
3351
3352 truncF= mod (F, power (y,l));
3354 for (int i= 0; i < factors.length() - 1; i++, j++)
3355 {
3356 if (l == (minBound+1)*2)
3357 {
3358 A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ[i]);
3359 }
3360 else
3361 {
3362 A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
3363 bufQ[i]
3364 );
3365 }
3366 }
3368 "time to compute logarithmic derivative: ");
3369
3370 for (int i= 0; i < sizeBounds; i++)
3371 {
3372 if (bounds [i] + 1 <= l/2)
3373 {
3374 wasInBounds= true;
3375 int k= tmin (bounds [i] + 1, l/2);
3376 C= CFMatrix ((l - k)*extensionDeg, factors.length() - 1);
3377 for (int ii= 0; ii < factors.length() - 1; ii++)
3378 {
3379 if (A[ii].size() - 1 >= i)
3380 {
3381 buf= getCoeffs (A[ii] [i], k, alpha);
3382 writeInMatrix (C, buf, ii + 1, 0);
3383 }
3384 }
3385
3386#ifdef HAVE_FLINT
3401 nmod_mat_mul (FLINTN, FLINTC, FLINTK); //no aliasing allowed!!
3402
3406#else
3408 NTLK= (*NTLC)*NTLN;
3409 transpose (NTLK, NTLK);
3410 kernel (NTLK, NTLK);
3411 transpose (NTLK, NTLK);
3412 NTLN *= NTLK;
3413 delete NTLC;
3414#endif
3415
3416#ifdef HAVE_FLINT
3417 if (nmod_mat_nrows (FLINTN) == 1)
3418#else
3419 if (NTLN.NumCols() == 1)
3420#endif
3421 {
3422 irreducible= true;
3423 break;
3424 }
3425#ifdef HAVE_FLINT
3426 if (isReduced (FLINTN) && l > (minBound+1)*2)
3427#else
3428 if (isReduced (NTLN) && l > (minBound+1)*2)
3429#endif
3430 {
3431 reduced= true;
3432 break;
3433 }
3434 }
3435 }
3436
3437#ifdef HAVE_FLINT
3438 if (nmod_mat_ncols (FLINTN) == 1)
3439#else
3440 if (NTLN.NumCols() == 1)
3441#endif
3442 {
3443 irreducible= true;
3444 break;
3445 }
3446 if (reduced)
3447 break;
3448 oldL= l;
3449 l += stepSize;
3450 stepSize *= 2;
3451 if (l > liftBound)
3452 {
3453 if (!hitBound)
3454 {
3455 l= liftBound;
3456 hitBound= true;
3457 }
3458 else
3459 break;
3460 }
3461 }
3462 delete [] A;
3463 if (!wasInBounds)
3464 {
3465 if (start)
3466 henselLiftResume12 (F, factors, start, degree (F) + 1, Pi, diophant, M);
3467 else
3468 henselLift12 (F, factors, degree (F) + 1, Pi, diophant, M);
3469 factors.insert (LCF);
3470 }
3471 return l;
3472}
3473#endif
3474
3475#ifdef HAVE_NTL // logarithmicDerivative
3476CFList
3478 int oldNumCols, int oldL, int precision,
3479 const CanonicalForm& eval
3480 )
3481{
3482 int d;
3483 bool isIrreducible= false;
3484 int* bounds= computeBounds (F, d, isIrreducible);
3485 Variable y= F.mvar();
3486 if (isIrreducible)
3487 {
3488 delete [] bounds;
3489 CanonicalForm G= F;
3490 F= 1;
3491 return CFList (G (y-eval, y));
3492 }
3493 CFArray * A= new CFArray [factors.length()];
3495#ifdef HAVE_FLINT
3498 for (long i=factors.length()-1; i >= 0; i--)
3499 nmod_mat_entry (FLINTN, i, i)= 1;
3500#else
3501 mat_zz_p NTLN;
3502 ident (NTLN, factors.length());
3503#endif
3504 int minBound= bounds[0];
3505 for (int i= 1; i < d; i++)
3506 {
3507 if (bounds[i] != 0)
3509 }
3510 int l= tmax (2*(minBound + 1), oldL);
3511 int oldL2= l/2;
3512 int stepSize= 2;
3513 bool useOldQs= false;
3514 bool hitBound= false;
3516 CFMatrix C;
3517 CFArray buf;
3518#ifdef HAVE_FLINT
3519 long rank;
3521#else
3522 mat_zz_p* NTLC, NTLK;
3523#endif
3525 while (l <= precision)
3526 {
3527 j= factors;
3528 truncF= mod (F, power (y,l));
3529 if (useOldQs)
3530 {
3531 for (int i= 0; i < factors.length(); i++, j++)
3532 A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL2, bufQ[i],
3533 bufQ[i]
3534 );
3535 }
3536 else
3537 {
3538 for (int i= 0; i < factors.length(); i++, j++)
3539 A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ [i]);
3540 }
3541 useOldQs= true;
3542 for (int i= 0; i < d; i++)
3543 {
3544 if (bounds [i] + 1 <= l/2)
3545 {
3546 int k= tmin (bounds [i] + 1, l/2);
3547 C= CFMatrix (l - k, factors.length());
3548 for (int ii= 0; ii < factors.length(); ii++)
3549 {
3550 if (A[ii].size() - 1 >= i)
3551 {
3552 buf= getCoeffs (A[ii] [i], k);
3553 writeInMatrix (C, buf, ii + 1, 0);
3554 }
3555 }
3556#ifdef HAVE_FLINT
3571 nmod_mat_mul (FLINTN, FLINTC, FLINTK); //no aliasing allowed!!
3572
3576#else
3578 NTLK= (*NTLC)*NTLN;
3579 transpose (NTLK, NTLK);
3580 kernel (NTLK, NTLK);
3581 transpose (NTLK, NTLK);
3582 NTLN *= NTLK;
3583 delete NTLC;
3584#endif
3585#ifdef HAVE_FLINT
3586 if (nmod_mat_ncols (FLINTN) == 1)
3587 {
3589#else
3590 if (NTLN.NumCols() == 1)
3591 {
3592#endif
3593 delete [] A;
3594 delete [] bounds;
3595 CanonicalForm G= F;
3596 F= 1;
3597 return CFList (G (y-eval,y));
3598 }
3599 }
3600 }
3601
3602#ifdef HAVE_FLINT
3604 {
3605 if (isReduced (FLINTN))
3606 {
3607 int * factorsFoundIndex= new int [nmod_mat_ncols (FLINTN)];
3608 for (long i= 0; i < nmod_mat_ncols (FLINTN); i++)
3609#else
3610 if (NTLN.NumCols() < oldNumCols - factorsFound)
3611 {
3612 if (isReduced (NTLN))
3613 {
3614 int * factorsFoundIndex= new int [NTLN.NumCols()];
3615 for (long i= 0; i < NTLN.NumCols(); i++)
3616#endif
3617 factorsFoundIndex[i]= 0;
3618 int factorsFound2= 0;
3619 CFList result;
3621#ifdef HAVE_FLINT
3624 );
3625 if (result.length() == nmod_mat_ncols (FLINTN))
3626 {
3628#else
3630 factorsFoundIndex, NTLN, eval, false
3631 );
3632 if (result.length() == NTLN.NumCols())
3633 {
3634#endif
3635 delete [] factorsFoundIndex;
3636 delete [] A;
3637 delete [] bounds;
3638 F= 1;
3639 return result;
3640 }
3641 delete [] factorsFoundIndex;
3642 }
3643 else if (l == precision)
3644 {
3646#ifdef HAVE_FLINT
3650#else
3653#endif
3654 F= bufF;
3655 delete [] zeroOne;
3656 delete [] A;
3657 delete [] bounds;
3658 return result;
3659 }
3660 }
3661 oldL2= l;
3662 l += stepSize;
3663 stepSize *= 2;
3664 if (l > precision)
3665 {
3666 if (!hitBound)
3667 {
3668 l= precision;
3669 hitBound= true;
3670 }
3671 else
3672 break;
3673 }
3674 }
3675#ifdef HAVE_FLINT
3677#endif
3678 delete [] bounds;
3679 delete [] A;
3680 return CFList();
3681}
3682#endif
3683
3684#ifdef HAVE_NTL // mat_zz_pE
3685CFList
3687 int oldNumCols, int oldL, const Variable&,
3688 int precision, const CanonicalForm& eval
3689 )
3690{
3691 int d;
3692 bool isIrreducible= false;
3693 Variable y= F.mvar();
3694 int* bounds= computeBounds (F, d, isIrreducible);
3695 if (isIrreducible)
3696 {
3697 delete [] bounds;
3698 CanonicalForm G= F;
3699 F= 1;
3700 return CFList (G (y-eval,y));
3701 }
3702 CFArray * A= new CFArray [factors.length()];
3705 ident (NTLN, factors.length());
3706 int minBound= bounds[0];
3707 for (int i= 1; i < d; i++)
3708 {
3709 if (bounds[i] != 0)
3711 }
3712 int l= tmax (2*(minBound + 1), oldL);
3713 int oldL2= l/2;
3714 int stepSize= 2;
3715 bool useOldQs= false;
3716 bool hitBound= false;
3718 CFMatrix C;
3720 CFArray buf;
3722 while (l <= precision)
3723 {
3724 j= factors;
3725 truncF= mod (F, power (y,l));
3726 if (useOldQs)
3727 {
3728 for (int i= 0; i < factors.length(); i++, j++)
3729 A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL2, bufQ[i],
3730 bufQ[i]
3731 );
3732 }
3733 else
3734 {
3735 for (int i= 0; i < factors.length(); i++, j++)
3736 A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ [i]);
3737 }
3738 useOldQs= true;
3739 for (int i= 0; i < d; i++)
3740 {
3741 if (bounds [i] + 1 <= l/2)
3742 {
3743 int k= tmin (bounds [i] + 1, l/2);
3744 C= CFMatrix (l - k, factors.length());
3745 for (int ii= 0; ii < factors.length(); ii++)
3746 {
3747 if (A[ii].size() - 1 >= i)
3748 {
3749 buf= getCoeffs (A[ii] [i], k);
3750 writeInMatrix (C, buf, ii + 1, 0);
3751 }
3752 }
3754 NTLK= (*NTLC)*NTLN;
3755 transpose (NTLK, NTLK);
3756 kernel (NTLK, NTLK);
3757 transpose (NTLK, NTLK);
3758 NTLN *= NTLK;
3759 delete NTLC;
3760 if (NTLN.NumCols() == 1)
3761 {
3762 delete [] A;
3763 delete [] bounds;
3764 CanonicalForm G= F;
3765 F= 1;
3766 return CFList (G (y-eval,y));
3767 }
3768 }
3769 }
3770
3771 if (NTLN.NumCols() < oldNumCols - factorsFound)
3772 {
3773 if (isReduced (NTLN))
3774 {
3775 int * factorsFoundIndex= new int [NTLN.NumCols()];
3776 for (long i= 0; i < NTLN.NumCols(); i++)
3777 factorsFoundIndex[i]= 0;
3778 int factorsFound2= 0;
3779 CFList result;
3782 factorsFoundIndex, NTLN, eval, false);
3783 if (result.length() == NTLN.NumCols())
3784 {
3785 delete [] factorsFoundIndex;
3786 delete [] A;
3787 delete [] bounds;
3788 F= 1;
3789 return result;
3790 }
3791 delete [] factorsFoundIndex;
3792 }
3793 else if (l == precision)
3794 {
3798 F= bufF;
3799 delete [] zeroOne;
3800 delete [] A;
3801 delete [] bounds;
3802 return result;
3803 }
3804 }
3805 oldL2= l;
3806 l += stepSize;
3807 stepSize *= 2;
3808 if (l > precision)
3809 {
3810 if (!hitBound)
3811 {
3812 l= precision;
3813 hitBound= true;
3814 }
3815 else
3816 break;
3817 }
3818 }
3819 delete [] bounds;
3820 delete [] A;
3821 return CFList();
3822}
3823#endif
3824
3825#ifdef HAVE_NTL // logarithmicDerivative
3826//over field extension
3827CFList
3829 int oldNumCols, int oldL, const CanonicalForm& evaluation,
3830 const ExtensionInfo& info, CFList& source, CFList& dest,
3831 int precision
3832 )
3833{
3835 int degMipo= degree (getMipo (info.getAlpha()));
3836 Variable alpha= info.getAlpha();
3837 int d;
3838 bool isIrreducible= false;
3839 int* bounds= computeBounds (F, d, isIrreducible);
3840 if (isIrreducible)
3841 {
3842 delete [] bounds;
3843 Variable y= Variable (2);
3844 CanonicalForm tmp= F (y - evaluation, y);
3845 CFList source, dest;
3846 tmp= mapDown (tmp, info, source, dest);
3847 F= 1;
3848 return CFList (tmp);
3849 }
3850
3851 CFArray * A= new CFArray [factors.length()];
3853#ifdef HAVE_FLINT
3856 for (long i=factors.length()-1; i >= 0; i--)
3857 nmod_mat_entry (FLINTN, i, i)= 1;
3858#else
3860 {
3862 zz_p::init (getCharacteristic());
3863 }
3864 mat_zz_p NTLN;
3865 ident (NTLN, factors.length());
3866#endif
3867 int minBound= bounds[0];
3868 for (int i= 1; i < d; i++)
3869 {
3870 if (bounds[i] != 0)
3872 }
3873 int l= tmax (oldL, 2*((minBound+1)/degMipo+1));
3874 int oldL2= l/2;
3875 int stepSize= 2;
3876 bool useOldQs= false;
3877 bool hitBound= false;
3878 Variable gamma= info.getBeta();
3879 CanonicalForm primElemAlpha= info.getGamma();
3882 Variable y= F.mvar();
3884 CFMatrix Mat, C;
3886#ifdef HAVE_FLINT
3887 long rank;
3889#else
3891#endif
3892 CFArray buf;
3893 while (l <= precision)
3894 {
3895 j= factors;
3896 if (GF)
3898 powX= power (y-gamma, l);
3900 for (int i= 0; i < l*degMipo; i++)
3901 {
3902 imBasis= mod (power (y, i), powX);
3903 imBasis= imBasis (power (y, degMipo), y);
3904 imBasis= imBasis (y, gamma);
3905 iter= imBasis;
3906 for (; iter.hasTerms(); iter++)
3907 Mat (iter.exp()+ 1, i+1)= iter.coeff();
3908 }
3909
3910#ifdef HAVE_FLINT
3915#else
3917 *NTLMat= inv (*NTLMat);
3918#endif
3919
3920 if (GF)
3922
3923 truncF= mod (F, power (y, l));
3924 if (useOldQs)
3925 {
3926 for (int i= 0; i < factors.length(); i++, j++)
3927 A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL2, bufQ[i],
3928 bufQ[i]
3929 );
3930 }
3931 else
3932 {
3933 for (int i= 0; i < factors.length(); i++, j++)
3934 A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ [i]);
3935 }
3936 useOldQs= true;
3937 for (int i= 0; i < d; i++)
3938 {
3939 if (bounds [i] + 1 <= (l/2)*degMipo)
3940 {
3941 int k= tmin (bounds [i] + 1, (l/2)*degMipo);
3942 C= CFMatrix (l*degMipo - k, factors.length());
3943 for (int ii= 0; ii < factors.length(); ii++)
3944 {
3945 if (A[ii].size() - 1 >= i)
3946 {
3947 if (GF)
3948 {
3949 A[ii] [i]= A [ii] [i] (y-evaluation, y);
3951 A[ii] [i]= GF2FalphaRep (A[ii] [i], alpha);
3952 if (alpha != gamma)
3954 gamma, source, dest
3955 );
3956#ifdef HAVE_FLINT
3957 buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, FLINTMatInv);
3958#else
3959 buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, *NTLMat);
3960#endif
3961 }
3962 else
3963 {
3964 A [ii] [i]= A [ii] [i] (y-evaluation, y);
3965 if (alpha != gamma)
3967 gamma, source, dest
3968 );
3969#ifdef HAVE_FLINT
3970 buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, FLINTMatInv);
3971#else
3972 buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, *NTLMat);
3973#endif
3974 }
3975 writeInMatrix (C, buf, ii + 1, 0);
3976 }
3977 if (GF)
3979 }
3980
3981 if (GF)
3983
3984#ifdef HAVE_FLINT
3999 nmod_mat_mul (FLINTN, FLINTC, FLINTK); //no aliasing allowed!!
4000
4004#else
4006 NTLK= (*NTLC)*NTLN;
4007 transpose (NTLK, NTLK);
4008 kernel (NTLK, NTLK);
4009 transpose (NTLK, NTLK);
4010 NTLN *= NTLK;
4011 delete NTLC;
4012#endif
4013
4014 if (GF)
4016
4017#ifdef HAVE_FLINT
4018 if (nmod_mat_ncols (FLINTN) == 1)
4019 {
4023#else
4024 if (NTLN.NumCols() == 1)
4025 {
4026 delete NTLMat;
4027#endif
4028 Variable y= Variable (2);
4029 CanonicalForm tmp= F (y - evaluation, y);
4030 CFList source, dest;
4031 tmp= mapDown (tmp, info, source, dest);
4032 delete [] A;
4033 delete [] bounds;
4034 F= 1;
4035 return CFList (tmp);
4036 }
4037 }
4038 }
4039
4040#ifdef HAVE_FLINT
4043#else
4044 delete NTLMat;
4045#endif
4046
4047#ifdef HAVE_FLINT
4049 {
4050 if (isReduced (FLINTN))
4051 {
4052 int * factorsFoundIndex= new int [nmod_mat_ncols (FLINTN)];
4053 for (long i= 0; i < nmod_mat_ncols (FLINTN); i++)
4054#else
4055 if (NTLN.NumCols() < oldNumCols - factorsFound)
4056 {
4057 if (isReduced (NTLN))
4058 {
4059 int * factorsFoundIndex= new int [NTLN.NumCols()];
4060 for (long i= 0; i < NTLN.NumCols(); i++)
4061#endif
4062 factorsFoundIndex[i]= 0;
4063 int factorsFound2= 0;
4064 CFList result;
4066#ifdef HAVE_FLINT
4069 );
4070 if (result.length() == nmod_mat_ncols (FLINTN))
4071 {
4073#else
4076 );
4077 if (result.length() == NTLN.NumCols())
4078 {
4079#endif
4080 delete [] factorsFoundIndex;
4081 delete [] A;
4082 delete [] bounds;
4083 F= 1;
4084 return result;
4085 }
4086 delete [] factorsFoundIndex;
4087 }
4088 else if (l == precision)
4089 {
4091#ifdef HAVE_FLINT
4095 );
4097#else
4101 );
4102#endif
4103 F= bufF;
4104 delete [] zeroOne;
4105 delete [] A;
4106 delete [] bounds;
4107 return result;
4108 }
4109 }
4110 oldL2= l;
4111 l += stepSize;
4112 stepSize *= 2;
4113 if (l > precision)
4114 {
4115 if (!hitBound)
4116 {
4117 hitBound= true;
4118 l= precision;
4119 }
4120 else
4121 break;
4122 }
4123 }
4124
4125#ifdef HAVE_FLINT
4127#endif
4128 delete [] bounds;
4129 delete [] A;
4130 return CFList();
4131}
4132#endif
4133
4134#ifdef HAVE_NTL // mat_zz_pE
4135CFList
4137 const Variable& alpha, int precision)
4138{
4139 int d;
4140 bool isIrreducible= false;
4141 int* bounds= computeBounds (F, d, isIrreducible);
4142 if (isIrreducible)
4143 {
4144 delete [] bounds;
4145 return CFList (F);
4146 }
4147 CFArray * A= new CFArray [factors.length()];
4150 {
4152 zz_p::init (getCharacteristic());
4153 }
4155 zz_pE::init (NTLMipo);
4157 ident (NTLN, factors.length());
4158 int minBound= bounds[0];
4159 for (int i= 1; i < d; i++)
4160 {
4161 if (bounds[i] != 0)
4163 }
4164 int l= tmin (2*(minBound + 1), precision);
4165 int oldL= l/2;
4166 int stepSize= 2;
4167 bool useOldQs= false;
4168 bool hitBound= false;
4170 CFMatrix C;
4171 CFArray buf;
4173 Variable y= F.mvar();
4175 while (l <= precision)
4176 {
4177 j= factors;
4178 truncF= mod (F, power (y, l));
4179 if (useOldQs)
4180 {
4181 for (int i= 0; i < factors.length(); i++, j++)
4182 A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i], bufQ[i]);
4183 }
4184 else
4185 {
4186 for (int i= 0; i < factors.length(); i++, j++)
4187 A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ [i]);
4188 }
4189 useOldQs= true;
4190 for (int i= 0; i < d; i++)
4191 {
4192 if (bounds [i] + 1 <= l/2)
4193 {
4194 int k= tmin (bounds [i] + 1, l/2);
4195 C= CFMatrix (l - k, factors.length());
4196 for (int ii= 0; ii < factors.length(); ii++)
4197 {
4198 if (A[ii].size() - 1 >= i)
4199 {
4200 buf= getCoeffs (A[ii] [i], k);
4201 writeInMatrix (C, buf, ii + 1, 0);
4202 }
4203 }
4205 NTLK= (*NTLC)*NTLN;
4206 transpose (NTLK, NTLK);
4207 kernel (NTLK, NTLK);
4208 transpose (NTLK, NTLK);
4209 NTLN *= NTLK;
4210 delete NTLC;
4211
4212 if (NTLN.NumCols() == 1)
4213 {
4214 delete [] A;
4215 delete [] bounds;
4216 return CFList (F);
4217 }
4218 }
4219 }
4220
4221 if (isReduced (NTLN) || l == precision)
4222 {
4227 NTLN
4228 );
4229 if (result.length() != NTLN.NumCols() && l != precision)
4231 if (result.length() == NTLN.NumCols())
4232 {
4233 delete [] zeroOne;
4234 delete [] A;
4235 delete [] bounds;
4236 return result;
4237 }
4238 if (l == precision)
4239 {
4240 delete [] zeroOne;
4241 delete [] A;
4242 delete [] bounds;
4243 return Union (result, factors);
4244 }
4245 delete [] zeroOne;
4246 }
4247 oldL= l;
4248 l += stepSize;
4249 stepSize *= 2;
4250 if (l > precision)
4251 {
4252 if (!hitBound)
4253 {
4254 l= precision;
4255 hitBound= true;
4256 }
4257 else
4258 break;
4259 }
4260 }
4261 delete [] bounds;
4262 delete [] A;
4263 return CFList();
4264}
4265#endif
4266
4267#ifdef HAVE_NTL // logarithmicDerivative
4268CFList
4270 int oldNumCols, int oldL, const Variable& alpha,
4271 int precision, const CanonicalForm& eval
4272 )
4273{
4274 int d;
4275 bool isIrreducible= false;
4276 Variable y= F.mvar();
4277 int* bounds= computeBounds (F, d, isIrreducible);
4278 if (isIrreducible)
4279 {
4280 delete [] bounds;
4281 CanonicalForm G= F;
4282 F= 1;
4283 return CFList (G (y-eval,y));
4284 }
4286 CFArray * A= new CFArray [factors.length()];
4288#ifdef HAVE_FLINT
4291 for (long i=factors.length()-1; i >= 0; i--)
4292 nmod_mat_entry (FLINTN, i, i)= 1;
4293#else
4294 mat_zz_p NTLN;
4295 ident (NTLN, factors.length());
4296#endif
4297 int minBound= bounds[0];
4298 for (int i= 1; i < d; i++)
4299 {
4300 if (bounds[i] != 0)
4302 }
4303 int l= tmax (2*(minBound + 1), oldL);
4304 int oldL2= l/2;
4305 int stepSize= 2;
4306 bool useOldQs= false;
4307 bool hitBound= false;
4309 CFMatrix C;
4310#ifdef HAVE_FLINT
4311 long rank;
4313#else
4314 mat_zz_p* NTLC, NTLK;
4315#endif
4316 CFArray buf;
4318 while (l <= precision)
4319 {
4320 j= factors;
4321 truncF= mod (F, power (y, l));
4322 if (useOldQs)
4323 {
4324 for (int i= 0; i < factors.length(); i++, j++)
4325 A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL2, bufQ[i],
4326 bufQ[i]
4327 );
4328 }
4329 else
4330 {
4331 for (int i= 0; i < factors.length(); i++, j++)
4332 A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ [i]);
4333 }
4334 useOldQs= true;
4335 for (int i= 0; i < d; i++)
4336 {
4337 if (bounds [i] + 1 <= l/2)
4338 {
4339 int k= tmin (bounds [i] + 1, l/2);
4340 C= CFMatrix ((l - k)*extensionDeg, factors.length());
4341 for (int ii= 0; ii < factors.length(); ii++)
4342 {
4343 if (A[ii].size() - 1 >= i)
4344 {
4345 buf= getCoeffs (A[ii] [i], k, alpha);
4346 writeInMatrix (C, buf, ii + 1, 0);
4347 }
4348 }
4349#ifdef HAVE_FLINT
4364 nmod_mat_mul (FLINTN, FLINTC, FLINTK); //no aliasing allowed!!
4365
4369#else
4371 NTLK= (*NTLC)*NTLN;
4372 transpose (NTLK, NTLK);
4373 kernel (NTLK, NTLK);
4374 transpose (NTLK, NTLK);
4375 NTLN *= NTLK;
4376 delete NTLC;
4377#endif
4378#ifdef HAVE_FLINT
4379 if (nmod_mat_ncols (FLINTN) == 1)
4380 {
4382#else
4383 if (NTLN.NumCols() == 1)
4384 {
4385#endif
4386 delete [] A;
4387 delete [] bounds;
4388 CanonicalForm G= F;
4389 F= 1;
4390 return CFList (G (y-eval,y));
4391 }
4392 }
4393 }
4394
4395#ifdef HAVE_FLINT
4397 {
4398 if (isReduced (FLINTN))
4399 {
4400 int * factorsFoundIndex= new int [nmod_mat_ncols (FLINTN)];
4401 for (long i= 0; i < nmod_mat_ncols (FLINTN); i++)
4402#else
4403 if (NTLN.NumCols() < oldNumCols - factorsFound)
4404 {
4405 if (isReduced (NTLN))
4406 {
4407 int * factorsFoundIndex= new int [NTLN.NumCols()];
4408 for (long i= 0; i < NTLN.NumCols(); i++)
4409#endif
4410 factorsFoundIndex[i]= 0;
4411 int factorsFound2= 0;
4412 CFList result;
4414#ifdef HAVE_FLINT
4417 );
4418 if (result.length() == nmod_mat_ncols (FLINTN))
4419 {
4421#else
4423 factorsFoundIndex, NTLN, eval, false
4424 );
4425 if (result.length() == NTLN.NumCols())
4426 {
4427#endif
4428 delete [] factorsFoundIndex;
4429 delete [] A;
4430 delete [] bounds;
4431 F= 1;
4432 return result;
4433 }
4434 delete [] factorsFoundIndex;
4435 }
4436 else if (l == precision)
4437 {
4439#ifdef HAVE_FLINT
4443#else
4446#endif
4447 F= bufF;
4448 delete [] zeroOne;
4449 delete [] A;
4450 delete [] bounds;
4451 return result;
4452 }
4453 }
4454 oldL2= l;
4455 l += stepSize;
4456 stepSize *= 2;
4457 if (l > precision)
4458 {
4459 if (!hitBound)
4460 {
4461 hitBound= true;
4462 l= precision;
4463 }
4464 else
4465 break;
4466 }
4467 }
4468#ifdef HAVE_FLINT
4470#endif
4471 delete [] bounds;
4472 delete [] A;
4473 return CFList();
4474}
4475#endif
4476
4477#ifdef HAVE_NTL // logarithmicDerivative
4478#ifdef HAVE_FLINT
4479CFList
4481 l, int d, int* bounds, CFArray& bufQ, nmod_mat_t FLINTN,
4482 const CanonicalForm& eval
4483 )
4484#else
4485CFList
4487 l, int d, int* bounds, CFArray& bufQ, mat_zz_p& NTLN,
4488 const CanonicalForm& eval
4489 )
4490#endif
4491{
4492 CFList result= CFList();
4493 CFArray * A= new CFArray [factors.length()];
4494 int oldL2= oldL/2;
4495 bool hitBound= false;
4496#ifdef HAVE_FLINT
4497 if (nmod_mat_nrows (FLINTN) != factors.length()) //refined factors
4498 {
4501 for (long i=factors.length()-1; i >= 0; i--)
4502 nmod_mat_entry (FLINTN, i, i)= 1;
4504 }
4505#else
4506 if (NTLN.NumRows() != factors.length()) //refined factors
4507 {
4508 ident (NTLN, factors.length());
4510 }
4511#endif
4512 bool useOldQs= false;
4514 CFMatrix C;
4515 CFArray buf;
4516#ifdef HAVE_FLINT
4517 long rank;
4519#else
4520 mat_zz_p* NTLC, NTLK;
4521#endif
4524 Variable y= F.mvar();
4525 while (oldL <= l)
4526 {
4527 j= factors;
4528 truncF= mod (F, power (y, oldL));
4529 if (useOldQs)
4530 {
4531 for (int i= 0; i < factors.length(); i++, j++)
4532 A[i]= logarithmicDerivative (truncF, j.getItem(), oldL, oldL2, bufQ[i],
4533 bufQ[i]
4534 );
4535 }
4536 else
4537 {
4538 for (int i= 0; i < factors.length(); i++, j++)
4539 A[i]= logarithmicDerivative (truncF, j.getItem(), oldL, bufQ [i]);
4540 }
4541 useOldQs= true;
4542
4543 for (int i= 0; i < d; i++)
4544 {
4545 if (bounds [i] + 1 <= oldL/2)
4546 {
4547 int k= tmin (bounds [i] + 1, oldL/2);
4548 C= CFMatrix (oldL - k, factors.length());
4549 for (int ii= 0; ii < factors.length(); ii++)
4550 {
4551 if (A[ii].size() - 1 >= i)
4552 {
4553 buf= getCoeffs (A[ii] [i], k);
4554 writeInMatrix (C, buf, ii + 1, 0);
4555 }
4556 }
4557#ifdef HAVE_FLINT
4572 nmod_mat_mul (FLINTN, FLINTC, FLINTK); //no aliasing allowed!!
4573
4577#else
4579 NTLK= (*NTLC)*NTLN;
4580 transpose (NTLK, NTLK);
4581 kernel (NTLK, NTLK);
4582 transpose (NTLK, NTLK);
4583 NTLN *= NTLK;
4584 delete NTLC;
4585#endif
4586#ifdef HAVE_FLINT
4587 if (nmod_mat_ncols (FLINTN) == 1)
4588#else
4589 if (NTLN.NumCols() == 1)
4590#endif
4591 {
4592 delete [] A;
4593 return CFList (F (y-eval,y));
4594 }
4595 }
4596 }
4597#ifdef HAVE_FLINT
4598 if (nmod_mat_ncols (FLINTN) == 1)
4599#else
4600 if (NTLN.NumCols() == 1)
4601#endif
4602 {
4603 delete [] A;
4604 return CFList (F (y-eval,y));
4605 }
4606 int * zeroOneVecs;
4607#ifdef HAVE_FLINT
4609#else
4611#endif
4612 bufF= F;
4614#ifdef HAVE_FLINT
4616#else
4618#endif
4619 delete [] zeroOneVecs;
4620 if (degree (bufF) + 1 + degree (LC (bufF, 1)) < oldL && result.length() > 0)
4621 {
4622 F= bufF;
4624 delete [] A;
4625 return result;
4626 }
4627
4628 result= CFList();
4629 oldL2= oldL;
4630 oldL *= 2;
4631 if (oldL > l)
4632 {
4633 if (!hitBound)
4634 {
4635 oldL= l;
4636 hitBound= true;
4637 }
4638 else
4639 break;
4640 }
4641 }
4642 delete [] A;
4643 return result;
4644}
4645#endif
4646
4647#ifdef HAVE_NTL // mat_zz_pE
4648CFList
4650 l, int d, int* bounds, CFArray& bufQ, mat_zz_pE& NTLN,
4651 const CanonicalForm& eval
4652 )
4653{
4654 CFList result= CFList();
4655 CFArray * A= new CFArray [factors.length()];
4656 int oldL2= oldL/2;
4657 bool hitBound= false;
4658 bool useOldQs= false;
4659 if (NTLN.NumRows() != factors.length()) //refined factors
4660 ident (NTLN, factors.length());
4662 CFMatrix C;
4663 CFArray buf;
4667 Variable y= F.mvar();
4668 while (oldL <= l)
4669 {
4670 j= factors;
4671 truncF= mod (F, power (y, oldL));
4672 if (useOldQs)
4673 {
4674 for (int i= 0; i < factors.length(); i++, j++)
4675 A[i]= logarithmicDerivative (truncF, j.getItem(), oldL, oldL2, bufQ[i],
4676 bufQ[i]
4677 );
4678 }
4679 else
4680 {
4681 for (int i= 0; i < factors.length(); i++, j++)
4682 A[i]= logarithmicDerivative (truncF, j.getItem(), oldL, bufQ [i]);
4683 }
4684 useOldQs= true;
4685
4686 for (int i= 0; i < d; i++)
4687 {
4688 if (bounds [i] + 1 <= oldL/2)
4689 {
4690 int k= tmin (bounds [i] + 1, oldL/2);
4691 C= CFMatrix (oldL - k, factors.length());
4692 for (int ii= 0; ii < factors.length(); ii++)
4693 {
4694 if (A[ii].size() - 1 >= i)
4695 {
4696 buf= getCoeffs (A[ii] [i], k);
4697 writeInMatrix (C, buf, ii + 1, 0);
4698 }
4699 }
4701 NTLK= (*NTLC)*NTLN;
4702 transpose (NTLK, NTLK);
4703 kernel (NTLK, NTLK);
4704 transpose (NTLK, NTLK);
4705 NTLN *= NTLK;
4706 delete NTLC;
4707
4708 if (NTLN.NumCols() == 1)
4709 {
4710 delete [] A;
4711 return CFList (F (y-eval,y));
4712 }
4713 }
4714 }
4715 if (NTLN.NumCols() == 1)
4716 {
4717 delete [] A;
4718 return CFList (F (y-eval,y));
4719 }
4720
4721 int * zeroOneVecs;
4723 bufF= F;
4726 delete [] zeroOneVecs;
4727 if (degree (bufF) + 1 + degree (LC (bufF, 1)) < l && result.length() > 0)
4728 {
4729 F= bufF;
4731 delete [] A;
4732 return result;
4733 }
4734
4735 result= CFList();
4736 oldL2= oldL;
4737 oldL *= 2;
4738 if (oldL > l)
4739 {
4740 if (!hitBound)
4741 {
4742 oldL= l;
4743 hitBound= true;
4744 }
4745 else
4746 break;
4747 }
4748 }
4749 delete [] A;
4750 return result;
4751}
4752#endif
4753
4754//over field extension
4755#ifdef HAVE_NTL // logarithmicDerivative
4756#ifdef HAVE_FLINT
4757CFList
4759 int* bounds, CFArray& bufQ, nmod_mat_t FLINTN, const
4761 CFList& source, CFList& dest
4762 )
4763#else
4764CFList
4765extIncreasePrecision (CanonicalForm& F, CFList& factors, int oldL, int l, int d,
4766 int* bounds, CFArray& bufQ, mat_zz_p& NTLN, const
4768 CFList& source, CFList& dest
4769 )
4770#endif
4771{
4772 CFList result= CFList();
4773 CFArray * A= new CFArray [factors.length()];
4774 int oldL2= oldL/2; //be careful
4775 bool hitBound= false;
4776 bool useOldQs= false;
4778 int degMipo= degree (getMipo (info.getAlpha()));
4779 Variable alpha= info.getAlpha();
4780
4781 Variable gamma= info.getBeta();
4782 CanonicalForm primElemAlpha= info.getGamma();
4784#ifdef HAVE_FLINT
4787 for (long i=factors.length()-1; i >= 0; i--)
4788 nmod_mat_entry (FLINTN, i, i)= 1;
4789#else
4790 if (NTLN.NumRows() != factors.length()) //refined factors
4791 ident (NTLN, factors.length());
4792#endif
4793 Variable y= F.mvar();
4796 CFMatrix Mat, C;
4798 CFArray buf;
4799#ifdef HAVE_FLINT
4800 long rank;
4802#else
4804#endif
4806 while (oldL <= l)
4807 {
4808 j= factors;
4809 if (GF)
4811
4812 powX= power (y-gamma, oldL);
4814 for (int i= 0; i < oldL*degMipo; i++)
4815 {
4816 imBasis= mod (power (y, i), powX);
4817 imBasis= imBasis (power (y, degMipo), y);
4818 imBasis= imBasis (y, gamma);
4819 iter= imBasis;
4820 for (; iter.hasTerms(); iter++)
4821 Mat (iter.exp()+ 1, i+1)= iter.coeff();
4822 }
4823
4824#ifdef HAVE_FLINT
4829#else
4831 *NTLMat= inv (*NTLMat);
4832#endif
4833
4834 if (GF)
4836
4837 truncF= mod (F, power (y, oldL));
4838 if (useOldQs)
4839 {
4840 for (int i= 0; i < factors.length(); i++, j++)
4841 A[i]= logarithmicDerivative (truncF, j.getItem(), oldL, oldL2, bufQ[i],
4842 bufQ[i]);
4843 }
4844 else
4845 {
4846 for (int i= 0; i < factors.length(); i++, j++)
4847 A[i]= logarithmicDerivative (truncF, j.getItem(), oldL, bufQ [i]);
4848 }
4849 useOldQs= true;
4850
4851 for (int i= 0; i < d; i++)
4852 {
4853 if (bounds [i] + 1 <= oldL/2)
4854 {
4855 int k= tmin (bounds [i] + 1, oldL/2);
4856 C= CFMatrix (oldL*degMipo - k, factors.length());
4857 for (int ii= 0; ii < factors.length(); ii++)
4858 {
4859 if (A[ii].size() - 1 >= i)
4860 {
4861 if (GF)
4862 {
4863 A [ii] [i]= A [ii] [i] (y-evaluation, y);
4865 A[ii] [i]= GF2FalphaRep (A[ii] [i], alpha);
4866 if (alpha != gamma)
4868 gamma, source, dest
4869 );
4870#ifdef HAVE_FLINT
4871 buf= getCoeffs (A[ii] [i], k, oldL, degMipo, gamma, 0, FLINTMatInv);
4872#else
4873 buf= getCoeffs (A[ii] [i], k, oldL, degMipo, gamma, 0, *NTLMat);
4874#endif
4875 }
4876 else
4877 {
4878 A [ii] [i]= A [ii] [i] (y-evaluation, y);
4879 if (alpha != gamma)
4881 gamma, source, dest
4882 );
4883#ifdef HAVE_FLINT
4884 buf= getCoeffs (A[ii] [i], k, oldL, degMipo, gamma, 0, FLINTMatInv);
4885#else
4886 buf= getCoeffs (A[ii] [i], k, oldL, degMipo, gamma, 0, *NTLMat);
4887#endif
4888 }
4889 writeInMatrix (C, buf, ii + 1, 0);
4890 }
4891 if (GF)
4893 }
4894
4895 if (GF)
4897
4898#ifdef HAVE_FLINT
4913 nmod_mat_mul (FLINTN, FLINTC, FLINTK); //no aliasing allowed!!
4914
4918#else
4920 NTLK= (*NTLC)*NTLN;
4921 transpose (NTLK, NTLK);
4922 kernel (NTLK, NTLK);
4923 transpose (NTLK, NTLK);
4924 NTLN *= NTLK;
4925 delete NTLC;
4926#endif
4927
4928 if (GF)
4930
4931#ifdef HAVE_FLINT
4932 if (nmod_mat_ncols (FLINTN) == 1)
4933 {
4936#else
4937 if (NTLN.NumCols() == 1)
4938 {
4939 delete NTLMat;
4940#endif
4941 Variable y= Variable (2);
4942 CanonicalForm tmp= F (y - evaluation, y);
4943 CFList source, dest;
4944 tmp= mapDown (tmp, info, source, dest);
4945 delete [] A;
4946 return CFList (tmp);
4947 }
4948 }
4949 }
4950
4951#ifdef HAVE_FLINT
4954#else
4955 delete NTLMat;
4956#endif
4957
4958#ifdef HAVE_FLINT
4959 if (nmod_mat_ncols (FLINTN) == 1)
4960#else
4961 if (NTLN.NumCols() == 1)
4962#endif
4963 {
4964 Variable y= Variable (2);
4965 CanonicalForm tmp= F (y - evaluation, y);
4966 CFList source, dest;
4967 tmp= mapDown (tmp, info, source, dest);
4968 delete [] A;
4969 return CFList (tmp);
4970 }
4971
4972 int * zeroOneVecs;
4973 bufF= F;
4975#ifdef HAVE_FLINT
4979 );
4980#else
4984 );
4985#endif
4986 delete [] zeroOneVecs;
4987 if (degree (bufF) + 1 + degree (LC (bufF, 1)) < l && result.length() > 0)
4988 {
4989 F= bufF;
4991 return result;
4992 }
4993
4994 result= CFList();
4995 oldL2= oldL;
4996 oldL *= 2;
4997 if (oldL > l)
4998 {
4999 if (!hitBound)
5000 {
5001 oldL= l;
5002 hitBound= true;
5003 }
5004 else
5005 break;
5006 }
5007 }
5008 delete [] A;
5009 return result;
5010}
5011#endif
5012
5013#ifdef HAVE_NTL // logarithmicDerivative
5014#ifdef HAVE_FLINT
5015CFList
5017 int d, int* bounds, CFArray& bufQ, nmod_mat_t FLINTN,
5018 const Variable& alpha, const CanonicalForm& eval
5019 )
5020#else
5021CFList
5023 int d, int* bounds, CFArray& bufQ, mat_zz_p& NTLN,
5024 const Variable& alpha, const CanonicalForm& eval
5025 )
5026#endif
5027{
5028 CFList result= CFList();
5029 CFArray * A= new CFArray [factors.length()];
5031 int oldL2= oldL/2;
5032 bool hitBound= false;
5033 bool useOldQs= false;
5034#ifdef HAVE_FLINT
5035 if (nmod_mat_nrows (FLINTN) != factors.length()) //refined factors
5036 {
5039 for (long i=factors.length()-1; i >= 0; i--)
5040 nmod_mat_entry (FLINTN, i, i)= 1;
5041 }
5042#else
5043 if (NTLN.NumRows() != factors.length()) //refined factors
5044 ident (NTLN, factors.length());
5045#endif
5047 CFMatrix C;
5048 CFArray buf;
5049#ifdef HAVE_FLINT
5050 long rank;
5052#else
5053 mat_zz_p* NTLC, NTLK;
5054#endif
5057 Variable y= F.mvar();
5058 while (oldL <= l)
5059 {
5060 j= factors;
5061 truncF= mod (F, power (y, oldL));
5062 if (useOldQs)
5063 {
5064 for (int i= 0; i < factors.length(); i++, j++)
5065 A[i]= logarithmicDerivative (truncF, j.getItem(), oldL, oldL2, bufQ[i],
5066 bufQ[i]
5067 );
5068 }
5069 else
5070 {
5071 for (int i= 0; i < factors.length(); i++, j++)
5072 A[i]= logarithmicDerivative (truncF, j.getItem(), oldL, bufQ [i]);
5073 }
5074 useOldQs= true;
5075
5076 for (int i= 0; i < d; i++)
5077 {
5078 if (bounds [i] + 1 <= oldL/2)
5079 {
5080 int k= tmin (bounds [i] + 1, oldL/2);
5082 for (int ii= 0; ii < factors.length(); ii++)
5083 {
5084 if (A[ii].size() - 1 >= i)
5085 {
5086 buf= getCoeffs (A[ii] [i], k, alpha);
5087 writeInMatrix (C, buf, ii + 1, 0);
5088 }
5089 }
5090#ifdef HAVE_FLINT
5105 nmod_mat_mul (FLINTN, FLINTC, FLINTK); //no aliasing allowed!!
5106
5110#else
5112 NTLK= (*NTLC)*NTLN;
5113 transpose (NTLK, NTLK);
5114 kernel (NTLK, NTLK);
5115 transpose (NTLK, NTLK);
5116 NTLN *= NTLK;
5117 delete NTLC;
5118#endif
5119#ifdef HAVE_FLINT
5120 if (nmod_mat_ncols (FLINTN) == 1)
5121#else
5122 if (NTLN.NumCols() == 1)
5123#endif
5124 {
5125 delete [] A;
5126 return CFList (F(y-eval,y));
5127 }
5128 }
5129 }
5130
5131 int * zeroOneVecs;
5132#ifdef HAVE_FLINT
5134#else
5136#endif
5137
5138 bufF= F;
5140#ifdef HAVE_FLINT
5142#else
5144#endif
5145 delete [] zeroOneVecs;
5146 if (degree (bufF) + 1 + degree (LC (bufF, 1)) < l && result.length() > 0)
5147 {
5148 F= bufF;
5150 delete [] A;
5151 return result;
5152 }
5153
5154 result= CFList();
5155 oldL2= oldL;
5156 oldL *= 2;
5157 if (oldL > l)
5158 {
5159 if (!hitBound)
5160 {
5161 oldL= l;
5162 hitBound= true;
5163 }
5164 else
5165 break;
5166 }
5167 }
5168 delete [] A;
5169 return result;
5170}
5171#endif
5172
5173#ifdef HAVE_NTL // logarithmicDerivative
5174#ifdef HAVE_FLINT
5175CFList
5177 factors, int l, int liftBound, int d, int*
5180 const CanonicalForm& eval
5181 )
5182#else
5183CFList
5185 factors, int l, int liftBound, int d, int*
5188 const CanonicalForm& eval
5189 )
5190#endif
5191{
5192 CanonicalForm LCF= LC (F, 1);
5193 CFList result;
5194 bool irreducible= false;
5197 CFArray *A = new CFArray [bufFactors.length()];
5198 bool useOldQs= false;
5199 bool hitBound= false;
5200 int oldL= l;
5201 int stepSize= 8; //TODO choose better step size?
5202 l += tmax (tmin (8, degree (F) + 1 + degree (LC (F, 1))-l), 2);
5203#ifdef HAVE_FLINT
5204 if (nmod_mat_nrows (FLINTN) != factors.length()) //refined factors
5205 {
5208 for (long i=factors.length()-1; i >= 0; i--)
5209 nmod_mat_entry (FLINTN, i, i)= 1;
5210 }
5211#else
5212 if (NTLN.NumRows() != factors.length()) //refined factors
5213 ident (NTLN, factors.length());
5214#endif
5216 CFMatrix C;
5217 CFArray buf;
5218#ifdef HAVE_FLINT
5219 long rank;
5221#else
5222 mat_zz_p* NTLC, NTLK;
5223#endif
5225 Variable y= F.mvar();
5226 while (l <= liftBound)
5227 {
5230 j= bufFactors;
5231 truncF= mod (F, power (y, l));
5232 if (useOldQs)
5233 {
5234 for (int i= 0; i < bufFactors.length(); i++, j++)
5235 A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
5236 bufQ[i]);
5237 }
5238 else
5239 {
5240 for (int i= 0; i < bufFactors.length(); i++, j++)
5241 A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ [i]);
5242 }
5243 for (int i= 0; i < d; i++)
5244 {
5245 if (bounds [i] + 1 <= l/2)
5246 {
5247 int k= tmin (bounds [i] + 1, l/2);
5248 C= CFMatrix (l - k, bufFactors.length());
5249 for (int ii= 0; ii < bufFactors.length(); ii++)
5250 {
5251 if (A[ii].size() - 1 >= i)
5252 {
5253 buf= getCoeffs (A[ii] [i], k);
5254 writeInMatrix (C, buf, ii + 1, 0);
5255 }
5256 }
5257#ifdef HAVE_FLINT
5272 nmod_mat_mul (FLINTN, FLINTC, FLINTK); //no aliasing allowed!!
5273
5277#else
5279 NTLK= (*NTLC)*NTLN;
5280 transpose (NTLK, NTLK);
5281 kernel (NTLK, NTLK);
5282 transpose (NTLK, NTLK);
5283 NTLN *= NTLK;
5284 delete NTLC;
5285#endif
5286#ifdef HAVE_FLINT
5287 if (nmod_mat_ncols (FLINTN) == 1)
5288#else
5289 if (NTLN.NumCols() == 1)
5290#endif
5291 {
5292 irreducible= true;
5293 break;
5294 }
5295 }
5296 }
5297
5298#ifdef HAVE_FLINT
5299 if (nmod_mat_ncols (FLINTN) == 1)
5300#else
5301 if (NTLN.NumCols() == 1)
5302#endif
5303 {
5304 irreducible= true;
5305 break;
5306 }
5307
5308#ifdef HAVE_FLINT
5310#else
5312#endif
5313 bufF= F;
5315#ifdef HAVE_FLINT
5317#else
5319#endif
5320 delete [] zeroOneVecs;
5321 if (result.length() > 0 && degree (bufF) + 1 + degree (LC (bufF, 1)) <= l)
5322 {
5323 F= bufF;
5325 delete [] A;
5326 return result;
5327 }
5328 else
5329 {
5330 bufF= F;
5332 }
5333
5334#ifdef HAVE_FLINT
5335 if (isReduced (FLINTN))
5336#else
5337 if (isReduced (NTLN))
5338#endif
5339 {
5340 int factorsFound= 0;
5341 bufF= F;
5342#ifdef HAVE_FLINT
5343 int* factorsFoundIndex= new int [nmod_mat_ncols (FLINTN)];
5344 for (long i= 0; i < nmod_mat_ncols (FLINTN); i++)
5345#else
5346 int* factorsFoundIndex= new int [NTLN.NumCols()];
5347 for (long i= 0; i < NTLN.NumCols(); i++)
5348#endif
5349 factorsFoundIndex[i]= 0;
5350#ifdef HAVE_FLINT
5351 if (l < liftBound)
5354 );
5355 else
5358 FLINTN, eval, false
5359 );
5360
5362#else
5363 if (l < liftBound)
5365 factorsFoundIndex, NTLN, eval, false
5366 );
5367 else
5370 NTLN, eval, false
5371 );
5372
5373 if (NTLN.NumCols() == result.length())
5374#endif
5375 {
5376 delete [] A;
5377 delete [] factorsFoundIndex;
5378 return result;
5379 }
5380 delete [] factorsFoundIndex;
5381 }
5382 result= CFList();
5383 oldL= l;
5384 stepSize *= 2;
5385 l += stepSize;
5386 if (l > liftBound)
5387 {
5388 if (!hitBound)
5389 {
5390 l= liftBound;
5391 hitBound= true;
5392 }
5393 else
5394 break;
5395 }
5396 }
5397 if (irreducible)
5398 {
5399 delete [] A;
5400 return CFList (F (y-eval,y));
5401 }
5402 delete [] A;
5404 return CFList();
5405}
5406#endif
5407
5408//Fq
5409#ifdef HAVE_NTL
5410CFList
5412 factors, int l, int liftBound, int d, int*
5415 const CanonicalForm& eval
5416 )
5417{
5418 CanonicalForm LCF= LC (F, 1);
5419 CFList result;
5420 bool irreducible= false;
5423 CFArray *A = new CFArray [bufFactors.length()];
5424 bool useOldQs= false;
5425 bool hitBound= false;
5426 int oldL= l;
5427 int stepSize= 8; //TODO choose better step size?
5428 l += tmax (tmin (8, degree (F) + 1 + degree (LC (F, 1))-l), 2);
5429 if (NTLN.NumRows() != factors.length()) //refined factors
5430 ident (NTLN, factors.length());
5432 CFArray buf;
5435 Variable y= F.mvar();
5436 while (l <= liftBound)
5437 {
5440 j= bufFactors;
5441 truncF= mod (F, power (y, l));
5442 if (useOldQs)
5443 {
5444 for (int i= 0; i < bufFactors.length(); i++, j++)
5445 A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
5446 bufQ[i]);
5447 }
5448 else
5449 {
5450 for (int i= 0; i < bufFactors.length(); i++, j++)
5451 A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ [i]);
5452 }
5453 for (int i= 0; i < d; i++)
5454 {
5455 if (bounds [i] + 1 <= l/2)
5456 {
5457 int k= tmin (bounds [i] + 1, l/2);
5459 for (int ii= 0; ii < bufFactors.length(); ii++)
5460 {
5461 if (A[ii].size() - 1 >= i)
5462 {
5463 buf= getCoeffs (A[ii] [i], k);
5464 writeInMatrix (C, buf, ii + 1, 0);
5465 }
5466 }
5468 NTLK= (*NTLC)*NTLN;
5469 transpose (NTLK, NTLK);
5470 kernel (NTLK, NTLK);
5471 transpose (NTLK, NTLK);
5472 NTLN *= NTLK;
5473 delete NTLC;
5474 if (NTLN.NumCols() == 1)
5475 {
5476 irreducible= true;
5477 break;
5478 }
5479 }
5480 }
5481 if (NTLN.NumCols() == 1)
5482 {
5483 irreducible= true;
5484 break;
5485 }
5486
5488 bufF= F;
5491 delete [] zeroOneVecs;
5492 if (result.length() > 0 && degree (bufF) + 1 + degree (LC (bufF, 1)) <= l)
5493 {
5494 F= bufF;
5496 delete [] A;
5497 return result;
5498 }
5499 else
5500 {
5501 bufF= F;
5503 }
5504
5505 if (isReduced (NTLN))
5506 {
5507 int factorsFound= 0;
5508 bufF= F;
5509 int* factorsFoundIndex= new int [NTLN.NumCols()];
5510 for (long i= 0; i < NTLN.NumCols(); i++)
5511 factorsFoundIndex[i]= 0;
5512 if (l < liftBound)
5514 factorsFoundIndex, NTLN, eval, false
5515 );
5516 else
5519 NTLN, eval, false
5520 );
5521 if (NTLN.NumCols() == result.length())
5522 {
5523 delete [] A;
5524 delete [] factorsFoundIndex;
5525 return result;
5526 }
5527 delete [] factorsFoundIndex;
5528 }
5529 result= CFList();
5530 oldL= l;
5531 stepSize *= 2;
5532 l += stepSize;
5533 if (l > liftBound)
5534 {
5535 if (!hitBound)
5536 {
5537 l= liftBound;
5538 hitBound= true;
5539 }
5540 else
5541 break;
5542 }
5543 }
5544 if (irreducible)
5545 {
5546 delete [] A;
5547 return CFList (F (y-eval,y));
5548 }
5549 delete [] A;
5551 return CFList();
5552}
5553#endif
5554
5555//over field extension
5556#ifdef HAVE_NTL // logarithmicDerivative
5557#ifdef HAVE_FLINT
5558CFList
5560 int liftBound, int d, int* bounds,
5563 const CanonicalForm& evaluation, const
5565 CFList& dest
5566 )
5567#else
5568CFList
5570 int liftBound, int d, int* bounds,
5573 const CanonicalForm& evaluation, const
5575 CFList& dest
5576 )
5577#endif
5578{
5579 CanonicalForm LCF= LC (F, 1);
5580 CFList result;
5581 bool irreducible= false;
5584 CFArray *A = new CFArray [bufFactors.length()];
5585 bool useOldQs= false;
5586 bool hitBound= false;
5588 int degMipo= degree (getMipo (info.getAlpha()));
5589 Variable alpha= info.getAlpha();
5590 int oldL= l; //be careful
5591 int stepSize= 8;
5592 l += tmax (tmin (8, degree (F) + 1 + degree (LC (F, 1))-l),2);
5593 Variable gamma= info.getBeta();
5594 CanonicalForm primElemAlpha= info.getGamma();
5596#ifdef HAVE_FLINT
5599 for (long i=factors.length()-1; i >= 0; i--)
5600 nmod_mat_entry (FLINTN, i, i)= 1;
5601#else
5602 if (NTLN.NumRows() != factors.length()) //refined factors
5603 ident (NTLN, factors.length());
5604#endif
5605 Variable y= F.mvar();
5607 CFMatrix Mat, C;
5609#ifdef HAVE_FLINT
5610 long rank;
5612#else
5614#endif
5616 CFArray buf;
5617 while (l <= liftBound)
5618 {
5621
5622 if (GF)
5624
5625 powX= power (y-gamma, l);
5627 for (int i= 0; i < l*degMipo; i++)
5628 {
5629
5630 imBasis= mod (power (y, i), powX);
5631 imBasis= imBasis (power (y, degMipo), y);
5632 imBasis= imBasis (y, gamma);
5633 iter= imBasis;
5634 for (; iter.hasTerms(); iter++)
5635 Mat (iter.exp()+ 1, i+1)= iter.coeff();
5636 }
5637
5638#ifdef HAVE_FLINT
5643#else
5645 *NTLMat= inv (*NTLMat);
5646#endif
5647
5648 if (GF)
5650
5651 j= bufFactors;
5652 truncF= mod (F, power (y, l));
5653 if (useOldQs)
5654 {
5655 for (int i= 0; i < bufFactors.length(); i++, j++)
5656 A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
5657 bufQ[i]);
5658 }
5659 else
5660 {
5661 for (int i= 0; i < bufFactors.length(); i++, j++)
5662 A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ [i]);
5663 }
5664 for (int i= 0; i < d; i++)
5665 {
5666 if (bounds [i] + 1 <= l/2)
5667 {
5668 int k= tmin (bounds [i] + 1, l/2);
5669 C= CFMatrix (l*degMipo - k, bufFactors.length());
5670 for (int ii= 0; ii < bufFactors.length(); ii++)
5671 {
5672 if (A[ii].size() - 1 >= i)
5673 {
5674 if (GF)
5675 {
5676 A [ii] [i]= A [ii] [i] (y-evaluation, y);
5678 A[ii] [i]= GF2FalphaRep (A[ii] [i], alpha);
5679 if (alpha != gamma)
5681 gamma, source, dest
5682 );
5683#ifdef HAVE_FLINT
5684 buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, FLINTMatInv);
5685#else
5686 buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, *NTLMat);
5687#endif
5688 }
5689 else
5690 {
5691 A [ii] [i]= A [ii] [i] (y-evaluation, y);
5692 if (alpha != gamma)
5694 gamma, source, dest
5695 );
5696#ifdef HAVE_FLINT
5697 buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, FLINTMatInv);
5698#else
5699 buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, *NTLMat);
5700#endif
5701 }
5702 writeInMatrix (C, buf, ii + 1, 0);
5703 }
5704 if (GF)
5706 }
5707
5708 if (GF)
5710
5711#ifdef HAVE_FLINT
5726 nmod_mat_mul (FLINTN, FLINTC, FLINTK); //no aliasing allowed!!
5727
5731#else
5733 NTLK= (*NTLC)*NTLN;
5734 transpose (NTLK, NTLK);
5735 kernel (NTLK, NTLK);
5736 transpose (NTLK, NTLK);
5737 NTLN *= NTLK;
5738 delete NTLC;
5739#endif
5740
5741 if (GF)
5743
5744#ifdef HAVE_FLINT
5745 if (nmod_mat_ncols (FLINTN) == 1)
5746#else
5747 if (NTLN.NumCols() == 1)
5748#endif
5749 {
5750 irreducible= true;
5751 break;
5752 }
5753 }
5754 }
5755
5756#ifdef HAVE_FLINT
5759 if (nmod_mat_ncols (FLINTN) == 1)
5760#else
5761 delete NTLMat;
5762 if (NTLN.NumCols() == 1)
5763#endif
5764 {
5765 irreducible= true;
5766 break;
5767 }
5768
5769 bufF= F;
5771#ifdef HAVE_FLINT
5775 );
5776#else
5780 );
5781#endif
5782 delete [] zeroOneVecs;
5783 if (result.length() > 0 && degree (bufF) + 1 + degree (LC (bufF, 1)) <= l)
5784 {
5785 F= bufF;
5787 delete [] A;
5788 return result;
5789 }
5790 else
5791 {
5792 bufF= F;
5794 }
5795
5796#ifdef HAVE_FLINT
5797 if (isReduced (FLINTN))
5798#else
5799 if (isReduced (NTLN))
5800#endif
5801 {
5802 int factorsFound= 0;
5803 bufF= F;
5804#ifdef HAVE_FLINT
5805 int* factorsFoundIndex= new int [nmod_mat_ncols (FLINTN)];
5806 for (long i= 0; i < nmod_mat_ncols (FLINTN); i++)
5807#else
5808 int* factorsFoundIndex= new int [NTLN.NumCols()];
5809 for (long i= 0; i < NTLN.NumCols(); i++)
5810#endif
5811 factorsFoundIndex[i]= 0;
5812#ifdef HAVE_FLINT
5813 if (l < degree (bufF) + 1 + degree (LCF))
5816 );
5817 else
5820 FLINTN, false, info, evaluation
5821 );
5823#else
5824 if (l < degree (bufF) + 1 + degree (LCF))
5827 );
5828 else
5831 NTLN, false, info, evaluation
5832 );
5833 if (NTLN.NumCols() == result.length())
5834#endif
5835 {
5836 delete [] A;
5837 delete [] factorsFoundIndex;
5838 return result;
5839 }
5840 delete [] factorsFoundIndex;
5841 }
5842 result= CFList();
5843 oldL= l;
5844 stepSize *= 2;
5845 l += stepSize;
5846 if (l > liftBound)
5847 {
5848 if (!hitBound)
5849 {
5850 l= liftBound;
5851 hitBound= true;
5852 }
5853 else
5854 break;
5855 }
5856 }
5857 if (irreducible)
5858 {
5859 delete [] A;
5860 Variable y= Variable (2);
5861 CanonicalForm tmp= F (y - evaluation, y);
5862 CFList source, dest;
5863 tmp= mapDown (tmp, info, source, dest);
5864 return CFList (tmp);
5865 }
5866 delete [] A;
5868 return CFList();
5869}
5870#endif
5871
5872#ifdef HAVE_NTL // logarithmicDerivative
5873#ifdef HAVE_FLINT
5874CFList
5876 l, int liftBound, int d, int* bounds,
5879 const Variable& alpha,
5880 const CanonicalForm& eval
5881 )
5882#else
5883CFList
5885 l, int liftBound, int d, int* bounds,
5888 const Variable& alpha,
5889 const CanonicalForm& eval
5890 )
5891#endif
5892{
5893 CanonicalForm LCF= LC (F, 1);
5894 CFList result;
5895 bool irreducible= false;
5898 CFArray *A = new CFArray [bufFactors.length()];
5899 bool useOldQs= false;
5901 bool hitBound= false;
5902 int oldL= l;
5903 int stepSize= 8; //TODO choose better step size?
5904 l += tmax (tmin (8, degree (F) + 1 + degree (LC (F, 1))-l), 2);
5905#ifdef HAVE_FLINT
5906 if (nmod_mat_nrows (FLINTN) != factors.length()) //refined factors
5907 {
5910 for (long i=factors.length()-1; i >= 0; i--)
5911 nmod_mat_entry (FLINTN, i, i)= 1;
5912 }
5913#else
5914 if (NTLN.NumRows() != factors.length()) //refined factors
5915 ident (NTLN, factors.length());
5916#endif
5918 CFMatrix C;
5919#ifdef HAVE_FLINT
5920 long rank;
5922#else
5923 mat_zz_p* NTLC, NTLK;
5924#endif
5926 Variable y= F.mvar();
5927 while (l <= liftBound)
5928 {
5931 j= bufFactors;
5932 truncF= mod (F, power (y, l));
5933 if (useOldQs)
5934 {
5935 for (int i= 0; i < bufFactors.length(); i++, j++)
5936 A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
5937 bufQ[i]);
5938 }
5939 else
5940 {
5941 for (int i= 0; i < bufFactors.length(); i++, j++)
5942 A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ [i]);
5943 }
5944 for (int i= 0; i < d; i++)
5945 {
5946 if (bounds [i] + 1 <= l/2)
5947 {
5948 int k= tmin (bounds [i] + 1, l/2);
5950 for (int ii= 0; ii < bufFactors.length(); ii++)
5951 {
5952 CFArray buf;
5953 if (A[ii].size() - 1 >= i)
5954 {
5955 buf= getCoeffs (A[ii] [i], k, alpha);
5956 writeInMatrix (C, buf, ii + 1, 0);
5957 }
5958 }
5959#ifdef HAVE_FLINT
5974 nmod_mat_mul (FLINTN, FLINTC, FLINTK); //no aliasing allowed!!
5975
5979#else
5981 NTLK= (*NTLC)*NTLN;
5982 transpose (NTLK, NTLK);
5983 kernel (NTLK, NTLK);
5984 transpose (NTLK, NTLK);
5985 NTLN *= NTLK;
5986 delete NTLC;
5987#endif
5988#ifdef HAVE_FLINT
5989 if (nmod_mat_ncols (FLINTN) == 1)
5990#else
5991 if (NTLN.NumCols() == 1)
5992#endif
5993 {
5994 irreducible= true;
5995 break;
5996 }
5997 }
5998 }
5999#ifdef HAVE_FLINT
6000 if (nmod_mat_ncols (FLINTN) == 1)
6001#else
6002 if (NTLN.NumCols() == 1)
6003#endif
6004 {
6005 irreducible= true;
6006 break;
6007 }
6008
6009#ifdef HAVE_FLINT
6011#else
6013#endif
6016#ifdef HAVE_FLINT
6018#else
6020#endif
6021 delete [] zeroOneVecs;
6022 if (result.length() > 0 && degree (bufF) + 1 + degree (LC (bufF, 1)) <= l)
6023 {
6024 F= bufF;
6026 delete [] A;
6027 return result;
6028 }
6029 else
6030 {
6031 bufF= F;
6033 }
6034
6035#ifdef HAVE_FLINT
6036 if (isReduced (FLINTN))
6037#else
6038 if (isReduced (NTLN))
6039#endif
6040 {
6041 int factorsFound= 0;
6042 bufF= F;
6043#ifdef HAVE_FLINT
6044 int* factorsFoundIndex= new int [nmod_mat_ncols (FLINTN)];
6045 for (long i= 0; i < nmod_mat_ncols (FLINTN); i++)
6046#else
6047 int* factorsFoundIndex= new int [NTLN.NumCols()];
6048 for (long i= 0; i < NTLN.NumCols(); i++)
6049#endif
6050 factorsFoundIndex[i]= 0;
6051#ifdef HAVE_FLINT
6052 if (l < degree (bufF) + 1 + degree (LCF))
6055 );
6056 else
6059 FLINTN, eval, false
6060 );
6062#else
6063 if (l < degree (bufF) + 1 + degree (LCF))
6065 factorsFoundIndex, NTLN, eval, false
6066 );
6067 else
6070 NTLN, eval, false
6071 );
6072 if (NTLN.NumCols() == result.length())
6073#endif
6074 {
6075 delete [] A;
6076 delete [] factorsFoundIndex;
6077 return result;
6078 }
6079 delete [] factorsFoundIndex;
6080 }
6081 result= CFList();
6082 oldL= l;
6083 stepSize *= 2;
6084 l += stepSize;
6085 if (l > liftBound)
6086 {
6087 if (!hitBound)
6088 {
6089 l= liftBound;
6090 hitBound= true;
6091 }
6092 else
6093 break;
6094 }
6095 }
6096 if (irreducible)
6097 {
6098 delete [] A;
6099 return CFList (F (y-eval,y));
6100 }
6101 delete [] A;
6103 return CFList();
6104}
6105#endif
6106
6107#ifndef HAVE_FLINT
6108void
6109refineAndRestartLift (const CanonicalForm& F, const mat_zz_p& NTLN, int
6112 )
6113{
6115 Variable y= Variable (2);
6116 CanonicalForm LCF= LC (F, 1);
6119 for (long i= 1; i <= NTLN.NumCols(); i++)
6120 {
6121 iter= factors;
6122 buf= 1;
6123 for (long j= 1; j <= NTLN.NumRows(); j++, iter++)
6124 {
6125 if (!IsZero (NTLN (j,i)))
6126 buf= mulNTL (buf, mod (iter.getItem(), y));
6127 }
6129 }
6132 Pi= CFArray();
6133 diophant= CFList();
6134 factors.insert (LCF);
6135 henselLift12 (F, factors, l, Pi, diophant, M);
6136}
6137#endif
6138
6139#ifdef HAVE_FLINT
6140#ifdef HAVE_NTL // henselLift12
6141void
6145 )
6146{
6148 Variable y= Variable (2);
6149 CanonicalForm LCF= LC (F, 1);
6152 for (long i= 0; i < nmod_mat_ncols (FLINTN); i++)
6153 {
6154 iter= factors;
6155 buf= 1;
6156 for (long j= 0; j < nmod_mat_nrows (FLINTN); j++, iter++)
6157 {
6158 if (!(nmod_mat_entry (FLINTN,j,i) == 0))
6159 buf= mulNTL (buf, mod (iter.getItem(), y));
6160 }
6162 }
6165 Pi= CFArray();
6166 diophant= CFList();
6167 factors.insert (LCF);
6168 henselLift12 (F, factors, l, Pi, diophant, M);
6169}
6170#endif
6171#endif
6172
6173#ifdef HAVE_NTL // mat_zz_pE
6174void
6178 )
6179{
6181 Variable y= Variable (2);
6182 CanonicalForm LCF= LC (F, 1);
6185 for (long i= 1; i <= NTLN.NumCols(); i++)
6186 {
6187 iter= factors;
6188 buf= 1;
6189 for (long j= 1; j <= NTLN.NumRows(); j++, iter++)
6190 {
6191 if (!IsZero (NTLN (j,i)))
6192 buf= mulNTL (buf, mod (iter.getItem(), y));
6193 }
6195 }
6198 Pi= CFArray();
6199 diophant= CFList();
6200 factors.insert (LCF);
6201 henselLift12 (F, factors, l, Pi, diophant, M);
6202}
6203#endif
6204
6205#ifdef HAVE_FLINT
6206CFList
6209 int& factorsFound, bool beenInThres, CFMatrix& M,
6212 )
6213#else
6214CFList
6217 int& factorsFound, bool beenInThres, CFMatrix& M,
6220 )
6221#endif
6222{
6223 int sizeOfLiftPre;
6224 int * liftPre= getLiftPrecisions (F, sizeOfLiftPre, degree (LC (F, 1), 2));
6225
6226 Variable y= F.mvar();
6227 factorsFound= 0;
6228 CanonicalForm LCF= LC (F, 1);
6229 CFList result;
6230 int smallFactorDeg= tmin (11, liftPre [sizeOfLiftPre- 1] + 1);
6231#ifdef HAVE_FLINT
6234 int * factorsFoundIndex= new int [nmod_mat_ncols (FLINTN)];
6235 for (long i= 0; i < nmod_mat_ncols (FLINTN); i++)
6236#else
6237 mat_zz_p NTLN= N;
6238 int * factorsFoundIndex= new int [NTLN.NumCols()];
6239 for (long i= 0; i < NTLN.NumCols(); i++)
6240#endif
6241 factorsFoundIndex [i]= 0;
6242
6243 if (degree (F) + 1 > smallFactorDeg)
6244 {
6245 if (l < smallFactorDeg)
6246 {
6248 factors.insert (LCF);
6250 TIMING_END_AND_PRINT (fac_fq_lift, "time to lift in reconstruction0: ");
6252 }
6253#ifdef HAVE_FLINT
6257 );
6258 TIMING_END_AND_PRINT (fac_fq_reconstruction, "time to reconstruct0: ");
6259 if (result.length() == nmod_mat_ncols (FLINTN))
6260 {
6262#else
6266 );
6267 TIMING_END_AND_PRINT (fac_fq_reconstruction, "time to reconstruct0: ");
6268 if (result.length() == NTLN.NumCols())
6269 {
6270#endif
6271 delete [] liftPre;
6272 delete [] factorsFoundIndex;
6273 return result;
6274 }
6275 }
6276
6277 int i= sizeOfLiftPre - 1;
6278 int dummy= 1;
6279 if (sizeOfLiftPre > 1 && sizeOfLiftPre < 30)
6280 {
6281 while (i > 0)
6282 {
6283 if (l < liftPre[i-1] + 1)
6284 {
6285 factors.insert (LCF);
6287 henselLiftResume12 (F, factors, l, liftPre[i-1] + 1, Pi, diophant, M);
6288 TIMING_END_AND_PRINT (fac_fq_lift, "time to lift in reconstruction1: ");
6289 l= liftPre[i-1] + 1;
6290 }
6291 else
6292 {
6293 i--;
6294 if (i != 0)
6295 continue;
6296 }
6297#ifdef HAVE_FLINT
6301 );
6302 TIMING_END_AND_PRINT (fac_fq_reconstruction, "time to reconstruct1: ");
6303 if (result.length() == nmod_mat_ncols (FLINTN))
6304 {
6306#else
6310 );
6311 TIMING_END_AND_PRINT (fac_fq_reconstruction, "time to reconstruct1: ");
6312 if (result.length() == NTLN.NumCols())
6313 {
6314#endif
6315 delete [] liftPre;
6316 delete [] factorsFoundIndex;
6317 return result;
6318 }
6319 i--;
6320 }
6321 }
6322 else
6323 {
6324 i= 1;
6325 while (((degree (F,y)/4)*i+1) + 4 <= smallFactorDeg)
6326 i++;
6327 while (i < 5)
6328 {
6329 dummy= tmin (degree (F,y)+1, ((degree (F,y)/4)+1)*i+4);
6330 if (l < dummy)
6331 {
6332 factors.insert (LCF);
6335 TIMING_END_AND_PRINT (fac_fq_lift, "time to lift in reconstruction2: ");
6336 l= dummy;
6337 if (i == 1 && degree (F)%4==0 && symmetric && factors.length() == 2 &&
6338 LC (F,1).inCoeffDomain() &&
6339 (degree (factors.getFirst(), 1) == degree (factors.getLast(),1)))
6340 {
6341 Variable x= Variable (1);
6343 int m= degree (F)/4+1;
6344 g= factors.getFirst();
6345 h= factors.getLast();
6346 g= mod (g, power (y,m));
6347 h= mod (h, power (y,m));
6348 g= g (y-evaluation, y);
6349 h= h (y-evaluation, y);
6350 gg= mod (swapvar (g,x,y),power (x,m));
6351 gg= gg (y + evaluation, y);
6352 multiplier1= factors.getLast()[m-1][0]/gg[m-1][0];
6353 gg= div (gg, power (y,m));
6354 gg= gg*power (y,m);
6355 hh= mod (swapvar (h,x,y),power (x,m));
6356 hh= hh (y + evaluation, y);
6357 multiplier2= factors.getFirst()[m-1][0]/hh[m-1][0];
6358 hh= div (hh, power (y,m));
6359 hh= hh*power (y,m);
6362 check1= gg (y-evaluation,y);
6363 check2= hh (y-evaluation,y);
6365 check1= swapvar (check1, x, y);
6366 if (check1/Lc (check1) == check2/Lc (check2))
6367 {
6368#ifdef HAVE_FLINT
6370#endif
6371 result.append (oldcheck1);
6372 result.append (check2);
6373 delete [] liftPre;
6374 delete [] factorsFoundIndex;
6375 return result;
6376 }
6377 }
6378 }
6379 else
6380 {
6381 i++;
6382 if (i < 5)
6383 continue;
6384 }
6385#ifdef HAVE_FLINT
6389 );
6390 TIMING_END_AND_PRINT (fac_fq_reconstruction, "time to reconstruct2: ");
6391 if (result.length() == nmod_mat_ncols (FLINTN))
6392 {
6394#else
6398 );
6399 TIMING_END_AND_PRINT (fac_fq_reconstruction, "time to reconstruct2: ");
6400 if (result.length() == NTLN.NumCols())
6401 {
6402#endif
6403 delete [] liftPre;
6404 delete [] factorsFoundIndex;
6405 return result;
6406 }
6407 i++;
6408 }
6409 }
6410
6411#ifdef HAVE_FLINT
6413#endif
6414 delete [] liftPre;
6415 delete [] factorsFoundIndex;
6416 return result;
6417}
6418
6419#ifdef HAVE_NTL // mat_zz_pE
6420CFList
6423 int& factorsFound, bool beenInThres, CFMatrix& M,
6426 )
6427{
6428 int sizeOfLiftPre;
6429 int * liftPre= getLiftPrecisions (F, sizeOfLiftPre, degree (LC (F, 1), 2));
6430 Variable y= F.mvar();
6431 factorsFound= 0;
6432 CanonicalForm LCF= LC (F, 1);
6433 CFList result;
6434 int smallFactorDeg= 11;
6435 mat_zz_pE NTLN= N;
6436 int * factorsFoundIndex= new int [NTLN.NumCols()];
6437 for (long i= 0; i < NTLN.NumCols(); i++)
6438 factorsFoundIndex [i]= 0;
6439
6440 if (degree (F) + 1 > smallFactorDeg)
6441 {
6442 if (l < smallFactorDeg)
6443 {
6445 factors.insert (LCF);
6447 TIMING_END_AND_PRINT (fac_fq_lift, "time to lift in reconstruction0: ");
6449 }
6453 );
6454 TIMING_END_AND_PRINT (fac_fq_reconstruction, "time to reconstruct0: ");
6455 if (result.length() == NTLN.NumCols())
6456 {
6457 delete [] liftPre;
6458 delete [] factorsFoundIndex;
6459 return result;
6460 }
6461 }
6462
6463 int i= sizeOfLiftPre - 1;
6464 int dummy= 1;
6465 if (sizeOfLiftPre > 1 && sizeOfLiftPre < 30)
6466 {
6467 while (i > 0)
6468 {
6469 if (l < liftPre[i-1] + 1)
6470 {
6471 factors.insert (LCF);
6473 henselLiftResume12 (F, factors, l, liftPre[i-1] + 1, Pi, diophant, M);
6474 TIMING_END_AND_PRINT (fac_fq_lift, "time to lift in reconstruction1: ");
6475 l= liftPre[i-1] + 1;
6476 }
6477 else
6478 {
6479 i--;
6480 if (i != 0)
6481 continue;
6482 }
6486 );
6487 TIMING_END_AND_PRINT (fac_fq_reconstruction, "time to reconstruct1: ");
6488 if (result.length() == NTLN.NumCols())
6489 {
6490 delete [] liftPre;
6491 delete [] factorsFoundIndex;
6492 return result;
6493 }
6494 i--;
6495 }
6496 }
6497 else
6498 {
6499 i= 1;
6500 while ((degree (F,y)/4+1)*i + 4 <= smallFactorDeg)
6501 i++;
6502 while (i < 5)
6503 {
6504 dummy= tmin (degree (F,y)+1, (degree (F,y)/4+1)*i+4);
6505 if (l < dummy)
6506 {
6507 factors.insert (LCF);
6510 TIMING_END_AND_PRINT (fac_fq_lift, "time to lift in reconstruction2: ");
6511 l= dummy;
6512 if (i == 1 && degree (F)%4==0 && symmetric && factors.length() == 2 &&
6513 LC (F,1).inCoeffDomain() &&
6514 (degree (factors.getFirst(), 1) == degree (factors.getLast(),1)))
6515 {
6516 Variable x= Variable (1);
6518 int m= degree (F)/4+1;
6519 g= factors.getFirst();
6520 h= factors.getLast();
6521 g= mod (g, power (y,m));
6522 h= mod (h, power (y,m));
6523 g= g (y-evaluation, y);
6524 h= h (y-evaluation, y);
6525 gg= mod (swapvar (g,x,y),power (x,m));
6526 gg= gg (y + evaluation, y);
6527 multiplier1= factors.getLast()[m-1][0]/gg[m-1][0];
6528 gg= div (gg, power (y,m));
6529 gg= gg*power (y,m);
6530 hh= mod (swapvar (h,x,y),power (x,m));
6531 hh= hh (y + evaluation, y);
6532 multiplier2= factors.getFirst()[m-1][0]/hh[m-1][0];
6533 hh= div (hh, power (y,m));
6534 hh= hh*power (y,m);
6537 check1= gg (y-evaluation,y);
6538 check2= hh (y-evaluation,y);
6540 check1= swapvar (check1, x, y);
6541 if (check1/Lc (check1) == check2/Lc (check2))
6542 {
6543 result.append (oldcheck1);
6544 result.append (check2);
6545 delete [] liftPre;
6546 delete [] factorsFoundIndex;
6547 return result;
6548 }
6549 }
6550 }
6551 else
6552 {
6553 i++;
6554 if (i < 5)
6555 continue;
6556 }
6560 );
6561 TIMING_END_AND_PRINT (fac_fq_reconstruction, "time to reconstruct2: ");
6562 if (result.length() == NTLN.NumCols())
6563 {
6564 delete [] liftPre;
6565 delete [] factorsFoundIndex;
6566 return result;
6567 }
6568 i++;
6569 }
6570 }
6571
6572 delete [] liftPre;
6573 delete [] factorsFoundIndex;
6574 return result;
6575}
6576#endif
6577
6578//over field extension
6579#ifdef HAVE_FLINT
6580CFList
6583 int& factorsFound, bool beenInThres, CFMatrix&
6584 M, CFArray& Pi, CFList& diophant, const
6587 )
6588#else
6589CFList
6592 int& factorsFound, bool beenInThres, CFMatrix&
6593 M, CFArray& Pi, CFList& diophant, const
6596 )
6597#endif
6598{
6599 int sizeOfLiftPre;
6600 int * liftPre= getLiftPrecisions (F, sizeOfLiftPre, degree (LC (F, 1), 2));
6601 Variable y= F.mvar();
6602 factorsFound= 0;
6603 CanonicalForm LCF= LC (F, 1);
6604 CFList result;
6605 int smallFactorDeg= 11;
6606#ifdef HAVE_FLINT
6609 int * factorsFoundIndex= new int [nmod_mat_ncols (FLINTN)];
6610 for (long i= 0; i < nmod_mat_ncols (FLINTN); i++)
6611#else
6612 mat_zz_p NTLN= N;
6613 int * factorsFoundIndex= new int [NTLN.NumCols()];
6614 for (long i= 0; i < NTLN.NumCols(); i++)
6615#endif
6616 factorsFoundIndex [i]= 0;
6617
6618 if (degree (F) + 1 > smallFactorDeg)
6619 {
6620 if (l < smallFactorDeg)
6621 {
6623 factors.insert (LCF);
6625 TIMING_END_AND_PRINT (fac_fq_lift, "time to lift in reconstruction0: ");
6627 }
6629#ifdef HAVE_FLINT
6633 );
6634#else
6638 );
6639#endif
6640 TIMING_END_AND_PRINT (fac_fq_reconstruction, "time to reconstruct0: ");
6641#ifdef HAVE_FLINT
6642 if (result.length() == nmod_mat_ncols (FLINTN))
6643 {
6645#else
6646 if (result.length() == NTLN.NumCols())
6647 {
6648#endif
6649 delete [] liftPre;
6650 delete [] factorsFoundIndex;
6651 return result;
6652 }
6653 }
6654
6655 int i= sizeOfLiftPre - 1;
6656 int dummy= 1;
6657 if (sizeOfLiftPre > 1 && sizeOfLiftPre < 30)
6658 {
6659 while (i > 0)
6660 {
6661 if (l < liftPre[i-1] + 1)
6662 {
6663 factors.insert (LCF);
6665 henselLiftResume12 (F, factors, l, liftPre[i-1] + 1, Pi, diophant, M);
6666 TIMING_END_AND_PRINT (fac_fq_lift, "time to lift in reconstruction1: ");
6667 l= liftPre[i-1] + 1;
6668 }
6669 else
6670 {
6671 i--;
6672 if (i != 0)
6673 continue;
6674 }
6676#ifdef HAVE_FLINT
6680 );
6681#else
6685 );
6686#endif
6687 TIMING_END_AND_PRINT (fac_fq_reconstruction, "time to reconstruct1: ");
6688#ifdef HAVE_FLINT
6689 if (result.length() == nmod_mat_ncols (FLINTN))
6690 {
6692#else
6693 if (result.length() == NTLN.NumCols())
6694 {
6695#endif
6696 delete [] liftPre;
6697 delete [] factorsFoundIndex;
6698 return result;
6699 }
6700 i--;
6701 }
6702 }
6703 else
6704 {
6705 i= 1;
6706 while ((degree (F,y)/4+1)*i + 4 <= smallFactorDeg)
6707 i++;
6708 while (i < 5)
6709 {
6710 dummy= tmin (degree (F,y)+1, (degree (F,y)/4+1)*i+4);
6711 if (l < dummy)
6712 {
6713 factors.insert (LCF);
6716 TIMING_END_AND_PRINT (fac_fq_lift, "time to lift in reconstruction2: ");
6717 l= dummy;
6718 }
6719 else
6720 {
6721 i++;
6722 if (i < 5)
6723 continue;
6724 }
6726#ifdef HAVE_FLINT
6730 );
6731#else
6735 );
6736#endif
6737 TIMING_END_AND_PRINT (fac_fq_reconstruction, "time to reconstruct2: ");
6738#ifdef HAVE_FLINT
6739 if (result.length() == nmod_mat_ncols (FLINTN))
6740 {
6742#else
6743 if (result.length() == NTLN.NumCols())
6744 {
6745#endif
6746 delete [] liftPre;
6747 delete [] factorsFoundIndex;
6748 return result;
6749 }
6750 i++;
6751 }
6752 }
6753
6754#ifdef HAVE_FLINT
6756#endif
6757 delete [] liftPre;
6758 delete [] factorsFoundIndex;
6759 return result;
6760}
6761
6762#ifdef HAVE_NTL // henselLift12
6763CFList
6766 CFMatrix& M, bool& success, int d, const CanonicalForm& eval
6767 )
6768{
6769 CanonicalForm F= G;
6771 bufUniFactors.insert (LC (F, 1));
6772 int smallFactorDeg= d;
6775 int adaptedLiftBound;
6776 success= false;
6777 int * factorsFoundIndex= new int [uniFactors.length()];
6778 for (int i= 0; i < uniFactors.length(); i++)
6779 factorsFoundIndex [i]= 0;
6783 delete [] factorsFoundIndex;
6784 if (degs.getLength() == 1)
6785 {
6786 degPat= degs;
6787 return earlyFactors;
6788 }
6789 if (success)
6790 {
6791 H= F;
6792 return earlyFactors;
6793 }
6794 int sizeOldF= size (G);
6795 if (size (F) < sizeOldF)
6796 {
6797 H= F;
6798 success= true;
6799 return earlyFactors;
6800 }
6801 else
6802 {
6804 return CFList();
6805 }
6806}
6807#endif
6808
6809#ifdef HAVE_NTL // henselLift12
6810CFList
6813 CFMatrix& M, bool& success, int d, const CanonicalForm&
6815 )
6816{
6817 CanonicalForm F= G;
6819 bufUniFactors.insert (LC (F, 1));
6820 int smallFactorDeg= d;
6823 int adaptedLiftBound;
6824 success= false;
6825 int * factorsFoundIndex= new int [uniFactors.length()];
6826 for (int i= 0; i < uniFactors.length(); i++)
6827 factorsFoundIndex [i]= 0;
6832 delete [] factorsFoundIndex;
6833 if (degs.getLength() == 1)
6834 {
6835 degPat= degs;
6836 return earlyFactors;
6837 }
6838 if (success)
6839 {
6840 H= F;
6841 return earlyFactors;
6842 }
6843 Variable y= F.mvar();
6844 int sizeOldF= size (G);
6845 if (size (F) < sizeOldF)
6846 {
6847 H= F;
6848 success= true;
6849 return earlyFactors;
6850 }
6851 else
6852 {
6854 return CFList();
6855 }
6856}
6857#endif
6858
6859#ifdef HAVE_NTL // matrix Fq
6860CFList
6862 const Variable& alpha, const DegreePattern& degPat,
6863 bool symmetric, const CanonicalForm& eval
6864 )
6865{
6867 CanonicalForm F= G;
6868 CanonicalForm LCF= LC (F, 1);
6869 Variable y= F.mvar();
6870 Variable x= Variable (1);
6871 int d;
6872 bool isIrreducible= false;
6873 int* bounds= computeBounds (F, d, isIrreducible);
6874 if (isIrreducible)
6875 {
6876 delete [] bounds;
6877 return CFList (G);
6878 }
6879 int minBound= bounds[0];
6880 for (int i= 1; i < d; i++)
6881 {
6882 if (bounds[i] != 0)
6884 }
6885
6887 CFArray Pi;
6889 int liftBound= 2*totaldegree (F) - 1;
6891
6894 bool success= false;
6896 success, minBound + 1, eval
6897 );
6898
6899 if (smallFactors.length() > 0)
6900 {
6901 if (smallFactors.length() == 1)
6902 {
6903 if (smallFactors.getFirst() == F)
6904 {
6905 delete [] bounds;
6906 return CFList (G (y-eval,y));
6907 }
6908 }
6909 if (degs.getLength() <= 1)
6910 {
6911 delete [] bounds;
6912 return smallFactors;
6913 }
6914 }
6915
6916 int index;
6918 for (CFListIterator i= smallFactors; i.hasItem(); i++)
6919 {
6920 index= 1;
6921 tmp1= mod (i.getItem(),y-eval);
6922 tmp1 /= Lc (tmp1);
6923 for (CFListIterator j= bufUniFactors; j.hasItem(); j++, index++)
6924 {
6925 tmp2= mod (j.getItem(), y);
6926 tmp2 /= Lc (tmp2);
6927 if (tmp1 == tmp2)
6928 {
6929 index++;
6930 j.remove(index);
6931 break;
6932 }
6933 }
6934 }
6935
6936 if (bufUniFactors.isEmpty())
6937 {
6938 delete [] bounds;
6939 return smallFactors;
6940 }
6941
6942 if (success)
6943 {
6944 F= H;
6945 delete [] bounds;
6947 if (isIrreducible)
6948 {
6949 smallFactors.append (F (y-eval,y));
6950 delete [] bounds;
6951 return smallFactors;
6952 }
6953 LCF= LC (F, 1);
6954
6955 minBound= bounds[0];
6956 for (int i= 1; i < d; i++)
6957 {
6958 if (bounds[i] != 0)
6960 }
6961 Pi= CFArray();
6962 diophant= CFList();
6963 liftBound= 2*totaldegree (F) - 1;
6966 degs.intersect (bufDegs);
6967 degs.refine();
6968 if (degs.getLength() <= 1)
6969 {
6970 smallFactors.append (F (y-eval,y));
6971 delete [] bounds;
6972 return smallFactors;
6973 }
6974 }
6975
6976 bool reduceFq2Fp= (degree (F) > getCharacteristic());
6978 int l= 1;
6979
6980#ifdef HAVE_FLINT
6982#endif
6983
6985 {
6987 zz_p::init (getCharacteristic());
6988 }
6989 mat_zz_p NTLN;
6990
6991 if (alpha.level() != 1)
6992 {
6994 zz_pE::init (NTLMipo);
6995 }
6997
6998 if (alpha.level() == 1)
6999 {
7000#ifdef HAVE_FLINT
7002 for (long i= bufUniFactors.length()-2; i >= 0; i--)
7003 nmod_mat_entry (FLINTN, i, i)= 1;
7004#else
7005 ident (NTLN, bufUniFactors.length() - 1);
7006#endif
7007 }
7008 else
7009 {
7010 if (reduceFq2Fp)
7011#ifdef HAVE_FLINT
7012 {
7014 for (long i= bufUniFactors.length()-2; i >= 0; i--)
7015 nmod_mat_entry (FLINTN, i, i)= 1;
7016 }
7017#else
7018 ident (NTLN, bufUniFactors.length() - 1);
7019#endif
7020 else
7022 }
7023 bool irreducible= false;
7025
7026 int oldL;
7028 if (success)
7029 {
7030 int start= 0;
7031 if (alpha.level() == 1)
7035#else
7037#endif
7039 );
7040 else
7041 {
7042 if (reduceFq2Fp)
7046#else
7048#endif
7050 alpha
7051 );
7052 else
7056 );
7057 }
7058 }
7059 else
7060 {
7061 if (alpha.level() == 1)
7062 {
7066#else
7068#endif
7070 );
7071 }
7072 else
7073 {
7074 if (reduceFq2Fp)
7078 FLINTN, diophant, M, Pi, bufQ,
7079#else
7080 NTLN, diophant, M, Pi, bufQ,
7081#endif
7083 );
7084 else
7087 M, Pi, bufQ, irreducible
7088 );
7089 }
7090 }
7091
7093 "time to compute a reduced lattice: ");
7095 if (oldL > liftBound)
7096 {
7097#ifdef HAVE_FLINT
7098 if (alpha.level() == 1 || (alpha.level() != 1 && reduceFq2Fp))
7100#endif
7101 delete [] bounds;
7102 return Union (smallFactors,
7104 power (y, degree (F) + 1),
7105 degs, eval, 1, bufUniFactors.length()/2
7106 )
7107 );
7108 }
7109
7110 l= oldL;
7111 if (irreducible)
7112 {
7113#ifdef HAVE_FLINT
7114 if (alpha.level() == 1 || (alpha.level() != 1 && reduceFq2Fp))
7116#endif
7117 delete [] bounds;
7118 return Union (CFList (F(y-eval,y)), smallFactors);
7119 }
7120
7122
7123 CFList result;
7124 if (l >= degree (F) + 1)
7125 {
7126 int * factorsFoundIndex;
7127 if (alpha.level() == 1 || (alpha.level() != 1 && reduceFq2Fp))
7128 {
7129#ifdef HAVE_FLINT
7131 for (long i= 0; i < nmod_mat_ncols (FLINTN); i++)
7132#else
7133 factorsFoundIndex= new int [NTLN.NumCols()];
7134 for (long i= 0; i < NTLN.NumCols(); i++)
7135#endif
7136 factorsFoundIndex[i]= 0;
7137 }
7138 else
7139 {
7140 factorsFoundIndex= new int [NTLNe.NumCols()];
7141 for (long i= 0; i < NTLNe.NumCols(); i++)
7142 factorsFoundIndex[i]= 0;
7143 }
7144 int factorsFound= 0;
7146 if (alpha.level() == 1 || (alpha.level() != 1 && reduceFq2Fp))
7150#else
7152#endif
7153 );
7154 else
7157 );
7158 if (alpha.level() == 1 || (alpha.level() != 1 && reduceFq2Fp))
7159 {
7160#ifdef HAVE_FLINT
7161 if (result.length() == nmod_mat_ncols (FLINTN))
7162 {
7163 if (alpha.level() == 1 || (alpha.level() != 1 && reduceFq2Fp))
7165#else
7166 if (result.length() == NTLN.NumCols())
7167 {
7168#endif
7169 delete [] factorsFoundIndex;
7170 delete [] bounds;
7171 return Union (result, smallFactors);
7172 }
7173 }
7174 else
7175 {
7176 if (result.length() == NTLNe.NumCols())
7177 {
7178 delete [] factorsFoundIndex;
7179 delete [] bounds;
7180 return Union (result, smallFactors);
7181 }
7182 }
7183 delete [] factorsFoundIndex;
7184 }
7185 if (l >= liftBound)
7186 {
7187 int * factorsFoundIndex;
7188 if (alpha.level() == 1 || (alpha.level() != 1 && reduceFq2Fp))
7189 {
7190#ifdef HAVE_FLINT
7192 for (long i= 0; i < nmod_mat_ncols (FLINTN); i++)
7193#else
7194 factorsFoundIndex= new int [NTLN.NumCols()];
7195 for (long i= 0; i < NTLN.NumCols(); i++)
7196#endif
7197 factorsFoundIndex[i]= 0;
7198 }
7199 else
7200 {
7201 factorsFoundIndex= new int [NTLNe.NumCols()];
7202 for (long i= 0; i < NTLNe.NumCols(); i++)
7203 factorsFoundIndex[i]= 0;
7204 }
7206 int factorsFound= 0;
7207 if (alpha.level() == 1 || (alpha.level() != 1 && reduceFq2Fp))
7211#else
7213#endif
7214 );
7215 else
7218 );
7219 if (alpha.level() == 1 || (alpha.level() != 1 && reduceFq2Fp))
7220 {
7221#ifdef HAVE_FLINT
7222 if (result.length() == nmod_mat_ncols(FLINTN))
7223 {
7225#else
7226 if (result.length() == NTLN.NumCols())
7227 {
7228#endif
7229 delete [] factorsFoundIndex;
7230 delete [] bounds;
7231 return Union (result, smallFactors);
7232 }
7233 }
7234 else
7235 {
7236 if (result.length() == NTLNe.NumCols())
7237 {
7238 delete [] factorsFoundIndex;
7239 delete [] bounds;
7240 return Union (result, smallFactors);
7241 }
7242 }
7243 delete [] factorsFoundIndex;
7244 }
7245
7246 result= CFList();
7247 bool beenInThres= false;
7248 int thres= 100;
7249 if (l <= thres)
7250 {
7251 if (alpha.level() == 1 || (alpha.level() != 1 && reduceFq2Fp))
7252 {
7253#ifdef HAVE_FLINT
7255 {
7257#else
7258 if (NTLN.NumCols() < bufUniFactors.length())
7259 {
7260 refineAndRestartLift (F, NTLN, liftBound, l, bufUniFactors, M, Pi,
7261#endif
7262 diophant
7263 );
7264 beenInThres= true;
7265 }
7266 }
7267 else
7268 {
7269 if (NTLNe.NumCols() < bufUniFactors.length())
7270 {
7271 refineAndRestartLift (F, NTLNe, liftBound, l, bufUniFactors, M, Pi,
7272 diophant
7273 );
7274 beenInThres= true;
7275 }
7276 }
7277 }
7278
7280 int factorsFound= 0;
7281 if (alpha.level() == 1 || (alpha.level() != 1 && reduceFq2Fp))
7282 {
7283#ifdef HAVE_FLINT
7284 result= earlyReconstructionAndLifting (F, FLINTN, bufF, bufUniFactors, l,
7285#else
7286 result= earlyReconstructionAndLifting (F, NTLN, bufF, bufUniFactors, l,
7287#endif
7288 factorsFound, beenInThres, M, Pi,
7289 diophant, symmetric, eval
7290 );
7291
7292#ifdef HAVE_FLINT
7293 if (result.length() == nmod_mat_ncols (FLINTN))
7294 {
7295 nmod_mat_clear (FLINTN);
7296#else
7297 if (result.length() == NTLN.NumCols())
7298 {
7299#endif
7300 delete [] bounds;
7301 return Union (result, smallFactors);
7302 }
7303 }
7304 else
7305 {
7306 result= earlyReconstructionAndLifting (F, NTLNe, bufF, bufUniFactors, l,
7307 factorsFound, beenInThres, M, Pi,
7308 diophant, symmetric, eval
7309 );
7310
7311 if (result.length() == NTLNe.NumCols())
7312 {
7313 delete [] bounds;
7314 return Union (result, smallFactors);
7315 }
7316 }
7317
7318 if (result.length() > 0)
7319 {
7320 if (beenInThres)
7321 {
7322 int index;
7323 for (CFListIterator i= result; i.hasItem(); i++)
7324 {
7325 index= 1;
7326 tmp1= mod (i.getItem(), y-eval);
7327 tmp1 /= Lc (tmp1);
7328 for (CFListIterator j= bufUniFactors; j.hasItem(); j++, index++)
7329 {
7330 tmp2= mod (j.getItem(), y);
7331 tmp2 /= Lc (tmp2);
7332 if (tmp1 == tmp2)
7333 {
7334 index++;
7335 j.remove(index);
7336 break;
7337 }
7338 }
7339 }
7340 }
7341 else
7342 {
7343 int * zeroOne;
7344 long numCols, numRows;
7345 if (alpha.level() == 1 || (alpha.level() != 1 && reduceFq2Fp))
7346 {
7347#ifdef HAVE_FLINT
7348 numCols= nmod_mat_ncols (FLINTN);
7349 numRows= nmod_mat_nrows (FLINTN);
7350 zeroOne= extractZeroOneVecs (FLINTN);
7351#else
7352 numCols= NTLN.NumCols();
7353 numRows= NTLN.NumRows();
7354 zeroOne= extractZeroOneVecs (NTLN);
7355#endif
7356 }
7357 else
7358 {
7359 numCols= NTLNe.NumCols();
7360 numRows= NTLNe.NumRows();
7361 zeroOne= extractZeroOneVecs (NTLNe);
7362 }
7368 for (int i= 0; i < numCols; i++)
7369 {
7370 if (zeroOne [i] == 0)
7371 continue;
7373 buf= 1;
7375 for (int j= 0; j < numRows; j++, iter++)
7376 {
7377 if (alpha.level() == 1 || (alpha.level() != 1 && reduceFq2Fp))
7378 {
7379#ifdef HAVE_FLINT
7380 if (!(nmod_mat_entry (FLINTN, j,i) == 0))
7381#else
7382 if (!IsZero (NTLN (j + 1,i + 1)))
7383#endif
7384 {
7385 factorsConsidered.append (iter.getItem());
7386 buf *= mod (iter.getItem(), y);
7387 }
7388 }
7389 else
7390 {
7391 if (!IsZero (NTLNe (j + 1,i + 1)))
7392 {
7393 factorsConsidered.append (iter.getItem());
7394 buf *= mod (iter.getItem(), y);
7395 }
7396 }
7397 }
7398 buf /= Lc (buf);
7399 for (iter2= result; iter2.hasItem(); iter2++)
7400 {
7401 tmp= mod (iter2.getItem(), y-eval);
7402 tmp /= Lc (tmp);
7403 if (tmp == buf)
7404 {
7406 break;
7407 }
7408 }
7409 }
7411 delete [] zeroOne;
7412 }
7413
7414 int oldNumCols;
7416 irreducible= false;
7417
7418 if (alpha.level() == 1)
7419 {
7420#ifdef HAVE_FLINT
7422#else
7423 oldNumCols= NTLN.NumCols();
7424#endif
7427 );
7428 }
7429 else
7430 {
7431 if (reduceFq2Fp)
7432 {
7433#ifdef HAVE_FLINT
7435#else
7436 oldNumCols= NTLN.NumCols();
7437#endif
7438
7441 );
7442 }
7443 else
7444 {
7445 oldNumCols= NTLNe.NumCols();
7446
7449 );
7450 }
7451 }
7452
7453 if (bufUniFactors.isEmpty() || degree (bufF) <= 0)
7454 {
7455#ifdef HAVE_FLINT
7456 if (alpha.level() == 1 || (alpha.level() != 1 && reduceFq2Fp))
7458#endif
7459 delete [] bounds;
7461 return Union (result, smallFactors);
7462 }
7463
7465 i.getItem()= mod (i.getItem(), y);
7466
7469 delete [] bounds;
7471 degs.intersect (bufDegs);
7472 degs.refine();
7473 if (degs.getLength() == 1 || bufUniFactors.length() == 1)
7474 {
7475#ifdef HAVE_FLINT
7476 if (alpha.level() == 1 || (alpha.level() != 1 && reduceFq2Fp))
7478#endif
7479 result.append (bufF (y-eval,y));
7480 return result;
7481 }
7482#ifdef HAVE_FLINT
7483 if (alpha.level() == 1 || (alpha.level() != 1 && reduceFq2Fp))
7485#endif
7488 eval
7489 )
7490 );
7491 }
7492
7493 if (l < liftBound)
7494 {
7495 if (alpha.level() == 1)
7496 {
7499 FLINTN, eval
7500#else
7501 NTLN, eval
7502#endif
7503 );
7504 }
7505 else
7506 {
7507 if (reduceFq2Fp)
7508 {
7512#else
7513 bufQ, NTLN, alpha, eval
7514#endif
7515 );
7516 }
7517 else
7518 {
7520 NTLNe, eval
7521 );
7522 }
7523 }
7524 if (alpha.level() == 1 || (alpha.level() != 1 && reduceFq2Fp))
7525 {
7526#ifdef HAVE_FLINT
7527 if (result.length()== nmod_mat_ncols (FLINTN))
7528 {
7530#else
7531 if (result.length()== NTLN.NumCols())
7532 {
7533#endif
7534 delete [] bounds;
7536 return result;
7537 }
7538 }
7539 else
7540 {
7541 if (result.length()== NTLNe.NumCols())
7542 {
7543 delete [] bounds;
7545 return result;
7546 }
7547 }
7548
7549 if (result.isEmpty())
7550 {
7551 if (alpha.level() == 1)
7555#else
7556 liftBound, d, bounds, NTLN,
7557#endif
7558 diophant, M, Pi, bufQ, eval
7559 );
7560 else
7561 {
7562 if (reduceFq2Fp)
7564 liftBound, d, bounds,
7566 FLINTN, diophant, M,
7567#else
7568 NTLN, diophant, M,
7569#endif
7570 Pi, bufQ, alpha, eval
7571 );
7572 else
7574 liftBound, d, bounds,
7575 NTLNe, diophant, M,
7576 Pi, bufQ, eval
7577 );
7578 }
7579
7580 if (alpha.level() == 1 || (alpha.level() != 1 && reduceFq2Fp))
7581 {
7582#ifdef HAVE_FLINT
7583 if (result.length() == nmod_mat_ncols (FLINTN))
7584 {
7586#else
7587 if (result.length() == NTLN.NumCols())
7588 {
7589#endif
7590 delete [] bounds;
7592 return result;
7593 }
7594 }
7595 else
7596 {
7597 if (result.length() == NTLNe.NumCols())
7598 {
7599 delete [] bounds;
7601 return result;
7602 }
7603 }
7604 }
7605 }
7606
7607 DEBOUTLN (cerr, "lattice recombination failed");
7608
7610 degs.intersect (bufDegs);
7611 degs.refine();
7612
7613 delete [] bounds;
7615#ifdef HAVE_FLINT
7616 if (alpha.level() == 1 || (alpha.level() != 1 && reduceFq2Fp))
7618#endif
7619 if (isIrreducible)
7620 {
7621 delete [] bounds;
7623 result.append (F (y-eval,y));
7624 return result;
7625 }
7626 minBound= bounds[0];
7627 for (int i= 1; i < d; i++)
7628 {
7629 if (bounds[i] != 0)
7631 }
7632
7633 if (minBound > 16 || result.length() == 0)
7634 {
7636 CanonicalForm MODl= power (y, degree (F) + 1);
7637 delete [] bounds;
7639 eval, 1, bufUniFactors.length()/2
7640 )
7641 );
7642 }
7643 else
7644 {
7647 i.getItem()= mod (i.getItem(), y);
7648 delete [] bounds;
7651 )
7652 );
7653 }
7654}
7655#endif
7656
7657#ifdef HAVE_NTL // findMinPoly
7660 int& degMipo
7661 )
7662{
7664 Variable alpha= info.getAlpha();
7665 if (GF)
7666 {
7670 GFMipo.mapinto();
7671 alpha= rootOf (GFMipo);
7673 }
7674 else
7675 {
7676 alpha= info.getAlpha();
7678 }
7679
7682 if ((!GF && evaluation != alpha) || (GF && evaluation != getGFGenerator()))
7683 {
7685 if (GF)
7686 {
7689 }
7690 else
7693 gamma= rootOf (mipo);
7695 bool fail= false;
7698
7699 if (GF)
7701 }
7702 else
7703 gamma= alpha;
7705 imPrimElemAlpha, 1, info.getGFName(), true
7706 );
7707
7708 return info2;
7709}
7710#endif
7711
7712#ifdef HAVE_NTL // extSieveSmallFactors,...
7713CFList
7715 const ExtensionInfo& extInfo, const
7717 )
7718{
7723 CanonicalForm F= G;
7724 Variable x= Variable (1);
7725 Variable y= F.mvar();
7727
7728
7729 int degMipo;
7731
7732 CFList source, dest;
7733 CanonicalForm LCF= LC (F, 1);
7734
7735 int d;
7736 bool isIrreducible= false;
7737 int* bounds= computeBounds (F, d, isIrreducible);
7738 if (isIrreducible)
7739 {
7740 delete [] bounds;
7741 CFList source, dest;
7743 tmp= mapDown (tmp, info, source, dest);
7744 return CFList (tmp);
7745 }
7746 int minBound= bounds[0];
7747 for (int i= 1; i < d; i++)
7748 {
7749 if (bounds[i] != 0)
7751 }
7752
7753
7754 CFArray Pi;
7756 int liftBound= tmax ((2*totaldegree (F) - 1)/degMipo + 1, degree (F) + 1 +
7757 degree (LC (F, 1)));
7759
7762 bool success= false;
7764 M, success, minBound + 1, evaluation, info
7765 );
7766
7767 if (smallFactors.length() > 0)
7768 {
7769 if (smallFactors.length() == 1)
7770 {
7771 if (smallFactors.getFirst() == F)
7772 {
7773 delete [] bounds;
7774 CFList source, dest;
7776 tmp= mapDown (tmp, info, source, dest);
7777 return CFList (tmp);
7778 }
7779 }
7780 if (degs.getLength() <= 1)
7781 {
7782 delete [] bounds;
7783 return smallFactors;
7784 }
7785 }
7786
7787 int index;
7789 for (CFListIterator i= smallFactors; i.hasItem(); i++)
7790 {
7791 index= 1;
7792 tmp1= mod (i.getItem(), y - evaluation);
7793 tmp1 /= Lc (tmp1);
7794 for (CFListIterator j= bufUniFactors; j.hasItem(); j++, index++)
7795 {
7796 tmp2= mod (j.getItem(), y);
7797 tmp2 /= Lc (tmp2);
7798 if (tmp1 == tmp2)
7799 {
7800 index++;
7801 j.remove(index);
7802 break;
7803 }
7804 }
7805 }
7806
7807 if (bufUniFactors.isEmpty())
7808 {
7809 delete [] bounds;
7810 return smallFactors;
7811 }
7812
7813 if (success)
7814 {
7815 F= H/Lc(H);
7816 delete [] bounds;
7818 if (isIrreducible)
7819 {
7820 delete [] bounds;
7821 CFList source, dest;
7822 CanonicalForm tmp= F (y - evaluation, y);
7823 tmp= mapDown (tmp, info, source, dest);
7825 return smallFactors;
7826 }
7827 LCF= LC (F, 1);
7828
7829 minBound= bounds[0];
7830 for (int i= 1; i < d; i++)
7831 {
7832 if (bounds[i] != 0)
7834 }
7835 Pi= CFArray();
7836 diophant= CFList();
7837 liftBound=tmax ((2*totaldegree (F) - 1)/degMipo + 1, degree (F) + 1 +
7838 degree (LC (F, 1)));
7841 degs.intersect (bufDegs);
7842 degs.refine();
7843 if (degs.getLength() <= 1)
7844 {
7845 delete [] bounds;
7846 CFList source, dest;
7847 CanonicalForm tmp= F (y - evaluation, y);
7848 tmp= mapDown (tmp, info, source, dest);
7850 return smallFactors;
7851 }
7852 }
7853
7855 int l= 1;
7856
7857#ifdef HAVE_FLINT
7861 for (long i= bufUniFactors.length()-2; i >= 0; i--)
7862 nmod_mat_entry (FLINTN, i, i)= 1;
7863#else
7865 {
7867 zz_p::init (getCharacteristic());
7868 }
7869 zz_pX NTLMipo;
7870 mat_zz_p NTLN;
7871
7872 ident (NTLN, bufUniFactors.length() - 1);
7873#endif
7874 bool irreducible= false;
7876
7877 int oldL;
7879 if (success)
7880 {
7881 int start= 0;
7882#ifdef HAVE_FLINT
7886 );
7887#else
7891 );
7892#endif
7893 }
7894 else
7895 {
7896#ifdef HAVE_FLINT
7900 source, dest
7901 );
7902#else
7906 source, dest
7907 );
7908#endif
7909 }
7911 "time to compute a reduced lattice: ");
7912
7914 if (oldL > liftBound)
7915 {
7916#ifdef HAVE_FLINT
7918#endif
7919 delete [] bounds;
7921 (bufUniFactors, F,
7922 power (y, degree (F) + 1),info,
7924 )
7925 );
7926 }
7927
7928 l= oldL;
7929 if (irreducible)
7930 {
7931#ifdef HAVE_FLINT
7933#endif
7934 delete [] bounds;
7935 CFList source, dest;
7936 CanonicalForm tmp= F (y - evaluation, y);
7937 tmp= mapDown (tmp, info, source, dest);
7938 return Union (CFList (tmp), smallFactors);
7939 }
7940
7942
7943 CFList result;
7944 if (l >= degree (F) + 1)
7945 {
7946 int * factorsFoundIndex;
7947
7948#ifdef HAVE_FLINT
7950 for (long i= 0; i < nmod_mat_ncols (FLINTN); i++)
7951#else
7952 factorsFoundIndex= new int [NTLN.NumCols()];
7953 for (long i= 0; i < NTLN.NumCols(); i++)
7954#endif
7955 factorsFoundIndex[i]= 0;
7956
7957 int factorsFound= 0;
7959
7960#ifdef HAVE_FLINT
7964 );
7965
7966 if (result.length() == nmod_mat_ncols (FLINTN))
7967 {
7969#else
7973 );
7974
7975 if (result.length() == NTLN.NumCols())
7976 {
7977#endif
7978 delete [] factorsFoundIndex;
7979 delete [] bounds;
7980 return Union (result, smallFactors);
7981 }
7982
7983 delete [] factorsFoundIndex;
7984 }
7985 if (l >= liftBound)
7986 {
7987 int * factorsFoundIndex;
7988#ifdef HAVE_FLINT
7990 for (long i= 0; i < nmod_mat_ncols (FLINTN); i++)
7991#else
7992 factorsFoundIndex= new int [NTLN.NumCols()];
7993 for (long i= 0; i < NTLN.NumCols(); i++)
7994#endif
7995 factorsFoundIndex[i]= 0;
7997 int factorsFound= 0;
7998
7999#ifdef HAVE_FLINT
8003 );
8004
8005 if (result.length() == nmod_mat_ncols (FLINTN))
8006 {
8008#else
8012 );
8013
8014 if (result.length() == NTLN.NumCols())
8015 {
8016#endif
8017 delete [] factorsFoundIndex;
8018 delete [] bounds;
8019 return Union (result, smallFactors);
8020 }
8021 delete [] factorsFoundIndex;
8022 }
8023
8024 result= CFList();
8025 bool beenInThres= false;
8026 int thres= 100;
8027#ifdef HAVE_FLINT
8029 {
8031 diophant
8032 );
8033#else
8034 if (l <= thres && bufUniFactors.length() > NTLN.NumCols())
8035 {
8037 diophant
8038 );
8039#endif
8040 beenInThres= true;
8041 }
8042
8043
8045 int factorsFound= 0;
8046
8047#ifdef HAVE_FLINT
8051 );
8052
8053 if (result.length() == nmod_mat_ncols (FLINTN))
8054 {
8056#else
8060 );
8061
8062 if (result.length() == NTLN.NumCols())
8063 {
8064#endif
8065 delete [] bounds;
8066 return Union (result, smallFactors);
8067 }
8068
8069 if (result.length() > 0)
8070 {
8071 if (beenInThres)
8072 {
8073 int index;
8074 for (CFListIterator i= result; i.hasItem(); i++)
8075 {
8076 index= 1;
8077 tmp1= mod (i.getItem(), y-evaluation);
8078 tmp1 /= Lc (tmp1);
8079 for (CFListIterator j= bufUniFactors; j.hasItem(); j++, index++)
8080 {
8081 tmp2= mod (j.getItem(), y);
8082 tmp2 /= Lc (tmp2);
8083 if (tmp1 == tmp2)
8084 {
8085 index++;
8086 j.remove(index);
8087 break;
8088 }
8089 }
8090 }
8091 }
8092 else
8093 {
8094#ifdef HAVE_FLINT
8096#else
8098#endif
8103#ifdef HAVE_FLINT
8104 for (int i= 0; i < nmod_mat_ncols (FLINTN); i++)
8105#else
8106 for (int i= 0; i < NTLN.NumCols(); i++)
8107#endif
8108 {
8109 if (zeroOne [i] == 0)
8110 continue;
8112 buf= 1;
8114#ifdef HAVE_FLINT
8115 for (int j= 0; j < nmod_mat_nrows (FLINTN); j++, iter++)
8116 {
8117 if (!(nmod_mat_entry (FLINTN, j, i) == 0))
8118#else
8119 for (int j= 0; j < NTLN.NumRows(); j++, iter++)
8120 {
8121 if (!IsZero (NTLN (j + 1,i + 1)))
8122#endif
8123 {
8124 factorsConsidered.append (iter.getItem());
8125 buf *= mod (iter.getItem(), y);
8126 }
8127 }
8128 buf /= Lc (buf);
8129 for (iter2= result; iter2.hasItem(); iter2++)
8130 {
8131 CanonicalForm tmp= mod (iter2.getItem(), y - evaluation);
8132 tmp /= Lc (tmp);
8133 if (tmp == buf)
8134 {
8136 break;
8137 }
8138 }
8139 }
8141 delete [] zeroOne;
8142 }
8143
8144 int oldNumCols;
8146 irreducible= false;
8147
8148#ifdef HAVE_FLINT //TODO
8152 source, dest, l
8153 );
8155#else
8156 oldNumCols= NTLN.NumCols();
8159 source, dest, l
8160 );
8161#endif
8162 if (bufUniFactors.isEmpty() || degree (bufF) <= 0)
8163 {
8164 delete [] bounds;
8166 return Union (result, smallFactors);
8167 }
8168
8170 i.getItem()= mod (i.getItem(), y);
8171
8172 delete [] bounds;
8175 degs.intersect (bufDegs);
8176 degs.refine();
8178 if (degs.getLength() == 1 || bufUniFactors.length() == 1)
8179 {
8180 CFList source, dest;
8182 tmp= mapDown (tmp, info, source, dest);
8183 result.append (tmp);
8184 return result;
8185 }
8188 )
8189 );
8190 }
8191
8192 if (l/degMipo < liftBound)
8193 {
8194#ifdef HAVE_FLINT
8196 FLINTN, evaluation, info2, source, dest
8197 );
8198
8199 if (result.length()== nmod_mat_ncols (FLINTN))
8200 {
8202#else
8204 NTLN, evaluation, info2, source, dest
8205 );
8206
8207 if (result.length()== NTLN.NumCols())
8208 {
8209#endif
8210 delete [] bounds;
8212 return result;
8213 }
8214
8215 if (result.isEmpty())
8216 {
8217#ifdef HAVE_FLINT
8220 diophant, M, Pi, bufQ,
8222 dest
8223 );
8224 if (result.length()== nmod_mat_ncols (FLINTN))
8225 {
8227#else
8229 liftBound, d, bounds, NTLN,
8230 diophant, M, Pi, bufQ,
8232 dest
8233 );
8234 if (result.length()== NTLN.NumCols())
8235 {
8236#endif
8237 delete [] bounds;
8239 return result;
8240 }
8241 }
8242 }
8243
8244#ifdef HAVE_FLINT
8246#endif
8247
8248 DEBOUTLN (cerr, "lattice recombination failed");
8249
8251 degs.intersect (bufDegs);
8252 degs.refine();
8253
8254 delete [] bounds;
8256 if (isIrreducible)
8257 {
8258 delete [] bounds;
8259 CFList source, dest;
8260 CanonicalForm tmp= F (y - evaluation, y);
8261 tmp= mapDown (tmp, info, source, dest);
8264 return result;
8265 }
8266 minBound= bounds[0];
8267 for (int i= 1; i < d; i++)
8268 {
8269 if (bounds[i] != 0)
8271 }
8272
8273 if (minBound > 16 || result.length() == 0)
8274 {
8276 CanonicalForm MODl= power (y, degree (F) + 1);
8277 delete [] bounds;
8279 degs, evaluation, 1,
8281 )
8282 );
8283 }
8284 else
8285 {
8288 i.getItem()= mod (i.getItem(), y);
8289 delete [] bounds;
8292 )
8293 );
8294 }
8295}
8296#endif
8297
8298#ifdef HAVE_NTL // henselLiftAndLatticeRecombi
8299CFList
8301
8302/// bivariate factorization over finite fields as decribed in "Factoring
8303/// multivariate polynomials over a finite field" by L Bernardin.
8304CFList
8306{
8307 if (F.inCoeffDomain())
8308 return CFList(F);
8309
8310 CanonicalForm A= F;
8312
8313 Variable alpha= info.getAlpha();
8314 Variable beta= info.getBeta();
8315 CanonicalForm gamma= info.getGamma();
8316 CanonicalForm delta= info.getDelta();
8317 int k= info.getGFDegree();
8318 bool extension= info.isInExtension();
8319 if (A.isUnivariate())
8320 {
8321 if (extension == false)
8322 return uniFactorizer (F, alpha, GF);
8323 else
8324 {
8325 CFList source, dest;
8326 A= mapDown (A, info, source, dest);
8327 return uniFactorizer (A, beta, GF);
8328 }
8329 }
8330
8331 CFMap N;
8332 A= compress (A, N);
8333 Variable y= A.mvar();
8334
8335 if (y.level() > 2) return CFList (F);
8336 Variable x= Variable (1);
8337
8338 //remove and factorize content
8341
8344
8345 if (!extension)
8346 {
8349 }
8350
8351 //trivial case
8353 if (A.inCoeffDomain())
8354 {
8357 decompress (factors, N);
8358 return factors;
8359 }
8360 else if (A.isUnivariate())
8361 {
8365 decompress (factors, N);
8366 return factors;
8367 }
8368
8369
8370 //check trivial case
8371 if (degree (A) == 1 || degree (A, 1) == 1 ||
8372 (size (A) == 2 && igcd (degree (A), degree (A,1))==1))
8373 {
8374 factors.append (A);
8375
8377 false, false, N);
8378
8379 if (!extension)
8381 return factors;
8382 }
8383
8384 // check derivatives
8385 bool derivXZero= false;
8388 if (derivX.isZero())
8389 derivXZero= true;
8390 else
8391 {
8392 gcdDerivX= gcd (A, derivX);
8393 if (degree (gcdDerivX) > 0)
8394 {
8401 if (!extension)
8403 return factorsG;
8404 }
8405 }
8406 bool derivYZero= false;
8409 if (derivY.isZero())
8410 derivYZero= true;
8411 else
8412 {
8413 gcdDerivY= gcd (A, derivY);
8414 if (degree (gcdDerivY) > 0)
8415 {
8422 if (!extension)
8424 return factorsG;
8425 }
8426 }
8427 //main variable is chosen s.t. the degree in x is minimal
8428 bool swap= false;
8429 if ((degree (A) > degree (A, x)) || derivXZero)
8430 {
8431 if (!derivYZero)
8432 {
8433 A= swapvar (A, y, x);
8437 swap= true;
8438 }
8439 }
8440
8441 int boundsLength;
8442 bool isIrreducible= false;
8444 if (isIrreducible)
8445 {
8446 delete [] bounds;
8447 factors.append (A);
8448
8450 swap, false, N);
8451
8452 if (!extension)
8454 return factors;
8455 }
8456
8457 int minBound= bounds[0];
8458 for (int i= 1; i < boundsLength; i++)
8459 {
8460 if (bounds[i] != 0)
8462 }
8463
8464 int boundsLength2;
8466 int minBound2= bounds2[0];
8467 for (int i= 1; i < boundsLength2; i++)
8468 {
8469 if (bounds2[i] != 0)
8471 }
8472
8473
8474 bool fail= false;
8479
8480 bool fail2= false;
8485 bool swap2= false;
8486
8487 // several univariate factorizations to obtain more information about the
8488 // degree pattern therefore usually less combinations have to be tried during
8489 // the recombination process
8490 int factorNums= 3;
8491 int subCheck1= substituteCheck (A, x);
8492 int subCheck2= substituteCheck (A, y);
8493 bool symmetric= false;
8494
8496 for (int i= 0; i < factorNums; i++)
8497 {
8498 bufAeval= A;
8501 TIMING_END_AND_PRINT (fac_fq_bi_evaluation, "time to find eval point: ");
8502 if (!derivXZero && !fail2 && !symmetric)
8503 {
8504 if (i == 0)
8505 {
8506 buf= swapvar (A, x, y);
8507 symmetric= (A/Lc (A) == buf/Lc (buf));
8508 }
8509 bufAeval2= buf;
8513 "time to find eval point wrt y: ");
8514 }
8515 // first try to change main variable if there is no valid evaluation point
8516 if (fail && (i == 0))
8517 {
8518 if (!derivXZero && !fail2 && !symmetric)
8519 {
8521 int dummy= subCheck2;
8524 tmp= A;
8525 A= buf;
8526 buf= tmp;
8528 swap2= true;
8529 fail= false;
8530 }
8531 else
8532 fail= true;
8533 }
8534
8535 // if there is no valid evaluation point pass to a field extension
8536 if (fail && (i == 0))
8537 {
8540 swap, swap2, N);
8542 delete [] bounds;
8543 delete [] bounds2;
8544 return factors;
8545 }
8546
8547 // there is at least one valid evaluation point
8548 // but we do not compute more univariate factorization over an extension
8549 if (fail && (i != 0))
8550 break;
8551
8552 // univariate factorization
8556 "time for univariate factorization over Fq: ");
8557 DEBOUTLN (cerr, "Lc (bufAeval)*prod (bufUniFactors)== bufAeval " <<
8559
8560 if (!derivXZero && !fail2 && !symmetric)
8561 {
8565 "time for univariate factorization in y over Fq: ");
8566 DEBOUTLN (cerr, "Lc (bufAeval2)*prod (bufUniFactors2)== bufAeval2 " <<
8568 }
8569
8570 if (bufUniFactors.length() == 1 ||
8571 (!fail2 && !derivXZero && !symmetric && (bufUniFactors2.length() == 1)))
8572 {
8573 if (extension)
8574 {
8575 CFList source, dest;
8576 appendMapDown (factors, A, info, source, dest);
8577 }
8578 else
8579 factors.append (A);
8580
8582 swap, swap2, N);
8583
8584 if (!extension)
8586 delete [] bounds;
8587 delete [] bounds2;
8588 return factors;
8589 }
8590
8591 if (i == 0 && !extension)
8592 {
8593 if (subCheck1 > 0)
8594 {
8596
8597 if (subCheck > 1 && (subCheck1%subCheck == 0))
8598 {
8600 subst (bufA, bufA, subCheck, x);
8604 swap, swap2, N);
8605 if (!extension)
8607 delete [] bounds;
8608 delete [] bounds2;
8609 return factors;
8610 }
8611 }
8612
8613 if (!derivXZero && !fail2 && !symmetric && subCheck2 > 0)
8614 {
8616
8617 if (subCheck > 1 && (subCheck2%subCheck == 0))
8618 {
8620 subst (bufA, bufA, subCheck, y);
8624 swap, swap2, N);
8625 if (!extension)
8627 delete [] bounds;
8628 delete [] bounds2;
8629 return factors;
8630 }
8631 }
8632 }
8633
8634 // degree analysis
8636 if (!derivXZero && !fail2 && !symmetric)
8638
8639 if (i == 0)
8640 {
8641 Aeval= bufAeval;
8644 degs= bufDegs;
8645 if (!derivXZero && !fail2 && !symmetric)
8646 {
8650 degs2= bufDegs2;
8651 }
8652 }
8653 else
8654 {
8655 degs.intersect (bufDegs);
8656 if (!derivXZero && !fail2 && !symmetric)
8657 {
8658 degs2.intersect (bufDegs2);
8660 {
8664 }
8665 }
8667 {
8669 Aeval= bufAeval;
8671 }
8672 }
8673 list.append (bufEvaluation);
8674 if (!derivXZero && !fail2 && !symmetric)
8676 }
8678 "total time for univariate factorizations: ");
8679
8680 if (!derivXZero && !fail2 && !symmetric)
8681 {
8684 && degs.getLength() > degs2.getLength() && minBound2 <= minBound))
8685 {
8686 degs= degs2;
8689 Aeval= Aeval2;
8690 A= buf;
8691 swap2= true;
8692 }
8693 }
8694
8695 if (degs.getLength() == 1) // A is irreducible
8696 {
8697 if (extension)
8698 {
8699 CFList source, dest;
8700 appendMapDown (factors, A, info, source, dest);
8701 }
8702 else
8703 factors.append (A);
8705 swap, swap2, N);
8706 if (!extension)
8708 delete [] bounds;
8709 delete [] bounds2;
8710 return factors;
8711 }
8712
8713 int liftBound= degree (A, y) + 1;
8714
8715 if (swap2)
8716 {
8717 delete [] bounds;
8718 bounds= bounds2;
8720 }
8721
8723 A= A (y + evaluation, y);
8725 "time to shift eval to zero: ");
8726
8727 int degMipo= 1;
8728 if (extension && alpha.level() != 1 && k==1)
8730
8731 DEBOUTLN (cerr, "uniFactors= " << uniFactors);
8732
8733 if ((GF && !extension) || (GF && extension && k != 1))
8734 {
8735 bool earlySuccess= false;
8742 "time for bivariate hensel lifting over Fq: ");
8743 DEBOUTLN (cerr, "lifted factors= " << uniFactors);
8744
8746
8748 if (extension)
8750 evaluation, 1, uniFactors.length()/2);
8751 else
8753 uniFactors.length()/2);
8755 "time for naive bivariate factor recombi over Fq: ");
8756
8757 if (earlySuccess)
8759 else if (!earlySuccess && degs.getLength() == 1)
8761 }
8762 else if (degree (A) > 4 && beta.level() == 1 && (2*minBound)/degMipo < 32)
8763 {
8765 if (extension)
8766 {
8769 );
8771 }
8772 else if (alpha.level() == 1 && !GF)
8773 {
8777 }
8778 else if (!extension && (alpha != x || GF))
8779 {
8783 }
8785 "time to bivar lift and LLL recombi over Fq: ");
8786 DEBOUTLN (cerr, "lifted factors= " << uniFactors);
8787 }
8788 else
8789 {
8790 bool earlySuccess= false;
8797 "time for bivar hensel lifting over Fq: ");
8798 DEBOUTLN (cerr, "lifted factors= " << uniFactors);
8799
8801 if (!extension)
8802 {
8806 "time for small subset naive recombi over Fq: ");
8807
8809 if (degree (A) > 0)
8810 {
8811 CFList tmp;
8813 if (alpha.level() == 1)
8816 );
8817 else
8818 {
8819 if (degree (A) > getCharacteristic())
8822 );
8823 else
8826 );
8827 }
8829 "time to increase precision: ");
8831 if (tmp.length() == 0 || (tmp.length() > 0 && uniFactors.length() != 0
8833 )
8834 {
8836 degs.intersect (bufDegs);
8837 degs.refine ();
8839 degs, evaluation, 4,
8840 uniFactors.length()/2
8841 )
8842 );
8843 }
8844 }
8845 }
8846 else
8847 {
8848 if (beta.level() != 1 || k > 1)
8849 {
8850 if (k > 1)
8851 {
8854 );
8855 }
8856 else
8857 {
8859 evaluation, 1, 3
8860 );
8861 if (degree (A) > 0)
8862 {
8865 degs.intersect (bufDegs);
8866 degs.refine ();
8869 1, tmp.length()/2
8870 )
8871 );
8872 }
8873 }
8874 }
8875 else
8876 {
8878 evaluation, 1, 3
8879 );
8881 if (degree (A) > 0)
8882 {
8883 int degMipo;
8885
8886 CFList source, dest;
8889 info2, source, dest, liftBound
8890 );
8892 if (tmp.length() == 0 || (tmp.length() > 0 && uniFactors.length() != 0
8894 )
8895 {
8897 degs.intersect (bufDegs);
8898 degs.refine ();
8901 4, uniFactors.length()/2
8902 )
8903 );
8904 }
8905 }
8906 }
8907 }
8908
8909 if (earlySuccess)
8911 else if (!earlySuccess && degs.getLength() == 1)
8913 }
8914
8915 if (!swap2)
8916 delete [] bounds2;
8917 delete [] bounds;
8918
8920 swap, swap2, N);
8921 if (!extension)
8923
8924 return factors;
8925}
8926#endif
8927
8928#ifdef HAVE_NTL // biFactorize
8929CFList
8931{
8932
8933 CanonicalForm A= F;
8934 Variable alpha= info.getAlpha();
8935 Variable beta= info.getBeta();
8936 int k= info.getGFDegree();
8937 char cGFName= info.getGFName();
8938 CanonicalForm delta= info.getDelta();
8939
8941 Variable x= Variable (1);
8943 if (!GF && alpha == x) // we are in F_p
8944 {
8945 bool extension= true;
8946 int p= getCharacteristic();
8947 if (p*p < (1<<16)) // pass to GF if possible
8948 {
8950 A= A.mapinto();
8953
8957 for (CFListIterator j= factors; j.hasItem(); j++)
8958 j.getItem()= GF2FalphaRep (j.getItem(), vBuf);
8959 prune (vBuf);
8960 }
8961 else // not able to pass to GF, pass to F_p(\alpha)
8962 {
8964 Variable v= rootOf (mipo);
8967 prune (v);
8968 }
8969 return factors;
8970 }
8971 else if (!GF && (alpha != x)) // we are in F_p(\alpha)
8972 {
8973 if (k == 1) // need factorization over F_p
8974 {
8975 int extDeg= degree (getMipo (alpha));
8976 extDeg++;
8978 Variable v= rootOf (mipo);
8981 prune (v);
8982 }
8983 else
8984 {
8985 if (beta == x)
8986 {
8989 bool primFail= false;
8990 Variable vBuf;
8992 ASSERT (!primFail, "failure in integer factorizer");
8993 if (primFail)
8994 ; //ERROR
8995 else
8997
8998 CFList source, dest;
9000 source, dest);
9003 prune (v);
9004 }
9005 else
9006 {
9009 bool primFail= false;
9010 Variable vBuf;
9011 ASSERT (!primFail, "failure in integer factorizer");
9012 if (primFail)
9013 ; //ERROR
9014 else
9015 imPrimElem= mapPrimElem (delta, beta, v);
9016
9017 CFList source, dest;
9019 source= CFList();
9020 dest= CFList();
9021 bufA= mapUp (bufA, beta, v, delta, imPrimElem, source, dest);
9024 prune (v);
9025 }
9026 }
9027 return factors;
9028 }
9029 else // we are in GF (p^k)
9030 {
9031 int p= getCharacteristic();
9033 bool extension= true;
9034 if (k == 1) // need factorization over F_p
9035 {
9036 extensionDeg++;
9037 if (ipower (p, extensionDeg) < (1<<16))
9038 // pass to GF(p^k+1)
9039 {
9043 A= GF2FalphaRep (A, vBuf);
9046 factors= biFactorize (A.mapinto(), info2);
9047 prune (vBuf);
9048 }
9049 else // not able to pass to another GF, pass to F_p(\alpha)
9050 {
9054 A= GF2FalphaRep (A, vBuf);
9058 prune (vBuf);
9059 }
9060 }
9061 else // need factorization over GF (p^k)
9062 {
9063 if (ipower (p, 2*extensionDeg) < (1<<16))
9064 // pass to GF (p^2k)
9065 {
9070 }
9071 else // not able to pass to GF (p^2k), pass to F_p (\alpha)
9072 {
9076 A= GF2FalphaRep (A, v1);
9079 bool primFail= false;
9080 Variable vBuf;
9082 ASSERT (!primFail, "failure in integer factorizer");
9083 if (primFail)
9084 ; //ERROR
9085 else
9087
9088 CFList source, dest;
9090 source, dest);
9094 for (CFListIterator i= factors; i.hasItem(); i++)
9096 prune (v1);
9097 }
9098 }
9099 return factors;
9100 }
9101}
9102#endif
9103#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:4082
int p
Definition cfModGcd.cc:4078
g
Definition cfModGcd.cc:4090
CanonicalForm test
Definition cfModGcd.cc:4096
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
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)
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:74
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:75
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:74
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:73
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:86
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:62
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:75
ExtensionInfo init4ext(const ExtensionInfo &info, const CanonicalForm &evaluation, int &degMipo)
const CanonicalForm const modpk & b
Definition facFqBivar.cc:63
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:415
bool uniFdivides(const CanonicalForm &A, const CanonicalForm &B)
divisibility test for univariate polys
Definition facMul.cc:3763
CanonicalForm mulMod2(const CanonicalForm &A, const CanonicalForm &B, const CanonicalForm &M)
Karatsuba style modular multiplication for bivariate polynomials.
Definition facMul.cc:2990
CanonicalForm prodMod(const CFList &L, const CanonicalForm &M)
product of all elements in L modulo M via divide-and-conquer.
Definition facMul.cc:3184
This file defines functions for fast multiplication and division with remainder.
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)