source: git/factory/facFqBivar.cc @ f78374

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