source: git/factory/facFqBivar.cc @ c1b9927

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