source: git/factory/facFqBivar.cc @ c49e6f

fieker-DuValspielwiese
Last change on this file since c49e6f was c49e6f, checked in by Martin Lee <martinlee84@…>, 11 years ago
fix: several fixes for factorization if extension needed
  • Property mode set to 100644
File size: 222.3 KB
Line 
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#include "config.h"
20
21#include "cf_assert.h"
22#include "debug.h"
23#include "timing.h"
24
25#include "canonicalform.h"
26#include "cf_defs.h"
27#include "cf_map_ext.h"
28#include "cf_random.h"
29#include "facHensel.h"
30#include "facMul.h"
31#include "cf_map.h"
32#include "cf_gcd_smallp.h"
33#include "facFqBivarUtil.h"
34#include "facFqBivar.h"
35#include "cfNewtonPolygon.h"
36#include "algext.h"
37
38#ifdef HAVE_NTL
39#include "NTLconvert.h"
40
41#ifdef HAVE_FLINT
42#include "FLINTconvert.h"
43#endif
44
45TIMING_DEFINE_PRINT(fac_fq_uni_factorizer)
46TIMING_DEFINE_PRINT(fac_fq_bi_hensel_lift)
47TIMING_DEFINE_PRINT(fac_fq_bi_factor_recombination)
48TIMING_DEFINE_PRINT(fac_fq_bi_evaluation)
49TIMING_DEFINE_PRINT(fac_fq_bi_shift_to_zero)
50
51CanonicalForm prodMod0 (const CFList& L, const CanonicalForm& M, const modpk& b)
52{
53  if (L.isEmpty())
54    return 1;
55  else if (L.length() == 1)
56    return mod (L.getFirst()(0, 1) , M);
57  else if (L.length() == 2)
58    return mod (mulNTL (L.getFirst()(0, 1),L.getLast()(0, 1), b), M);
59  else
60  {
61    int l= L.length()/2;
62    CFListIterator i= L;
63    CFList tmp1, tmp2;
64    CanonicalForm buf1, buf2;
65    for (int j= 1; j <= l; j++, i++)
66      tmp1.append (i.getItem());
67    tmp2= Difference (L, tmp1);
68    buf1= prodMod0 (tmp1, M, b);
69    buf2= prodMod0 (tmp2, M, b);
70    return mod (mulNTL (buf1,buf2, b), M);
71  }
72}
73
74CanonicalForm evalPoint (const CanonicalForm& F, CanonicalForm & eval,
75                         const Variable& alpha, CFList& list, const bool& GF,
76                         bool& fail)
77{
78  fail= false;
79  Variable x= Variable(2);
80  Variable y= Variable(1);
81  FFRandom genFF;
82  GFRandom genGF;
83  CanonicalForm random, mipo;
84  double bound;
85  int p= getCharacteristic ();
86  if (alpha.level() != 1)
87  {
88    mipo= getMipo (alpha);
89    int d= degree (mipo);
90    bound= ipower (p, d);
91  }
92  else if (GF)
93  {
94    int d= getGFDegree();
95    bound= ipower (p, d);
96  }
97  else
98    bound= p;
99
100  random= 0;
101  do
102  {
103    if (list.length() >= bound)
104    {
105      fail= true;
106      break;
107    }
108    if (list.isEmpty())
109      random= 0;
110    else if (GF)
111    {
112      if (list.length() == 1)
113        random= getGFGenerator();
114      else
115        random= genGF.generate();
116    }
117    else if (list.length() < p || alpha.level() == 1)
118      random= genFF.generate();
119    else if (alpha != x && list.length() >= p)
120    {
121      if (list.length() == p)
122        random= alpha;
123      else
124      {
125        AlgExtRandomF genAlgExt (alpha);
126        random= genAlgExt.generate();
127      }
128    }
129    if (find (list, random)) continue;
130    eval= F (random, x);
131    if (degree (eval) != degree (F, y))
132    { //leading coeff vanishes
133      if (!find (list, random))
134        list.append (random);
135      continue;
136    }
137    if (degree (gcd (deriv (eval, eval.mvar()), eval), eval.mvar()) > 0)
138    { //evaluated polynomial is not squarefree
139      if (!find (list, random))
140        list.append (random);
141      continue;
142    }
143  } while (find (list, random));
144
145  return random;
146}
147
148CFList
149uniFactorizer (const CanonicalForm& A, const Variable& alpha, const bool& GF)
150{
151  Variable x= A.mvar();
152  if (A.inCoeffDomain())
153    return CFList();
154  ASSERT (A.isUnivariate(),
155          "univariate polynomial expected or constant expected");
156  CFFList factorsA;
157  if (fac_NTL_char != getCharacteristic())
158  {
159    fac_NTL_char= getCharacteristic();
160    zz_p::init (getCharacteristic());
161  }
162  if (GF)
163  {
164    int k= getGFDegree();
165    char cGFName= gf_name;
166    CanonicalForm mipo= gf_mipo;
167    setCharacteristic (getCharacteristic());
168    Variable beta= rootOf (mipo.mapinto());
169    CanonicalForm buf= GF2FalphaRep (A, beta);
170    if (getCharacteristic() > 2)
171    {
172      zz_pX NTLMipo= convertFacCF2NTLzzpX (mipo.mapinto());
173      zz_pE::init (NTLMipo);
174      zz_pEX NTLA= convertFacCF2NTLzz_pEX (buf, NTLMipo);
175      MakeMonic (NTLA);
176      vec_pair_zz_pEX_long NTLFactorsA= CanZass (NTLA);
177      zz_pE multi= to_zz_pE (1);
178      factorsA= convertNTLvec_pair_zzpEX_long2FacCFFList (NTLFactorsA, multi,
179                                                         x, beta);
180    }
181    else
182    {
183      GF2X NTLMipo= convertFacCF2NTLGF2X (mipo.mapinto());
184      GF2E::init (NTLMipo);
185      GF2EX NTLA= convertFacCF2NTLGF2EX (buf, NTLMipo);
186      MakeMonic (NTLA);
187      vec_pair_GF2EX_long NTLFactorsA= CanZass (NTLA);
188      GF2E multi= to_GF2E (1);
189      factorsA= convertNTLvec_pair_GF2EX_long2FacCFFList (NTLFactorsA, multi,
190                                                           x, beta);
191    }
192    setCharacteristic (getCharacteristic(), k, cGFName);
193    for (CFFListIterator i= factorsA; i.hasItem(); i++)
194    {
195      buf= i.getItem().factor();
196      buf= Falpha2GFRep (buf);
197      i.getItem()= CFFactor (buf, i.getItem().exp());
198    }
199  }
200  else if (alpha.level() != 1)
201  {
202    if (getCharacteristic() > 2)
203    {
204      zz_pX NTLMipo= convertFacCF2NTLzzpX (getMipo (alpha));
205      zz_pE::init (NTLMipo);
206      zz_pEX NTLA= convertFacCF2NTLzz_pEX (A, NTLMipo);
207      MakeMonic (NTLA);
208      vec_pair_zz_pEX_long NTLFactorsA= CanZass (NTLA);
209      zz_pE multi= to_zz_pE (1);
210      factorsA= convertNTLvec_pair_zzpEX_long2FacCFFList (NTLFactorsA, multi,
211                                                           x, alpha);
212    }
213    else
214    {
215      GF2X NTLMipo= convertFacCF2NTLGF2X (getMipo (alpha));
216      GF2E::init (NTLMipo);
217      GF2EX NTLA= convertFacCF2NTLGF2EX (A, NTLMipo);
218      MakeMonic (NTLA);
219      vec_pair_GF2EX_long NTLFactorsA= CanZass (NTLA);
220      GF2E multi= to_GF2E (1);
221      factorsA= convertNTLvec_pair_GF2EX_long2FacCFFList (NTLFactorsA, multi,
222                                                           x, alpha);
223    }
224  }
225  else
226  {
227#ifdef HAVE_FLINT
228    nmod_poly_t FLINTA;
229    convertFacCF2nmod_poly_t (FLINTA, A);
230    nmod_poly_factor_t result;
231    nmod_poly_factor_init (result);
232    mp_limb_t leadingCoeff= nmod_poly_factor (result, FLINTA);
233    factorsA= convertFLINTnmod_poly_factor2FacCFFList (result, leadingCoeff, x);
234    if (factorsA.getFirst().factor().inCoeffDomain())
235      factorsA.removeFirst();
236    nmod_poly_factor_clear (result);
237    nmod_poly_clear (FLINTA);
238#else
239    if (getCharacteristic() > 2)
240    {
241      zz_pX NTLA= convertFacCF2NTLzzpX (A);
242      MakeMonic (NTLA);
243      vec_pair_zz_pX_long NTLFactorsA= CanZass (NTLA);
244      zz_p multi= to_zz_p (1);
245      factorsA= convertNTLvec_pair_zzpX_long2FacCFFList (NTLFactorsA, multi,
246                                                          x);
247    }
248    else
249    {
250      GF2X NTLA= convertFacCF2NTLGF2X (A);
251      vec_pair_GF2X_long NTLFactorsA= CanZass (NTLA);
252      GF2 multi= to_GF2 (1);
253      factorsA= convertNTLvec_pair_GF2X_long2FacCFFList (NTLFactorsA, multi,
254                                                          x);
255    }
256#endif
257  }
258  CFList uniFactors;
259  for (CFFListIterator i= factorsA; i.hasItem(); i++)
260    uniFactors.append (i.getItem().factor());
261  return uniFactors;
262}
263
264/// naive factor recombination as decribed in "Factoring
265/// multivariate polynomials over a finite field" by L Bernardin.
266CFList
267extFactorRecombination (CFList& factors, CanonicalForm& F,
268                        const CanonicalForm& N, const ExtensionInfo& info,
269                        DegreePattern& degs, const CanonicalForm& eval, int s,
270                        int thres)
271{
272  if (factors.length() == 0)
273  {
274    F= 1;
275    return CFList();
276  }
277  if (F.inCoeffDomain())
278    return CFList();
279
280  Variable alpha= info.getAlpha();
281  Variable beta= info.getBeta();
282  CanonicalForm gamma= info.getGamma();
283  CanonicalForm delta= info.getDelta();
284  int k= info.getGFDegree();
285
286  CanonicalForm M= N;
287  int l= degree (N);
288  Variable y= F.mvar();
289  Variable x= Variable (1);
290  CFList source, dest;
291  if (degs.getLength() <= 1 || factors.length() == 1)
292  {
293    CFList result= CFList(mapDown (F(y-eval, y), info, source, dest));
294    F= 1;
295    return result;
296  }
297
298  DEBOUTLN (cerr, "LC (F, 1)*prodMod (factors, M) == F " <<
299            (mod (LC (F, 1)*prodMod (factors, M), M)/Lc (mod (LC (F, 1)*prodMod (factors, M), M)) == F/Lc (F)));
300  int degMipoBeta= 1;
301  if (!k && beta.level() != 1)
302    degMipoBeta= degree (getMipo (beta));
303
304  CFList T, S, Diff;
305  T= factors;
306
307  CFList result;
308  CanonicalForm buf, buf2, quot;
309
310  buf= F;
311
312  CanonicalForm g, LCBuf= LC (buf, x);
313  int * v= new int [T.length()];
314  for (int i= 0; i < T.length(); i++)
315    v[i]= 0;
316
317  CFArray TT;
318  DegreePattern bufDegs1, bufDegs2;
319  bufDegs1= degs;
320  int subsetDeg;
321  TT= copy (factors);
322  bool nosubset= false;
323  bool recombination= false;
324  bool trueFactor= false;
325  CanonicalForm test;
326  CanonicalForm buf0= buf (0, x)*LCBuf;
327  while (T.length() >= 2*s && s <= thres)
328  {
329    while (nosubset == false)
330    {
331      if (T.length() == s)
332      {
333        delete [] v;
334        if (recombination)
335        {
336          T.insert (LCBuf);
337          g= prodMod (T, M);
338          T.removeFirst();
339          g /= content(g);
340          g= g (y - eval, y);
341          g /= Lc (g);
342          appendTestMapDown (result, g, info, source, dest);
343          F= 1;
344          return result;
345        }
346        else
347        {
348          appendMapDown (result, F (y - eval, y), info, source, dest);
349          F= 1;
350          return result;
351        }
352      }
353      S= subset (v, s, TT, nosubset);
354      if (nosubset) break;
355      subsetDeg= subsetDegree (S);
356      // skip those combinations that are not possible
357      if (!degs.find (subsetDeg))
358        continue;
359      else
360      {
361        test= prodMod0 (S, M);
362        test *= LCBuf;
363        test = mod (test, M);
364        if (fdivides (test, buf0))
365        {
366          S.insert (LCBuf);
367          g= prodMod (S, M);
368          S.removeFirst();
369          g /= content (g, x);
370          if (fdivides (g, buf, quot))
371          {
372            buf2= g (y - eval, y);
373            buf2 /= Lc (buf2);
374
375            if (!k && beta.level() == 1)
376            {
377              if (degree (buf2, alpha) < degMipoBeta)
378              {
379                buf= quot;
380                LCBuf= LC (buf, x);
381                recombination= true;
382                appendTestMapDown (result, buf2, info, source, dest);
383                trueFactor= true;
384              }
385            }
386            else
387            {
388              if (!isInExtension (buf2, gamma, k, delta, source, dest))
389              {
390                buf= quot;
391                LCBuf= LC (buf, x);
392                recombination= true;
393                appendTestMapDown (result, buf2, info, source, dest);
394                trueFactor= true;
395              }
396            }
397            if (trueFactor)
398            {
399              T= Difference (T, S);
400              l -= degree (g);
401              M= power (y, l);
402              buf0= buf (0, x)*LCBuf;
403
404              // compute new possible degree pattern
405              bufDegs2= DegreePattern (T);
406              bufDegs1.intersect (bufDegs2);
407              bufDegs1.refine ();
408              if (T.length() < 2*s || T.length() == s ||
409                  bufDegs1.getLength() == 1)
410              {
411                delete [] v;
412                if (recombination)
413                {
414                  buf= buf (y-eval,y);
415                  buf /= Lc (buf);
416                  appendTestMapDown (result, buf, info, source,
417                                      dest);
418                  F= 1;
419                  return result;
420                }
421                else
422                {
423                  appendMapDown (result, F (y - eval, y), info, source, dest);
424                  F= 1;
425                  return result;
426                }
427              }
428              trueFactor= false;
429              TT= copy (T);
430              indexUpdate (v, s, T.length(), nosubset);
431              if (nosubset) break;
432            }
433          }
434        }
435      }
436    }
437    s++;
438    if (T.length() < 2*s || T.length() == s)
439    {
440      delete [] v;
441      if (recombination)
442      {
443        buf= buf (y-eval,y);
444        buf /= Lc (buf);
445        appendTestMapDown (result, buf, info, source, dest);
446        F= 1;
447        return result;
448      }
449      else
450      {
451        appendMapDown (result, F (y - eval, y), info, source, dest);
452        F= 1;
453        return result;
454      }
455    }
456    for (int i= 0; i < T.length(); i++)
457      v[i]= 0;
458    nosubset= false;
459  }
460  if (T.length() < 2*s)
461  {
462    appendMapDown (result, F (y - eval, y), info, source, dest);
463    F= 1;
464    delete [] v;
465    return result;
466  }
467
468  if (s > thres)
469  {
470    factors= T;
471    F= buf;
472    degs= bufDegs1;
473  }
474
475  delete [] v;
476  return result;
477}
478
479/// naive factor recombination as decribed in "Factoring
480/// multivariate polynomials over a finite field" by L Bernardin.
481CFList
482factorRecombination (CFList& factors, CanonicalForm& F,
483                     const CanonicalForm& N, DegreePattern& degs, int s,
484                     int thres, const modpk& b
485                    )
486{
487  if (factors.length() == 0)
488  {
489    F= 1;
490    return CFList ();
491  }
492  if (F.inCoeffDomain())
493    return CFList();
494  if (degs.getLength() <= 1 || factors.length() == 1)
495  {
496    CFList result= CFList (F);
497    F= 1;
498    return result;
499  }
500#ifdef DEBUGOUTPUT
501  if (b.getp() == 0)
502    DEBOUTLN (cerr, "LC (F, 1)*prodMod (factors, N) == F " <<
503              (mod (LC (F, 1)*prodMod (factors, N),N)/Lc (mod (LC (F, 1)*prodMod (factors, N),N)) == F/Lc(F)));
504  else
505    DEBOUTLN (cerr, "LC (F, 1)*prodMod (factors, N) == F " <<
506              (mod (b(LC (F, 1)*prodMod (factors, N)),N)/Lc (mod (b(LC (F, 1)*prodMod (factors, N)),N)) == F/Lc(F)));
507#endif
508
509  CFList T, S;
510
511  CanonicalForm M= N;
512  int l= degree (N);
513  T= factors;
514  CFList result;
515  Variable y= Variable (2);
516  Variable x= Variable (1);
517  CanonicalForm LCBuf= LC (F, x);
518  CanonicalForm g, quot, buf= F;
519  int * v= new int [T.length()];
520  for (int i= 0; i < T.length(); i++)
521    v[i]= 0;
522  bool nosubset= false;
523  CFArray TT;
524  DegreePattern bufDegs1, bufDegs2;
525  bufDegs1= degs;
526  int subsetDeg;
527  TT= copy (factors);
528  bool recombination= false;
529  CanonicalForm test;
530  bool isRat= (isOn (SW_RATIONAL) && getCharacteristic() == 0) ||
531               getCharacteristic() > 0;
532  if (!isRat)
533    On (SW_RATIONAL);
534  CanonicalForm buf0= mulNTL (buf (0, x), LCBuf);
535  if (!isRat)
536    Off (SW_RATIONAL);
537  while (T.length() >= 2*s && s <= thres)
538  {
539    while (nosubset == false)
540    {
541      if (T.length() == s)
542      {
543        delete [] v;
544        if (recombination)
545        {
546          T.insert (LCBuf);
547          g= prodMod (T, M);
548          if (b.getp() != 0)
549            g= b(g);
550          T.removeFirst();
551          result.append (g/content (g, x));
552          F= 1;
553          return result;
554        }
555        else
556        {
557          result= CFList (F);
558          F= 1;
559          return result;
560        }
561      }
562      S= subset (v, s, TT, nosubset);
563      if (nosubset) break;
564      subsetDeg= subsetDegree (S);
565      // skip those combinations that are not possible
566      if (!degs.find (subsetDeg))
567        continue;
568      else
569      {
570        if (!isRat)
571          On (SW_RATIONAL);
572        test= prodMod0 (S, M);
573        if (!isRat)
574        {
575          test *= bCommonDen (test);
576          Off (SW_RATIONAL);
577        }
578        test= mulNTL (test, LCBuf, b);
579        test= mod (test, M);
580        if (uniFdivides (test, buf0))
581        {
582          if (!isRat)
583            On (SW_RATIONAL);
584          S.insert (LCBuf);
585          g= prodMod (S, M);
586          S.removeFirst();
587          if (!isRat)
588          {
589            g *= bCommonDen(g);
590            Off (SW_RATIONAL);
591          }
592          if (b.getp() != 0)
593            g= b(g);
594          if (!isRat)
595            On (SW_RATIONAL);
596          g /= content (g, x);
597          if (!isRat)
598          {
599            On (SW_RATIONAL);
600            g *= bCommonDen (g);
601            Off (SW_RATIONAL);
602            g /= icontent (g);
603            On (SW_RATIONAL);
604          }
605          if (fdivides (g, buf, quot))
606          {
607            recombination= true;
608            result.append (g);
609            if (b.getp() != 0)
610              buf= quot*bCommonDen (quot);
611            else
612              buf= quot;
613            LCBuf= LC (buf, x);
614            T= Difference (T, S);
615            l -= degree (g);
616            M= power (y, l);
617            buf0= mulNTL (buf (0, x), LCBuf);
618            if (!isRat)
619              Off (SW_RATIONAL);
620            // compute new possible degree pattern
621            bufDegs2= DegreePattern (T);
622            bufDegs1.intersect (bufDegs2);
623            bufDegs1.refine ();
624            if (T.length() < 2*s || T.length() == s ||
625                bufDegs1.getLength() == 1)
626            {
627              delete [] v;
628              if (recombination)
629              {
630                result.append (buf);
631                F= 1;
632                return result;
633              }
634              else
635              {
636                result= CFList (F);
637                F= 1;
638                return result;
639              }
640            }
641            TT= copy (T);
642            indexUpdate (v, s, T.length(), nosubset);
643            if (nosubset) break;
644          }
645          if (!isRat)
646            Off (SW_RATIONAL);
647        }
648      }
649    }
650    s++;
651    if (T.length() < 2*s || T.length() == s)
652    {
653      delete [] v;
654      if (recombination)
655      {
656        result.append (buf);
657        F= 1;
658        return result;
659      }
660      else
661      {
662        result= CFList (F);
663        F= 1;
664        return result;
665      }
666    }
667    for (int i= 0; i < T.length(); i++)
668      v[i]= 0;
669    nosubset= false;
670  }
671  delete [] v;
672  if (T.length() < 2*s)
673  {
674    result.append (F);
675    F= 1;
676    return result;
677  }
678
679  if (s > thres)
680  {
681    factors= T;
682    F= buf;
683    degs= bufDegs1;
684  }
685
686  return result;
687}
688
689Variable chooseExtension (const Variable & alpha, const Variable& beta, int k)
690{
691  if (fac_NTL_char != getCharacteristic())
692  {
693    fac_NTL_char= getCharacteristic();
694    zz_p::init (getCharacteristic());
695  }
696  zz_pX NTLIrredpoly;
697  int i=1, m= 2;
698  // extension of F_p needed
699  if (alpha.level() == 1 && beta.level() == 1 && k == 1)
700  {
701    i= 1;
702    m= 2;
703  } //extension of F_p(alpha) needed but want to factorize over F_p
704  else if (alpha.level() != 1 && beta.level() == 1 && k == 1)
705  {
706    i= 1;
707    m= degree (getMipo (alpha)) + 1;
708  } //extension of F_p(alpha) needed for first time
709  else if (alpha.level() != 1 && beta.level() == 1 && k != 1)
710  {
711    i= 2;
712    m= degree (getMipo (alpha));
713  }
714  else if (alpha.level() != 1 && beta.level() != 1 && k != 1)
715  {
716    m= degree (getMipo (beta));
717    i= degree (getMipo (alpha))/m + 1;
718  }
719  BuildIrred (NTLIrredpoly, i*m);
720  CanonicalForm newMipo= convertNTLzzpX2CF (NTLIrredpoly, Variable (1));
721  return rootOf (newMipo);
722}
723
724void
725earlyFactorDetection (CFList& reconstructedFactors, CanonicalForm& F, CFList&
726                      factors, int& adaptedLiftBound, int*& factorsFoundIndex,
727                      DegreePattern& degs, bool& success, int deg,
728                      const modpk& b)
729{
730  DegreePattern bufDegs1= degs;
731  DegreePattern bufDegs2;
732  CFList T= factors;
733  CanonicalForm buf= F;
734  Variable x= Variable (1);
735  CanonicalForm g, quot;
736  CanonicalForm M= power (F.mvar(), deg);
737  adaptedLiftBound= 0;
738  int d= degree (F), l= 0;
739  bool isRat= (isOn (SW_RATIONAL) && getCharacteristic() == 0) || getCharacteristic() > 0;
740  if (!isRat)
741    On (SW_RATIONAL);
742  if (b.getp() != 0)
743    buf *= bCommonDen (buf);
744  CanonicalForm LCBuf= LC (buf, x);
745  CanonicalForm buf0= mulNTL (buf (0,x), LCBuf);
746  CanonicalForm buf1= mulNTL (buf (1,x), LCBuf);
747  if (!isRat)
748    Off (SW_RATIONAL);
749  CanonicalForm test0, test1;
750
751  for (CFListIterator i= factors; i.hasItem(); i++, l++)
752  {
753    if (!bufDegs1.find (degree (i.getItem(), 1)) || factorsFoundIndex[l] == 1)
754      continue;
755    else
756    {
757      test1= mod (mulNTL (i.getItem() (1,x), LCBuf, b), M);
758      if (uniFdivides (test1, buf1))
759      {
760        test0= mod (mulNTL (i.getItem() (0,x), LCBuf, b), M);
761        if (uniFdivides (test0, buf0))
762        {
763          if (!isRat)
764            On (SW_RATIONAL);
765          g= mulMod2 (i.getItem(), LCBuf, M);
766          if (!isRat)
767          {
768            g *= bCommonDen(g);
769            Off (SW_RATIONAL);
770          }
771          if (b.getp() != 0)
772            g= b(g);
773          if (!isRat)
774            On (SW_RATIONAL);
775          g /= content (g, x);
776          if (!isRat)
777          {
778            On (SW_RATIONAL);
779            g *= bCommonDen (g);
780            Off (SW_RATIONAL);
781            g /= icontent (g);
782            On (SW_RATIONAL);
783          }
784          if (fdivides (g, buf, quot))
785          {
786            reconstructedFactors.append (g);
787            factorsFoundIndex[l]= 1;
788            if (b.getp() != 0)
789              buf= quot*bCommonDen(quot);
790            else
791              buf= quot;
792            d -= degree (g);
793            LCBuf= LC (buf, x);
794            buf0= mulNTL (buf (0,x), LCBuf);
795            buf1= mulNTL (buf (1,x), LCBuf);
796            if (!isRat)
797              Off (SW_RATIONAL);
798            T= Difference (T, CFList (i.getItem()));
799            F= buf;
800
801            // compute new possible degree pattern
802            bufDegs2= DegreePattern (T);
803            bufDegs1.intersect (bufDegs2);
804            bufDegs1.refine ();
805            if (bufDegs1.getLength() <= 1)
806            {
807              if (!buf.inCoeffDomain())
808              {
809                reconstructedFactors.append (buf);
810                F= 1;
811              }
812              break;
813            }
814          }
815          if (!isRat)
816            Off (SW_RATIONAL);
817        }
818      }
819    }
820  }
821  adaptedLiftBound= d + 1;
822  if (adaptedLiftBound < deg)
823  {
824    degs= bufDegs1;
825    success= true;
826  }
827  if (bufDegs1.getLength() <= 1)
828    degs= bufDegs1;
829}
830
831void
832extEarlyFactorDetection (CFList& reconstructedFactors, CanonicalForm& F, CFList&
833                         factors,int& adaptedLiftBound, int*& factorsFoundIndex,
834                         DegreePattern& degs, bool& success, const
835                         ExtensionInfo& info, const CanonicalForm& eval, int deg
836                        )
837{
838  Variable alpha= info.getAlpha();
839  Variable beta= info.getBeta();
840  CanonicalForm gamma= info.getGamma();
841  CanonicalForm delta= info.getDelta();
842  int k= info.getGFDegree();
843  DegreePattern bufDegs1= degs, bufDegs2;
844  CFList result;
845  CFList T= factors;
846  Variable y= F.mvar();
847  Variable x= Variable (1);
848  CanonicalForm buf= F, LCBuf= LC (buf, x), g, buf2;
849  CanonicalForm M= power (y, deg);
850  adaptedLiftBound= 0;
851  bool trueFactor= false;
852  int d= degree (F), l= 0;
853  CFList source, dest;
854  int degMipoBeta= 1;
855  if (!k && beta.level() != 1)
856    degMipoBeta= degree (getMipo (beta));
857  CanonicalForm quot;
858  for (CFListIterator i= factors; i.hasItem(); i++, l++)
859  {
860    if (!bufDegs1.find (degree (i.getItem(), 1)) || factorsFoundIndex[l] == 1)
861      continue;
862    else
863    {
864      g= mulMod2 (i.getItem(), LCBuf, M);
865      g /= content (g, x);
866      if (fdivides (g, buf, quot))
867      {
868        buf2= g (y - eval, y);
869        buf2 /= Lc (buf2);
870
871        if (!k && beta == x)
872        {
873          if (degree (buf2, alpha) < degMipoBeta)
874          {
875            appendTestMapDown (reconstructedFactors, buf2, info, source, dest);
876            factorsFoundIndex[l]= 1;
877            buf= quot;
878            d -= degree (g);
879            LCBuf= LC (buf, x);
880            trueFactor= true;
881          }
882        }
883        else
884        {
885          if (!isInExtension (buf2, gamma, k, delta, source, dest))
886          {
887            appendTestMapDown (reconstructedFactors, buf2, info, source, dest);
888            factorsFoundIndex[l]= 1;
889            buf= quot;
890            d -= degree (g);
891            LCBuf= LC (buf, x);
892            trueFactor= true;
893          }
894        }
895        if (trueFactor)
896        {
897          T= Difference (T, CFList (i.getItem()));
898          F= buf;
899
900          // compute new possible degree pattern
901          bufDegs2= DegreePattern (T);
902          bufDegs1.intersect (bufDegs2);
903          bufDegs1.refine ();
904          trueFactor= false;
905          if (bufDegs1.getLength() <= 1)
906          {
907            if (!buf.inCoeffDomain())
908            {
909              buf= buf (y - eval, y);
910              buf /= Lc (buf);
911              appendMapDown (reconstructedFactors, buf, info, source, dest);
912              F= 1;
913            }
914            break;
915          }
916        }
917      }
918    }
919  }
920  adaptedLiftBound= d + 1;
921  if (adaptedLiftBound < deg)
922  {
923    degs= bufDegs1;
924    success= true;
925  }
926  if (bufDegs1.getLength() <= 1)
927    degs= bufDegs1;
928}
929
930int*
931getCombinations (int * rightSide, int sizeOfRightSide, int& sizeOfOutput,
932                 int degreeLC)
933{
934  Variable x= Variable (1);
935  int p= getCharacteristic();
936  int d= getGFDegree();
937  char cGFName= gf_name;
938  setCharacteristic(0);
939  CanonicalForm buf= 1;
940  for (int i= 0; i < sizeOfRightSide; i++)
941    buf *= (power (x, rightSide [i]) + 1);
942
943  int j= 0;
944  for (CFIterator i= buf; i.hasTerms(); i++, j++)
945  {
946    if (i.exp() < degreeLC)
947    {
948      j++;
949      break;
950    }
951  }
952
953  ASSERT ( j > 1, "j > 1 expected" );
954
955  int* result = new int  [j - 1];
956  sizeOfOutput= j - 1;
957
958  int i= 0;
959  for (CFIterator m = buf; i < j - 1; i++, m++)
960    result [i]= m.exp();
961
962  if (d > 1)
963    setCharacteristic (p, d, cGFName);
964  else
965    setCharacteristic (p);
966  return result;
967}
968
969int *
970getLiftPrecisions (const CanonicalForm& F, int& sizeOfOutput, int degreeLC)
971{
972  int sizeOfNewtonPoly;
973  int ** newtonPolyg= newtonPolygon (F, sizeOfNewtonPoly);
974  int sizeOfRightSide;
975  int * rightSide= getRightSide(newtonPolyg, sizeOfNewtonPoly, sizeOfRightSide);
976  int * result= getCombinations(rightSide, sizeOfRightSide, sizeOfOutput,
977                                degreeLC);
978  delete [] rightSide;
979  for (int i= 0; i < sizeOfNewtonPoly; i++)
980    delete [] newtonPolyg[i];
981  delete [] newtonPolyg;
982  return result;
983}
984
985void
986deleteFactors (CFList& factors, int* factorsFoundIndex)
987{
988  CFList result;
989  int i= 0;
990  for (CFListIterator iter= factors; iter.hasItem(); iter++, i++)
991  {
992    if (factorsFoundIndex[i] == 1)
993      continue;
994    else
995      result.append (iter.getItem());
996  }
997  factors= result;
998}
999
1000CFList
1001henselLiftAndEarly (CanonicalForm& A, bool& earlySuccess, CFList&
1002                    earlyFactors, DegreePattern& degs, int& liftBound,
1003                    const CFList& uniFactors, const ExtensionInfo& info,
1004                    const CanonicalForm& eval, modpk& b)
1005{
1006  Variable alpha= info.getAlpha();
1007  Variable beta= info.getBeta();
1008  CanonicalForm gamma= info.getGamma();
1009  CanonicalForm delta= info.getDelta();
1010  bool extension= info.isInExtension();
1011
1012  int sizeOfLiftPre;
1013  int * liftPre= getLiftPrecisions (A, sizeOfLiftPre, degree (LC (A, 1), 2));
1014
1015  Variable x= Variable (1);
1016  Variable y= Variable (2);
1017  CFArray Pi;
1018  CFList diophant;
1019  CFList bufUniFactors= uniFactors;
1020  CanonicalForm bufA= A;
1021  CanonicalForm lcA0= 0;
1022  bool mipoHasDen= false;
1023  if (getCharacteristic() == 0 && b.getp() != 0)
1024  {
1025    if (alpha.level() == 1)
1026    {
1027      lcA0= lc (A (0, 2));
1028      A *= b.inverse (lcA0);
1029      A= b (A);
1030      for (CFListIterator i= bufUniFactors; i.hasItem(); i++)
1031        i.getItem()= b (i.getItem()*b.inverse (lc (i.getItem())));
1032    }
1033    else
1034    {
1035      lcA0= Lc (A (0,2));
1036      On (SW_RATIONAL);
1037      mipoHasDen= !bCommonDen(getMipo(alpha)).isOne();
1038      Off (SW_RATIONAL);
1039      CanonicalForm lcA0inverse= b.inverse (lcA0);
1040      A *= lcA0inverse;
1041      A= b (A);
1042      // Lc of bufUniFactors is in Z
1043      for (CFListIterator i= bufUniFactors; i.hasItem(); i++)
1044        i.getItem()= b (i.getItem()*b.inverse (lc (i.getItem())));
1045    }
1046  }
1047  bufUniFactors.insert (LC (A, x));
1048  CFMatrix M= CFMatrix (liftBound, bufUniFactors.length() - 1);
1049  earlySuccess= false;
1050  int newLiftBound= 0;
1051
1052  int smallFactorDeg= tmin (11, liftPre [sizeOfLiftPre- 1] + 1);//this is a tunable parameter
1053  int dummy;
1054  int * factorsFoundIndex= new int [uniFactors.length()];
1055  for (int i= 0; i < uniFactors.length(); i++)
1056    factorsFoundIndex [i]= 0;
1057
1058  CFList bufBufUniFactors;
1059  Variable v= alpha;
1060  if (smallFactorDeg >= liftBound || degree (A,y) <= 4)
1061    henselLift12 (A, bufUniFactors, liftBound, Pi, diophant, M, b, true);
1062  else if (sizeOfLiftPre > 1 && sizeOfLiftPre < 30)
1063  {
1064    henselLift12 (A, bufUniFactors, smallFactorDeg, Pi, diophant, M, b, true);
1065    if (mipoHasDen)
1066    {
1067      for (CFListIterator iter= bufUniFactors; iter.hasItem(); iter++)
1068        if (hasFirstAlgVar (iter.getItem(), v))
1069          break;
1070      if (v != alpha)
1071      {
1072        bufBufUniFactors= bufUniFactors;
1073        for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
1074          iter.getItem()= replacevar (iter.getItem(), v, alpha);
1075        A= replacevar (A, alpha, v);
1076      }
1077    }
1078
1079    if (!extension)
1080    {
1081      if (v==alpha)
1082        earlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
1083                              factorsFoundIndex, degs, earlySuccess,
1084                              smallFactorDeg, b);
1085      else
1086        earlyFactorDetection(earlyFactors, bufA, bufBufUniFactors, newLiftBound,
1087                             factorsFoundIndex, degs, earlySuccess,
1088                             smallFactorDeg, b);
1089    }
1090    else
1091      extEarlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
1092                               factorsFoundIndex, degs, earlySuccess, info,
1093                               eval, smallFactorDeg);
1094    if (degs.getLength() > 1 && !earlySuccess &&
1095        smallFactorDeg != liftPre [sizeOfLiftPre-1] + 1)
1096    {
1097      if (newLiftBound >= liftPre[sizeOfLiftPre-1]+1)
1098      {
1099        bufUniFactors.insert (LC (A, x));
1100        henselLiftResume12 (A, bufUniFactors, smallFactorDeg,
1101                            liftPre[sizeOfLiftPre-1] + 1, Pi, diophant, M, b);
1102        if (v!=alpha)
1103        {
1104          bufBufUniFactors= bufUniFactors;
1105          for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
1106            iter.getItem()= replacevar (iter.getItem(), v, alpha);
1107        }
1108        if (!extension)
1109        {
1110          if (v==alpha)
1111          earlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
1112                                factorsFoundIndex, degs, earlySuccess,
1113                                liftPre[sizeOfLiftPre-1] + 1, b);
1114          else
1115          earlyFactorDetection (earlyFactors,bufA,bufBufUniFactors,newLiftBound,
1116                                factorsFoundIndex, degs, earlySuccess,
1117                                liftPre[sizeOfLiftPre-1] + 1, b);
1118        }
1119        else
1120          extEarlyFactorDetection (earlyFactors,bufA,bufUniFactors,newLiftBound,
1121                                   factorsFoundIndex, degs, earlySuccess, info,
1122                                   eval, liftPre[sizeOfLiftPre-1] + 1);
1123      }
1124    }
1125    else if (earlySuccess)
1126      liftBound= newLiftBound;
1127
1128    int i= sizeOfLiftPre - 1;
1129    while (degs.getLength() > 1 && !earlySuccess && i - 1 >= 0)
1130    {
1131      if (newLiftBound >= liftPre[i] + 1)
1132      {
1133        bufUniFactors.insert (LC (A, x));
1134        henselLiftResume12 (A, bufUniFactors, liftPre[i] + 1,
1135                            liftPre[i-1] + 1, Pi, diophant, M, b);
1136        if (v!=alpha)
1137        {
1138          bufBufUniFactors= bufUniFactors;
1139          for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
1140            iter.getItem()= replacevar (iter.getItem(), v, alpha);
1141        }
1142        if (!extension)
1143        {
1144          if (v==alpha)
1145          earlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
1146                                factorsFoundIndex, degs, earlySuccess,
1147                                liftPre[i-1] + 1, b);
1148          else
1149          earlyFactorDetection (earlyFactors,bufA,bufBufUniFactors,newLiftBound,
1150                                factorsFoundIndex, degs, earlySuccess,
1151                                liftPre[i-1] + 1, b);
1152        }
1153        else
1154          extEarlyFactorDetection (earlyFactors,bufA,bufUniFactors,newLiftBound,
1155                                   factorsFoundIndex, degs, earlySuccess, info,
1156                                   eval, liftPre[i-1] + 1);
1157      }
1158      else
1159      {
1160        liftBound= newLiftBound;
1161        break;
1162      }
1163      i--;
1164    }
1165    if (earlySuccess)
1166      liftBound= newLiftBound;
1167    //after here all factors are lifted to liftPre[sizeOfLiftPre-1]
1168  }
1169  else
1170  {
1171    henselLift12 (A, bufUniFactors, smallFactorDeg, Pi, diophant, M, b, true);
1172    if (mipoHasDen)
1173    {
1174      for (CFListIterator iter= bufUniFactors; iter.hasItem(); iter++)
1175        if (hasFirstAlgVar (iter.getItem(), v))
1176          break;
1177      if (v != alpha)
1178      {
1179        bufBufUniFactors= bufUniFactors;
1180        for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
1181          iter.getItem()= replacevar (iter.getItem(), v, alpha);
1182        A= replacevar (A, alpha, v);
1183      }
1184    }
1185    if (!extension)
1186    {
1187      if (v==alpha)
1188      earlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
1189                            factorsFoundIndex, degs, earlySuccess,
1190                            smallFactorDeg, b);
1191      else
1192      earlyFactorDetection (earlyFactors, bufA, bufBufUniFactors, newLiftBound,
1193                            factorsFoundIndex, degs, earlySuccess,
1194                            smallFactorDeg, b);
1195    }
1196    else
1197      extEarlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
1198                               factorsFoundIndex, degs, earlySuccess, info,
1199                               eval, smallFactorDeg);
1200    int i= 1;
1201    while ((degree (A,y)/4)*i + 4 <= smallFactorDeg)
1202      i++;
1203    dummy= tmin (degree (A,y)+1, (degree (A,y)/4)*i+4);
1204    if (degs.getLength() > 1 && !earlySuccess && dummy > smallFactorDeg)
1205    {
1206      bufUniFactors.insert (LC (A, x));
1207      henselLiftResume12 (A, bufUniFactors, smallFactorDeg,
1208                          dummy, Pi, diophant, M, b);
1209      if (v!=alpha)
1210      {
1211        bufBufUniFactors= bufUniFactors;
1212        for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
1213          iter.getItem()= replacevar (iter.getItem(), v, alpha);
1214      }
1215      if (!extension)
1216      {
1217        if (v==alpha)
1218        earlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
1219                              factorsFoundIndex, degs, earlySuccess, dummy, b);
1220        else
1221        earlyFactorDetection (earlyFactors, bufA,bufBufUniFactors, newLiftBound,
1222                              factorsFoundIndex, degs, earlySuccess, dummy, b);
1223      }
1224      else
1225        extEarlyFactorDetection (earlyFactors, bufA,bufUniFactors, newLiftBound,
1226                                 factorsFoundIndex, degs, earlySuccess, info,
1227                                 eval, dummy);
1228    }
1229    while (degs.getLength() > 1 && !earlySuccess && i < 4)
1230    {
1231      if (newLiftBound >= dummy)
1232      {
1233        bufUniFactors.insert (LC (A, x));
1234        dummy= tmin (degree (A,y)+1, (degree (A,y)/4)*(i+1)+4);
1235        henselLiftResume12 (A, bufUniFactors, (degree (A,y)/4)*i + 4,
1236                            dummy, Pi, diophant, M, b);
1237        if (v!=alpha)
1238        {
1239          bufBufUniFactors= bufUniFactors;
1240          for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
1241            iter.getItem()= replacevar (iter.getItem(), v, alpha);
1242        }
1243        if (!extension)
1244        {
1245          if (v==alpha)
1246          earlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
1247                                factorsFoundIndex, degs, earlySuccess, dummy,b);
1248          else
1249          earlyFactorDetection (earlyFactors,bufA,bufBufUniFactors,newLiftBound,
1250                                factorsFoundIndex, degs, earlySuccess, dummy,b);
1251        }
1252        else
1253          extEarlyFactorDetection (earlyFactors,bufA,bufUniFactors,newLiftBound,
1254                                   factorsFoundIndex, degs, earlySuccess, info,
1255                                   eval, dummy);
1256      }
1257      else
1258      {
1259        liftBound= newLiftBound;
1260        break;
1261      }
1262      i++;
1263    }
1264    if (earlySuccess)
1265      liftBound= newLiftBound;
1266  }
1267
1268  A= bufA;
1269  if (earlyFactors.length() > 0 && degs.getLength() > 1)
1270  {
1271    liftBound= degree (A,y) + 1;
1272    earlySuccess= true;
1273    deleteFactors (bufUniFactors, factorsFoundIndex);
1274  }
1275
1276  delete [] factorsFoundIndex;
1277  delete [] liftPre;
1278
1279  return bufUniFactors;
1280}
1281
1282CFList
1283henselLiftAndEarly (CanonicalForm& A, bool& earlySuccess, CFList&
1284                    earlyFactors, DegreePattern& degs, int& liftBound,
1285                    const CFList& uniFactors, const ExtensionInfo& info,
1286                    const CanonicalForm& eval)
1287{
1288  modpk dummy= modpk();
1289  return henselLiftAndEarly (A, earlySuccess, earlyFactors, degs, liftBound,
1290                             uniFactors, info, eval, dummy);
1291}
1292
1293long isReduced (const mat_zz_p& M)
1294{
1295  long i, j, nonZero;
1296  for (i = 1; i <= M.NumRows(); i++)
1297  {
1298    nonZero= 0;
1299    for (j = 1; j <= M.NumCols(); j++)
1300    {
1301      if (!IsZero (M (i,j)))
1302        nonZero++;
1303    }
1304    if (nonZero != 1)
1305      return 0;
1306  }
1307  return 1;
1308}
1309
1310#ifdef HAVE_FLINT
1311long isReduced (const nmod_mat_t M)
1312{
1313  long i, j, nonZero;
1314  for (i = 1; i <= nmod_mat_nrows(M); i++)
1315  {
1316    nonZero= 0;
1317    for (j = 1; j <= nmod_mat_ncols (M); j++)
1318    {
1319      if (!(nmod_mat_entry (M, i-1, j-1)==0))
1320        nonZero++;
1321    }
1322    if (nonZero != 1)
1323      return 0;
1324  }
1325  return 1;
1326}
1327#endif
1328
1329long isReduced (const mat_zz_pE& M)
1330{
1331  long i, j, nonZero;
1332  for (i = 1; i <= M.NumRows(); i++)
1333  {
1334    nonZero= 0;
1335    for (j = 1; j <= M.NumCols(); j++)
1336    {
1337      if (!IsZero (M (i,j)))
1338        nonZero++;
1339    }
1340    if (nonZero != 1)
1341      return 0;
1342  }
1343  return 1;
1344}
1345
1346int * extractZeroOneVecs (const mat_zz_p& M)
1347{
1348  long i, j;
1349  bool nonZeroOne= false;
1350  int * result= new int [M.NumCols()];
1351  for (i = 1; i <= M.NumCols(); i++)
1352  {
1353    for (j = 1; j <= M.NumRows(); j++)
1354    {
1355      if (!(IsOne (M (j,i)) || IsZero (M (j,i))))
1356      {
1357        nonZeroOne= true;
1358        break;
1359      }
1360    }
1361    if (!nonZeroOne)
1362      result [i - 1]= 1;
1363    else
1364      result [i - 1]= 0;
1365    nonZeroOne= false;
1366  }
1367  return result;
1368}
1369
1370#ifdef HAVE_FLINT
1371int * extractZeroOneVecs (const nmod_mat_t M)
1372{
1373  long i, j;
1374  bool nonZeroOne= false;
1375  int * result= new int [nmod_mat_ncols (M)];
1376  for (i = 0; i < nmod_mat_ncols (M); i++)
1377  {
1378    for (j = 0; j < nmod_mat_nrows (M); j++)
1379    {
1380      if (!((nmod_mat_entry (M, j, i) == 1) || (nmod_mat_entry (M, j,i) == 0)))
1381      {
1382        nonZeroOne= true;
1383        break;
1384      }
1385    }
1386    if (!nonZeroOne)
1387      result [i]= 1;
1388    else
1389      result [i]= 0;
1390    nonZeroOne= false;
1391  }
1392  return result;
1393}
1394#endif
1395
1396int * extractZeroOneVecs (const mat_zz_pE& M)
1397{
1398  long i, j;
1399  bool nonZeroOne= false;
1400  int * result= new int [M.NumCols()];
1401  for (i = 1; i <= M.NumCols(); i++)
1402  {
1403    for (j = 1; j <= M.NumRows(); j++)
1404    {
1405      if (!(IsOne (M (j,i)) || IsZero (M (j,i))))
1406      {
1407        nonZeroOne= true;
1408        break;
1409      }
1410    }
1411    if (!nonZeroOne)
1412      result [i - 1]= 1;
1413    else
1414      result [i - 1]= 0;
1415    nonZeroOne= false;
1416  }
1417  return result;
1418}
1419
1420void
1421reconstructionTry (CFList& reconstructedFactors, CanonicalForm& F, const CFList&
1422                   factors, const int liftBound, int& factorsFound, int*&
1423                   factorsFoundIndex, mat_zz_pE& N, bool beenInThres
1424                  )
1425{
1426  Variable y= Variable (2);
1427  Variable x= Variable (1);
1428  CanonicalForm yToL= power (y, liftBound);
1429  if (factors.length() == 2)
1430  {
1431    CanonicalForm tmp1, tmp2, tmp3;
1432    tmp1= factors.getFirst();
1433    tmp2= factors.getLast();
1434    tmp1 *= LC (F, x);
1435    tmp1= mod (tmp1, yToL);
1436    tmp1 /= content (tmp1, x);
1437    tmp2 *= LC (F, x);
1438    tmp2= mod (tmp2, yToL);
1439    tmp2 /= content (tmp2, x);
1440    tmp3 = tmp1*tmp2;
1441    if (tmp3/Lc (tmp3) == F/Lc (F))
1442    {
1443      factorsFound++;
1444      F= 1;
1445      reconstructedFactors.append (tmp1);
1446      reconstructedFactors.append (tmp2);
1447      return;
1448    }
1449  }
1450  CanonicalForm quot, buf;
1451  CFListIterator iter;
1452  for (long i= 1; i <= N.NumCols(); i++)
1453  {
1454    if (factorsFoundIndex [i - 1] == 1)
1455      continue;
1456    iter= factors;
1457    if (beenInThres)
1458    {
1459      int count= 1;
1460      while (count < i)
1461      {
1462        count++;
1463        iter++;
1464      }
1465      buf= iter.getItem();
1466    }
1467    else
1468    {
1469      buf= 1;
1470      for (long j= 1; j <= N.NumRows(); j++, iter++)
1471      {
1472        if (!IsZero (N (j,i)))
1473          buf= mulMod2 (buf, iter.getItem(), yToL);
1474      }
1475    }
1476    buf *= LC (F, x);
1477    buf= mod (buf, yToL);
1478    buf /= content (buf, x);
1479    if (fdivides (buf, F, quot))
1480    {
1481      factorsFoundIndex[i - 1]= 1;
1482      factorsFound++;
1483      F= quot;
1484      F /= Lc (F);
1485      reconstructedFactors.append (buf);
1486    }
1487    if (degree (F) <= 0)
1488      return;
1489    if (factorsFound + 1 == N.NumCols())
1490    {
1491      reconstructedFactors.append (F);
1492      return;
1493    }
1494  }
1495}
1496
1497void
1498reconstructionTry (CFList& reconstructedFactors, CanonicalForm& F, const CFList&
1499                   factors, const int liftBound, int& factorsFound, int*&
1500                   factorsFoundIndex, mat_zz_p& N, bool beenInThres
1501                  )
1502{
1503  Variable y= Variable (2);
1504  Variable x= Variable (1);
1505  CanonicalForm yToL= power (y, liftBound);
1506  if (factors.length() == 2)
1507  {
1508    CanonicalForm tmp1, tmp2, tmp3;
1509    tmp1= factors.getFirst();
1510    tmp2= factors.getLast();
1511    tmp1 *= LC (F, x);
1512    tmp1= mod (tmp1, yToL);
1513    tmp1 /= content (tmp1, x);
1514    tmp2 *= LC (F, x);
1515    tmp2= mod (tmp2, yToL);
1516    tmp2 /= content (tmp2, x);
1517    tmp3 = tmp1*tmp2;
1518    if (tmp3/Lc (tmp3) == F/Lc (F))
1519    {
1520      factorsFound++;
1521      F= 1;
1522      reconstructedFactors.append (tmp1);
1523      reconstructedFactors.append (tmp2);
1524      return;
1525    }
1526  }
1527  CanonicalForm quot, buf;
1528  CFListIterator iter;
1529  for (long i= 1; i <= N.NumCols(); i++)
1530  {
1531    if (factorsFoundIndex [i - 1] == 1)
1532      continue;
1533    iter= factors;
1534    if (beenInThres)
1535    {
1536      int count= 1;
1537      while (count < i)
1538      {
1539        count++;
1540        iter++;
1541      }
1542      buf= iter.getItem();
1543    }
1544    else
1545    {
1546      buf= 1;
1547      for (long j= 1; j <= N.NumRows(); j++, iter++)
1548      {
1549        if (!IsZero (N (j,i)))
1550          buf= mulMod2 (buf, iter.getItem(), yToL);
1551      }
1552    }
1553    buf *= LC (F, x);
1554    buf= mod (buf, yToL);
1555    buf /= content (buf, x);
1556    if (fdivides (buf, F, quot))
1557    {
1558      factorsFoundIndex[i - 1]= 1;
1559      factorsFound++;
1560      F= quot;
1561      F /= Lc (F);
1562      reconstructedFactors.append (buf);
1563    }
1564    if (degree (F) <= 0)
1565      return;
1566    if (factorsFound + 1 == N.NumCols())
1567    {
1568      reconstructedFactors.append (F);
1569      return;
1570    }
1571  }
1572}
1573
1574#ifdef HAVE_FLINT
1575void
1576reconstructionTry (CFList& reconstructedFactors, CanonicalForm& F, const CFList&
1577                   factors, const int liftBound, int& factorsFound, int*&
1578                   factorsFoundIndex, nmod_mat_t N, bool beenInThres
1579                  )
1580{
1581  Variable y= Variable (2);
1582  Variable x= Variable (1);
1583  CanonicalForm yToL= power (y, liftBound);
1584  if (factors.length() == 2)
1585  {
1586    CanonicalForm tmp1, tmp2, tmp3;
1587    tmp1= factors.getFirst();
1588    tmp2= factors.getLast();
1589    tmp1 *= LC (F, x);
1590    tmp1= mod (tmp1, yToL);
1591    tmp1 /= content (tmp1, x);
1592    tmp2 *= LC (F, x);
1593    tmp2= mod (tmp2, yToL);
1594    tmp2 /= content (tmp2, x);
1595    tmp3 = tmp1*tmp2;
1596    if (tmp3/Lc (tmp3) == F/Lc (F))
1597    {
1598      factorsFound++;
1599      F= 1;
1600      reconstructedFactors.append (tmp1);
1601      reconstructedFactors.append (tmp2);
1602      return;
1603    }
1604  }
1605  CanonicalForm quot, buf;
1606  CFListIterator iter;
1607  for (long i= 0; i < nmod_mat_ncols (N); i++)
1608  {
1609    if (factorsFoundIndex [i] == 1)
1610      continue;
1611    iter= factors;
1612    if (beenInThres)
1613    {
1614      int count= 0;
1615      while (count < i)
1616      {
1617        count++;
1618        iter++;
1619      }
1620      buf= iter.getItem();
1621    }
1622    else
1623    {
1624      buf= 1;
1625      for (long j= 0; j < nmod_mat_nrows (N); j++, iter++)
1626      {
1627        if (!(nmod_mat_entry (N, j, i) == 0))
1628          buf= mulMod2 (buf, iter.getItem(), yToL);
1629      }
1630    }
1631    buf *= LC (F, x);
1632    buf= mod (buf, yToL);
1633    buf /= content (buf, x);
1634    if (fdivides (buf, F, quot))
1635    {
1636      factorsFoundIndex[i]= 1;
1637      factorsFound++;
1638      F= quot;
1639      F /= Lc (F);
1640      reconstructedFactors.append (buf);
1641    }
1642    if (degree (F) <= 0)
1643      return;
1644    if (factorsFound + 1 == nmod_mat_ncols (N))
1645    {
1646      reconstructedFactors.append (F);
1647      return;
1648    }
1649  }
1650}
1651#endif
1652
1653CFList
1654reconstruction (CanonicalForm& G, CFList& factors, int* zeroOneVecs, int
1655                precision, const mat_zz_pE& N
1656               )
1657{
1658  Variable y= Variable (2);
1659  Variable x= Variable (1);
1660  CanonicalForm F= G;
1661  CanonicalForm yToL= power (y, precision);
1662  CanonicalForm quot, buf;
1663  CFList result, factorsConsidered;
1664  CFList bufFactors= factors;
1665  CFListIterator iter;
1666  for (long i= 1; i <= N.NumCols(); i++)
1667  {
1668    if (zeroOneVecs [i - 1] == 0)
1669      continue;
1670    iter= factors;
1671    buf= 1;
1672    factorsConsidered= CFList();
1673    for (long j= 1; j <= N.NumRows(); j++, iter++)
1674    {
1675      if (!IsZero (N (j,i)))
1676      {
1677        factorsConsidered.append (iter.getItem());
1678        buf= mulMod2 (buf, iter.getItem(), yToL);
1679      }
1680    }
1681    buf *= LC (F, x);
1682    buf= mod (buf, yToL);
1683    buf /= content (buf, x);
1684    if (fdivides (buf, F, quot))
1685    {
1686      F= quot;
1687      F /= Lc (F);
1688      result.append (buf);
1689      bufFactors= Difference (bufFactors, factorsConsidered);
1690    }
1691    if (degree (F) <= 0)
1692    {
1693      G= F;
1694      factors= bufFactors;
1695      return result;
1696    }
1697  }
1698  G= F;
1699  factors= bufFactors;
1700  return result;
1701}
1702
1703CFList
1704monicReconstruction (CanonicalForm& G, CFList& factors, int* zeroOneVecs,
1705                     int precision, const mat_zz_pE& N
1706                    )
1707{
1708  Variable y= Variable (2);
1709  Variable x= Variable (1);
1710  CanonicalForm F= G;
1711  CanonicalForm yToL= power (y, precision);
1712  CanonicalForm quot, buf, buf2;
1713  CFList result;
1714  CFList bufFactors= factors;
1715  CFList factorsConsidered;
1716  CFListIterator iter;
1717  for (long i= 1; i <= N.NumCols(); i++)
1718  {
1719    if (zeroOneVecs [i - 1] == 0)
1720      continue;
1721    iter= factors;
1722    buf= 1;
1723    factorsConsidered= CFList();
1724    for (long j= 1; j <= N.NumRows(); j++, iter++)
1725    {
1726      if (!IsZero (N (j,i)))
1727      {
1728        factorsConsidered.append (iter.getItem());
1729        buf= mulMod2 (buf, iter.getItem(), yToL);
1730      }
1731    }
1732    buf2= buf;
1733    buf *= LC (F, x);
1734    buf= mod (buf, yToL);
1735    buf /= content (buf, x);
1736    if (fdivides (buf, F, quot))
1737    {
1738      F= quot;
1739      F /= Lc (F);
1740      result.append (buf2);
1741      bufFactors= Difference (bufFactors, factorsConsidered);
1742    }
1743    if (degree (F) <= 0)
1744    {
1745      G= F;
1746      factors= bufFactors;
1747      return result;
1748    }
1749  }
1750  G= F;
1751  factors= bufFactors;
1752  return result;
1753}
1754
1755CFList
1756extReconstruction (CanonicalForm& G, CFList& factors, int* zeroOneVecs, int
1757                   precision, const mat_zz_p& N, const ExtensionInfo& info,
1758                   const CanonicalForm& evaluation
1759                  )
1760{
1761  Variable y= Variable (2);
1762  Variable x= Variable (1);
1763  Variable alpha= info.getAlpha();
1764  Variable beta= info.getBeta();
1765  int k= info.getGFDegree();
1766  CanonicalForm gamma= info.getGamma();
1767  CanonicalForm delta= info.getDelta();
1768  CanonicalForm F= G;
1769  CanonicalForm yToL= power (y, precision);
1770  CFList result;
1771  CFList bufFactors= factors;
1772  CFList factorsConsidered;
1773  CanonicalForm buf2, quot, buf;
1774  CFListIterator iter;
1775  for (long i= 1; i <= N.NumCols(); i++)
1776  {
1777    if (zeroOneVecs [i - 1] == 0)
1778      continue;
1779    iter= factors;
1780    buf= 1;
1781    factorsConsidered= CFList();
1782    for (long j= 1; j <= N.NumRows(); j++, iter++)
1783    {
1784      if (!IsZero (N (j,i)))
1785      {
1786        factorsConsidered.append (iter.getItem());
1787        buf= mulMod2 (buf, iter.getItem(), yToL);
1788      }
1789    }
1790    buf *= LC (F, x);
1791    buf= mod (buf, yToL);
1792    buf /= content (buf, x);
1793    buf2= buf (y-evaluation, y);
1794    buf2 /= Lc (buf2);
1795    if (!k && beta == x)
1796    {
1797      if (degree (buf2, alpha) < 1)
1798      {
1799        if (fdivides (buf, F, quot))
1800        {
1801          F= quot;
1802          F /= Lc (F);
1803          result.append (buf2);
1804          bufFactors= Difference (bufFactors, factorsConsidered);
1805        }
1806      }
1807    }
1808    else
1809    {
1810      CFList source, dest;
1811
1812      if (!isInExtension (buf2, gamma, k, delta, source, dest))
1813      {
1814        if (fdivides (buf, F, quot))
1815        {
1816          F= quot;
1817          F /= Lc (F);
1818          result.append (buf2);
1819          bufFactors= Difference (bufFactors, factorsConsidered);
1820        }
1821      }
1822    }
1823    if (degree (F) <= 0)
1824    {
1825      G= F;
1826      factors= bufFactors;
1827      return result;
1828    }
1829  }
1830  G= F;
1831  factors= bufFactors;
1832  return result;
1833}
1834
1835#ifdef HAVE_FLINT
1836CFList
1837extReconstruction (CanonicalForm& G, CFList& factors, int* zeroOneVecs, int
1838                   precision, const nmod_mat_t N, const ExtensionInfo& info,
1839                   const CanonicalForm& evaluation
1840                  )
1841{
1842  Variable y= Variable (2);
1843  Variable x= Variable (1);
1844  Variable alpha= info.getAlpha();
1845  Variable beta= info.getBeta();
1846  int k= info.getGFDegree();
1847  CanonicalForm gamma= info.getGamma();
1848  CanonicalForm delta= info.getDelta();
1849  CanonicalForm F= G;
1850  CanonicalForm yToL= power (y, precision);
1851  CFList result;
1852  CFList bufFactors= factors;
1853  CFList factorsConsidered;
1854  CanonicalForm buf2, quot, buf;
1855  CFListIterator iter;
1856  for (long i= 0; i < nmod_mat_ncols(N); i++)
1857  {
1858    if (zeroOneVecs [i] == 0)
1859      continue;
1860    iter= factors;
1861    buf= 1;
1862    factorsConsidered= CFList();
1863    for (long j= 0; j < nmod_mat_ncols(N); j++, iter++)
1864    {
1865      if (!(nmod_mat_entry (N, j, i) == 0))
1866      {
1867        factorsConsidered.append (iter.getItem());
1868        buf= mulMod2 (buf, iter.getItem(), yToL);
1869      }
1870    }
1871    buf *= LC (F, x);
1872    buf= mod (buf, yToL);
1873    buf /= content (buf, x);
1874    buf2= buf (y-evaluation, y);
1875    buf2 /= Lc (buf2);
1876    if (!k && beta == x)
1877    {
1878      if (degree (buf2, alpha) < 1)
1879      {
1880        if (fdivides (buf, F, quot))
1881        {
1882          F= quot;
1883          F /= Lc (F);
1884          result.append (buf2);
1885          bufFactors= Difference (bufFactors, factorsConsidered);
1886        }
1887      }
1888    }
1889    else
1890    {
1891      CFList source, dest;
1892
1893      if (!isInExtension (buf2, gamma, k, delta, source, dest))
1894      {
1895        if (fdivides (buf, F, quot))
1896        {
1897          F= quot;
1898          F /= Lc (F);
1899          result.append (buf2);
1900          bufFactors= Difference (bufFactors, factorsConsidered);
1901        }
1902      }
1903    }
1904    if (degree (F) <= 0)
1905    {
1906      G= F;
1907      factors= bufFactors;
1908      return result;
1909    }
1910  }
1911  G= F;
1912  factors= bufFactors;
1913  return result;
1914}
1915#endif
1916
1917CFList
1918reconstruction (CanonicalForm& G, CFList& factors, int* zeroOneVecs,
1919                int precision, const mat_zz_p& N)
1920{
1921  Variable y= Variable (2);
1922  Variable x= Variable (1);
1923  CanonicalForm F= G;
1924  CanonicalForm yToL= power (y, precision);
1925  CanonicalForm quot, buf;
1926  CFList result;
1927  CFList bufFactors= factors;
1928  CFList factorsConsidered;
1929  CFListIterator iter;
1930  for (long i= 1; i <= N.NumCols(); i++)
1931  {
1932    if (zeroOneVecs [i - 1] == 0)
1933      continue;
1934    iter= factors;
1935    buf= 1;
1936    factorsConsidered= CFList();
1937    for (long j= 1; j <= N.NumRows(); j++, iter++)
1938    {
1939      if (!IsZero (N (j,i)))
1940      {
1941        factorsConsidered.append (iter.getItem());
1942        buf= mulMod2 (buf, iter.getItem(), yToL);
1943      }
1944    }
1945    buf *= LC (F, x);
1946    buf= mod (buf, yToL);
1947    buf /= content (buf, x);
1948    if (fdivides (buf, F, quot))
1949    {
1950      F= quot;
1951      F /= Lc (F);
1952      result.append (buf);
1953      bufFactors= Difference (bufFactors, factorsConsidered);
1954    }
1955    if (degree (F) <= 0)
1956    {
1957      G= F;
1958      factors= bufFactors;
1959      return result;
1960    }
1961  }
1962  G= F;
1963  factors= bufFactors;
1964  return result;
1965}
1966
1967#ifdef HAVE_FLINT
1968CFList
1969reconstruction (CanonicalForm& G, CFList& factors, int* zeroOneVecs,
1970                int precision, const nmod_mat_t N)
1971{
1972  Variable y= Variable (2);
1973  Variable x= Variable (1);
1974  CanonicalForm F= G;
1975  CanonicalForm yToL= power (y, precision);
1976  CanonicalForm quot, buf;
1977  CFList result;
1978  CFList bufFactors= factors;
1979  CFList factorsConsidered;
1980  CFListIterator iter;
1981  for (long i= 0; i < nmod_mat_ncols (N); i++)
1982  {
1983    if (zeroOneVecs [i] == 0)
1984      continue;
1985    iter= factors;
1986    buf= 1;
1987    factorsConsidered= CFList();
1988    for (long j= 0; j < nmod_mat_nrows (N); j++, iter++)
1989    {
1990      if (!(nmod_mat_entry (N, j, i) == 0))
1991      {
1992        factorsConsidered.append (iter.getItem());
1993        buf= mulMod2 (buf, iter.getItem(), yToL);
1994      }
1995    }
1996    buf *= LC (F, x);
1997    buf= mod (buf, yToL);
1998    buf /= content (buf, x);
1999    if (fdivides (buf, F, quot))
2000    {
2001      F= quot;
2002      F /= Lc (F);
2003      result.append (buf);
2004      bufFactors= Difference (bufFactors, factorsConsidered);
2005    }
2006    if (degree (F) <= 0)
2007    {
2008      G= F;
2009      factors= bufFactors;
2010      return result;
2011    }
2012  }
2013  G= F;
2014  factors= bufFactors;
2015  return result;
2016}
2017#endif
2018
2019void
2020extReconstructionTry (CFList& reconstructedFactors, CanonicalForm& F, const
2021                      CFList& factors, const int liftBound, int& factorsFound,
2022                      int*& factorsFoundIndex, mat_zz_p& N, bool beenInThres,
2023                      const ExtensionInfo& info, const CanonicalForm& evaluation
2024                     )
2025{
2026  Variable y= Variable (2);
2027  Variable x= Variable (1);
2028  Variable alpha= info.getAlpha();
2029  Variable beta= info.getBeta();
2030  int k= info.getGFDegree();
2031  CanonicalForm gamma= info.getGamma();
2032  CanonicalForm delta= info.getDelta();
2033  CanonicalForm yToL= power (y, liftBound);
2034  CFList source, dest;
2035  if (factors.length() == 2)
2036  {
2037    CanonicalForm tmp1, tmp2, tmp3;
2038    tmp1= factors.getFirst();
2039    tmp2= factors.getLast();
2040    tmp1 *= LC (F, x);
2041    tmp1= mod (tmp1, yToL);
2042    tmp1 /= content (tmp1, x);
2043    tmp2 *= LC (F, x);
2044    tmp2= mod (tmp2, yToL);
2045    tmp2 /= content (tmp2, x);
2046    tmp3 = tmp1*tmp2;
2047    if (tmp3/Lc (tmp3) == F/Lc (F))
2048    {
2049      tmp1= tmp1 (y - evaluation, y);
2050      tmp2= tmp2 (y - evaluation, y);
2051      tmp1 /= Lc (tmp1);
2052      tmp2 /= Lc (tmp2);
2053      if (!k && beta == x && degree (tmp2, alpha) < 1 &&
2054          degree (tmp1, alpha) < 1)
2055      {
2056        factorsFound++;
2057        F= 1;
2058        tmp1= mapDown (tmp1, info, source, dest);
2059        tmp2= mapDown (tmp2, info, source, dest);
2060        reconstructedFactors.append (tmp1);
2061        reconstructedFactors.append (tmp2);
2062        return;
2063      }
2064      else if (!isInExtension (tmp2, gamma, k, delta, source, dest) &&
2065               !isInExtension (tmp1, gamma, k, delta, source, dest))
2066      {
2067        factorsFound++;
2068        F= 1;
2069        tmp1= mapDown (tmp1, info, source, dest);
2070        tmp2= mapDown (tmp2, info, source, dest);
2071        reconstructedFactors.append (tmp1);
2072        reconstructedFactors.append (tmp2);
2073        return;
2074      }
2075    }
2076  }
2077  CanonicalForm quot, buf, buf2;
2078  CFListIterator iter;
2079  for (long i= 1; i <= N.NumCols(); i++)
2080  {
2081    if (factorsFoundIndex [i - 1] == 1)
2082      continue;
2083    iter= factors;
2084    if (beenInThres)
2085    {
2086      int count= 1;
2087      while (count < i)
2088      {
2089        count++;
2090        iter++;
2091      }
2092      buf= iter.getItem();
2093    }
2094    else
2095    {
2096      buf= 1;
2097      for (long j= 1; j <= N.NumRows(); j++, iter++)
2098      {
2099        if (!IsZero (N (j,i)))
2100          buf= mulMod2 (buf, iter.getItem(), yToL);
2101      }
2102    }
2103    buf *= LC (F, x);
2104    buf= mod (buf, yToL);
2105    buf /= content (buf, x);
2106    buf2= buf (y - evaluation, y);
2107    buf2 /= Lc (buf2);
2108    if (!k && beta == x)
2109    {
2110      if (degree (buf2, alpha) < 1)
2111      {
2112        if (fdivides (buf, F, quot))
2113        {
2114          factorsFoundIndex[i - 1]= 1;
2115          factorsFound++;
2116          F= quot;
2117          F /= Lc (F);
2118          buf2= mapDown (buf2, info, source, dest);
2119          reconstructedFactors.append (buf2);
2120        }
2121      }
2122    }
2123    else
2124    {
2125      if (!isInExtension (buf2, gamma, k, delta, source, dest))
2126      {
2127        if (fdivides (buf, F, quot))
2128        {
2129          factorsFoundIndex[i - 1]= 1;
2130          factorsFound++;
2131          F= quot;
2132          F /= Lc (F);
2133          buf2= mapDown (buf2, info, source, dest);
2134          reconstructedFactors.append (buf2);
2135        }
2136      }
2137    }
2138    if (degree (F) <= 0)
2139      return;
2140    if (factorsFound + 1 == N.NumCols())
2141    {
2142      CanonicalForm tmp= F (y - evaluation, y);
2143      tmp= mapDown (tmp, info, source, dest);
2144      reconstructedFactors.append (tmp);
2145      return;
2146    }
2147  }
2148}
2149
2150#ifdef HAVE_FLINT
2151void
2152extReconstructionTry (CFList& reconstructedFactors, CanonicalForm& F, const
2153                      CFList& factors, const int liftBound, int& factorsFound,
2154                      int*& factorsFoundIndex, nmod_mat_t N, bool beenInThres,
2155                      const ExtensionInfo& info, const CanonicalForm& evaluation
2156                     )
2157{
2158  Variable y= Variable (2);
2159  Variable x= Variable (1);
2160  Variable alpha= info.getAlpha();
2161  Variable beta= info.getBeta();
2162  int k= info.getGFDegree();
2163  CanonicalForm gamma= info.getGamma();
2164  CanonicalForm delta= info.getDelta();
2165  CanonicalForm yToL= power (y, liftBound);
2166  CFList source, dest;
2167  if (factors.length() == 2)
2168  {
2169    CanonicalForm tmp1, tmp2, tmp3;
2170    tmp1= factors.getFirst();
2171    tmp2= factors.getLast();
2172    tmp1 *= LC (F, x);
2173    tmp1= mod (tmp1, yToL);
2174    tmp1 /= content (tmp1, x);
2175    tmp2 *= LC (F, x);
2176    tmp2= mod (tmp2, yToL);
2177    tmp2 /= content (tmp2, x);
2178    tmp3 = tmp1*tmp2;
2179    if (tmp3/Lc (tmp3) == F/Lc (F))
2180    {
2181      tmp1= tmp1 (y - evaluation, y);
2182      tmp2= tmp2 (y - evaluation, y);
2183      tmp1 /= Lc (tmp1);
2184      tmp2 /= Lc (tmp2);
2185      if (!k && beta == x && degree (tmp2, alpha) < 1 &&
2186          degree (tmp1, alpha) < 1)
2187      {
2188        factorsFound++;
2189        F= 1;
2190        tmp1= mapDown (tmp1, info, source, dest);
2191        tmp2= mapDown (tmp2, info, source, dest);
2192        reconstructedFactors.append (tmp1);
2193        reconstructedFactors.append (tmp2);
2194        return;
2195      }
2196      else if (!isInExtension (tmp2, gamma, k, delta, source, dest) &&
2197               !isInExtension (tmp1, gamma, k, delta, source, dest))
2198      {
2199        factorsFound++;
2200        F= 1;
2201        tmp1= mapDown (tmp1, info, source, dest);
2202        tmp2= mapDown (tmp2, info, source, dest);
2203        reconstructedFactors.append (tmp1);
2204        reconstructedFactors.append (tmp2);
2205        return;
2206      }
2207    }
2208  }
2209  CanonicalForm quot, buf, buf2;
2210  CFListIterator iter;
2211  for (long i= 0; i < nmod_mat_ncols (N); i++)
2212  {
2213    if (factorsFoundIndex [i] == 1)
2214      continue;
2215    iter= factors;
2216    if (beenInThres)
2217    {
2218      int count= 0;
2219      while (count < i)
2220      {
2221        count++;
2222        iter++;
2223      }
2224      buf= iter.getItem();
2225    }
2226    else
2227    {
2228      buf= 1;
2229      for (long j= 0; j < nmod_mat_nrows (N); j++, iter++)
2230      {
2231        if (!(nmod_mat_entry (N, j, i) == 0))
2232          buf= mulMod2 (buf, iter.getItem(), yToL);
2233      }
2234    }
2235    buf *= LC (F, x);
2236    buf= mod (buf, yToL);
2237    buf /= content (buf, x);
2238    buf2= buf (y - evaluation, y);
2239    buf2 /= Lc (buf2);
2240    if (!k && beta == x)
2241    {
2242      if (degree (buf2, alpha) < 1)
2243      {
2244        if (fdivides (buf, F, quot))
2245        {
2246          factorsFoundIndex[i]= 1;
2247          factorsFound++;
2248          F= quot;
2249          F /= Lc (F);
2250          buf2= mapDown (buf2, info, source, dest);
2251          reconstructedFactors.append (buf2);
2252        }
2253      }
2254    }
2255    else
2256    {
2257      if (!isInExtension (buf2, gamma, k, delta, source, dest))
2258      {
2259        if (fdivides (buf, F, quot))
2260        {
2261          factorsFoundIndex[i]= 1;
2262          factorsFound++;
2263          F= quot;
2264          F /= Lc (F);
2265          buf2= mapDown (buf2, info, source, dest);
2266          reconstructedFactors.append (buf2);
2267        }
2268      }
2269    }
2270    if (degree (F) <= 0)
2271      return;
2272    if (factorsFound + 1 == nmod_mat_nrows (N))
2273    {
2274      CanonicalForm tmp= F (y - evaluation, y);
2275      tmp= mapDown (tmp, info, source, dest);
2276      reconstructedFactors.append (tmp);
2277      return;
2278    }
2279  }
2280}
2281#endif
2282
2283//over Fp
2284int
2285liftAndComputeLattice (const CanonicalForm& F, int* bounds, int sizeBounds, int
2286                       start, int liftBound, int minBound, CFList& factors,
2287                       mat_zz_p& NTLN, CFList& diophant, CFMatrix& M, CFArray&
2288                       Pi, CFArray& bufQ, bool& irreducible
2289                      )
2290{
2291  CanonicalForm LCF= LC (F, 1);
2292  CFArray *A= new CFArray [factors.length() - 1];
2293  bool wasInBounds= false;
2294  bool hitBound= false;
2295  int l= (minBound+1)*2;
2296  int stepSize= 2;
2297  int oldL= l/2;
2298  bool reduced= false;
2299  mat_zz_p NTLK, *NTLC;
2300  CFMatrix C;
2301  CFArray buf;
2302  CFListIterator j;
2303  CanonicalForm truncF;
2304  Variable y= F.mvar();
2305  while (l <= liftBound)
2306  {
2307    if (start)
2308    {
2309      henselLiftResume12 (F, factors, start, l, Pi, diophant, M);
2310      start= 0;
2311    }
2312    else
2313    {
2314      if (wasInBounds)
2315        henselLiftResume12 (F, factors, oldL, l, Pi, diophant, M);
2316      else
2317        henselLift12 (F, factors, l, Pi, diophant, M);
2318    }
2319
2320    factors.insert (LCF);
2321    j= factors;
2322    j++;
2323
2324    truncF= mod (F, power (y, l));
2325    for (int i= 0; i < factors.length() - 1; i++, j++)
2326    {
2327      if (!wasInBounds)
2328        A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ[i]);
2329      else
2330        A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
2331                                     bufQ[i]);
2332    }
2333
2334    for (int i= 0; i < sizeBounds; i++)
2335    {
2336      if (bounds [i] + 1 <= l/2)
2337      {
2338        wasInBounds= true;
2339        int k= tmin (bounds [i] + 1, l/2);
2340        C= CFMatrix (l - k, factors.length() - 1);
2341        for (int ii= 0; ii < factors.length() - 1; ii++)
2342        {
2343          if (A[ii].size() - 1 >= i)
2344          {
2345            buf= getCoeffs (A[ii] [i], k);
2346            writeInMatrix (C, buf, ii + 1, 0);
2347          }
2348        }
2349        NTLC= convertFacCFMatrix2NTLmat_zz_p(C);
2350        NTLK= (*NTLC)*NTLN;
2351        transpose (NTLK, NTLK);
2352        kernel (NTLK, NTLK);
2353        transpose (NTLK, NTLK);
2354        NTLN *= NTLK;
2355
2356        if (NTLN.NumCols() == 1)
2357        {
2358          irreducible= true;
2359          break;
2360        }
2361        if (isReduced (NTLN) && l > (minBound+1)*2)
2362        {
2363          reduced= true;
2364          break;
2365        }
2366      }
2367    }
2368
2369    if (irreducible)
2370      break;
2371    if (reduced)
2372      break;
2373    oldL= l;
2374    l += stepSize;
2375    stepSize *= 2;
2376    if (l > liftBound)
2377    {
2378      if (!hitBound)
2379      {
2380        l= liftBound;
2381        hitBound= true;
2382      }
2383      else
2384        break;
2385    }
2386  }
2387  delete [] A;
2388  if (!wasInBounds)
2389  {
2390    if (start)
2391      henselLiftResume12 (F, factors, start, degree (F) + 1, Pi, diophant, M);
2392    else
2393      henselLift12 (F, factors, degree (F) + 1, Pi, diophant, M);
2394    factors.insert (LCF);
2395  }
2396  return l;
2397}
2398
2399#ifdef HAVE_FLINT
2400int
2401liftAndComputeLattice (const CanonicalForm& F, int* bounds, int sizeBounds, int
2402                       start, int liftBound, int minBound, CFList& factors,
2403                       nmod_mat_t FLINTN, CFList& diophant, CFMatrix& M,CFArray&
2404                       Pi, CFArray& bufQ, bool& irreducible
2405                      )
2406{
2407  CanonicalForm LCF= LC (F, 1);
2408  CFArray *A= new CFArray [factors.length() - 1];
2409  bool wasInBounds= false;
2410  bool hitBound= false;
2411  int l= (minBound+1)*2;
2412  int stepSize= 2;
2413  int oldL= l/2;
2414  bool reduced= false;
2415  long rank;
2416  nmod_mat_t FLINTK, FLINTC, null;
2417  CFMatrix C;
2418  CFArray buf;
2419  CFListIterator j;
2420  CanonicalForm truncF;
2421  Variable y= F.mvar();
2422  while (l <= liftBound)
2423  {
2424    if (start)
2425    {
2426      henselLiftResume12 (F, factors, start, l, Pi, diophant, M);
2427      start= 0;
2428    }
2429    else
2430    {
2431      if (wasInBounds)
2432        henselLiftResume12 (F, factors, oldL, l, Pi, diophant, M);
2433      else
2434        henselLift12 (F, factors, l, Pi, diophant, M);
2435    }
2436
2437    factors.insert (LCF);
2438    j= factors;
2439    j++;
2440
2441    truncF= mod (F, power (y, l));
2442    for (int i= 0; i < factors.length() - 1; i++, j++)
2443    {
2444      if (!wasInBounds)
2445        A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ[i]);
2446      else
2447        A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
2448                                     bufQ[i]);
2449    }
2450
2451    for (int i= 0; i < sizeBounds; i++)
2452    {
2453      if (bounds [i] + 1 <= l/2)
2454      {
2455        wasInBounds= true;
2456        int k= tmin (bounds [i] + 1, l/2);
2457        C= CFMatrix (l - k, factors.length() - 1);
2458        for (int ii= 0; ii < factors.length() - 1; ii++)
2459        {
2460          if (A[ii].size() - 1 >= i)
2461          {
2462            buf= getCoeffs (A[ii] [i], k);
2463            writeInMatrix (C, buf, ii + 1, 0);
2464          }
2465        }
2466
2467        convertFacCFMatrix2nmod_mat_t (FLINTC, C);
2468        nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
2469                       getCharacteristic());
2470        nmod_mat_mul (FLINTK, FLINTC, FLINTN);
2471        nmod_mat_init (null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
2472                       getCharacteristic());
2473        rank= nmod_mat_nullspace (null, FLINTK);
2474        nmod_mat_clear (FLINTK);
2475        nmod_mat_window_init (FLINTK, null, 0, 0, nmod_mat_nrows(null), rank);
2476        nmod_mat_clear (FLINTC);
2477        nmod_mat_init_set (FLINTC, FLINTN);
2478        nmod_mat_clear (FLINTN);
2479        nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
2480                       getCharacteristic());
2481        nmod_mat_mul (FLINTN, FLINTC, FLINTK); //no aliasing allowed!!
2482
2483        nmod_mat_clear (FLINTC);
2484        nmod_mat_window_clear (FLINTK);
2485        nmod_mat_clear (null);
2486        if (nmod_mat_ncols (FLINTN) == 1)
2487        {
2488          irreducible= true;
2489          break;
2490        }
2491        if (isReduced (FLINTN) && l > (minBound+1)*2)
2492        {
2493          reduced= true;
2494          break;
2495        }
2496      }
2497    }
2498
2499    if (irreducible)
2500      break;
2501    if (reduced)
2502      break;
2503    oldL= l;
2504    l += stepSize;
2505    stepSize *= 2;
2506    if (l > liftBound)
2507    {
2508      if (!hitBound)
2509      {
2510        l= liftBound;
2511        hitBound= true;
2512      }
2513      else
2514        break;
2515    }
2516  }
2517  delete [] A;
2518  if (!wasInBounds)
2519  {
2520    if (start)
2521      henselLiftResume12 (F, factors, start, degree (F) + 1, Pi, diophant, M);
2522    else
2523      henselLift12 (F, factors, degree (F) + 1, Pi, diophant, M);
2524    factors.insert (LCF);
2525  }
2526  return l;
2527}
2528#endif
2529
2530//over field extension
2531int
2532extLiftAndComputeLattice (const CanonicalForm& F, int* bounds, int sizeBounds,
2533                          int liftBound, int minBound, int start, CFList&
2534                          factors, mat_zz_p& NTLN, CFList& diophant,
2535                          CFMatrix& M, CFArray& Pi, CFArray& bufQ, bool&
2536                          irreducible, const CanonicalForm& evaluation, const
2537                          ExtensionInfo& info, CFList& source, CFList& dest
2538                         )
2539{
2540  bool GF= (CFFactory::gettype()==GaloisFieldDomain);
2541  CanonicalForm LCF= LC (F, 1);
2542  CFArray *A= new CFArray [factors.length() - 1];
2543  bool wasInBounds= false;
2544  bool hitBound= false;
2545  int degMipo;
2546  Variable alpha;
2547  alpha= info.getAlpha();
2548  degMipo= degree (getMipo (alpha));
2549
2550  Variable gamma= info.getBeta();
2551  CanonicalForm primElemAlpha= info.getGamma();
2552  CanonicalForm imPrimElemAlpha= info.getDelta();
2553
2554  int stepSize= 2;
2555  int l= ((minBound+1)/degMipo+1)*2;
2556  l= tmax (l, 2);
2557  if (start > l)
2558    l= start;
2559  int oldL= l/2;
2560  bool reduced= false;
2561  Variable y= F.mvar();
2562  Variable x= Variable (1);
2563  CanonicalForm powX, imBasis, truncF;
2564  CFMatrix Mat, C;
2565  CFArray buf;
2566  CFIterator iter;
2567  mat_zz_p* NTLMat, *NTLC, NTLK;
2568  CFListIterator j;
2569  while (l <= liftBound)
2570  {
2571    if (start)
2572    {
2573      henselLiftResume12 (F, factors, start, l, Pi, diophant, M);
2574      start= 0;
2575    }
2576    else
2577    {
2578      if (wasInBounds)
2579        henselLiftResume12 (F, factors, oldL, l, Pi, diophant, M);
2580      else
2581        henselLift12 (F, factors, l, Pi, diophant, M);
2582    }
2583
2584    factors.insert (LCF);
2585
2586    if (GF)
2587      setCharacteristic (getCharacteristic());
2588
2589    powX= power (y-gamma, l);
2590    Mat= CFMatrix (l*degMipo, l*degMipo);
2591    for (int i= 0; i < l*degMipo; i++)
2592    {
2593      imBasis= mod (power (y, i), powX);
2594      imBasis= imBasis (power (y, degMipo), y);
2595      imBasis= imBasis (y, gamma);
2596      iter= imBasis;
2597      for (; iter.hasTerms(); iter++)
2598        Mat (iter.exp()+ 1, i+1)= iter.coeff();
2599    }
2600
2601    NTLMat= convertFacCFMatrix2NTLmat_zz_p (Mat);
2602    *NTLMat= inv (*NTLMat);
2603
2604    if (GF)
2605      setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
2606
2607    j= factors;
2608    j++;
2609
2610    truncF= mod (F, power (y, l));
2611    for (int i= 0; i < factors.length() - 1; i++, j++)
2612    {
2613      if (!wasInBounds)
2614        A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ[i]);
2615      else
2616        A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
2617                                     bufQ[i]);
2618    }
2619
2620    for (int i= 0; i < sizeBounds; i++)
2621    {
2622      if (bounds [i] + 1 <= (l/2)*degMipo)
2623      {
2624        wasInBounds= true;
2625        int k= tmin (bounds [i] + 1, (l/2)*degMipo);
2626        C= CFMatrix (l*degMipo - k, factors.length() - 1);
2627
2628        for (int ii= 0; ii < factors.length() - 1; ii++)
2629        {
2630          if (A[ii].size() - 1 >= i)
2631          {
2632            if (GF)
2633            {
2634              A [ii] [i]= A [ii] [i] (y-evaluation, y);
2635              setCharacteristic (getCharacteristic());
2636              A[ii] [i]= GF2FalphaRep (A[ii] [i], alpha);
2637              if (alpha != gamma)
2638                A [ii] [i]= mapDown (A[ii] [i], imPrimElemAlpha, primElemAlpha,
2639                                     gamma, source, dest
2640                                    );
2641              buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, *NTLMat);
2642            }
2643            else
2644            {
2645              A [ii] [i]= A [ii] [i] (y-evaluation, y);
2646              if (alpha != gamma)
2647                A[ii] [i]= mapDown (A[ii] [i], imPrimElemAlpha, primElemAlpha,
2648                                    gamma, source, dest
2649                                   );
2650              buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, *NTLMat);
2651            }
2652            writeInMatrix (C, buf, ii + 1, 0);
2653          }
2654          if (GF)
2655            setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
2656        }
2657
2658        if (GF)
2659          setCharacteristic(getCharacteristic());
2660
2661        NTLC= convertFacCFMatrix2NTLmat_zz_p(C);
2662        NTLK= (*NTLC)*NTLN;
2663        transpose (NTLK, NTLK);
2664        kernel (NTLK, NTLK);
2665        transpose (NTLK, NTLK);
2666        NTLN *= NTLK;
2667
2668        if (GF)
2669          setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
2670
2671        if (NTLN.NumCols() == 1)
2672        {
2673          irreducible= true;
2674          break;
2675        }
2676        if (isReduced (NTLN))
2677        {
2678          reduced= true;
2679          break;
2680        }
2681      }
2682    }
2683
2684    if (NTLN.NumCols() == 1)
2685    {
2686      irreducible= true;
2687      break;
2688    }
2689    if (reduced)
2690      break;
2691    oldL= l;
2692    l += stepSize;
2693    stepSize *= 2;
2694    if (l > liftBound)
2695    {
2696      if (!hitBound)
2697      {
2698        l= liftBound;
2699        hitBound= true;
2700      }
2701      else
2702        break;
2703    }
2704  }
2705  delete [] A;
2706  if (!wasInBounds)
2707  {
2708    if (start)
2709      henselLiftResume12 (F, factors, start, degree (F) + 1, Pi, diophant, M);
2710    else
2711      henselLift12 (F, factors, degree (F) + 1, Pi, diophant, M);
2712    factors.insert (LCF);
2713  }
2714  return l;
2715}
2716
2717/*#ifdef HAVE_FLINT
2718//over field extension
2719int
2720extLiftAndComputeLattice (const CanonicalForm& F, int* bounds, int sizeBounds,
2721                          int liftBound, int minBound, int start, CFList&
2722                          factors, nmod_mat_t FLINTN, CFList& diophant,
2723                          CFMatrix& M, CFArray& Pi, CFArray& bufQ, bool&
2724                          irreducible, const CanonicalForm& evaluation, const
2725                          ExtensionInfo& info, CFList& source, CFList& dest
2726                         )
2727{
2728  bool GF= (CFFactory::gettype()==GaloisFieldDomain);
2729  CanonicalForm LCF= LC (F, 1);
2730  CFArray *A= new CFArray [factors.length() - 1];
2731  bool wasInBounds= false;
2732  bool hitBound= false;
2733  int degMipo;
2734  Variable alpha;
2735  alpha= info.getAlpha();
2736  degMipo= degree (getMipo (alpha));
2737
2738  Variable gamma= info.getBeta();
2739  CanonicalForm primElemAlpha= info.getGamma();
2740  CanonicalForm imPrimElemAlpha= info.getDelta();
2741
2742  int stepSize= 2;
2743  int l= ((minBound+1)/degMipo+1)*2;
2744  l= tmax (l, 2);
2745  if (start > l)
2746    l= start;
2747  int oldL= l/2;
2748  bool reduced= false;
2749  Variable y= F.mvar();
2750  Variable x= Variable (1);
2751  CanonicalForm powX, imBasis, truncF;
2752  CFMatrix Mat, C;
2753  CFArray buf;
2754  CFIterator iter;
2755  long rank;
2756  nmod_mat_t FLINTMat, FLINTMatInv, FLINTC, FLINTK, null;
2757  CFListIterator j;
2758  while (l <= liftBound)
2759  {
2760    if (start)
2761    {
2762      henselLiftResume12 (F, factors, start, l, Pi, diophant, M);
2763      start= 0;
2764    }
2765    else
2766    {
2767      if (wasInBounds)
2768        henselLiftResume12 (F, factors, oldL, l, Pi, diophant, M);
2769      else
2770        henselLift12 (F, factors, l, Pi, diophant, M);
2771    }
2772
2773    factors.insert (LCF);
2774
2775    if (GF)
2776      setCharacteristic (getCharacteristic());
2777
2778    powX= power (y-gamma, l);
2779    Mat= CFMatrix (l*degMipo, l*degMipo);
2780    for (int i= 0; i < l*degMipo; i++)
2781    {
2782      imBasis= mod (power (y, i), powX);
2783      imBasis= imBasis (power (y, degMipo), y);
2784      imBasis= imBasis (y, gamma);
2785      iter= imBasis;
2786      for (; iter.hasTerms(); iter++)
2787        Mat (iter.exp()+ 1, i+1)= iter.coeff();
2788    }
2789
2790    convertFacCFMatrix2nmod_mat_t (FLINTMat, Mat);
2791    nmod_mat_init (FLINTMatInv, nmod_mat_nrows (FLINTMat),
2792                   nmod_mat_nrows (FLINTMat), getCharacteristic());
2793    nmod_mat_inv (FLINTMatInv, FLINTMat);
2794
2795    if (GF)
2796      setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
2797
2798    j= factors;
2799    j++;
2800
2801    truncF= mod (F, power (y, l));
2802    for (int i= 0; i < factors.length() - 1; i++, j++)
2803    {
2804      if (!wasInBounds)
2805        A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ[i]);
2806      else
2807        A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
2808                                     bufQ[i]);
2809    }
2810
2811    for (int i= 0; i < sizeBounds; i++)
2812    {
2813      if (bounds [i] + 1 <= (l/2)*degMipo)
2814      {
2815        wasInBounds= true;
2816        int k= tmin (bounds [i] + 1, (l/2)*degMipo);
2817        C= CFMatrix (l*degMipo - k, factors.length() - 1);
2818
2819        for (int ii= 0; ii < factors.length() - 1; ii++)
2820        {
2821          if (A[ii].size() - 1 >= i)
2822          {
2823            if (GF)
2824            {
2825              A [ii] [i]= A [ii] [i] (y-evaluation, y);
2826              setCharacteristic (getCharacteristic());
2827              A[ii] [i]= GF2FalphaRep (A[ii] [i], alpha);
2828              if (alpha != gamma)
2829                A [ii] [i]= mapDown (A[ii] [i], imPrimElemAlpha, primElemAlpha,
2830                                     gamma, source, dest
2831                                    );
2832              buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, FLINTMatInv); //TODO
2833            }
2834            else
2835            {
2836              A [ii] [i]= A [ii] [i] (y-evaluation, y);
2837              if (alpha != gamma)
2838                A[ii] [i]= mapDown (A[ii] [i], imPrimElemAlpha, primElemAlpha,
2839                                    gamma, source, dest
2840                                   );
2841              buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, FLINTMatInv); //TODO
2842            }
2843            writeInMatrix (C, buf, ii + 1, 0);
2844          }
2845          if (GF)
2846            setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
2847        }
2848
2849        if (GF)
2850          setCharacteristic(getCharacteristic());
2851
2852        convertFacCFMatrix2nmod_mat_t (FLINTC, C);
2853        nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
2854                       getCharacteristic());
2855        nmod_mat_mul (FLINTK, FLINTC, FLINTN);
2856        nmod_mat_init (null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
2857                       getCharacteristic());
2858        rank= nmod_mat_nullspace (null, FLINTK);
2859        nmod_mat_clear (FLINTK);
2860        nmod_mat_window_init (FLINTK, null, 0, 0, nmod_mat_nrows(null), rank);
2861        nmod_mat_clear (FLINTC);
2862        nmod_mat_init_set (FLINTC, FLINTN);
2863        nmod_mat_clear (FLINTN);
2864        nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
2865                       getCharacteristic());
2866        nmod_mat_mul (FLINTN, FLINTC, FLINTK); //no aliasing allowed!!
2867
2868        nmod_mat_clear (FLINTC);
2869        nmod_mat_window_clear (FLINTK);
2870        nmod_mat_clear (null);
2871
2872        if (GF)
2873          setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
2874
2875        if (nmod_mat_ncols (FLINTN) == 1)
2876        {
2877          irreducible= true;
2878          break;
2879        }
2880        if (isReduced (FLINTN))
2881        {
2882          reduced= true;
2883          break;
2884        }
2885      }
2886    }
2887
2888    nmod_mat_clear (FLINTMat);
2889    nmod_mat_clear (FLINTMatInv);
2890
2891    if (nmod_mat_ncols (FLINTN) == 1)
2892    {
2893      irreducible= true;
2894      break;
2895    }
2896    if (reduced)
2897      break;
2898    oldL= l;
2899    l += stepSize;
2900    stepSize *= 2;
2901    if (l > liftBound)
2902    {
2903      if (!hitBound)
2904      {
2905        l= liftBound;
2906        hitBound= true;
2907      }
2908      else
2909        break;
2910    }
2911  }
2912  delete [] A;
2913  if (!wasInBounds)
2914  {
2915    if (start)
2916      henselLiftResume12 (F, factors, start, degree (F) + 1, Pi, diophant, M);
2917    else
2918      henselLift12 (F, factors, degree (F) + 1, Pi, diophant, M);
2919    factors.insert (LCF);
2920  }
2921  return l;
2922}
2923#endif*/
2924
2925// over Fq
2926int
2927liftAndComputeLattice (const CanonicalForm& F, int* bounds, int sizeBounds,
2928                       int start, int liftBound, int minBound, CFList& factors,
2929                       mat_zz_pE& NTLN, CFList& diophant, CFMatrix& M, CFArray&
2930                       Pi, CFArray& bufQ, bool& irreducible
2931                      )
2932{
2933  CanonicalForm LCF= LC (F, 1);
2934  CFArray *A= new CFArray [factors.length() - 1];
2935  bool wasInBounds= false;
2936  bool hitBound= false;
2937  int l= (minBound+1)*2;
2938  int stepSize= 2;
2939  int oldL= l/2;
2940  bool reduced= false;
2941  CFListIterator j;
2942  mat_zz_pE* NTLC, NTLK;
2943  CFArray buf;
2944  CFMatrix C;
2945  Variable y= F.mvar();
2946  CanonicalForm truncF;
2947  while (l <= liftBound)
2948  {
2949    if (start)
2950    {
2951      henselLiftResume12 (F, factors, start, l, Pi, diophant, M);
2952      start= 0;
2953    }
2954    else
2955    {
2956      if (wasInBounds)
2957        henselLiftResume12 (F, factors, oldL, l, Pi, diophant, M);
2958      else
2959        henselLift12 (F, factors, l, Pi, diophant, M);
2960    }
2961
2962    factors.insert (LCF);
2963    j= factors;
2964    j++;
2965
2966    truncF= mod (F, power (y,l));
2967    for (int i= 0; i < factors.length() - 1; i++, j++)
2968    {
2969      if (l == (minBound+1)*2)
2970      {
2971        A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ[i]);
2972      }
2973      else
2974      {
2975        A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
2976                                     bufQ[i]
2977                                    );
2978      }
2979    }
2980
2981    for (int i= 0; i < sizeBounds; i++)
2982    {
2983      if (bounds [i] + 1 <= l/2)
2984      {
2985        wasInBounds= true;
2986        int k= tmin (bounds [i] + 1, l/2);
2987        C= CFMatrix (l - k, factors.length() - 1);
2988        for (int ii= 0; ii < factors.length() - 1; ii++)
2989        {
2990
2991          if (A[ii].size() - 1 >= i)
2992          {
2993            buf= getCoeffs (A[ii] [i], k);
2994            writeInMatrix (C, buf, ii + 1, 0);
2995          }
2996        }
2997
2998        NTLC= convertFacCFMatrix2NTLmat_zz_pE(C);
2999        NTLK= (*NTLC)*NTLN;
3000        transpose (NTLK, NTLK);
3001        kernel (NTLK, NTLK);
3002        transpose (NTLK, NTLK);
3003        NTLN *= NTLK;
3004
3005        if (NTLN.NumCols() == 1)
3006        {
3007          irreducible= true;
3008          break;
3009        }
3010        if (isReduced (NTLN) && l > (minBound+1)*2)
3011        {
3012          reduced= true;
3013          break;
3014        }
3015      }
3016    }
3017
3018    if (NTLN.NumCols() == 1)
3019    {
3020      irreducible= true;
3021      break;
3022    }
3023    if (reduced)
3024      break;
3025    oldL= l;
3026    l += stepSize;
3027    stepSize *= 2;
3028    if (l > liftBound)
3029    {
3030      if (!hitBound)
3031      {
3032        l= liftBound;
3033        hitBound= true;
3034      }
3035      else
3036        break;
3037    }
3038  }
3039  delete [] A;
3040  if (!wasInBounds)
3041  {
3042    if (start)
3043      henselLiftResume12 (F, factors, start, degree (F) + 1, Pi, diophant, M);
3044    else
3045      henselLift12 (F, factors, degree (F) + 1, Pi, diophant, M);
3046    factors.insert (LCF);
3047  }
3048  return l;
3049}
3050
3051#ifdef HAVE_FLINT
3052int
3053liftAndComputeLatticeFq2Fp (const CanonicalForm& F, int* bounds, int sizeBounds,
3054                            int start, int liftBound, int minBound, CFList&
3055                            factors, nmod_mat_t FLINTN, CFList& diophant,
3056                            CFMatrix& M, CFArray& Pi, CFArray& bufQ, bool&
3057                            irreducible, const Variable& alpha
3058                           )
3059#else
3060int
3061liftAndComputeLatticeFq2Fp (const CanonicalForm& F, int* bounds, int sizeBounds,
3062                            int start, int liftBound, int minBound, CFList&
3063                            factors, mat_zz_p& NTLN, CFList& diophant, CFMatrix&
3064                            M, CFArray& Pi, CFArray& bufQ, bool& irreducible,
3065                            const Variable& alpha
3066                           )
3067#endif
3068{
3069  CanonicalForm LCF= LC (F, 1);
3070  CFArray *A= new CFArray [factors.length() - 1];
3071  bool wasInBounds= false;
3072  int l= (minBound+1)*2;
3073  int oldL= l/2;
3074  int stepSize= 2;
3075  bool hitBound= false;
3076  int extensionDeg= degree (getMipo (alpha));
3077  bool reduced= false;
3078  CFListIterator j;
3079  CFMatrix C;
3080  CFArray buf;
3081#ifdef HAVE_FLINT
3082  long rank;
3083  nmod_mat_t FLINTC, FLINTK, null;
3084#else
3085  mat_zz_p* NTLC, NTLK;
3086#endif
3087  Variable y= F.mvar();
3088  CanonicalForm truncF;
3089  while (l <= liftBound)
3090  {
3091    if (start)
3092    {
3093      henselLiftResume12 (F, factors, start, l, Pi, diophant, M);
3094      start= 0;
3095    }
3096    else
3097    {
3098      if (wasInBounds)
3099        henselLiftResume12 (F, factors, oldL, l, Pi, diophant, M);
3100      else
3101        henselLift12 (F, factors, l, Pi, diophant, M);
3102    }
3103
3104    factors.insert (LCF);
3105    j= factors;
3106    j++;
3107
3108    truncF= mod (F, power (y,l));
3109    for (int i= 0; i < factors.length() - 1; i++, j++)
3110    {
3111      if (l == (minBound+1)*2)
3112      {
3113        A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ[i]);
3114      }
3115      else
3116      {
3117        A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
3118                                     bufQ[i]
3119                                    );
3120      }
3121    }
3122
3123    for (int i= 0; i < sizeBounds; i++)
3124    {
3125      if (bounds [i] + 1 <= l/2)
3126      {
3127        wasInBounds= true;
3128        int k= tmin (bounds [i] + 1, l/2);
3129        C= CFMatrix ((l - k)*extensionDeg, factors.length() - 1);
3130        for (int ii= 0; ii < factors.length() - 1; ii++)
3131        {
3132          if (A[ii].size() - 1 >= i)
3133          {
3134            buf= getCoeffs (A[ii] [i], k, alpha);
3135            writeInMatrix (C, buf, ii + 1, 0);
3136          }
3137        }
3138
3139#ifdef HAVE_FLINT
3140        convertFacCFMatrix2nmod_mat_t (FLINTC, C);
3141        nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
3142                       getCharacteristic());
3143        nmod_mat_mul (FLINTK, FLINTC, FLINTN);
3144        nmod_mat_init (null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
3145                       getCharacteristic());
3146        rank= nmod_mat_nullspace (null, FLINTK);
3147        nmod_mat_clear (FLINTK);
3148        nmod_mat_window_init (FLINTK, null, 0, 0, nmod_mat_nrows(null), rank);
3149        nmod_mat_clear (FLINTC);
3150        nmod_mat_init_set (FLINTC, FLINTN);
3151        nmod_mat_clear (FLINTN);
3152        nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
3153                       getCharacteristic());
3154        nmod_mat_mul (FLINTN, FLINTC, FLINTK); //no aliasing allowed!!
3155
3156        nmod_mat_clear (FLINTC);
3157        nmod_mat_window_clear (FLINTK);
3158        nmod_mat_clear (null);
3159#else
3160        NTLC= convertFacCFMatrix2NTLmat_zz_p(C);
3161        NTLK= (*NTLC)*NTLN;
3162        transpose (NTLK, NTLK);
3163        kernel (NTLK, NTLK);
3164        transpose (NTLK, NTLK);
3165        NTLN *= NTLK;
3166#endif
3167
3168#ifdef HAVE_FLINT
3169        if (nmod_mat_nrows (FLINTN) == 1)
3170#else
3171        if (NTLN.NumCols() == 1)
3172#endif
3173        {
3174          irreducible= true;
3175          break;
3176        }
3177#ifdef HAVE_FLINT
3178        if (isReduced (FLINTN) && l > (minBound+1)*2)
3179#else
3180        if (isReduced (NTLN) && l > (minBound+1)*2)
3181#endif
3182        {
3183          reduced= true;
3184          break;
3185        }
3186      }
3187    }
3188
3189#ifdef HAVE_FLINT
3190    if (nmod_mat_ncols (FLINTN) == 1)
3191#else
3192    if (NTLN.NumCols() == 1)
3193#endif
3194    {
3195      irreducible= true;
3196      break;
3197    }
3198    if (reduced)
3199      break;
3200    oldL= l;
3201    l += stepSize;
3202    stepSize *= 2;
3203    if (l > liftBound)
3204    {
3205      if (!hitBound)
3206      {
3207        l= liftBound;
3208        hitBound= true;
3209      }
3210      else
3211        break;
3212    }
3213  }
3214  delete [] A;
3215  if (!wasInBounds)
3216  {
3217    if (start)
3218      henselLiftResume12 (F, factors, start, degree (F) + 1, Pi, diophant, M);
3219    else
3220      henselLift12 (F, factors, degree (F) + 1, Pi, diophant, M);
3221    factors.insert (LCF);
3222  }
3223  return l;
3224}
3225
3226CFList
3227increasePrecision (CanonicalForm& F, CFList& factors, int factorsFound,
3228                   int oldNumCols, int oldL, int precision
3229                  )
3230{
3231  int d;
3232  bool isIrreducible= false;
3233  int* bounds= computeBounds (F, d, isIrreducible);
3234  if (isIrreducible)
3235  {
3236    delete [] bounds;
3237    CanonicalForm G= F;
3238    F= 1;
3239    return CFList (G);
3240  }
3241  CFArray * A= new CFArray [factors.length()];
3242  CFArray bufQ= CFArray (factors.length());
3243#ifdef HAVE_FLINT
3244  nmod_mat_t FLINTN;
3245  nmod_mat_init (FLINTN,factors.length(),factors.length(), getCharacteristic());
3246  for (long i=factors.length()-1; i >= 0; i--)
3247    nmod_mat_entry (FLINTN, i, i)= 1;
3248#else
3249  mat_zz_p NTLN;
3250  ident (NTLN, factors.length());
3251#endif
3252  int minBound= bounds[0];
3253  for (int i= 1; i < d; i++)
3254  {
3255    if (bounds[i] != 0)
3256      minBound= tmin (minBound, bounds[i]);
3257  }
3258  int l= tmax (2*(minBound + 1), oldL);
3259  int oldL2= l/2;
3260  int stepSize= 2;
3261  bool useOldQs= false;
3262  bool hitBound= false;
3263  CFListIterator j;
3264  CFMatrix C;
3265  CFArray buf;
3266#ifdef HAVE_FLINT
3267  long rank;
3268  nmod_mat_t FLINTC, FLINTK, null;
3269#else
3270  mat_zz_p* NTLC, NTLK;
3271#endif
3272  Variable y= F.mvar();
3273  CanonicalForm truncF;
3274  while (l <= precision)
3275  {
3276    j= factors;
3277    truncF= mod (F, power (y,l));
3278    if (useOldQs)
3279    {
3280      for (int i= 0; i < factors.length(); i++, j++)
3281        A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL2, bufQ[i],
3282                                     bufQ[i]
3283                                    );
3284    }
3285    else
3286    {
3287      for (int i= 0; i < factors.length(); i++, j++)
3288        A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ [i]);
3289    }
3290    useOldQs= true;
3291    for (int i= 0; i < d; i++)
3292    {
3293      if (bounds [i] + 1 <= l/2)
3294      {
3295        int k= tmin (bounds [i] + 1, l/2);
3296        C= CFMatrix (l - k, factors.length());
3297        for (int ii= 0; ii < factors.length(); ii++)
3298        {
3299          if (A[ii].size() - 1 >= i)
3300          {
3301            buf= getCoeffs (A[ii] [i], k);
3302            writeInMatrix (C, buf, ii + 1, 0);
3303          }
3304        }
3305#ifdef HAVE_FLINT
3306        convertFacCFMatrix2nmod_mat_t (FLINTC, C);
3307        nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
3308                       getCharacteristic());
3309        nmod_mat_mul (FLINTK, FLINTC, FLINTN);
3310        nmod_mat_init (null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
3311                       getCharacteristic());
3312        rank= nmod_mat_nullspace (null, FLINTK);
3313        nmod_mat_clear (FLINTK);
3314        nmod_mat_window_init (FLINTK, null, 0, 0, nmod_mat_nrows(null), rank);
3315        nmod_mat_clear (FLINTC);
3316        nmod_mat_init_set (FLINTC, FLINTN);
3317        nmod_mat_clear (FLINTN);
3318        nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
3319                       getCharacteristic());
3320        nmod_mat_mul (FLINTN, FLINTC, FLINTK); //no aliasing allowed!!
3321
3322        nmod_mat_clear (FLINTC);
3323        nmod_mat_window_clear (FLINTK);
3324        nmod_mat_clear (null);
3325#else
3326        NTLC= convertFacCFMatrix2NTLmat_zz_p(C);
3327        NTLK= (*NTLC)*NTLN;
3328        transpose (NTLK, NTLK);
3329        kernel (NTLK, NTLK);
3330        transpose (NTLK, NTLK);
3331        NTLN *= NTLK;
3332#endif
3333#ifdef HAVE_FLINT
3334        if (nmod_mat_ncols (FLINTN) == 1)
3335        {
3336          nmod_mat_clear (FLINTN);
3337#else
3338        if (NTLN.NumCols() == 1)
3339        {
3340#endif
3341          delete [] A;
3342          delete [] bounds;
3343          CanonicalForm G= F;
3344          F= 1;
3345          return CFList (G);
3346        }
3347      }
3348    }
3349
3350#ifdef HAVE_FLINT
3351    if (nmod_mat_ncols (FLINTN) < oldNumCols - factorsFound)
3352    {
3353      if (isReduced (FLINTN))
3354      {
3355        int * factorsFoundIndex= new int [nmod_mat_ncols (FLINTN)];
3356        for (long i= 0; i < nmod_mat_ncols (FLINTN); i++)
3357#else
3358    if (NTLN.NumCols() < oldNumCols - factorsFound)
3359    {
3360      if (isReduced (NTLN))
3361      {
3362        int * factorsFoundIndex= new int [NTLN.NumCols()];
3363        for (long i= 0; i < NTLN.NumCols(); i++)
3364#endif
3365          factorsFoundIndex[i]= 0;
3366        int factorsFound2= 0;
3367        CFList result;
3368        CanonicalForm bufF= F;
3369#ifdef HAVE_FLINT
3370        reconstructionTry (result, bufF, factors, degree (F) + 1, factorsFound2,
3371                           factorsFoundIndex, FLINTN, false
3372                          );
3373        if (result.length() == nmod_mat_ncols (FLINTN))
3374        {
3375          nmod_mat_clear (FLINTN);
3376#else
3377        reconstructionTry (result, bufF, factors, degree (F) + 1, factorsFound2,
3378                           factorsFoundIndex, NTLN, false
3379                          );
3380        if (result.length() == NTLN.NumCols())
3381        {
3382#endif
3383          delete [] factorsFoundIndex;
3384          delete [] A;
3385          delete [] bounds;
3386          F= 1;
3387          return result;
3388        }
3389        delete [] factorsFoundIndex;
3390      }
3391      else if (l == precision)
3392      {
3393        CanonicalForm bufF= F;
3394#ifdef HAVE_FLINT
3395        int * zeroOne= extractZeroOneVecs (FLINTN);
3396        CFList result= reconstruction (bufF,factors,zeroOne,precision,FLINTN);
3397        nmod_mat_clear (FLINTN);
3398#else
3399        int * zeroOne= extractZeroOneVecs (NTLN);
3400        CFList result= reconstruction (bufF, factors, zeroOne, precision, NTLN);
3401#endif
3402        F= bufF;
3403        delete [] zeroOne;
3404        delete [] A;
3405        delete [] bounds;
3406        return result;
3407      }
3408    }
3409    oldL2= l;
3410    l += stepSize;
3411    stepSize *= 2;
3412    if (l > precision)
3413    {
3414      if (!hitBound)
3415      {
3416        l= precision;
3417        hitBound= true;
3418      }
3419      else
3420        break;
3421    }
3422  }
3423#ifdef HAVE_FLINT
3424  nmod_mat_clear (FLINTN);
3425#endif
3426  delete [] bounds;
3427  delete [] A;
3428  return CFList();
3429}
3430
3431CFList
3432increasePrecision (CanonicalForm& F, CFList& factors, int factorsFound,
3433                   int oldNumCols, int oldL, const Variable&,
3434                   int precision
3435                  )
3436{
3437  int d;
3438  bool isIrreducible= false;
3439  int* bounds= computeBounds (F, d, isIrreducible);
3440  if (isIrreducible)
3441  {
3442    delete [] bounds;
3443    CanonicalForm G= F;
3444    F= 1;
3445    return CFList (G);
3446  }
3447  CFArray * A= new CFArray [factors.length()];
3448  CFArray bufQ= CFArray (factors.length());
3449  mat_zz_pE NTLN;
3450  ident (NTLN, factors.length());
3451  int minBound= bounds[0];
3452  for (int i= 1; i < d; i++)
3453  {
3454    if (bounds[i] != 0)
3455      minBound= tmin (minBound, bounds[i]);
3456  }
3457  int l= tmax (2*(minBound + 1), oldL);
3458  int oldL2= l/2;
3459  int stepSize= 2;
3460  bool useOldQs= false;
3461  bool hitBound= false;
3462  CFListIterator j;
3463  CFMatrix C;
3464  mat_zz_pE* NTLC, NTLK;
3465  CFArray buf;
3466  Variable y= F.mvar();
3467  CanonicalForm truncF;
3468  while (l <= precision)
3469  {
3470    j= factors;
3471    truncF= mod (F, power (y,l));
3472    if (useOldQs)
3473    {
3474      for (int i= 0; i < factors.length(); i++, j++)
3475        A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL2, bufQ[i],
3476                                     bufQ[i]
3477                                    );
3478    }
3479    else
3480    {
3481      for (int i= 0; i < factors.length(); i++, j++)
3482        A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ [i]);
3483    }
3484    useOldQs= true;
3485    for (int i= 0; i < d; i++)
3486    {
3487      if (bounds [i] + 1 <= l/2)
3488      {
3489        int k= tmin (bounds [i] + 1, l/2);
3490        C= CFMatrix (l - k, factors.length());
3491        for (int ii= 0; ii < factors.length(); ii++)
3492        {
3493          if (A[ii].size() - 1 >= i)
3494          {
3495            buf= getCoeffs (A[ii] [i], k);
3496            writeInMatrix (C, buf, ii + 1, 0);
3497          }
3498        }
3499        NTLC= convertFacCFMatrix2NTLmat_zz_pE(C);
3500        NTLK= (*NTLC)*NTLN;
3501        transpose (NTLK, NTLK);
3502        kernel (NTLK, NTLK);
3503        transpose (NTLK, NTLK);
3504        NTLN *= NTLK;
3505        if (NTLN.NumCols() == 1)
3506        {
3507          delete [] A;
3508          delete [] bounds;
3509          CanonicalForm G= F;
3510          F= 1;
3511          return CFList (G);
3512        }
3513      }
3514    }
3515
3516    if (NTLN.NumCols() < oldNumCols - factorsFound)
3517    {
3518      if (isReduced (NTLN))
3519      {
3520        int * factorsFoundIndex= new int [NTLN.NumCols()];
3521        for (long i= 0; i < NTLN.NumCols(); i++)
3522          factorsFoundIndex[i]= 0;
3523        int factorsFound2= 0;
3524        CFList result;
3525        CanonicalForm bufF= F;
3526        reconstructionTry (result, bufF, factors, degree (F) + 1, factorsFound2,
3527                           factorsFoundIndex, NTLN, false);
3528        if (result.length() == NTLN.NumCols())
3529        {
3530          delete [] factorsFoundIndex;
3531          delete [] A;
3532          delete [] bounds;
3533          F= 1;
3534          return result;
3535        }
3536        delete [] factorsFoundIndex;
3537      }
3538      else if (l == precision)
3539      {
3540        CanonicalForm bufF= F;
3541        int * zeroOne= extractZeroOneVecs (NTLN);
3542        CFList result= reconstruction (bufF, factors, zeroOne, precision, NTLN);
3543        F= bufF;
3544        delete [] zeroOne;
3545        delete [] A;
3546        delete [] bounds;
3547        return result;
3548      }
3549    }
3550    oldL2= l;
3551    l += stepSize;
3552    stepSize *= 2;
3553    if (l > precision)
3554    {
3555      if (!hitBound)
3556      {
3557        l= precision;
3558        hitBound= true;
3559      }
3560      else
3561        break;
3562    }
3563  }
3564  delete [] bounds;
3565  delete [] A;
3566  return CFList();
3567}
3568
3569//over field extension
3570CFList
3571extIncreasePrecision (CanonicalForm& F, CFList& factors, int factorsFound,
3572                      int oldNumCols, int oldL, const CanonicalForm& evaluation,
3573                      const ExtensionInfo& info, CFList& source, CFList& dest,
3574                      int precision
3575                     )
3576{
3577  bool GF= (CFFactory::gettype()==GaloisFieldDomain);
3578  int degMipo= degree (getMipo (info.getAlpha()));
3579  Variable alpha= info.getAlpha();
3580  int d;
3581  bool isIrreducible= false;
3582  int* bounds= computeBounds (F, d, isIrreducible);
3583  if (isIrreducible)
3584  {
3585    delete [] bounds;
3586    Variable y= Variable (2);
3587    CanonicalForm tmp= F (y - evaluation, y);
3588    CFList source, dest;
3589    tmp= mapDown (tmp, info, source, dest);
3590    F= 1;
3591    return CFList (tmp);
3592  }
3593
3594  CFArray * A= new CFArray [factors.length()];
3595  CFArray bufQ= CFArray (factors.length());
3596  if (fac_NTL_char != getCharacteristic())
3597  {
3598    fac_NTL_char= getCharacteristic();
3599    zz_p::init (getCharacteristic());
3600  }
3601  mat_zz_p NTLN;
3602  ident (NTLN, factors.length());
3603  int minBound= bounds[0];
3604  for (int i= 1; i < d; i++)
3605  {
3606    if (bounds[i] != 0)
3607      minBound= tmin (minBound, bounds[i]);
3608  }
3609  int l= tmax (oldL, 2*((minBound+1)/degMipo+1));
3610  int oldL2= l/2;
3611  int stepSize= 2;
3612  bool useOldQs= false;
3613  bool hitBound= false;
3614  Variable gamma= info.getBeta();
3615  CanonicalForm primElemAlpha= info.getGamma();
3616  CanonicalForm imPrimElemAlpha= info.getDelta();
3617  CFListIterator j;
3618  Variable y= F.mvar();
3619  CanonicalForm powX, imBasis, truncF;
3620  CFMatrix Mat, C;
3621  CFIterator iter;
3622  mat_zz_p* NTLMat,*NTLC, NTLK;
3623  CFArray buf;
3624  while (l <= precision)
3625  {
3626    j= factors;
3627    if (GF)
3628      setCharacteristic (getCharacteristic());
3629    powX= power (y-gamma, l);
3630    Mat= CFMatrix (l*degMipo, l*degMipo);
3631    for (int i= 0; i < l*degMipo; i++)
3632    {
3633      imBasis= mod (power (y, i), powX);
3634      imBasis= imBasis (power (y, degMipo), y);
3635      imBasis= imBasis (y, gamma);
3636      iter= imBasis;
3637      for (; iter.hasTerms(); iter++)
3638          Mat (iter.exp()+ 1, i+1)= iter.coeff();
3639    }
3640
3641    NTLMat= convertFacCFMatrix2NTLmat_zz_p (Mat);
3642    *NTLMat= inv (*NTLMat);
3643    if (GF)
3644      setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
3645
3646    truncF= mod (F, power (y, l));
3647    if (useOldQs)
3648    {
3649      for (int i= 0; i < factors.length(); i++, j++)
3650        A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL2, bufQ[i],
3651                                     bufQ[i]
3652                                    );
3653    }
3654    else
3655    {
3656      for (int i= 0; i < factors.length(); i++, j++)
3657        A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ [i]);
3658    }
3659    useOldQs= true;
3660    for (int i= 0; i < d; i++)
3661    {
3662      if (bounds [i] + 1 <= (l/2)*degMipo)
3663      {
3664        int k= tmin (bounds [i] + 1, (l/2)*degMipo);
3665        C= CFMatrix (l*degMipo - k, factors.length());
3666        for (int ii= 0; ii < factors.length(); ii++)
3667        {
3668          if (A[ii].size() - 1 >= i)
3669          {
3670            if (GF)
3671            {
3672              A[ii] [i]= A [ii] [i] (y-evaluation, y);
3673              setCharacteristic (getCharacteristic());
3674              A[ii] [i]= GF2FalphaRep (A[ii] [i], alpha);
3675              if (alpha != gamma)
3676                A [ii] [i]= mapDown (A[ii] [i], imPrimElemAlpha, primElemAlpha,
3677                                     gamma, source, dest
3678                                    );
3679              buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, *NTLMat);
3680            }
3681            else
3682            {
3683              A [ii] [i]= A [ii] [i] (y-evaluation, y);
3684              if (alpha != gamma)
3685                A[ii] [i]= mapDown (A[ii] [i], imPrimElemAlpha, primElemAlpha,
3686                                    gamma, source, dest
3687                                   );
3688              buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, *NTLMat);
3689            }
3690            writeInMatrix (C, buf, ii + 1, 0);
3691          }
3692          if (GF)
3693            setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
3694        }
3695
3696        if (GF)
3697          setCharacteristic(getCharacteristic());
3698
3699        NTLC= convertFacCFMatrix2NTLmat_zz_p(C);
3700        NTLK= (*NTLC)*NTLN;
3701        transpose (NTLK, NTLK);
3702        kernel (NTLK, NTLK);
3703        transpose (NTLK, NTLK);
3704        NTLN *= NTLK;
3705
3706        if (GF)
3707          setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
3708
3709        if (NTLN.NumCols() == 1)
3710        {
3711          Variable y= Variable (2);
3712          CanonicalForm tmp= F (y - evaluation, y);
3713          CFList source, dest;
3714          tmp= mapDown (tmp, info, source, dest);
3715          delete [] A;
3716          delete [] bounds;
3717          F= 1;
3718          return CFList (tmp);
3719        }
3720      }
3721    }
3722
3723    if (NTLN.NumCols() < oldNumCols - factorsFound)
3724    {
3725      if (isReduced (NTLN))
3726      {
3727        int * factorsFoundIndex= new int [NTLN.NumCols()];
3728        for (long i= 0; i < NTLN.NumCols(); i++)
3729          factorsFoundIndex[i]= 0;
3730        int factorsFound2= 0;
3731        CFList result;
3732        CanonicalForm bufF= F;
3733        extReconstructionTry (result, bufF, factors,degree (F)+1, factorsFound2,
3734                              factorsFoundIndex, NTLN, false, info, evaluation
3735                             );
3736        if (result.length() == NTLN.NumCols())
3737        {
3738          delete [] factorsFoundIndex;
3739          delete [] A;
3740          delete [] bounds;
3741          F= 1;
3742          return result;
3743        }
3744        delete [] factorsFoundIndex;
3745      }
3746      else if (l == precision)
3747      {
3748        CanonicalForm bufF= F;
3749        int * zeroOne= extractZeroOneVecs (NTLN);
3750        CFList result= extReconstruction (bufF, factors, zeroOne, precision,
3751                                          NTLN, info, evaluation
3752                                         );
3753        F= bufF;
3754        delete [] zeroOne;
3755        delete [] A;
3756        delete [] bounds;
3757        return result;
3758      }
3759    }
3760    oldL2= l;
3761    l += stepSize;
3762    stepSize *= 2;
3763    if (l > precision)
3764    {
3765      if (!hitBound)
3766      {
3767        hitBound= true;
3768        l= precision;
3769      }
3770      else
3771        break;
3772    }
3773  }
3774  delete [] bounds;
3775  delete [] A;
3776  return CFList();
3777}
3778
3779CFList
3780increasePrecision2 (const CanonicalForm& F, CFList& factors,
3781                    const Variable& alpha, int precision)
3782{
3783  int d;
3784  bool isIrreducible= false;
3785  int* bounds= computeBounds (F, d, isIrreducible);
3786  if (isIrreducible)
3787  {
3788    delete [] bounds;
3789    return CFList (F);
3790  }
3791  CFArray * A= new CFArray [factors.length()];
3792  CFArray bufQ= CFArray (factors.length());
3793  if (fac_NTL_char != getCharacteristic())
3794  {
3795    fac_NTL_char= getCharacteristic();
3796    zz_p::init (getCharacteristic());
3797  }
3798  zz_pX NTLMipo= convertFacCF2NTLzzpX (getMipo (alpha));
3799  zz_pE::init (NTLMipo);
3800  mat_zz_pE NTLN;
3801  ident (NTLN, factors.length());
3802  int minBound= bounds[0];
3803  for (int i= 1; i < d; i++)
3804  {
3805    if (bounds[i] != 0)
3806      minBound= tmin (minBound, bounds[i]);
3807  }
3808  int l= tmin (2*(minBound + 1), precision);
3809  int oldL= l/2;
3810  int stepSize= 2;
3811  bool useOldQs= false;
3812  bool hitBound= false;
3813  CFListIterator j;
3814  CFMatrix C;
3815  CFArray buf;
3816  mat_zz_pE* NTLC, NTLK;
3817  Variable y= F.mvar();
3818  CanonicalForm truncF;
3819  while (l <= precision)
3820  {
3821    j= factors;
3822    truncF= mod (F, power (y, l));
3823    if (useOldQs)
3824    {
3825      for (int i= 0; i < factors.length(); i++, j++)
3826        A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i], bufQ[i]);
3827    }
3828    else
3829    {
3830      for (int i= 0; i < factors.length(); i++, j++)
3831        A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ [i]);
3832    }
3833    useOldQs= true;
3834    for (int i= 0; i < d; i++)
3835    {
3836      if (bounds [i] + 1 <= l/2)
3837      {
3838        int k= tmin (bounds [i] + 1, l/2);
3839        C= CFMatrix (l - k, factors.length());
3840        for (int ii= 0; ii < factors.length(); ii++)
3841        {
3842          if (A[ii].size() - 1 >= i)
3843          {
3844            buf= getCoeffs (A[ii] [i], k);
3845            writeInMatrix (C, buf, ii + 1, 0);
3846          }
3847        }
3848        NTLC= convertFacCFMatrix2NTLmat_zz_pE(C);
3849        NTLK= (*NTLC)*NTLN;
3850        transpose (NTLK, NTLK);
3851        kernel (NTLK, NTLK);
3852        transpose (NTLK, NTLK);
3853        NTLN *= NTLK;
3854        if (NTLN.NumCols() == 1)
3855        {
3856          delete [] A;
3857          delete [] bounds;
3858          return CFList (F);
3859        }
3860      }
3861    }
3862
3863    if (isReduced (NTLN) || l == precision)
3864    {
3865      CanonicalForm bufF= F;
3866      int * zeroOne= extractZeroOneVecs (NTLN);
3867      CFList bufFactors= factors;
3868      CFList result= monicReconstruction (bufF, factors, zeroOne, precision,
3869                                          NTLN
3870                                         );
3871      if (result.length() != NTLN.NumCols() && l != precision)
3872        factors= bufFactors;
3873      if (result.length() == NTLN.NumCols())
3874      {
3875        delete [] zeroOne;
3876        delete [] A;
3877        delete [] bounds;
3878        return result;
3879      }
3880      if (l == precision)
3881      {
3882        delete [] zeroOne;
3883        delete [] A;
3884        delete [] bounds;
3885        return Union (result, factors);
3886      }
3887    }
3888    oldL= l;
3889    l += stepSize;
3890    stepSize *= 2;
3891    if (l > precision)
3892    {
3893      if (!hitBound)
3894      {
3895        l= precision;
3896        hitBound= true;
3897      }
3898      else
3899        break;
3900    }
3901  }
3902  delete [] bounds;
3903  delete [] A;
3904  return CFList();
3905}
3906
3907CFList
3908increasePrecisionFq2Fp (CanonicalForm& F, CFList& factors, int factorsFound,
3909                        int oldNumCols, int oldL, const Variable& alpha,
3910                        int precision
3911                       )
3912{
3913  int d;
3914  bool isIrreducible= false;
3915  int* bounds= computeBounds (F, d, isIrreducible);
3916  if (isIrreducible)
3917  {
3918    delete [] bounds;
3919    CanonicalForm G= F;
3920    F= 1;
3921    return CFList (G);
3922  }
3923  int extensionDeg= degree (getMipo (alpha));
3924  CFArray * A= new CFArray [factors.length()];
3925  CFArray bufQ= CFArray (factors.length());
3926#ifdef HAVE_FLINT
3927  nmod_mat_t FLINTN;
3928  nmod_mat_init (FLINTN,factors.length(),factors.length(), getCharacteristic());
3929  for (long i=factors.length()-1; i >= 0; i--)
3930    nmod_mat_entry (FLINTN, i, i)= 1;
3931#else
3932  mat_zz_p NTLN;
3933  ident (NTLN, factors.length());
3934#endif
3935  int minBound= bounds[0];
3936  for (int i= 1; i < d; i++)
3937  {
3938    if (bounds[i] != 0)
3939      minBound= tmin (minBound, bounds[i]);
3940  }
3941  int l= tmax (2*(minBound + 1), oldL);
3942  int oldL2= l/2;
3943  int stepSize= 2;
3944  bool useOldQs= false;
3945  bool hitBound= false;
3946  CFListIterator j;
3947  CFMatrix C;
3948#ifdef HAVE_FLINT
3949  long rank;
3950  nmod_mat_t FLINTC, FLINTK, null;
3951#else
3952  mat_zz_p* NTLC, NTLK;
3953#endif
3954  CFArray buf;
3955  Variable y= F.mvar();
3956  CanonicalForm truncF;
3957  while (l <= precision)
3958  {
3959    j= factors;
3960    truncF= mod (F, power (y, l));
3961    if (useOldQs)
3962    {
3963      for (int i= 0; i < factors.length(); i++, j++)
3964        A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL2, bufQ[i],
3965                                     bufQ[i]
3966                                    );
3967    }
3968    else
3969    {
3970      for (int i= 0; i < factors.length(); i++, j++)
3971        A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ [i]);
3972    }
3973    useOldQs= true;
3974    for (int i= 0; i < d; i++)
3975    {
3976      if (bounds [i] + 1 <= l/2)
3977      {
3978        int k= tmin (bounds [i] + 1, l/2);
3979        C= CFMatrix ((l - k)*extensionDeg, factors.length());
3980        for (int ii= 0; ii < factors.length(); ii++)
3981        {
3982          if (A[ii].size() - 1 >= i)
3983          {
3984            buf= getCoeffs (A[ii] [i], k, alpha);
3985            writeInMatrix (C, buf, ii + 1, 0);
3986          }
3987        }
3988#ifdef HAVE_FLINT
3989        convertFacCFMatrix2nmod_mat_t (FLINTC, C);
3990        nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
3991                       getCharacteristic());
3992        nmod_mat_mul (FLINTK, FLINTC, FLINTN);
3993        nmod_mat_init (null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
3994                       getCharacteristic());
3995        rank= nmod_mat_nullspace (null, FLINTK);
3996        nmod_mat_clear (FLINTK);
3997        nmod_mat_window_init (FLINTK, null, 0, 0, nmod_mat_nrows(null), rank);
3998        nmod_mat_clear (FLINTC);
3999        nmod_mat_init_set (FLINTC, FLINTN);
4000        nmod_mat_clear (FLINTN);
4001        nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
4002                       getCharacteristic());
4003        nmod_mat_mul (FLINTN, FLINTC, FLINTK); //no aliasing allowed!!
4004
4005        nmod_mat_clear (FLINTC);
4006        nmod_mat_window_clear (FLINTK);
4007        nmod_mat_clear (null);
4008#else
4009        NTLC= convertFacCFMatrix2NTLmat_zz_p(C);
4010        NTLK= (*NTLC)*NTLN;
4011        transpose (NTLK, NTLK);
4012        kernel (NTLK, NTLK);
4013        transpose (NTLK, NTLK);
4014        NTLN *= NTLK;
4015#endif
4016#ifdef HAVE_FLINT
4017        if (nmod_mat_ncols (FLINTN) == 1)
4018        {
4019          nmod_mat_clear (FLINTN);
4020#else
4021        if (NTLN.NumCols() == 1)
4022        {
4023#endif
4024          delete [] A;
4025          delete [] bounds;
4026          CanonicalForm G= F;
4027          F= 1;
4028          return CFList (G);
4029        }
4030      }
4031    }
4032
4033#ifdef HAVE_FLINT
4034    if (nmod_mat_ncols (FLINTN) < oldNumCols - factorsFound)
4035    {
4036      if (isReduced (FLINTN))
4037      {
4038        int * factorsFoundIndex= new int [nmod_mat_ncols (FLINTN)];
4039        for (long i= 0; i < nmod_mat_ncols (FLINTN); i++)
4040#else
4041    if (NTLN.NumCols() < oldNumCols - factorsFound)
4042    {
4043      if (isReduced (NTLN))
4044      {
4045        int * factorsFoundIndex= new int [NTLN.NumCols()];
4046        for (long i= 0; i < NTLN.NumCols(); i++)
4047#endif
4048          factorsFoundIndex[i]= 0;
4049        int factorsFound2= 0;
4050        CFList result;
4051        CanonicalForm bufF= F;
4052#ifdef HAVE_FLINT
4053        reconstructionTry (result, bufF, factors, degree (F) + 1, factorsFound2,
4054                           factorsFoundIndex, FLINTN, false
4055                          );
4056        if (result.length() == nmod_mat_ncols (FLINTN))
4057        {
4058          nmod_mat_clear (FLINTN);
4059#else
4060        reconstructionTry (result, bufF, factors, degree (F) + 1, factorsFound2,
4061                           factorsFoundIndex, NTLN, false
4062                          );
4063        if (result.length() == NTLN.NumCols())
4064        {
4065#endif
4066          delete [] factorsFoundIndex;
4067          delete [] A;
4068          delete [] bounds;
4069          F= 1;
4070          return result;
4071        }
4072        delete [] factorsFoundIndex;
4073      }
4074      else if (l == precision)
4075      {
4076        CanonicalForm bufF= F;
4077#ifdef HAVE_FLINT
4078        int * zeroOne= extractZeroOneVecs (FLINTN);
4079        CFList result= reconstruction (bufF,factors,zeroOne,precision,FLINTN);
4080        nmod_mat_clear (FLINTN);
4081#else
4082        int * zeroOne= extractZeroOneVecs (NTLN);
4083        CFList result= reconstruction (bufF, factors, zeroOne, precision, NTLN);
4084#endif
4085        F= bufF;
4086        delete [] zeroOne;
4087        delete [] A;
4088        delete [] bounds;
4089        return result;
4090      }
4091    }
4092    oldL2= l;
4093    l += stepSize;
4094    stepSize *= 2;
4095    if (l > precision)
4096    {
4097      if (!hitBound)
4098      {
4099        hitBound= true;
4100        l= precision;
4101      }
4102      else
4103        break;
4104    }
4105  }
4106#ifdef HAVE_FLINT
4107  nmod_mat_clear (FLINTN);
4108#endif
4109  delete [] bounds;
4110  delete [] A;
4111  return CFList();
4112}
4113
4114#ifdef HAVE_FLINT
4115CFList
4116increasePrecision (CanonicalForm& F, CFList& factors, int oldL, int
4117                   l, int d, int* bounds, CFArray& bufQ, nmod_mat_t FLINTN
4118                  )
4119#else
4120CFList
4121increasePrecision (CanonicalForm& F, CFList& factors, int oldL, int
4122                   l, int d, int* bounds, CFArray& bufQ, mat_zz_p& NTLN
4123                  )
4124#endif
4125{
4126  CFList result= CFList();
4127  CFArray * A= new CFArray [factors.length()];
4128  int oldL2= oldL/2;
4129  bool hitBound= false;
4130#ifdef HAVE_FLINT
4131  if (nmod_mat_nrows (FLINTN) != factors.length()) //refined factors
4132  {
4133    nmod_mat_clear (FLINTN);
4134    nmod_mat_init(FLINTN,factors.length(),factors.length(),getCharacteristic());
4135    for (long i=factors.length()-1; i >= 0; i--)
4136      nmod_mat_entry (FLINTN, i, i)= 1;
4137    bufQ= CFArray (factors.length());
4138  }
4139#else
4140  if (NTLN.NumRows() != factors.length()) //refined factors
4141  {
4142    ident (NTLN, factors.length());
4143    bufQ= CFArray (factors.length());
4144  }
4145#endif
4146  bool useOldQs= false;
4147  CFListIterator j;
4148  CFMatrix C;
4149  CFArray buf;
4150#ifdef HAVE_FLINT
4151  long rank;
4152  nmod_mat_t FLINTC, FLINTK, null;
4153#else
4154  mat_zz_p* NTLC, NTLK;
4155#endif
4156  CanonicalForm bufF, truncF;
4157  CFList bufUniFactors;
4158  Variable y= F.mvar();
4159  while (oldL <= l)
4160  {
4161    j= factors;
4162    truncF= mod (F, power (y, oldL));
4163    if (useOldQs)
4164    {
4165      for (int i= 0; i < factors.length(); i++, j++)
4166        A[i]= logarithmicDerivative (truncF, j.getItem(), oldL, oldL2, bufQ[i],
4167                                     bufQ[i]
4168                                    );
4169    }
4170    else
4171    {
4172      for (int i= 0; i < factors.length(); i++, j++)
4173        A[i]= logarithmicDerivative (truncF, j.getItem(), oldL, bufQ [i]);
4174    }
4175    useOldQs= true;
4176
4177    for (int i= 0; i < d; i++)
4178    {
4179      if (bounds [i] + 1 <= oldL/2)
4180      {
4181        int k= tmin (bounds [i] + 1, oldL/2);
4182        C= CFMatrix (oldL - k, factors.length());
4183        for (int ii= 0; ii < factors.length(); ii++)
4184        {
4185          if (A[ii].size() - 1 >= i)
4186          {
4187            buf= getCoeffs (A[ii] [i], k);
4188            writeInMatrix (C, buf, ii + 1, 0);
4189          }
4190        }
4191#ifdef HAVE_FLINT
4192        convertFacCFMatrix2nmod_mat_t (FLINTC, C);
4193        nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
4194                       getCharacteristic());
4195        nmod_mat_mul (FLINTK, FLINTC, FLINTN);
4196        nmod_mat_init (null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
4197                       getCharacteristic());
4198        rank= nmod_mat_nullspace (null, FLINTK);
4199        nmod_mat_clear (FLINTK);
4200        nmod_mat_window_init (FLINTK, null, 0, 0, nmod_mat_nrows(null), rank);
4201        nmod_mat_clear (FLINTC);
4202        nmod_mat_init_set (FLINTC, FLINTN);
4203        nmod_mat_clear (FLINTN);
4204        nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
4205                       getCharacteristic());
4206        nmod_mat_mul (FLINTN, FLINTC, FLINTK); //no aliasing allowed!!
4207
4208        nmod_mat_clear (FLINTC);
4209        nmod_mat_window_clear (FLINTK);
4210        nmod_mat_clear (null);
4211#else
4212        NTLC= convertFacCFMatrix2NTLmat_zz_p(C);
4213        NTLK= (*NTLC)*NTLN;
4214        transpose (NTLK, NTLK);
4215        kernel (NTLK, NTLK);
4216        transpose (NTLK, NTLK);
4217        NTLN *= NTLK;
4218#endif
4219#ifdef HAVE_FLINT
4220        if (nmod_mat_ncols (FLINTN) == 1)
4221#else
4222        if (NTLN.NumCols() == 1)
4223#endif
4224        {
4225          delete [] A;
4226          return CFList (F);
4227        }
4228      }
4229    }
4230#ifdef HAVE_FLINT
4231    if (nmod_mat_ncols (FLINTN) == 1)
4232#else
4233    if (NTLN.NumCols() == 1)
4234#endif
4235    {
4236      delete [] A;
4237      return CFList (F);
4238    }
4239    int * zeroOneVecs;
4240#ifdef HAVE_FLINT
4241    zeroOneVecs= extractZeroOneVecs (FLINTN);
4242#else
4243    zeroOneVecs= extractZeroOneVecs (NTLN);
4244#endif
4245    bufF= F;
4246    bufUniFactors= factors;
4247#ifdef HAVE_FLINT
4248    result= reconstruction (bufF, bufUniFactors, zeroOneVecs, oldL, FLINTN);
4249#else
4250    result= reconstruction (bufF, bufUniFactors, zeroOneVecs, oldL, NTLN);
4251#endif
4252    delete [] zeroOneVecs;
4253    if (degree (bufF) + 1 + degree (LC (bufF, 1)) < oldL && result.length() > 0)
4254    {
4255      F= bufF;
4256      factors= bufUniFactors;
4257      delete [] A;
4258      return result;
4259    }
4260
4261    result= CFList();
4262    oldL2= oldL;
4263    oldL *= 2;
4264    if (oldL > l)
4265    {
4266      if (!hitBound)
4267      {
4268        oldL= l;
4269        hitBound= true;
4270      }
4271      else
4272        break;
4273    }
4274  }
4275  delete [] A;
4276  return result;
4277}
4278
4279CFList
4280increasePrecision (CanonicalForm& F, CFList& factors, int oldL, int
4281                   l, int d, int* bounds, CFArray& bufQ, mat_zz_pE& NTLN
4282                  )
4283{
4284  CFList result= CFList();
4285  CFArray * A= new CFArray [factors.length()];
4286  int oldL2= oldL/2;
4287  bool hitBound= false;
4288  bool useOldQs= false;
4289  if (NTLN.NumRows() != factors.length()) //refined factors
4290    ident (NTLN, factors.length());
4291  CFListIterator j;
4292  CFMatrix C;
4293  CFArray buf;
4294  mat_zz_pE* NTLC, NTLK;
4295  CanonicalForm bufF, truncF;
4296  CFList bufUniFactors;
4297  Variable y= F.mvar();
4298  while (oldL <= l)
4299  {
4300    j= factors;
4301    truncF= mod (F, power (y, oldL));
4302    if (useOldQs)
4303    {
4304      for (int i= 0; i < factors.length(); i++, j++)
4305        A[i]= logarithmicDerivative (truncF, j.getItem(), oldL, oldL2, bufQ[i],
4306                                     bufQ[i]
4307                                    );
4308    }
4309    else
4310    {
4311      for (int i= 0; i < factors.length(); i++, j++)
4312        A[i]= logarithmicDerivative (truncF, j.getItem(), oldL, bufQ [i]);
4313    }
4314    useOldQs= true;
4315
4316    for (int i= 0; i < d; i++)
4317    {
4318      if (bounds [i] + 1 <= oldL/2)
4319      {
4320        int k= tmin (bounds [i] + 1, oldL/2);
4321        C= CFMatrix (oldL - k, factors.length());
4322        for (int ii= 0; ii < factors.length(); ii++)
4323        {
4324          if (A[ii].size() - 1 >= i)
4325          {
4326            buf= getCoeffs (A[ii] [i], k);
4327            writeInMatrix (C, buf, ii + 1, 0);
4328          }
4329        }
4330        NTLC= convertFacCFMatrix2NTLmat_zz_pE(C);
4331        NTLK= (*NTLC)*NTLN;
4332        transpose (NTLK, NTLK);
4333        kernel (NTLK, NTLK);
4334        transpose (NTLK, NTLK);
4335        NTLN *= NTLK;
4336        if (NTLN.NumCols() == 1)
4337        {
4338          delete [] A;
4339          return CFList (F);
4340        }
4341      }
4342    }
4343    if (NTLN.NumCols() == 1)
4344    {
4345      delete [] A;
4346      return CFList (F);
4347    }
4348
4349    int * zeroOneVecs;
4350    zeroOneVecs= extractZeroOneVecs (NTLN);
4351    bufF= F;
4352    bufUniFactors= factors;
4353    result= reconstruction (bufF, bufUniFactors, zeroOneVecs, oldL, NTLN);
4354    delete [] zeroOneVecs;
4355    if (degree (bufF) + 1 + degree (LC (bufF, 1)) < l && result.length() > 0)
4356    {
4357      F= bufF;
4358      factors= bufUniFactors;
4359      delete [] A;
4360      return result;
4361    }
4362
4363    result= CFList();
4364    oldL2= oldL;
4365    oldL *= 2;
4366    if (oldL > l)
4367    {
4368      if (!hitBound)
4369      {
4370        oldL= l;
4371        hitBound= true;
4372      }
4373      else
4374        break;
4375    }
4376  }
4377  delete [] A;
4378  return result;
4379}
4380
4381//over field extension
4382CFList
4383extIncreasePrecision (CanonicalForm& F, CFList& factors, int oldL, int l, int d,
4384                      int* bounds, CFArray& bufQ, mat_zz_p& NTLN, const
4385                      CanonicalForm& evaluation, const ExtensionInfo& info,
4386                      CFList& source, CFList& dest
4387                     )
4388{
4389  CFList result= CFList();
4390  CFArray * A= new CFArray [factors.length()];
4391  int oldL2= oldL/2; //be careful
4392  bool hitBound= false;
4393  bool useOldQs= false;
4394  bool GF= (CFFactory::gettype()==GaloisFieldDomain);
4395  int degMipo= degree (getMipo (info.getAlpha()));
4396  Variable alpha= info.getAlpha();
4397
4398  Variable gamma= info.getBeta();
4399  CanonicalForm primElemAlpha= info.getGamma();
4400  CanonicalForm imPrimElemAlpha= info.getDelta();
4401  if (NTLN.NumRows() != factors.length()) //refined factors
4402    ident (NTLN, factors.length());
4403  Variable y= F.mvar();
4404  CFListIterator j;
4405  CanonicalForm powX, imBasis, bufF, truncF;
4406  CFMatrix Mat, C;
4407  CFIterator iter;
4408  mat_zz_p* NTLMat;
4409  CFArray buf;
4410  mat_zz_p* NTLC, NTLK;
4411  CFList bufUniFactors;
4412  while (oldL <= l)
4413  {
4414    j= factors;
4415    if (GF)
4416      setCharacteristic (getCharacteristic());
4417
4418    powX= power (y-gamma, oldL);
4419    Mat= CFMatrix (oldL*degMipo, oldL*degMipo);
4420    for (int i= 0; i < oldL*degMipo; i++)
4421    {
4422      imBasis= mod (power (y, i), powX);
4423      imBasis= imBasis (power (y, degMipo), y);
4424      imBasis= imBasis (y, gamma);
4425      iter= imBasis;
4426      for (; iter.hasTerms(); iter++)
4427        Mat (iter.exp()+ 1, i+1)= iter.coeff();
4428    }
4429
4430    NTLMat= convertFacCFMatrix2NTLmat_zz_p (Mat);
4431    *NTLMat= inv (*NTLMat);
4432    if (GF)
4433      setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
4434
4435    truncF= mod (F, power (y, oldL));
4436    if (useOldQs)
4437    {
4438      for (int i= 0; i < factors.length(); i++, j++)
4439        A[i]= logarithmicDerivative (truncF, j.getItem(), oldL, oldL2, bufQ[i],
4440                                     bufQ[i]);
4441    }
4442    else
4443    {
4444      for (int i= 0; i < factors.length(); i++, j++)
4445        A[i]= logarithmicDerivative (truncF, j.getItem(), oldL, bufQ [i]);
4446    }
4447    useOldQs= true;
4448
4449    for (int i= 0; i < d; i++)
4450    {
4451      if (bounds [i] + 1 <= oldL/2)
4452      {
4453        int k= tmin (bounds [i] + 1, oldL/2);
4454        C= CFMatrix (oldL*degMipo - k, factors.length());
4455        for (int ii= 0; ii < factors.length(); ii++)
4456        {
4457          if (A[ii].size() - 1 >= i)
4458          {
4459            if (GF)
4460            {
4461              A [ii] [i]= A [ii] [i] (y-evaluation, y);
4462              setCharacteristic (getCharacteristic());
4463              A[ii] [i]= GF2FalphaRep (A[ii] [i], alpha);
4464              if (alpha != gamma)
4465                A [ii] [i]= mapDown (A[ii] [i], imPrimElemAlpha, primElemAlpha,
4466                                     gamma, source, dest
4467                                    );
4468              buf= getCoeffs (A[ii] [i], k, oldL, degMipo, gamma, 0, *NTLMat);
4469            }
4470            else
4471            {
4472              A [ii] [i]= A [ii] [i] (y-evaluation, y);
4473              if (alpha != gamma)
4474                A[ii] [i]= mapDown (A[ii] [i], imPrimElemAlpha, primElemAlpha,
4475                                    gamma, source, dest
4476                                   );
4477              buf= getCoeffs (A[ii] [i], k, oldL, degMipo, gamma, 0, *NTLMat);
4478            }
4479            writeInMatrix (C, buf, ii + 1, 0);
4480          }
4481          if (GF)
4482            setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
4483        }
4484
4485        if (GF)
4486          setCharacteristic(getCharacteristic());
4487
4488        NTLC= convertFacCFMatrix2NTLmat_zz_p(C);
4489        NTLK= (*NTLC)*NTLN;
4490        transpose (NTLK, NTLK);
4491        kernel (NTLK, NTLK);
4492        transpose (NTLK, NTLK);
4493        NTLN *= NTLK;
4494
4495        if (GF)
4496          setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
4497
4498        if (NTLN.NumCols() == 1)
4499        {
4500          Variable y= Variable (2);
4501          CanonicalForm tmp= F (y - evaluation, y);
4502          CFList source, dest;
4503          tmp= mapDown (tmp, info, source, dest);
4504          delete [] A;
4505          return CFList (tmp);
4506        }
4507      }
4508    }
4509    if (NTLN.NumCols() == 1)
4510    {
4511      Variable y= Variable (2);
4512      CanonicalForm tmp= F (y - evaluation, y);
4513      CFList source, dest;
4514      tmp= mapDown (tmp, info, source, dest);
4515      delete [] A;
4516      return CFList (tmp);
4517    }
4518
4519    int * zeroOneVecs;
4520    zeroOneVecs= extractZeroOneVecs (NTLN);
4521    bufF= F;
4522    bufUniFactors= factors;
4523    result= extReconstruction (bufF, bufUniFactors, zeroOneVecs, oldL, NTLN,
4524                               info, evaluation
4525                              );
4526    delete [] zeroOneVecs;
4527    if (degree (bufF) + 1 + degree (LC (bufF, 1)) < l && result.length() > 0)
4528    {
4529      F= bufF;
4530      factors= bufUniFactors;
4531      return result;
4532    }
4533
4534    result= CFList();
4535    oldL2= oldL;
4536    oldL *= 2;
4537    if (oldL > l)
4538    {
4539      if (!hitBound)
4540      {
4541        oldL= l;
4542        hitBound= true;
4543      }
4544      else
4545        break;
4546    }
4547  }
4548  delete [] A;
4549  return result;
4550}
4551
4552#ifdef HAVE_FLINT
4553CFList
4554increasePrecisionFq2Fp (CanonicalForm& F, CFList& factors, int oldL, int l,
4555                        int d, int* bounds, CFArray& bufQ, nmod_mat_t FLINTN,
4556                        const Variable& alpha
4557                       )
4558#else
4559CFList
4560increasePrecisionFq2Fp (CanonicalForm& F, CFList& factors, int oldL, int l,
4561                        int d, int* bounds, CFArray& bufQ, mat_zz_p& NTLN,
4562                        const Variable& alpha
4563                       )
4564#endif
4565{
4566  CFList result= CFList();
4567  CFArray * A= new CFArray [factors.length()];
4568  int extensionDeg= degree (getMipo (alpha));
4569  int oldL2= oldL/2;
4570  bool hitBound= false;
4571  bool useOldQs= false;
4572#ifdef HAVE_FLINT
4573  if (nmod_mat_nrows (FLINTN) != factors.length()) //refined factors
4574  {
4575    nmod_mat_clear (FLINTN);
4576    nmod_mat_init(FLINTN,factors.length(),factors.length(),getCharacteristic());
4577    for (long i=factors.length()-1; i >= 0; i--)
4578      nmod_mat_entry (FLINTN, i, i)= 1;
4579  }
4580#else
4581  if (NTLN.NumRows() != factors.length()) //refined factors
4582    ident (NTLN, factors.length());
4583#endif
4584  CFListIterator j;
4585  CFMatrix C;
4586  CFArray buf;
4587#ifdef HAVE_FLINT
4588  long rank;
4589  nmod_mat_t FLINTC, FLINTK, null;
4590#else
4591  mat_zz_p* NTLC, NTLK;
4592#endif
4593  CanonicalForm bufF, truncF;
4594  CFList bufUniFactors;
4595  Variable y= F.mvar();
4596  while (oldL <= l)
4597  {
4598    j= factors;
4599    truncF= mod (F, power (y, oldL));
4600    if (useOldQs)
4601    {
4602      for (int i= 0; i < factors.length(); i++, j++)
4603        A[i]= logarithmicDerivative (truncF, j.getItem(), oldL, oldL2, bufQ[i],
4604                                     bufQ[i]
4605                                    );
4606    }
4607    else
4608    {
4609      for (int i= 0; i < factors.length(); i++, j++)
4610        A[i]= logarithmicDerivative (truncF, j.getItem(), oldL, bufQ [i]);
4611    }
4612    useOldQs= true;
4613
4614    for (int i= 0; i < d; i++)
4615    {
4616      if (bounds [i] + 1 <= oldL/2)
4617      {
4618        int k= tmin (bounds [i] + 1, oldL/2);
4619        C= CFMatrix ((oldL - k)*extensionDeg, factors.length());
4620        for (int ii= 0; ii < factors.length(); ii++)
4621        {
4622          if (A[ii].size() - 1 >= i)
4623          {
4624            buf= getCoeffs (A[ii] [i], k, alpha);
4625            writeInMatrix (C, buf, ii + 1, 0);
4626          }
4627        }
4628#ifdef HAVE_FLINT
4629        convertFacCFMatrix2nmod_mat_t (FLINTC, C);
4630        nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
4631                       getCharacteristic());
4632        nmod_mat_mul (FLINTK, FLINTC, FLINTN);
4633        nmod_mat_init (null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
4634                       getCharacteristic());
4635        rank= nmod_mat_nullspace (null, FLINTK);
4636        nmod_mat_clear (FLINTK);
4637        nmod_mat_window_init (FLINTK, null, 0, 0, nmod_mat_nrows(null), rank);
4638        nmod_mat_clear (FLINTC);
4639        nmod_mat_init_set (FLINTC, FLINTN);
4640        nmod_mat_clear (FLINTN);
4641        nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
4642                       getCharacteristic());
4643        nmod_mat_mul (FLINTN, FLINTC, FLINTK); //no aliasing allowed!!
4644
4645        nmod_mat_clear (FLINTC);
4646        nmod_mat_window_clear (FLINTK);
4647        nmod_mat_clear (null);
4648#else
4649        NTLC= convertFacCFMatrix2NTLmat_zz_p(C);
4650        NTLK= (*NTLC)*NTLN;
4651        transpose (NTLK, NTLK);
4652        kernel (NTLK, NTLK);
4653        transpose (NTLK, NTLK);
4654        NTLN *= NTLK;
4655#endif
4656#ifdef HAVE_FLINT
4657        if (nmod_mat_ncols (FLINTN) == 1)
4658#else
4659        if (NTLN.NumCols() == 1)
4660#endif
4661        {
4662          delete [] A;
4663          return CFList (F);
4664        }
4665      }
4666    }
4667
4668    int * zeroOneVecs;
4669#ifdef HAVE_FLINT
4670    zeroOneVecs= extractZeroOneVecs (FLINTN);
4671#else
4672    zeroOneVecs= extractZeroOneVecs (NTLN);
4673#endif
4674
4675    bufF= F;
4676    bufUniFactors= factors;
4677#ifdef HAVE_FLINT
4678    result= reconstruction (bufF, bufUniFactors, zeroOneVecs, oldL, FLINTN);
4679#else
4680    result= reconstruction (bufF, bufUniFactors, zeroOneVecs, oldL, NTLN);
4681#endif
4682    delete [] zeroOneVecs;
4683    if (degree (bufF) + 1 + degree (LC (bufF, 1)) < l && result.length() > 0)
4684    {
4685      F= bufF;
4686      factors= bufUniFactors;
4687      delete [] A;
4688      return result;
4689    }
4690
4691    result= CFList();
4692    oldL2= oldL;
4693    oldL *= 2;
4694    if (oldL > l)
4695    {
4696      if (!hitBound)
4697      {
4698        oldL= l;
4699        hitBound= true;
4700      }
4701      else
4702        break;
4703    }
4704  }
4705  delete [] A;
4706  return result;
4707}
4708
4709#ifdef HAVE_FLINT
4710CFList
4711furtherLiftingAndIncreasePrecision (CanonicalForm& F, CFList&
4712                                    factors, int l, int liftBound, int d, int*
4713                                    bounds, nmod_mat_t FLINTN, CFList& diophant,
4714                                    CFMatrix& M, CFArray& Pi, CFArray& bufQ
4715                                   )
4716#else
4717CFList
4718furtherLiftingAndIncreasePrecision (CanonicalForm& F, CFList&
4719                                    factors, int l, int liftBound, int d, int*
4720                                    bounds, mat_zz_p& NTLN, CFList& diophant,
4721                                    CFMatrix& M, CFArray& Pi, CFArray& bufQ
4722                                   )
4723#endif
4724{
4725  CanonicalForm LCF= LC (F, 1);
4726  CFList result;
4727  bool irreducible= false;
4728  CFList bufFactors= factors;
4729  CFArray *A = new CFArray [bufFactors.length()];
4730  bool useOldQs= false;
4731  bool hitBound= false;
4732  int oldL= l;
4733  int stepSize= 8; //TODO choose better step size?
4734  l += tmax (tmin (8, degree (F) + 1 + degree (LC (F, 1))-l), 2);
4735#ifdef HAVE_FLINT
4736  if (nmod_mat_nrows (FLINTN) != factors.length()) //refined factors
4737  {
4738    nmod_mat_clear (FLINTN);
4739    nmod_mat_init(FLINTN,factors.length(),factors.length(),getCharacteristic());
4740    for (long i=factors.length()-1; i >= 0; i--)
4741      nmod_mat_entry (FLINTN, i, i)= 1;
4742  }
4743#else
4744  if (NTLN.NumRows() != factors.length()) //refined factors
4745    ident (NTLN, factors.length());
4746#endif
4747  CFListIterator j;
4748  CFMatrix C;
4749  CFArray buf;
4750#ifdef HAVE_FLINT
4751  long rank;
4752  nmod_mat_t FLINTC, FLINTK, null;
4753#else
4754  mat_zz_p* NTLC, NTLK;
4755#endif
4756  CanonicalForm bufF, truncF;
4757  Variable y= F.mvar();
4758  while (l <= liftBound)
4759  {
4760    bufFactors.insert (LCF);
4761    henselLiftResume12 (F, bufFactors, oldL, l, Pi, diophant, M);
4762    bufFactors.insert (LCF);
4763    bufFactors.removeFirst();
4764    j= bufFactors;
4765    truncF= mod (F, power (y, l));
4766    if (useOldQs)
4767    {
4768      for (int i= 0; i < bufFactors.length(); i++, j++)
4769        A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
4770                                     bufQ[i]);
4771    }
4772    else
4773    {
4774      for (int i= 0; i < bufFactors.length(); i++, j++)
4775        A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ [i]);
4776    }
4777    for (int i= 0; i < d; i++)
4778    {
4779      if (bounds [i] + 1 <= l/2)
4780      {
4781        int k= tmin (bounds [i] + 1, l/2);
4782        C= CFMatrix (l - k, bufFactors.length());
4783        for (int ii= 0; ii < bufFactors.length(); ii++)
4784        {
4785          if (A[ii].size() - 1 >= i)
4786          {
4787            buf= getCoeffs (A[ii] [i], k);
4788            writeInMatrix (C, buf, ii + 1, 0);
4789          }
4790        }
4791#ifdef HAVE_FLINT
4792        convertFacCFMatrix2nmod_mat_t (FLINTC, C);
4793        nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
4794                       getCharacteristic());
4795        nmod_mat_mul (FLINTK, FLINTC, FLINTN);
4796        nmod_mat_init (null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
4797                       getCharacteristic());
4798        rank= nmod_mat_nullspace (null, FLINTK);
4799        nmod_mat_clear (FLINTK);
4800        nmod_mat_window_init (FLINTK, null, 0, 0, nmod_mat_nrows(null), rank);
4801        nmod_mat_clear (FLINTC);
4802        nmod_mat_init_set (FLINTC, FLINTN);
4803        nmod_mat_clear (FLINTN);
4804        nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
4805                       getCharacteristic());
4806        nmod_mat_mul (FLINTN, FLINTC, FLINTK); //no aliasing allowed!!
4807
4808        nmod_mat_clear (FLINTC);
4809        nmod_mat_window_clear (FLINTK);
4810        nmod_mat_clear (null);
4811#else
4812        NTLC= convertFacCFMatrix2NTLmat_zz_p(C);
4813        NTLK= (*NTLC)*NTLN;
4814        transpose (NTLK, NTLK);
4815        kernel (NTLK, NTLK);
4816        transpose (NTLK, NTLK);
4817        NTLN *= NTLK;
4818#endif
4819#ifdef HAVE_FLINT
4820        if (nmod_mat_ncols (FLINTN) == 1)
4821#else
4822        if (NTLN.NumCols() == 1)
4823#endif
4824        {
4825          irreducible= true;
4826          break;
4827        }
4828      }
4829    }
4830
4831#ifdef HAVE_FLINT
4832    if (nmod_mat_ncols (FLINTN) == 1)
4833#else
4834    if (NTLN.NumCols() == 1)
4835#endif
4836    {
4837      irreducible= true;
4838      break;
4839    }
4840
4841#ifdef HAVE_FLINT
4842    int * zeroOneVecs= extractZeroOneVecs (FLINTN);
4843#else
4844    int * zeroOneVecs= extractZeroOneVecs (NTLN);
4845#endif
4846    bufF= F;
4847#ifdef HAVE_FLINT
4848    result= reconstruction (bufF, bufFactors, zeroOneVecs, l, FLINTN);
4849#else
4850    result= reconstruction (bufF, bufFactors, zeroOneVecs, l, NTLN);
4851#endif
4852    delete [] zeroOneVecs;
4853    if (result.length() > 0 && degree (bufF) + 1 + degree (LC (bufF, 1)) <= l)
4854    {
4855      F= bufF;
4856      factors= bufFactors;
4857      delete [] A;
4858      return result;
4859    }
4860
4861#ifdef HAVE_FLINT
4862    if (isReduced (FLINTN))
4863#else
4864    if (isReduced (NTLN))
4865#endif
4866    {
4867      int factorsFound= 0;
4868      bufF= F;
4869#ifdef HAVE_FLINT
4870      int* factorsFoundIndex= new int [nmod_mat_ncols (FLINTN)];
4871      for (long i= 0; i < nmod_mat_ncols (FLINTN); i++)
4872#else
4873      int* factorsFoundIndex= new int [NTLN.NumCols()];
4874      for (long i= 0; i < NTLN.NumCols(); i++)
4875#endif
4876        factorsFoundIndex[i]= 0;
4877#ifdef HAVE_FLINT
4878      if (l < liftBound)
4879        reconstructionTry (result, bufF, bufFactors, l, factorsFound,
4880                           factorsFoundIndex, FLINTN, false
4881                          );
4882      else
4883        reconstructionTry (result, bufF, bufFactors, degree (bufF) + 1 +
4884                           degree (LCF), factorsFound, factorsFoundIndex,
4885                           FLINTN, false
4886                          );
4887
4888      if (nmod_mat_ncols (FLINTN) == result.length())
4889#else
4890      if (l < liftBound)
4891        reconstructionTry (result, bufF, bufFactors, l, factorsFound,
4892                           factorsFoundIndex, NTLN, false
4893                          );
4894      else
4895        reconstructionTry (result, bufF, bufFactors, degree (bufF) + 1 +
4896                           degree (LCF), factorsFound, factorsFoundIndex,
4897                           NTLN, false
4898                          );
4899
4900      if (NTLN.NumCols() == result.length())
4901#endif
4902      {
4903        delete [] A;
4904        delete [] factorsFoundIndex;
4905        return result;
4906      }
4907      delete [] factorsFoundIndex;
4908    }
4909    result= CFList();
4910    oldL= l;
4911    stepSize *= 2;
4912    l += stepSize;
4913    if (l > liftBound)
4914    {
4915      if (!hitBound)
4916      {
4917        l= liftBound;
4918        hitBound= true;
4919      }
4920      else
4921        break;
4922    }
4923  }
4924  if (irreducible)
4925  {
4926    delete [] A;
4927    return CFList (F);
4928  }
4929  delete [] A;
4930  factors= bufFactors;
4931  return CFList();
4932}
4933
4934//Fq
4935CFList
4936furtherLiftingAndIncreasePrecision (CanonicalForm& F, CFList&
4937                                    factors, int l, int liftBound, int d, int*
4938                                    bounds, mat_zz_pE& NTLN, CFList& diophant,
4939                                    CFMatrix& M, CFArray& Pi, CFArray& bufQ
4940                                   )
4941{
4942  CanonicalForm LCF= LC (F, 1);
4943  CFList result;
4944  bool irreducible= false;
4945  CFList bufFactors= factors;
4946  CFArray *A = new CFArray [bufFactors.length()];
4947  bool useOldQs= false;
4948  bool hitBound= false;
4949  int oldL= l;
4950  int stepSize= 8; //TODO choose better step size?
4951  l += tmax (tmin (8, degree (F) + 1 + degree (LC (F, 1))-l), 2);
4952  if (NTLN.NumRows() != factors.length()) //refined factors
4953    ident (NTLN, factors.length());
4954  CFListIterator j;
4955  CFArray buf;
4956  mat_zz_pE* NTLC, NTLK;
4957  CanonicalForm bufF, truncF;
4958  Variable y= F.mvar();
4959  while (l <= liftBound)
4960  {
4961    bufFactors.insert (LCF);
4962    henselLiftResume12 (F, bufFactors, oldL, l, Pi, diophant, M);
4963    j= bufFactors;
4964    truncF= mod (F, power (y, l));
4965    if (useOldQs)
4966    {
4967      for (int i= 0; i < bufFactors.length(); i++, j++)
4968        A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
4969                                     bufQ[i]);
4970    }
4971    else
4972    {
4973      for (int i= 0; i < bufFactors.length(); i++, j++)
4974        A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ [i]);
4975    }
4976    for (int i= 0; i < d; i++)
4977    {
4978      if (bounds [i] + 1 <= l/2)
4979      {
4980        int k= tmin (bounds [i] + 1, l/2);
4981        CFMatrix C= CFMatrix (l - k, bufFactors.length());
4982        for (int ii= 0; ii < bufFactors.length(); ii++)
4983        {
4984          if (A[ii].size() - 1 >= i)
4985          {
4986            buf= getCoeffs (A[ii] [i], k);
4987            writeInMatrix (C, buf, ii + 1, 0);
4988          }
4989        }
4990        NTLC= convertFacCFMatrix2NTLmat_zz_pE(C);
4991        NTLK= (*NTLC)*NTLN;
4992        transpose (NTLK, NTLK);
4993        kernel (NTLK, NTLK);
4994        transpose (NTLK, NTLK);
4995        NTLN *= NTLK;
4996        if (NTLN.NumCols() == 1)
4997        {
4998          irreducible= true;
4999          break;
5000        }
5001      }
5002    }
5003    if (NTLN.NumCols() == 1)
5004    {
5005      irreducible= true;
5006      break;
5007    }
5008
5009    int * zeroOneVecs= extractZeroOneVecs (NTLN);
5010    bufF= F;
5011    result= reconstruction (bufF, bufFactors, zeroOneVecs, l, NTLN);
5012    delete [] zeroOneVecs;
5013    if (result.length() > 0 && degree (bufF) + 1 + degree (LC (bufF, 1)) <= l)
5014    {
5015      F= bufF;
5016      factors= bufFactors;
5017      delete [] A;
5018      return result;
5019    }
5020
5021    if (isReduced (NTLN))
5022    {
5023      int factorsFound= 0;
5024      bufF= F;
5025      int* factorsFoundIndex= new int [NTLN.NumCols()];
5026      for (long i= 0; i < NTLN.NumCols(); i++)
5027        factorsFoundIndex[i]= 0;
5028      if (l < liftBound)
5029        reconstructionTry (result, bufF, bufFactors, l, factorsFound,
5030                           factorsFoundIndex, NTLN, false
5031                          );
5032      else
5033        reconstructionTry (result, bufF, bufFactors, degree (bufF) + 1 +
5034                           degree (LCF), factorsFound, factorsFoundIndex,
5035                           NTLN, false
5036                          );
5037      if (NTLN.NumCols() == result.length())
5038      {
5039        delete [] A;
5040        delete [] factorsFoundIndex;
5041        return result;
5042      }
5043      delete [] factorsFoundIndex;
5044    }
5045    result= CFList();
5046    oldL= l;
5047    stepSize *= 2;
5048    l += stepSize;
5049    if (l > liftBound)
5050    {
5051      if (!hitBound)
5052      {
5053        l= liftBound;
5054        hitBound= true;
5055      }
5056      else
5057        break;
5058    }
5059  }
5060  if (irreducible)
5061  {
5062    delete [] A;
5063    return CFList (F);
5064  }
5065  delete [] A;
5066  factors= bufFactors;
5067  return CFList();
5068}
5069
5070//over field extension
5071CFList
5072extFurtherLiftingAndIncreasePrecision (CanonicalForm& F, CFList& factors, int l,
5073                                       int liftBound, int d, int* bounds,
5074                                       mat_zz_p& NTLN, CFList& diophant,
5075                                       CFMatrix& M, CFArray& Pi, CFArray& bufQ,
5076                                       const CanonicalForm& evaluation, const
5077                                       ExtensionInfo& info, CFList& source,
5078                                       CFList& dest
5079                                      )
5080{
5081  CanonicalForm LCF= LC (F, 1);
5082  CFList result;
5083  bool irreducible= false;
5084  CFList bufFactors= factors;
5085  CFArray *A = new CFArray [bufFactors.length()];
5086  bool useOldQs= false;
5087  bool hitBound= false;
5088  bool GF= (CFFactory::gettype()==GaloisFieldDomain);
5089  int degMipo= degree (getMipo (info.getAlpha()));
5090  Variable alpha= info.getAlpha();
5091  int oldL= l; //be careful
5092  int stepSize= 8;
5093  l += tmax (tmin (8, degree (F) + 1 + degree (LC (F, 1))-l),2);
5094  Variable gamma= info.getBeta();
5095  CanonicalForm primElemAlpha= info.getGamma();
5096  CanonicalForm imPrimElemAlpha= info.getDelta();
5097  if (NTLN.NumRows() != factors.length()) //refined factors
5098    ident (NTLN, factors.length());
5099  Variable y= F.mvar();
5100  CanonicalForm powX, imBasis, bufF, truncF;
5101  CFMatrix Mat, C;
5102  CFIterator iter;
5103  mat_zz_p* NTLMat,*NTLC, NTLK;
5104  CFListIterator j;
5105  CFArray buf;
5106  while (l <= liftBound)
5107  {
5108    bufFactors.insert (LCF);
5109    henselLiftResume12 (F, bufFactors, oldL, l, Pi, diophant, M);
5110
5111    if (GF)
5112      setCharacteristic (getCharacteristic());
5113
5114    powX= power (y-gamma, l);
5115    Mat= CFMatrix (l*degMipo, l*degMipo);
5116    for (int i= 0; i < l*degMipo; i++)
5117    {
5118
5119      imBasis= mod (power (y, i), powX);
5120      imBasis= imBasis (power (y, degMipo), y);
5121      imBasis= imBasis (y, gamma);
5122      iter= imBasis;
5123      for (; iter.hasTerms(); iter++)
5124        Mat (iter.exp()+ 1, i+1)= iter.coeff();
5125    }
5126
5127    NTLMat= convertFacCFMatrix2NTLmat_zz_p (Mat);
5128    *NTLMat= inv (*NTLMat);
5129
5130    if (GF)
5131      setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
5132
5133    j= bufFactors;
5134    truncF= mod (F, power (y, l));
5135    if (useOldQs)
5136    {
5137      for (int i= 0; i < bufFactors.length(); i++, j++)
5138        A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
5139                                     bufQ[i]);
5140    }
5141    else
5142    {
5143      for (int i= 0; i < bufFactors.length(); i++, j++)
5144        A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ [i]);
5145    }
5146    for (int i= 0; i < d; i++)
5147    {
5148      if (bounds [i] + 1 <= l/2)
5149      {
5150        int k= tmin (bounds [i] + 1, l/2);
5151        C= CFMatrix (l*degMipo - k, bufFactors.length());
5152        for (int ii= 0; ii < bufFactors.length(); ii++)
5153        {
5154          if (A[ii].size() - 1 >= i)
5155          {
5156            if (GF)
5157            {
5158              A [ii] [i]= A [ii] [i] (y-evaluation, y);
5159              setCharacteristic (getCharacteristic());
5160              A[ii] [i]= GF2FalphaRep (A[ii] [i], alpha);
5161              if (alpha != gamma)
5162                A [ii] [i]= mapDown (A[ii] [i], imPrimElemAlpha, primElemAlpha,
5163                                     gamma, source, dest
5164                                    );
5165              buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, *NTLMat);
5166            }
5167            else
5168            {
5169              A [ii] [i]= A [ii] [i] (y-evaluation, y);
5170              if (alpha != gamma)
5171                A[ii] [i]= mapDown (A[ii] [i], imPrimElemAlpha, primElemAlpha,
5172                                    gamma, source, dest
5173                                   );
5174              buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, *NTLMat);
5175            }
5176            writeInMatrix (C, buf, ii + 1, 0);
5177          }
5178          if (GF)
5179            setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
5180        }
5181
5182        if (GF)
5183          setCharacteristic(getCharacteristic());
5184        NTLC= convertFacCFMatrix2NTLmat_zz_p(C);
5185        NTLK= (*NTLC)*NTLN;
5186        transpose (NTLK, NTLK);
5187        kernel (NTLK, NTLK);
5188        transpose (NTLK, NTLK);
5189        NTLN *= NTLK;
5190        if (GF)
5191          setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
5192
5193        if (NTLN.NumCols() == 1)
5194        {
5195          irreducible= true;
5196          break;
5197        }
5198      }
5199    }
5200    if (NTLN.NumCols() == 1)
5201    {
5202      irreducible= true;
5203      break;
5204    }
5205
5206    int * zeroOneVecs= extractZeroOneVecs (NTLN);
5207    bufF= F;
5208    result= extReconstruction (bufF, bufFactors, zeroOneVecs, l, NTLN, info,
5209                               evaluation
5210                              );
5211    delete [] zeroOneVecs;
5212    if (result.length() > 0 && degree (bufF) + 1 + degree (LC (bufF, 1)) <= l)
5213    {
5214      F= bufF;
5215      factors= bufFactors;
5216      delete [] A;
5217      return result;
5218    }
5219
5220    if (isReduced (NTLN))
5221    {
5222      int factorsFound= 0;
5223      bufF= F;
5224      int* factorsFoundIndex= new int [NTLN.NumCols()];
5225      for (long i= 0; i < NTLN.NumCols(); i++)
5226        factorsFoundIndex[i]= 0;
5227      if (l < degree (bufF) + 1 + degree (LCF))
5228        extReconstructionTry (result, bufF, bufFactors, l, factorsFound,
5229                              factorsFoundIndex, NTLN, false, info, evaluation
5230                             );
5231      else
5232        extReconstructionTry (result, bufF, bufFactors, degree (bufF) + 1 +
5233                              degree (LCF), factorsFound, factorsFoundIndex,
5234                              NTLN, false, info, evaluation
5235                             );
5236      if (NTLN.NumCols() == result.length())
5237      {
5238        delete [] A;
5239        delete [] factorsFoundIndex;
5240        return result;
5241      }
5242      delete [] factorsFoundIndex;
5243    }
5244    result= CFList();
5245    oldL= l;
5246    stepSize *= 2;
5247    l += stepSize;
5248    if (l > liftBound)
5249    {
5250      if (!hitBound)
5251      {
5252        l= liftBound;
5253        hitBound= true;
5254      }
5255      else
5256        break;
5257    }
5258  }
5259  if (irreducible)
5260  {
5261    delete [] A;
5262    Variable y= Variable (2);
5263    CanonicalForm tmp= F (y - evaluation, y);
5264    CFList source, dest;
5265    tmp= mapDown (tmp, info, source, dest);
5266    return CFList (tmp);
5267  }
5268  delete [] A;
5269  factors= bufFactors;
5270  return CFList();
5271}
5272
5273#ifdef HAVE_FLINT
5274CFList
5275furtherLiftingAndIncreasePrecisionFq2Fp (CanonicalForm& F, CFList& factors, int
5276                                         l, int liftBound, int d, int* bounds,
5277                                         nmod_mat_t FLINTN, CFList& diophant,
5278                                         CFMatrix& M, CFArray& Pi, CFArray& bufQ,
5279                                         const Variable& alpha
5280                                        )
5281#else
5282CFList
5283furtherLiftingAndIncreasePrecisionFq2Fp (CanonicalForm& F, CFList& factors, int
5284                                         l, int liftBound, int d, int* bounds,
5285                                         mat_zz_p& NTLN, CFList& diophant,
5286                                         CFMatrix& M, CFArray& Pi, CFArray& bufQ,
5287                                         const Variable& alpha
5288                                        )
5289#endif
5290{
5291  CanonicalForm LCF= LC (F, 1);
5292  CFList result;
5293  bool irreducible= false;
5294  CFList bufFactors= factors;
5295  CFArray *A = new CFArray [bufFactors.length()];
5296  bool useOldQs= false;
5297  int extensionDeg= degree (getMipo (alpha));
5298  bool hitBound= false;
5299  int oldL= l;
5300  int stepSize= 8; //TODO choose better step size?
5301  l += tmax (tmin (8, degree (F) + 1 + degree (LC (F, 1))-l), 2);
5302#ifdef HAVE_FLINT
5303  if (nmod_mat_nrows (FLINTN) != factors.length()) //refined factors
5304  {
5305    nmod_mat_clear (FLINTN);
5306    nmod_mat_init(FLINTN,factors.length(),factors.length(),getCharacteristic());
5307    for (long i=factors.length()-1; i >= 0; i--)
5308      nmod_mat_entry (FLINTN, i, i)= 1;
5309  }
5310#else
5311  if (NTLN.NumRows() != factors.length()) //refined factors
5312    ident (NTLN, factors.length());
5313#endif
5314  CFListIterator j;
5315  CFMatrix C;
5316#ifdef HAVE_FLINT
5317  long rank;
5318  nmod_mat_t FLINTC, FLINTK, null;
5319#else
5320  mat_zz_p* NTLC, NTLK;
5321#endif
5322  CanonicalForm bufF, truncF;
5323  Variable y= F.mvar();
5324  while (l <= liftBound)
5325  {
5326    bufFactors.insert (LCF);
5327    henselLiftResume12 (F, bufFactors, oldL, l, Pi, diophant, M);
5328    j= bufFactors;
5329    truncF= mod (F, power (y, l));
5330    if (useOldQs)
5331    {
5332      for (int i= 0; i < bufFactors.length(); i++, j++)
5333        A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
5334                                     bufQ[i]);
5335    }
5336    else
5337    {
5338      for (int i= 0; i < bufFactors.length(); i++, j++)
5339        A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ [i]);
5340    }
5341    for (int i= 0; i < d; i++)
5342    {
5343      if (bounds [i] + 1 <= l/2)
5344      {
5345        int k= tmin (bounds [i] + 1, l/2);
5346        C= CFMatrix ((l - k)*extensionDeg, bufFactors.length());
5347        for (int ii= 0; ii < bufFactors.length(); ii++)
5348        {
5349          CFArray buf;
5350          if (A[ii].size() - 1 >= i)
5351          {
5352            buf= getCoeffs (A[ii] [i], k, alpha);
5353            writeInMatrix (C, buf, ii + 1, 0);
5354          }
5355        }
5356#ifdef HAVE_FLINT
5357        convertFacCFMatrix2nmod_mat_t (FLINTC, C);
5358        nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
5359                       getCharacteristic());
5360        nmod_mat_mul (FLINTK, FLINTC, FLINTN);
5361        nmod_mat_init (null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
5362                       getCharacteristic());
5363        rank= nmod_mat_nullspace (null, FLINTK);
5364        nmod_mat_clear (FLINTK);
5365        nmod_mat_window_init (FLINTK, null, 0, 0, nmod_mat_nrows(null), rank);
5366        nmod_mat_clear (FLINTC);
5367        nmod_mat_init_set (FLINTC, FLINTN);
5368        nmod_mat_clear (FLINTN);
5369        nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
5370                       getCharacteristic());
5371        nmod_mat_mul (FLINTN, FLINTC, FLINTK); //no aliasing allowed!!
5372
5373        nmod_mat_clear (FLINTC);
5374        nmod_mat_window_clear (FLINTK);
5375        nmod_mat_clear (null);
5376#else
5377        NTLC= convertFacCFMatrix2NTLmat_zz_p(C);
5378        NTLK= (*NTLC)*NTLN;
5379        transpose (NTLK, NTLK);
5380        kernel (NTLK, NTLK);
5381        transpose (NTLK, NTLK);
5382        NTLN *= NTLK;
5383#endif
5384#ifdef HAVE_FLINT
5385        if (nmod_mat_ncols (FLINTN) == 1)
5386#else
5387        if (NTLN.NumCols() == 1)
5388#endif
5389        {
5390          irreducible= true;
5391          break;
5392        }
5393      }
5394    }
5395#ifdef HAVE_FLINT
5396    if (nmod_mat_ncols (FLINTN) == 1)
5397#else
5398    if (NTLN.NumCols() == 1)
5399#endif
5400    {
5401      irreducible= true;
5402      break;
5403    }
5404
5405#ifdef HAVE_FLINT
5406    int * zeroOneVecs= extractZeroOneVecs (FLINTN);
5407#else
5408    int * zeroOneVecs= extractZeroOneVecs (NTLN);
5409#endif
5410    CanonicalForm bufF= F;
5411#ifdef HAVE_FLINT
5412    result= reconstruction (bufF, bufFactors, zeroOneVecs, l, FLINTN);
5413#else
5414    result= reconstruction (bufF, bufFactors, zeroOneVecs, l, NTLN);
5415#endif
5416    delete [] zeroOneVecs;
5417    if (result.length() > 0 && degree (bufF) + 1 + degree (LC (bufF, 1)) <= l)
5418    {
5419      F= bufF;
5420      factors= bufFactors;
5421      delete [] A;
5422      return result;
5423    }
5424
5425#ifdef HAVE_FLINT
5426    if (isReduced (FLINTN))
5427#else
5428    if (isReduced (NTLN))
5429#endif
5430    {
5431      int factorsFound= 0;
5432      bufF= F;
5433#ifdef HAVE_FLINT
5434      int* factorsFoundIndex= new int [nmod_mat_ncols (FLINTN)];
5435      for (long i= 0; i < nmod_mat_ncols (FLINTN); i++)
5436#else
5437      int* factorsFoundIndex= new int [NTLN.NumCols()];
5438      for (long i= 0; i < NTLN.NumCols(); i++)
5439#endif
5440        factorsFoundIndex[i]= 0;
5441#ifdef HAVE_FLINT
5442      if (l < degree (bufF) + 1 + degree (LCF))
5443        reconstructionTry (result, bufF, bufFactors, l, factorsFound,
5444                           factorsFoundIndex, FLINTN, false
5445                          );
5446      else
5447        reconstructionTry (result, bufF, bufFactors, degree (bufF) + 1 +
5448                           degree (LCF), factorsFound, factorsFoundIndex,
5449                           FLINTN, false
5450                          );
5451      if (nmod_mat_ncols (FLINTN) == result.length())
5452#else
5453      if (l < degree (bufF) + 1 + degree (LCF))
5454        reconstructionTry (result, bufF, bufFactors, l, factorsFound,
5455                           factorsFoundIndex, NTLN, false
5456                          );
5457      else
5458        reconstructionTry (result, bufF, bufFactors, degree (bufF) + 1 +
5459                           degree (LCF), factorsFound, factorsFoundIndex,
5460                           NTLN, false
5461                          );
5462      if (NTLN.NumCols() == result.length())
5463#endif
5464      {
5465        delete [] A;
5466        delete [] factorsFoundIndex;
5467        return result;
5468      }
5469      delete [] factorsFoundIndex;
5470    }
5471    result= CFList();
5472    oldL= l;
5473    stepSize *= 2;
5474    l += stepSize;
5475    if (l > liftBound)
5476    {
5477      if (!hitBound)
5478      {
5479        l= liftBound;
5480        hitBound= true;
5481      }
5482      else
5483        break;
5484    }
5485  }
5486  if (irreducible)
5487  {
5488    delete [] A;
5489    return CFList (F);
5490  }
5491  delete [] A;
5492  factors= bufFactors;
5493  return CFList();
5494}
5495
5496void
5497refineAndRestartLift (const CanonicalForm& F, const mat_zz_p& NTLN, int
5498                      liftBound, int l, CFList& factors, CFMatrix& M, CFArray&
5499                      Pi, CFList& diophant
5500                     )
5501{
5502  CFList bufFactors;
5503  Variable y= Variable (2);
5504  CanonicalForm LCF= LC (F, 1);
5505  CFListIterator iter;
5506  CanonicalForm buf;
5507  for (long i= 1; i <= NTLN.NumCols(); i++)
5508  {
5509    iter= factors;
5510    buf= 1;
5511    for (long j= 1; j <= NTLN.NumRows(); j++, iter++)
5512    {
5513      if (!IsZero (NTLN (j,i)))
5514        buf= mulNTL (buf, mod (iter.getItem(), y));
5515    }
5516    bufFactors.append (buf);
5517  }
5518  factors= bufFactors;
5519  M= CFMatrix (liftBound, factors.length());
5520  Pi= CFArray();
5521  diophant= CFList();
5522  factors.insert (LCF);
5523  henselLift12 (F, factors, l, Pi, diophant, M);
5524}
5525
5526#ifdef HAVE_FLINT
5527void
5528refineAndRestartLift (const CanonicalForm& F, const nmod_mat_t FLINTN, int
5529                      liftBound, int l, CFList& factors, CFMatrix& M, CFArray&
5530                      Pi, CFList& diophant
5531                     )
5532{
5533  CFList bufFactors;
5534  Variable y= Variable (2);
5535  CanonicalForm LCF= LC (F, 1);
5536  CFListIterator iter;
5537  CanonicalForm buf;
5538  for (long i= 0; i < nmod_mat_ncols (FLINTN); i++)
5539  {
5540    iter= factors;
5541    buf= 1;
5542    for (long j= 0; j < nmod_mat_nrows (FLINTN); j++, iter++)
5543    {
5544      if (!(nmod_mat_entry (FLINTN,j,i) == 0))
5545        buf= mulNTL (buf, mod (iter.getItem(), y));
5546    }
5547    bufFactors.append (buf);
5548  }
5549  factors= bufFactors;
5550  M= CFMatrix (liftBound, factors.length());
5551  Pi= CFArray();
5552  diophant= CFList();
5553  factors.insert (LCF);
5554  henselLift12 (F, factors, l, Pi, diophant, M);
5555}
5556#endif
5557
5558void
5559refineAndRestartLift (const CanonicalForm& F, const mat_zz_pE& NTLN, int
5560                      liftBound, int l, CFList& factors, CFMatrix& M, CFArray&
5561                      Pi, CFList& diophant
5562                     )
5563{
5564  CFList bufFactors;
5565  Variable y= Variable (2);
5566  CanonicalForm LCF= LC (F, 1);
5567  CFListIterator iter;
5568  CanonicalForm buf;
5569  for (long i= 1; i <= NTLN.NumCols(); i++)
5570  {
5571    iter= factors;
5572    buf= 1;
5573    for (long j= 1; j <= NTLN.NumRows(); j++, iter++)
5574    {
5575      if (!IsZero (NTLN (j,i)))
5576        buf= mulNTL (buf, mod (iter.getItem(), y));
5577    }
5578    bufFactors.append (buf);
5579  }
5580  factors= bufFactors;
5581  M= CFMatrix (liftBound, factors.length());
5582  Pi= CFArray();
5583  diophant= CFList();
5584  factors.insert (LCF);
5585  henselLift12 (F, factors, l, Pi, diophant, M);
5586}
5587
5588#ifdef HAVE_FLINT
5589CFList
5590earlyReconstructionAndLifting (const CanonicalForm& F, const nmod_mat_t N,
5591                               CanonicalForm& bufF, CFList& factors, int& l,
5592                               int& factorsFound, bool beenInThres, CFMatrix& M,
5593                               CFArray& Pi, CFList& diophant, bool symmetric,
5594                               const CanonicalForm& evaluation
5595                              )
5596#else
5597CFList
5598earlyReconstructionAndLifting (const CanonicalForm& F, const mat_zz_p& N,
5599                               CanonicalForm& bufF, CFList& factors, int& l,
5600                               int& factorsFound, bool beenInThres, CFMatrix& M,
5601                               CFArray& Pi, CFList& diophant, bool symmetric,
5602                               const CanonicalForm& evaluation
5603                              )
5604#endif
5605{
5606  int sizeOfLiftPre;
5607  int * liftPre= getLiftPrecisions (F, sizeOfLiftPre, degree (LC (F, 1), 2));
5608
5609  Variable y= F.mvar();
5610  factorsFound= 0;
5611  CanonicalForm LCF= LC (F, 1);
5612  CFList result;
5613  int smallFactorDeg= tmin (11, liftPre [sizeOfLiftPre- 1] + 1);
5614#ifdef HAVE_FLINT
5615  nmod_mat_t FLINTN;
5616  nmod_mat_init_set (FLINTN, N);
5617  int * factorsFoundIndex= new int [nmod_mat_ncols (FLINTN)];
5618  for (long i= 0; i < nmod_mat_ncols (FLINTN); i++)
5619#else
5620  mat_zz_p NTLN= N;
5621  int * factorsFoundIndex= new int [NTLN.NumCols()];
5622  for (long i= 0; i < NTLN.NumCols(); i++)
5623#endif
5624    factorsFoundIndex [i]= 0;
5625
5626  if (degree (F) + 1 > smallFactorDeg)
5627  {
5628    if (l < smallFactorDeg)
5629    {
5630      factors.insert (LCF);
5631      henselLiftResume12 (F, factors, l, smallFactorDeg, Pi, diophant, M);
5632      l= smallFactorDeg;
5633    }
5634#ifdef HAVE_FLINT
5635    reconstructionTry (result, bufF, factors, smallFactorDeg, factorsFound,
5636                       factorsFoundIndex, FLINTN, beenInThres
5637                      );
5638    if (result.length() == nmod_mat_ncols (FLINTN))
5639    {
5640      nmod_mat_clear (FLINTN);
5641#else
5642    reconstructionTry (result, bufF, factors, smallFactorDeg, factorsFound,
5643                       factorsFoundIndex, NTLN, beenInThres
5644                      );
5645    if (result.length() == NTLN.NumCols())
5646    {
5647#endif
5648      delete [] liftPre;
5649      delete [] factorsFoundIndex;
5650      return result;
5651    }
5652  }
5653
5654  int i= sizeOfLiftPre - 1;
5655  int dummy= 1;
5656  if (sizeOfLiftPre > 1 && sizeOfLiftPre < 30)
5657  {
5658    while (i > 0)
5659    {
5660      if (l < liftPre[i-1] + 1)
5661      {
5662        factors.insert (LCF);
5663        henselLiftResume12 (F, factors, l, liftPre[i-1] + 1, Pi, diophant, M);
5664        l= liftPre[i-1] + 1;
5665      }
5666      else
5667      {
5668        i--;
5669        if (i != 0)
5670          continue;
5671      }
5672#ifdef HAVE_FLINT
5673      reconstructionTry (result, bufF, factors, l, factorsFound,
5674                         factorsFoundIndex, FLINTN, beenInThres
5675                        );
5676      if (result.length() == nmod_mat_ncols (FLINTN))
5677      {
5678        nmod_mat_clear (FLINTN);
5679#else
5680      reconstructionTry (result, bufF, factors, l, factorsFound,
5681                         factorsFoundIndex, NTLN, beenInThres
5682                        );
5683      if (result.length() == NTLN.NumCols())
5684      {
5685#endif
5686        delete [] liftPre;
5687        delete [] factorsFoundIndex;
5688        return result;
5689      }
5690      i--;
5691    }
5692  }
5693  else
5694  {
5695    i= 1;
5696    while (((degree (F,y)/4)*i+1) + 4 <= smallFactorDeg)
5697      i++;
5698    while (i < 5)
5699    {
5700      dummy= tmin (degree (F,y)+1, ((degree (F,y)/4)+1)*i+4);
5701      if (l < dummy)
5702      {
5703        factors.insert (LCF);
5704        henselLiftResume12 (F, factors, l, dummy, Pi, diophant, M);
5705        l= dummy;
5706        if (i == 1 && degree (F)%4==0 && symmetric && factors.length() == 2 &&
5707            LC (F,1).inCoeffDomain() &&
5708           (degree (factors.getFirst(), 1) == degree (factors.getLast(),1)))
5709        {
5710          Variable x= Variable (1);
5711          CanonicalForm g, h, gg, hh, multiplier1, multiplier2, check1, check2;
5712          int m= degree (F)/4+1;
5713          g= factors.getFirst();
5714          h= factors.getLast();
5715          g= mod (g, power (y,m));
5716          h= mod (h, power (y,m));
5717          g= g (y-evaluation, y);
5718          h= h (y-evaluation, y);
5719          gg= mod (swapvar (g,x,y),power (x,m));
5720          gg= gg (y + evaluation, y);
5721          multiplier1= factors.getLast()[m-1][0]/gg[m-1][0];
5722          gg= div (gg, power (y,m));
5723          gg= gg*power (y,m);
5724          hh= mod (swapvar (h,x,y),power (x,m));
5725          hh= hh (y + evaluation, y);
5726          multiplier2= factors.getFirst()[m-1][0]/hh[m-1][0];
5727          hh= div (hh, power (y,m));
5728          hh= hh*power (y,m);
5729          gg= multiplier1*gg+mod (factors.getLast(), power (y,m));
5730          hh= multiplier2*hh+mod (factors.getFirst(), power (y,m));
5731          check1= gg (y-evaluation,y);
5732          check2= hh (y-evaluation,y);
5733          check1= swapvar (check1, x, y);
5734          if (check1/Lc (check1) == check2/Lc (check2))
5735          {
5736#ifdef HAVE_FLINT
5737            nmod_mat_clear (FLINTN);
5738#endif
5739            result.append (gg);
5740            result.append (hh);
5741            delete [] liftPre;
5742            delete [] factorsFoundIndex;
5743            return result;
5744          }
5745        }
5746      }
5747      else
5748      {
5749        i++;
5750        if (i < 5)
5751          continue;
5752      }
5753#ifdef HAVE_FLINT
5754      reconstructionTry (result, bufF, factors, l, factorsFound,
5755                         factorsFoundIndex, FLINTN, beenInThres
5756                        );
5757      if (result.length() == nmod_mat_ncols (FLINTN))
5758      {
5759        nmod_mat_clear (FLINTN);
5760#else
5761      reconstructionTry (result, bufF, factors, l, factorsFound,
5762                         factorsFoundIndex, NTLN, beenInThres
5763                        );
5764      if (result.length() == NTLN.NumCols())
5765      {
5766#endif
5767        delete [] liftPre;
5768        delete [] factorsFoundIndex;
5769        return result;
5770      }
5771      i++;
5772    }
5773  }
5774
5775#ifdef HAVE_FLINT
5776  nmod_mat_clear (FLINTN);
5777#endif
5778  delete [] liftPre;
5779  delete [] factorsFoundIndex;
5780  return result;
5781}
5782
5783CFList
5784earlyReconstructionAndLifting (const CanonicalForm& F, const mat_zz_pE& N,
5785                               CanonicalForm& bufF, CFList& factors, int& l,
5786                               int& factorsFound, bool beenInThres, CFMatrix& M,
5787                               CFArray& Pi, CFList& diophant, bool symmetric,
5788                               const CanonicalForm& evaluation
5789                              )
5790{
5791  int sizeOfLiftPre;
5792  int * liftPre= getLiftPrecisions (F, sizeOfLiftPre, degree (LC (F, 1), 2));
5793  Variable y= F.mvar();
5794  factorsFound= 0;
5795  CanonicalForm LCF= LC (F, 1);
5796  CFList result;
5797  int smallFactorDeg= 11;
5798  mat_zz_pE NTLN= N;
5799  int * factorsFoundIndex= new int [NTLN.NumCols()];
5800  for (long i= 0; i < NTLN.NumCols(); i++)
5801    factorsFoundIndex [i]= 0;
5802
5803  if (degree (F) + 1 > smallFactorDeg)
5804  {
5805    if (l < smallFactorDeg)
5806    {
5807      factors.insert (LCF);
5808      henselLiftResume12 (F, factors, l, smallFactorDeg, Pi, diophant, M);
5809      l= smallFactorDeg;
5810    }
5811    reconstructionTry (result, bufF, factors, smallFactorDeg, factorsFound,
5812                       factorsFoundIndex, NTLN, beenInThres
5813                      );
5814    if (result.length() == NTLN.NumCols())
5815    {
5816      delete [] liftPre;
5817      delete [] factorsFoundIndex;
5818      return result;
5819    }
5820  }
5821
5822  int i= sizeOfLiftPre - 1;
5823  int dummy= 1;
5824  if (sizeOfLiftPre > 1 && sizeOfLiftPre < 30)
5825  {
5826    while (i > 0)
5827    {
5828      if (l < liftPre[i-1] + 1)
5829      {
5830        factors.insert (LCF);
5831        henselLiftResume12 (F, factors, l, liftPre[i-1] + 1, Pi, diophant, M);
5832        l= liftPre[i-1] + 1;
5833      }
5834      else
5835      {
5836        i--;
5837        if (i != 0)
5838          continue;
5839      }
5840      reconstructionTry (result, bufF, factors, l, factorsFound,
5841                         factorsFoundIndex, NTLN, beenInThres
5842                        );
5843      if (result.length() == NTLN.NumCols())
5844      {
5845        delete [] liftPre;
5846        delete [] factorsFoundIndex;
5847        return result;
5848      }
5849      i--;
5850    }
5851  }
5852  else
5853  {
5854    i= 1;
5855    while ((degree (F,y)/4+1)*i + 4 <= smallFactorDeg)
5856      i++;
5857    while (i < 5)
5858    {
5859      dummy= tmin (degree (F,y)+1, (degree (F,y)/4+1)*i+4);
5860      if (l < dummy)
5861      {
5862        factors.insert (LCF);
5863        henselLiftResume12 (F, factors, l, dummy, Pi, diophant, M);
5864        l= dummy;
5865        if (i == 1 && degree (F)%4==0 && symmetric && factors.length() == 2 &&
5866            LC (F,1).inCoeffDomain() &&
5867           (degree (factors.getFirst(), 1) == degree (factors.getLast(),1)))
5868        {
5869          Variable x= Variable (1);
5870          CanonicalForm g, h, gg, hh, multiplier1, multiplier2, check1, check2;
5871          int m= degree (F)/4+1;
5872          g= factors.getFirst();
5873          h= factors.getLast();
5874          g= mod (g, power (y,m));
5875          h= mod (h, power (y,m));
5876          g= g (y-evaluation, y);
5877          h= h (y-evaluation, y);
5878          gg= mod (swapvar (g,x,y),power (x,m));
5879          gg= gg (y + evaluation, y);
5880          multiplier1= factors.getLast()[m-1][0]/gg[m-1][0];
5881          gg= div (gg, power (y,m));
5882          gg= gg*power (y,m);
5883          hh= mod (swapvar (h,x,y),power (x,m));
5884          hh= hh (y + evaluation, y);
5885          multiplier2= factors.getFirst()[m-1][0]/hh[m-1][0];
5886          hh= div (hh, power (y,m));
5887          hh= hh*power (y,m);
5888          gg= multiplier1*gg+mod (factors.getLast(), power (y,m));
5889          hh= multiplier2*hh+mod (factors.getFirst(), power (y,m));
5890          check1= gg (y-evaluation,y);
5891          check2= hh (y-evaluation,y);
5892          check1= swapvar (check1, x, y);
5893          if (check1/Lc (check1) == check2/Lc (check2))
5894          {
5895            result.append (gg);
5896            result.append (hh);
5897            delete [] liftPre;
5898            delete [] factorsFoundIndex;
5899            return result;
5900          }
5901        }
5902      }
5903      else
5904      {
5905        i++;
5906        if (i < 5)
5907          continue;
5908      }
5909      reconstructionTry (result, bufF, factors, l, factorsFound,
5910                         factorsFoundIndex, NTLN, beenInThres
5911                        );
5912      if (result.length() == NTLN.NumCols())
5913      {
5914        delete [] liftPre;
5915        delete [] factorsFoundIndex;
5916        return result;
5917      }
5918      i++;
5919    }
5920  }
5921
5922  delete [] liftPre;
5923  delete [] factorsFoundIndex;
5924  return result;
5925}
5926
5927//over field extension
5928CFList
5929extEarlyReconstructionAndLifting (const CanonicalForm& F, const mat_zz_p& N,
5930                                  CanonicalForm& bufF, CFList& factors, int& l,
5931                                  int& factorsFound, bool beenInThres, CFMatrix&
5932                                  M, CFArray& Pi, CFList& diophant, const
5933                                  ExtensionInfo& info, const CanonicalForm&
5934                                  evaluation
5935                                 )
5936{
5937  int sizeOfLiftPre;
5938  int * liftPre= getLiftPrecisions (F, sizeOfLiftPre, degree (LC (F, 1), 2));
5939  Variable y= F.mvar();
5940  factorsFound= 0;
5941  CanonicalForm LCF= LC (F, 1);
5942  CFList result;
5943  int smallFactorDeg= 11;
5944  mat_zz_p NTLN= N;
5945  int * factorsFoundIndex= new int [NTLN.NumCols()];
5946  for (long i= 0; i < NTLN.NumCols(); i++)
5947    factorsFoundIndex [i]= 0;
5948
5949  if (degree (F) + 1 > smallFactorDeg)
5950  {
5951    if (l < smallFactorDeg)
5952    {
5953      factors.insert (LCF);
5954      henselLiftResume12 (F, factors, l, smallFactorDeg, Pi, diophant, M);
5955      l= smallFactorDeg;
5956    }
5957    extReconstructionTry (result, bufF, factors, smallFactorDeg, factorsFound,
5958                          factorsFoundIndex, NTLN, beenInThres, info,
5959                          evaluation
5960                      );
5961    if (result.length() == NTLN.NumCols())
5962    {
5963      delete [] liftPre;
5964      delete [] factorsFoundIndex;
5965      return result;
5966    }
5967  }
5968
5969  int i= sizeOfLiftPre - 1;
5970  int dummy= 1;
5971  if (sizeOfLiftPre > 1 && sizeOfLiftPre < 30)
5972  {
5973    while (i > 0)
5974    {
5975      if (l < liftPre[i-1] + 1)
5976      {
5977        factors.insert (LCF);
5978        henselLiftResume12 (F, factors, l, liftPre[i-1] + 1, Pi, diophant, M);
5979        l= liftPre[i-1] + 1;
5980      }
5981      else
5982      {
5983        i--;
5984        if (i != 0)
5985          continue;
5986      }
5987      extReconstructionTry (result, bufF, factors, l, factorsFound,
5988                            factorsFoundIndex, NTLN, beenInThres, info,
5989                            evaluation
5990                           );
5991      if (result.length() == NTLN.NumCols())
5992      {
5993        delete [] liftPre;
5994        delete [] factorsFoundIndex;
5995