source: git/factory/facFqBivar.cc @ a36fcb5

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