source: git/factory/facFqBivar.cc @ 72bfc8

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