source: git/factory/facFqBivar.cc @ 978ce3

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