source: git/factory/facFqBivar.cc @ a209e1d

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