source: git/factory/facFqBivar.cc @ 3ed6758

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