source: git/factory/facFqBivar.cc @ da984c

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