source: git/factory/facFqFactorize.cc @ eefc3a

spielwiese
Last change on this file since eefc3a was eefc3a, checked in by Martin Lee <martinlee84@…>, 12 years ago
chg: postpone shifting of evaluation point to zero until it is really needed
  • Property mode set to 100644
File size: 73.6 KB
Line 
1/*****************************************************************************\
2 * Computer Algebra System SINGULAR
3\*****************************************************************************/
4/** @file facFqFactorize.cc
5 *
6 * This file implements functions for factoring a multivariate polynomial over
7 * a finite field.
8 *
9 * ABSTRACT: "Efficient Multivariate Factorization over Finite Fields" by
10 * L. Bernardin & M. Monagon. Precomputation of leading coefficients is
11 * described in "Sparse Hensel lifting" by E. Kaltofen
12 *
13 * @author Martin Lee
14 *
15 * @internal @version \$Id$
16 *
17 **/
18/*****************************************************************************/
19
20#include "config.h"
21
22#include "cf_assert.h"
23#include "debug.h"
24#include "timing.h"
25
26#include "facFqFactorizeUtil.h"
27#include "facFqFactorize.h"
28#include "cf_random.h"
29#include "facHensel.h"
30#include "cf_gcd_smallp.h"
31#include "cf_map_ext.h"
32#include "algext.h"
33#include "facSparseHensel.h"
34
35#ifdef HAVE_NTL
36#include <NTL/ZZ_pEX.h>
37#include "NTLconvert.h"
38
39TIMING_DEFINE_PRINT(fac_bi_factorizer)
40TIMING_DEFINE_PRINT(fac_hensel_lift)
41TIMING_DEFINE_PRINT(fac_factor_recombination)
42
43static inline
44CanonicalForm
45listGCD (const CFList& L);
46
47static inline
48CanonicalForm
49myContent (const CanonicalForm& F)
50{
51  CanonicalForm G= swapvar (F, F.mvar(), Variable (1));
52  CFList L;
53  for (CFIterator i= G; i.hasTerms(); i++)
54    L.append (i.coeff());
55  if (L.length() == 2)
56    return swapvar (gcd (L.getFirst(), L.getLast()), F.mvar(), Variable (1));
57  if (L.length() == 1)
58    return LC (F, Variable (1));
59  return swapvar (listGCD (L), F.mvar(), Variable (1));
60}
61
62static inline
63CanonicalForm
64listGCD (const CFList& L)
65{
66  if (L.length() == 1)
67    return L.getFirst();
68  if (L.length() == 2)
69    return gcd (L.getFirst(), L.getLast());
70  else
71  {
72    CFList lHi, lLo;
73    CanonicalForm resultHi, resultLo;
74    int length= L.length()/2;
75    int j= 0;
76    for (CFListIterator i= L; j < length; i++, j++)
77      lHi.append (i.getItem());
78    lLo= Difference (L, lHi);
79    resultHi= listGCD (lHi);
80    resultLo= listGCD (lLo);
81    if (resultHi.isOne() || resultLo.isOne())
82      return 1;
83    return gcd (resultHi, resultLo);
84  }
85}
86
87static inline
88CanonicalForm
89myContent (const CanonicalForm& F, const Variable& x)
90{
91  if (degree (F, x) <= 0)
92    return 1;
93  CanonicalForm G= F;
94  bool swap= false;
95  if (x != F.mvar())
96  {
97    swap= true;
98    G= swapvar (F, x, F.mvar());
99  }
100  CFList L;
101  Variable alpha;
102  for (CFIterator i= G; i.hasTerms(); i++)
103    L.append (i.coeff());
104  if (L.length() == 2)
105  {
106    if (swap)
107      return swapvar (gcd (L.getFirst(), L.getLast()), F.mvar(), x);
108    else
109      return gcd (L.getFirst(), L.getLast());
110  }
111  if (L.length() == 1)
112  {
113    return LC (F, x);
114  }
115  if (swap)
116    return swapvar (listGCD (L), F.mvar(), x);
117  else
118    return listGCD (L);
119}
120
121CanonicalForm myCompress (const CanonicalForm& F, CFMap& N)
122{
123  int n= F.level();
124  int * degsf= new int [n + 1];
125  int ** swap;
126  swap= new int* [n + 1];
127  for (int i= 0; i <= n; i++)
128  {
129    degsf[i]= 0;
130    swap [i]= new int [2];
131    swap [i] [0]= 0;
132    swap [i] [1]= 0;
133  }
134  int i= 1;
135  n= 1;
136  degsf= degrees (F, degsf);
137
138  CanonicalForm result= F;
139  while ( i <= F.level() )
140  {
141    while( degsf[i] == 0 ) i++;
142    swap[n][0]= i;
143    swap[n][1]= degsf[i];
144    if (i != n)
145      result= swapvar (result, Variable (n), Variable(i));
146    n++; i++;
147  }
148
149  int buf1, buf2;
150  n--;
151
152  for (i= 1; i < n; i++)
153  {
154    for (int j= 1; j < n - i + 1; j++)
155    {
156      if (swap[j][1] < swap[j + 1][1])
157      {
158        buf1= swap [j + 1] [0];
159        buf2= swap [j + 1] [1];
160        swap[j + 1] [0]= swap[j] [0];
161        swap[j + 1] [1]= swap[j] [1];
162        swap[j][0]= buf1;
163        swap[j][1]= buf2;
164        result= swapvar (result, Variable (j + 1), Variable (j));
165      }
166    }
167  }
168
169  for (i= n; i > 0; i--)
170  {
171    if (i != swap[i] [0])
172      N.newpair (Variable (i), Variable (swap[i] [0]));
173  }
174
175  for (i= 0; i <= n; i++)
176    delete [] swap[i];
177  delete [] swap;
178
179  delete [] degsf;
180
181  return result;
182}
183
184CFList
185extFactorRecombination (const CFList& factors, const CanonicalForm& F,
186                        const CFList& M, const ExtensionInfo& info,
187                        const CFList& evaluation)
188{
189  Variable alpha= info.getAlpha();
190  Variable beta= info.getBeta();
191  CanonicalForm gamma= info.getGamma();
192  CanonicalForm delta= info.getDelta();
193  int k= info.getGFDegree();
194  CFList source, dest;
195  if (factors.length() == 1)
196  {
197    CanonicalForm buf= reverseShift (F, evaluation);
198    return CFList (mapDown (buf, info, source, dest));
199  }
200  if (factors.length() < 1)
201    return CFList();
202
203  int degMipoBeta= 1;
204  if (!k && beta.level() != 1)
205    degMipoBeta= degree (getMipo (beta));
206
207  CFList T, S;
208  T= factors;
209
210  int s= 1;
211  CFList result;
212  CanonicalForm buf;
213
214  buf= F;
215
216  CanonicalForm g, LCBuf= LC (buf, Variable (1));
217  CanonicalForm buf2, quot;
218  int * v= new int [T.length()];
219  for (int i= 0; i < T.length(); i++)
220    v[i]= 0;
221  bool noSubset= false;
222  CFArray TT;
223  TT= copy (factors);
224  bool recombination= false;
225  bool trueFactor= false;
226  while (T.length() >= 2*s)
227  {
228    while (noSubset == false)
229    {
230      if (T.length() == s)
231      {
232        delete [] v;
233        if (recombination)
234        {
235          T.insert (LCBuf);
236          g= prodMod (T, M);
237          T.removeFirst();
238          result.append (g/myContent (g));
239          g= reverseShift (g, evaluation);
240          g /= Lc (g);
241          appendTestMapDown (result, g, info, source, dest);
242          return result;
243        }
244        else
245        {
246          buf= reverseShift (buf, evaluation);
247          return CFList (buf);
248        }
249      }
250
251      S= subset (v, s, TT, noSubset);
252      if (noSubset) break;
253
254      S.insert (LCBuf);
255      g= prodMod (S, M);
256      S.removeFirst();
257      g /= myContent (g);
258      if (fdivides (g, buf, quot))
259      {
260        buf2= reverseShift (g, evaluation);
261        buf2 /= Lc (buf2);
262        if (!k && beta == Variable (1))
263        {
264          if (degree (buf2, alpha) < degMipoBeta)
265          {
266            appendTestMapDown (result, buf2, info, source, dest);
267            buf= quot;
268            LCBuf= LC (buf, Variable (1));
269            recombination= true;
270            trueFactor= true;
271          }
272        }
273        else
274        {
275          if (!isInExtension (buf2, gamma, k, delta, source, dest))
276          {
277            appendTestMapDown (result, buf2, info, source, dest);
278            buf /= g;
279            LCBuf= LC (buf, Variable (1));
280            recombination= true;
281            trueFactor= true;
282          }
283        }
284
285        if (trueFactor)
286        {
287          T= Difference (T, S);
288
289          if (T.length() < 2*s || T.length() == s)
290          {
291            buf= reverseShift (buf, evaluation);
292            buf /= Lc (buf);
293            appendTestMapDown (result, buf, info, source, dest);
294            delete [] v;
295            return result;
296          }
297          trueFactor= false;
298          TT= copy (T);
299          indexUpdate (v, s, T.length(), noSubset);
300          if (noSubset) break;
301        }
302      }
303    }
304    s++;
305    if (T.length() < 2*s || T.length() == s)
306    {
307      buf= reverseShift (buf, evaluation);
308      appendTestMapDown (result, buf, info, source, dest);
309      delete [] v;
310      return result;
311    }
312    for (int i= 0; i < T.length(); i++)
313      v[i]= 0;
314    noSubset= false;
315  }
316  if (T.length() < 2*s)
317  {
318    buf= reverseShift (F, evaluation);
319    appendMapDown (result, buf, info, source, dest);
320  }
321
322  delete [] v;
323  return result;
324}
325
326CFList
327factorRecombination (const CanonicalForm& F, const CFList& factors,
328                     const CFList& M)
329{
330  if (factors.length() == 1)
331    return CFList(F);
332  if (factors.length() < 1)
333    return CFList();
334
335  CFList T, S;
336
337  T= factors;
338
339  int s= 1;
340  CFList result;
341  CanonicalForm LCBuf= LC (F, Variable (1));
342  CanonicalForm g, buf= F;
343  int * v= new int [T.length()];
344  for (int i= 0; i < T.length(); i++)
345    v[i]= 0;
346  bool noSubset= false;
347  CFArray TT;
348  TT= copy (factors);
349  Variable y= F.level() - 1;
350  bool recombination= false;
351  CanonicalForm h, quot;
352  while (T.length() >= 2*s)
353  {
354    while (noSubset == false)
355    {
356      if (T.length() == s)
357      {
358        delete [] v;
359        if (recombination)
360        {
361          T.insert (LC (buf));
362          g= prodMod (T, M);
363          result.append (g/myContent (g));
364          return result;
365        }
366        else
367          return CFList (F);
368      }
369      S= subset (v, s, TT, noSubset);
370      if (noSubset) break;
371      S.insert (LCBuf);
372      g= prodMod (S, M);
373      S.removeFirst();
374      g /= myContent (g);
375      if (fdivides (g, buf, quot))
376      {
377        recombination= true;
378        result.append (g);
379        buf= quot;
380        LCBuf= LC (buf, Variable(1));
381        T= Difference (T, S);
382        if (T.length() < 2*s || T.length() == s)
383        {
384          result.append (buf);
385          delete [] v;
386          return result;
387        }
388        TT= copy (T);
389        indexUpdate (v, s, T.length(), noSubset);
390        if (noSubset) break;
391      }
392    }
393    s++;
394    if (T.length() < 2*s || T.length() == s)
395    {
396      result.append (buf);
397      delete [] v;
398      return result;
399    }
400    for (int i= 0; i < T.length(); i++)
401      v[i]= 0;
402    noSubset= false;
403  }
404  if (T.length() < 2*s)
405    result.append (F);
406
407  delete [] v;
408  return result;
409}
410
411int
412liftBoundAdaption (const CanonicalForm& F, const CFList& factors, bool&
413                   success, const int deg, const CFList& MOD, const int bound)
414{
415  int adaptedLiftBound= 0;
416  CanonicalForm buf= F;
417  Variable y= F.mvar();
418  CanonicalForm LCBuf= LC (buf, Variable (1));
419  CanonicalForm g, quot;
420  CFList M= MOD;
421  M.append (power (y, deg));
422  int d= bound;
423  int e= 0;
424  int nBuf;
425  for (CFListIterator i= factors; i.hasItem(); i++)
426  {
427    g= mulMod (i.getItem(), LCBuf, M);
428    g /= myContent (g);
429    if (fdivides (g, buf, quot))
430    {
431      nBuf= degree (g, y) + degree (LC (g, 1), y);
432      d -= nBuf;
433      e= tmax (e, nBuf);
434      buf= quot;
435      LCBuf= LC (buf, Variable (1));
436    }
437  }
438  adaptedLiftBound= d;
439
440  if (adaptedLiftBound < deg)
441  {
442    if (adaptedLiftBound < degree (F) + 1)
443    {
444      if (d == 1)
445      {
446        if (e + 1 > deg)
447        {
448          adaptedLiftBound= deg;
449          success= false;
450        }
451        else
452        {
453          success= true;
454          if (e + 1 < degree (F) + 1)
455            adaptedLiftBound= deg;
456          else
457            adaptedLiftBound= e + 1;
458        }
459      }
460      else
461      {
462        success= true;
463        adaptedLiftBound= deg;
464      }
465    }
466    else
467    {
468      success= true;
469    }
470  }
471  return adaptedLiftBound;
472}
473
474int
475extLiftBoundAdaption (const CanonicalForm& F, const CFList& factors, bool&
476                      success, const ExtensionInfo& info, const CFList& eval,
477                      const int deg, const CFList& MOD, const int bound)
478{
479  Variable alpha= info.getAlpha();
480  Variable beta= info.getBeta();
481  CanonicalForm gamma= info.getGamma();
482  CanonicalForm delta= info.getDelta();
483  int k= info.getGFDegree();
484  int adaptedLiftBound= 0;
485  CanonicalForm buf= F;
486  Variable y= F.mvar();
487  CanonicalForm LCBuf= LC (buf, Variable (1));
488  CanonicalForm g, gg, quot;
489  CFList M= MOD;
490  M.append (power (y, deg));
491  adaptedLiftBound= 0;
492  int d= bound;
493  int e= 0;
494  int nBuf;
495  int degMipoBeta= 1;
496  if (!k && beta.level() != 1)
497    degMipoBeta= degree (getMipo (beta));
498
499  CFList source, dest;
500  for (CFListIterator i= factors; i.hasItem(); i++)
501  {
502    g= mulMod (i.getItem(), LCBuf, M);
503    g /= myContent (g);
504    if (fdivides (g, buf, quot))
505    {
506      gg= reverseShift (g, eval);
507      gg /= Lc (gg);
508      if (!k && beta == Variable (1))
509      {
510        if (degree (gg, alpha) < degMipoBeta)
511        {
512          buf= quot;
513          nBuf= degree (g, y) + degree (LC (g, Variable (1)), y);
514          d -= nBuf;
515          e= tmax (e, nBuf);
516          LCBuf= LC (buf, Variable (1));
517        }
518      }
519      else
520      {
521        if (!isInExtension (gg, gamma, k, delta, source, dest))
522        {
523          buf= quot;
524          nBuf= degree (g, y) + degree (LC (g, Variable (1)), y);
525          d -= nBuf;
526          e= tmax (e, nBuf);
527          LCBuf= LC (buf, Variable (1));
528        }
529      }
530    }
531  }
532  adaptedLiftBound= d;
533
534  if (adaptedLiftBound < deg)
535  {
536    if (adaptedLiftBound < degree (F) + 1)
537    {
538      if (d == 1)
539      {
540        if (e + 1 > deg)
541        {
542          adaptedLiftBound= deg;
543          success= false;
544        }
545        else
546        {
547          success= true;
548          if (e + 1 < degree (F) + 1)
549            adaptedLiftBound= deg;
550          else
551            adaptedLiftBound= e + 1;
552        }
553      }
554      else
555      {
556        success= true;
557        adaptedLiftBound= deg;
558      }
559    }
560    else
561    {
562      success= true;
563    }
564  }
565
566  return adaptedLiftBound;
567}
568
569CFList
570earlyFactorDetect (CanonicalForm& F, CFList& factors, int& adaptedLiftBound,
571                   bool& success, const int deg, const CFList& MOD,
572                   const int bound)
573{
574  CFList result;
575  CFList T= factors;
576  CanonicalForm buf= F;
577  Variable y= F.mvar();
578  CanonicalForm LCBuf= LC (buf, Variable (1));
579  CanonicalForm g, quot;
580  CFList M= MOD;
581  M.append (power (y, deg));
582  adaptedLiftBound= 0;
583  int d= bound;
584  int e= 0;
585  int nBuf;
586  for (CFListIterator i= factors; i.hasItem(); i++)
587  {
588    g= mulMod (i.getItem(), LCBuf, M);
589    g /= myContent (g);
590    if (fdivides (g, buf, quot))
591    {
592      result.append (g);
593      nBuf= degree (g, y) + degree (LC (g, Variable (1)), y);
594      d -= nBuf;
595      e= tmax (e, nBuf);
596      buf= quot;
597      LCBuf= LC (buf, Variable (1));
598      T= Difference (T, CFList (i.getItem()));
599    }
600  }
601  adaptedLiftBound= d;
602
603  if (adaptedLiftBound < deg)
604  {
605    if (adaptedLiftBound < degree (F) + 1)
606    {
607      if (d == 1)
608        adaptedLiftBound= tmin (e + 1, deg);
609      else
610        adaptedLiftBound= deg;
611    }
612    factors= T;
613    F= buf;
614    success= true;
615  }
616  return result;
617}
618
619CFList
620extEarlyFactorDetect (CanonicalForm& F, CFList& factors, int& adaptedLiftBound,
621                      bool& success, const ExtensionInfo& info, const CFList&
622                      eval, const int deg, const CFList& MOD, const int bound)
623{
624  Variable alpha= info.getAlpha();
625  Variable beta= info.getBeta();
626  CanonicalForm gamma= info.getGamma();
627  CanonicalForm delta= info.getDelta();
628  int k= info.getGFDegree();
629  CFList result;
630  CFList T= factors;
631  CanonicalForm buf= F;
632  Variable y= F.mvar();
633  CanonicalForm LCBuf= LC (buf, Variable (1));
634  CanonicalForm g, gg, quot;
635  CFList M= MOD;
636  M.append (power (y, deg));
637  adaptedLiftBound= 0;
638  int d= bound;
639  int e= 0;
640  int nBuf;
641  CFList source, dest;
642
643  int degMipoBeta= 1;
644  if (!k && beta.level() != 1)
645    degMipoBeta= degree (getMipo (beta));
646
647  for (CFListIterator i= factors; i.hasItem(); i++)
648  {
649    g= mulMod (i.getItem(), LCBuf, M);
650    g /= myContent (g);
651    if (fdivides (g, buf, quot))
652    {
653      gg= reverseShift (g, eval);
654      gg /= Lc (gg);
655      if (!k && beta == Variable (1))
656      {
657        if (degree (gg, alpha) < degMipoBeta)
658        {
659          appendTestMapDown (result, gg, info, source, dest);
660          buf= quot;
661          nBuf= degree (g, y) + degree (LC (g, Variable (1)), y);
662          d -= nBuf;
663          e= tmax (e, nBuf);
664          LCBuf= LC (buf, Variable (1));
665          T= Difference (T, CFList (i.getItem()));
666        }
667      }
668      else
669      {
670        if (!isInExtension (gg, gamma, k, delta, source, dest))
671        {
672          appendTestMapDown (result, gg, info, source, dest);
673          buf= quot;
674          nBuf= degree (g, y) + degree (LC (g, Variable (1)), y);
675          d -= nBuf;
676          e= tmax (e, nBuf);
677          LCBuf= LC (buf, Variable (1));
678          T= Difference (T, CFList (i.getItem()));
679         }
680      }
681    }
682  }
683  adaptedLiftBound= d;
684
685  if (adaptedLiftBound < deg)
686  {
687    if (adaptedLiftBound < degree (F) + 1)
688    {
689      if (d == 1)
690        adaptedLiftBound= tmin (e + 1, deg);
691      else
692        adaptedLiftBound= deg;
693    }
694    success= true;
695    factors= T;
696    F= buf;
697  }
698  return result;
699}
700
701CFList
702evalPoints (const CanonicalForm& F, CFList & eval, const Variable& alpha,
703            CFList& list, const bool& GF, bool& fail)
704{
705  int k= F.level() - 1;
706  Variable x= Variable (1);
707  CFList result;
708  FFRandom genFF;
709  GFRandom genGF;
710  int p= getCharacteristic ();
711  double bound;
712  if (alpha != Variable (1))
713  {
714    bound= pow ((double) p, (double) degree (getMipo(alpha)));
715    bound= pow ((double) bound, (double) k);
716  }
717  else if (GF)
718  {
719    bound= pow ((double) p, (double) getGFDegree());
720    bound= pow ((double) bound, (double) k);
721  }
722  else
723    bound= pow ((double) p, (double) k);
724
725  CanonicalForm random;
726  CanonicalForm deriv_x, gcd_deriv;
727  do
728  {
729    random= 0;
730    // possible overflow if list.length() does not fit into a int
731    if (list.length() >= bound)
732    {
733      fail= true;
734      break;
735    }
736    for (int i= 0; i < k; i++)
737    {
738      if (list.isEmpty())
739        result.append (0);
740      else if (GF)
741      {
742        result.append (genGF.generate());
743        random += result.getLast()*power (x, i);
744      }
745      else if (alpha.level() != 1)
746      {
747        AlgExtRandomF genAlgExt (alpha);
748        result.append (genAlgExt.generate());
749        random += result.getLast()*power (x, i);
750      }
751      else
752      {
753        result.append (genFF.generate());
754        random += result.getLast()*power (x, i);
755      }
756    }
757    if (find (list, random))
758    {
759      result= CFList();
760      continue;
761    }
762    int l= F.level();
763    eval.insert (F);
764    bool bad= false;
765    for (CFListIterator i= result; i.hasItem(); i++, l--)
766    {
767      eval.insert (eval.getFirst()(i.getItem(), l));
768      if (degree (eval.getFirst(), l - 1) != degree (F, l - 1))
769      {
770        if (!find (list, random))
771          list.append (random);
772        result= CFList();
773        eval= CFList();
774        bad= true;
775        break;
776      }
777    }
778
779    if (bad)
780      continue;
781
782    if (degree (eval.getFirst()) != degree (F, 1))
783    {
784      if (!find (list, random))
785        list.append (random);
786      result= CFList();
787      eval= CFList();
788      continue;
789    }
790
791    deriv_x= deriv (eval.getFirst(), x);
792    gcd_deriv= gcd (eval.getFirst(), deriv_x);
793    if (degree (gcd_deriv) > 0)
794    {
795      if (!find (list, random))
796        list.append (random);
797      result= CFList();
798      eval= CFList();
799      continue;
800    }
801    CFListIterator i= eval;
802    i++;
803    CanonicalForm contentx= content (i.getItem(), x);
804    if (degree (contentx) > 0)
805    {
806      if (!find (list, random))
807        list.append (random);
808      result= CFList();
809      eval= CFList();
810      continue;
811    }
812
813    if (list.length() >= bound)
814    {
815      fail= true;
816      break;
817    }
818  } while (find (list, random));
819
820  if (!eval.isEmpty())
821    eval.removeFirst();
822
823  return result;
824}
825
826static inline
827int newMainVariableSearch (CanonicalForm& A, CFList& Aeval, CFList&
828                           evaluation, const Variable& alpha, const int lev,
829                           CanonicalForm& g
830                          )
831{
832  Variable x= Variable (1);
833  CanonicalForm derivI, buf;
834  bool GF= (CFFactory::gettype() == GaloisFieldDomain);
835  int swapLevel= 0;
836  CFList list;
837  bool fail= false;
838  buf= A;
839  Aeval= CFList();
840  evaluation= CFList();
841  for (int i= lev; i <= A.level(); i++)
842  {
843    derivI= deriv (buf, Variable (i));
844    if (!derivI.isZero())
845    {
846      g= gcd (buf, derivI);
847      if (degree (g) > 0)
848        return -1;
849
850      buf= swapvar (buf, x, Variable (i));
851      Aeval= CFList();
852      evaluation= CFList();
853      fail= false;
854      evaluation= evalPoints (buf, Aeval, alpha, list, GF, fail);
855      if (!fail)
856      {
857        A= buf;
858        swapLevel= i;
859        break;
860      }
861      else
862        buf= A;
863    }
864  }
865  return swapLevel;
866}
867
868CanonicalForm lcmContent (const CanonicalForm& A, CFList& contentAi)
869{
870  int i= A.level();
871  contentAi.append (myContent (A, i));
872  contentAi.append (myContent (A, i - 1));
873  CanonicalForm result= lcm (contentAi.getFirst(), contentAi.getLast());
874  for (i= i - 2; i > 0; i--)
875  {
876    contentAi.append (content (A, i));
877    result= lcm (result, contentAi.getLast());
878  }
879  return result;
880}
881
882CFList
883henselLiftAndEarly (CanonicalForm& A, CFList& MOD, int*& liftBounds, bool&
884                    earlySuccess, CFList& earlyFactors, const CFList& Aeval,
885                    const CFList& biFactors, const CFList& evaluation,
886                    const ExtensionInfo& info)
887{
888  bool extension= info.isInExtension();
889  CFList bufFactors= biFactors;
890  bufFactors.insert (LC (Aeval.getFirst(), 1));
891
892  sortList (bufFactors, Variable (1));
893
894  CFList diophant;
895  CFArray Pi;
896  int smallFactorDeg= 11; //tunable parameter
897  CFList result;
898  int adaptedLiftBound= 0;
899  int liftBound= liftBounds[1];
900
901  earlySuccess= false;
902  CFList earlyReconstFactors;
903  CFListIterator j= Aeval;
904  j++;
905  CanonicalForm buf= j.getItem();
906  CFMatrix Mat= CFMatrix (liftBound, bufFactors.length() - 1);
907  MOD= CFList (power (Variable (2), liftBounds[0]));
908  if (smallFactorDeg >= liftBound)
909  {
910    result= henselLift23 (Aeval, bufFactors, liftBounds, diophant, Pi, Mat);
911  }
912  else if (smallFactorDeg >= degree (buf) + 1)
913  {
914    liftBounds[1]= degree (buf) + 1;
915    result= henselLift23 (Aeval, bufFactors, liftBounds, diophant, Pi, Mat);
916    if (Aeval.length() == 2)
917    {
918      if (!extension)
919        earlyFactors= earlyFactorDetect
920                       (buf, result, adaptedLiftBound, earlySuccess,
921                        degree (buf) + 1, MOD, liftBound);
922      else
923        earlyFactors= extEarlyFactorDetect
924                       (buf, result, adaptedLiftBound, earlySuccess,
925                        info, evaluation, degree
926                        (buf) + 1, MOD, liftBound);
927    }
928    else
929    {
930      if (!extension)
931        adaptedLiftBound= liftBoundAdaption (buf, result, earlySuccess,
932                                             degree (buf) + 1, MOD, liftBound);
933      else
934        adaptedLiftBound= extLiftBoundAdaption (buf, result, earlySuccess, info,
935                                                evaluation, degree (buf) + 1,
936                                                MOD, liftBound);
937    }
938    if (!earlySuccess)
939    {
940      result.insert (LC (buf, 1));
941      liftBounds[1]= adaptedLiftBound;
942      liftBound= adaptedLiftBound;
943      henselLiftResume (buf, result, degree (buf) + 1, liftBound,
944                        Pi, diophant, Mat, MOD);
945    }
946    else
947      liftBounds[1]= adaptedLiftBound;
948  }
949  else if (smallFactorDeg < degree (buf) + 1)
950  {
951    liftBounds[1]= smallFactorDeg;
952    result= henselLift23 (Aeval, bufFactors, liftBounds, diophant, Pi, Mat);
953    if (Aeval.length() == 2)
954    {
955      if (!extension)
956        earlyFactors= earlyFactorDetect (buf, result, adaptedLiftBound,
957                                         earlySuccess, smallFactorDeg, MOD,
958                                         liftBound);
959      else
960        earlyFactors= extEarlyFactorDetect (buf, result, adaptedLiftBound,
961                                            earlySuccess, info, evaluation,
962                                            smallFactorDeg, MOD, liftBound);
963    }
964    else
965    {
966      if (!extension)
967        adaptedLiftBound= liftBoundAdaption (buf, result, earlySuccess,
968                                             smallFactorDeg, MOD, liftBound);
969      else
970        adaptedLiftBound= extLiftBoundAdaption (buf, result, earlySuccess, info,
971                                                evaluation, smallFactorDeg, MOD,
972                                                liftBound);
973    }
974
975    if (!earlySuccess)
976    {
977      result.insert (LC (buf, 1));
978      henselLiftResume (buf, result, smallFactorDeg, degree (buf) + 1,
979                        Pi, diophant, Mat, MOD);
980      if (Aeval.length() == 2)
981      {
982         if (!extension)
983           earlyFactors= earlyFactorDetect (buf, result, adaptedLiftBound,
984                                            earlySuccess, degree (buf) + 1,
985                                            MOD, liftBound);
986         else
987           earlyFactors= extEarlyFactorDetect (buf, result, adaptedLiftBound,
988                                               earlySuccess, info, evaluation,
989                                               degree (buf) + 1, MOD,
990                                               liftBound);
991      }
992      else
993      {
994        if (!extension)
995          adaptedLiftBound= liftBoundAdaption (buf, result, earlySuccess,
996                                               degree (buf) + 1, MOD,liftBound);
997        else
998          adaptedLiftBound= extLiftBoundAdaption (buf, result, earlySuccess,
999                                                  info, evaluation,
1000                                                  degree (buf) + 1, MOD,
1001                                                  liftBound);
1002      }
1003      if (!earlySuccess)
1004      {
1005        result.insert (LC (buf, 1));
1006        liftBounds[1]= adaptedLiftBound;
1007        liftBound= adaptedLiftBound;
1008        henselLiftResume (buf, result, degree (buf) + 1, liftBound,
1009                          Pi, diophant, Mat, MOD);
1010      }
1011      else
1012        liftBounds[1]= adaptedLiftBound;
1013    }
1014    else
1015      liftBounds[1]= adaptedLiftBound;
1016  }
1017
1018  MOD.append (power (Variable (3), liftBounds[1]));
1019
1020  if (Aeval.length() > 2)
1021  {
1022    CFListIterator j= Aeval;
1023    j++;
1024    CFList bufEval;
1025    bufEval.append (j.getItem());
1026    j++;
1027    int liftBoundsLength= Aeval.getLast().level() - 1;
1028    for (int i= 2; i <= liftBoundsLength && j.hasItem(); i++, j++)
1029    {
1030      earlySuccess= false;
1031      result.insert (LC (bufEval.getFirst(), 1));
1032      bufEval.append (j.getItem());
1033      liftBound= liftBounds[i];
1034      Mat= CFMatrix (liftBounds[i], result.length() - 1);
1035
1036      buf= j.getItem();
1037      if (smallFactorDeg >= liftBound)
1038        result= henselLift (bufEval, result, MOD, diophant, Pi, Mat,
1039                            liftBounds[i -  1], liftBounds[i]);
1040      else if (smallFactorDeg >= degree (buf) + 1)
1041      {
1042        result= henselLift (bufEval, result, MOD, diophant, Pi, Mat,
1043                            liftBounds[i -  1], degree (buf) + 1);
1044
1045        if (Aeval.length() == i + 1)
1046        {
1047          if (!extension)
1048            earlyFactors= earlyFactorDetect
1049                           (buf, result, adaptedLiftBound, earlySuccess,
1050                            degree (buf) + 1, MOD, liftBound);
1051          else
1052            earlyFactors= extEarlyFactorDetect
1053                           (buf, result, adaptedLiftBound, earlySuccess,
1054                            info, evaluation, degree (buf) + 1, MOD, liftBound);
1055        }
1056        else
1057        {
1058          if (!extension)
1059            adaptedLiftBound= liftBoundAdaption
1060                                (buf, result, earlySuccess, degree (buf)
1061                                 + 1,  MOD, liftBound);
1062          else
1063            adaptedLiftBound= extLiftBoundAdaption
1064                                (buf, result, earlySuccess, info, evaluation,
1065                                 degree (buf) + 1, MOD, liftBound);
1066        }
1067
1068        if (!earlySuccess)
1069        {
1070          result.insert (LC (buf, 1));
1071          liftBounds[i]= adaptedLiftBound;
1072          liftBound= adaptedLiftBound;
1073          henselLiftResume (buf, result, degree (buf) + 1, liftBound,
1074                            Pi, diophant, Mat, MOD);
1075        }
1076        else
1077        {
1078          liftBounds[i]= adaptedLiftBound;
1079        }
1080      }
1081      else if (smallFactorDeg < degree (buf) + 1)
1082      {
1083        result= henselLift (bufEval, result, MOD, diophant, Pi, Mat,
1084                            liftBounds[i -  1], smallFactorDeg);
1085
1086        if (Aeval.length() == i + 1)
1087        {
1088          if (!extension)
1089            earlyFactors= earlyFactorDetect
1090                           (buf, result, adaptedLiftBound, earlySuccess,
1091                            smallFactorDeg, MOD, liftBound);
1092          else
1093            earlyFactors= extEarlyFactorDetect
1094                           (buf, result, adaptedLiftBound, earlySuccess,
1095                            info, evaluation, smallFactorDeg, MOD, liftBound);
1096        }
1097        else
1098        {
1099          if (!extension)
1100            adaptedLiftBound= liftBoundAdaption
1101                                (buf, result, earlySuccess,
1102                                 smallFactorDeg, MOD, liftBound);
1103          else
1104            adaptedLiftBound= extLiftBoundAdaption
1105                                (buf, result, earlySuccess, info, evaluation,
1106                                 smallFactorDeg, MOD, liftBound);
1107        }
1108
1109        if (!earlySuccess)
1110        {
1111          result.insert (LC (buf, 1));
1112          henselLiftResume (buf, result, smallFactorDeg,
1113                            degree (buf) + 1, Pi, diophant, Mat, MOD);
1114          if (Aeval.length() == i + 1)
1115          {
1116            if (!extension)
1117              earlyFactors= earlyFactorDetect
1118                             (buf, result, adaptedLiftBound, earlySuccess,
1119                              degree (buf) +  1,  MOD, liftBound);
1120            else
1121              earlyFactors= extEarlyFactorDetect
1122                             (buf, result, adaptedLiftBound, earlySuccess,
1123                              info, evaluation, degree (buf) + 1, MOD,
1124                              liftBound);
1125          }
1126          else
1127          {
1128            if (!extension)
1129              adaptedLiftBound= liftBoundAdaption
1130                                  (buf, result, earlySuccess, degree
1131                                   (buf) +  1,  MOD, liftBound);
1132            else
1133              adaptedLiftBound= extLiftBoundAdaption
1134                                  (buf, result, earlySuccess, info, evaluation,
1135                                   degree (buf) + 1,  MOD, liftBound);
1136          }
1137
1138          if (!earlySuccess)
1139          {
1140            result.insert (LC (buf, 1));
1141            liftBounds[i]= adaptedLiftBound;
1142            liftBound= adaptedLiftBound;
1143            henselLiftResume (buf, result, degree (buf) + 1, liftBound,
1144                              Pi, diophant, Mat, MOD);
1145          }
1146          else
1147            liftBounds[i]= adaptedLiftBound;
1148        }
1149        else
1150          liftBounds[i]= adaptedLiftBound;
1151      }
1152      MOD.append (power (Variable (i + 2), liftBounds[i]));
1153      bufEval.removeFirst();
1154    }
1155    bufFactors= result;
1156  }
1157  else
1158    bufFactors= result;
1159
1160  if (earlySuccess)
1161    A= buf;
1162  return result;
1163}
1164
1165void
1166gcdFreeBasis (CFFList& factors1, CFFList& factors2)
1167{
1168  CanonicalForm g;
1169  int k= factors1.length();
1170  int l= factors2.length();
1171  int n= 1;
1172  int m;
1173  CFFListIterator j;
1174  for (CFFListIterator i= factors1; (n < k && i.hasItem()); i++, n++)
1175  {
1176    m= 1;
1177    for (j= factors2; (m < l && j.hasItem()); j++, m++)
1178    {
1179      g= gcd (i.getItem().factor(), j.getItem().factor());
1180      if (degree (g) > 0)
1181      {
1182        j.getItem()= CFFactor (j.getItem().factor()/g, j.getItem().exp());
1183        i.getItem()= CFFactor (i.getItem().factor()/g, i.getItem().exp());
1184        factors1.append (CFFactor (g, i.getItem().exp()));
1185        factors2.append (CFFactor (g, j.getItem().exp()));
1186      }
1187    }
1188  }
1189}
1190
1191CFList
1192distributeContent (const CFList& L, const CFList* differentSecondVarFactors,
1193                   int length
1194                  )
1195{
1196  CFList l= L;
1197  CanonicalForm content= l.getFirst();
1198
1199  if (content.inCoeffDomain())
1200    return l;
1201
1202  if (l.length() == 1)
1203  {
1204    CFList result;
1205    for (int i= 0; i < length; i++)
1206    {
1207      if (differentSecondVarFactors[i].isEmpty())
1208        continue;
1209      if (result.isEmpty())
1210      {
1211        result= differentSecondVarFactors[i];
1212        for (CFListIterator iter= result; iter.hasItem(); iter++)
1213          content /= iter.getItem();
1214      }
1215      else
1216      {
1217        CFListIterator iter1= result;
1218        for (CFListIterator iter2= differentSecondVarFactors[i]; iter2.hasItem();
1219             iter2++, iter1++)
1220        {
1221          iter1.getItem() *= iter2.getItem();
1222          content /= iter2.getItem();
1223        }
1224      }
1225    }
1226    result.insert (content);
1227    return result;
1228  }
1229
1230  Variable v;
1231  CFListIterator iter1;
1232  CanonicalForm tmp, g;
1233  for (int i= 0; i < length; i++)
1234  {
1235    if (differentSecondVarFactors[i].isEmpty())
1236      continue;
1237    iter1= l;
1238    iter1++;
1239
1240    v= Variable (i + 3);
1241    for (CFListIterator iter2= differentSecondVarFactors[i]; iter2.hasItem();
1242         iter2++, iter1++)
1243    {
1244      if (degree (iter2.getItem(),v) == degree (iter1.getItem(),v))
1245        continue;
1246      tmp= iter1.getItem();
1247      for (int j= tmp.level(); j > 1; j--)
1248      {
1249        if (j == i + 3)
1250          continue;
1251        tmp= tmp (0, j);
1252      }
1253      g= gcd (iter2.getItem(), content);
1254      if (degree (g) > 0)
1255      {
1256        iter2.getItem() /= tmp;
1257        content /= g;
1258        iter1.getItem() *= g;
1259      }
1260    }
1261  }
1262
1263  l.removeFirst();
1264  l.insert (content);
1265  return l;
1266}
1267
1268CFList evaluateAtZero (const CanonicalForm& F)
1269{
1270  CFList result;
1271  CanonicalForm buf= F;
1272  result.insert (buf);
1273  for (int i= F.level(); i > 2; i--)
1274  {
1275    buf= buf (0, i);
1276    result.insert (buf);
1277  }
1278  return result;
1279}
1280
1281CFList evaluateAtEval (const CanonicalForm& F, const CFArray& eval)
1282{
1283  CFList result;
1284  CanonicalForm buf= F;
1285  result.insert (buf);
1286  int k= eval.size();
1287  for (int i= 1; i < k; i++)
1288  {
1289    buf= buf (eval[i], i + 2);
1290    result.insert (buf);
1291  }
1292  return result;
1293}
1294
1295CFList evaluateAtEval (const CanonicalForm& F, const CFList& evaluation, int l)
1296{
1297  CFList result;
1298  CanonicalForm buf= F;
1299  result.insert (buf);
1300  int k= evaluation.length() + l - 1;
1301  CFListIterator j= evaluation;
1302  for (int i= k; j.hasItem() && i > l; i--, j++)
1303  {
1304    if (F.level() < i)
1305      continue;
1306    buf= buf (j.getItem(), i);
1307    result.insert (buf);
1308  }
1309  return result;
1310}
1311
1312int
1313testFactors (const CanonicalForm& G, const CFList& uniFactors,
1314             const Variable& alpha, CanonicalForm& sqrfPartF, CFList& factors,
1315             CFFList*& bufSqrfFactors, CFList& evalSqrfPartF,
1316             const CFArray& evalPoint)
1317{
1318  CanonicalForm tmp;
1319  CFListIterator j;
1320  for (CFListIterator i= uniFactors; i.hasItem(); i++)
1321  {
1322    tmp= i.getItem();
1323    if (i.hasItem())
1324      i++;
1325    else
1326      break;
1327    for (j= i; j.hasItem(); j++)
1328    {
1329      if (tmp == j.getItem())
1330        return 0;
1331    }
1332  }
1333
1334  CanonicalForm F= G;
1335  CFFList sqrfFactorization= squarefreeFactorization (F, alpha);
1336
1337  sqrfPartF= 1;
1338  for (CFFListIterator i= sqrfFactorization; i.hasItem(); i++)
1339    sqrfPartF *= i.getItem().factor();
1340
1341  evalSqrfPartF= evaluateAtEval (sqrfPartF, evalPoint);
1342
1343  CanonicalForm test= evalSqrfPartF.getFirst() (evalPoint[0], 2);
1344
1345  if (degree (test) != degree (sqrfPartF, 1))
1346    return 0;
1347
1348  CFFList sqrfFactors;
1349  CFList tmp2;
1350  int k= 0;
1351  factors= uniFactors;
1352  CFFListIterator iter;
1353  for (CFListIterator i= factors; i.hasItem(); i++, k++)
1354  {
1355    tmp= 1;
1356    sqrfFactors= squarefreeFactorization (i.getItem(), alpha);
1357
1358    for (iter= sqrfFactors; iter.hasItem(); iter++)
1359    {
1360      tmp2.append (iter.getItem().factor());
1361      tmp *= iter.getItem().factor();
1362    }
1363    i.getItem()= tmp/Lc(tmp);
1364    bufSqrfFactors [k]= sqrfFactors;
1365  }
1366
1367  for (int i= 0; i < factors.length() - 1; i++)
1368  {
1369    for (k= i + 1; k < factors.length(); k++)
1370    {
1371      gcdFreeBasis (bufSqrfFactors [i], bufSqrfFactors[k]);
1372    }
1373  }
1374
1375  factors= CFList();
1376  for (int i= 0; i < uniFactors.length(); i++)
1377  {
1378    if (i == 0)
1379    {
1380      for (iter= bufSqrfFactors [i]; iter.hasItem(); iter++)
1381      {
1382        if (iter.getItem().factor().inCoeffDomain())
1383          continue;
1384        iter.getItem()= CFFactor (iter.getItem().factor()/
1385                                  Lc (iter.getItem().factor()),
1386                                  iter.getItem().exp());
1387        factors.append (iter.getItem().factor());
1388      }
1389    }
1390    else
1391    {
1392      for (iter= bufSqrfFactors [i]; iter.hasItem(); iter++)
1393      {
1394        if (iter.getItem().factor().inCoeffDomain())
1395          continue;
1396        iter.getItem()= CFFactor (iter.getItem().factor()/
1397                                  Lc (iter.getItem().factor()),
1398                                  iter.getItem().exp());
1399        if (!find (factors, iter.getItem().factor()))
1400          factors.append (iter.getItem().factor());
1401      }
1402    }
1403  }
1404
1405  test= prod (factors);
1406  tmp= evalSqrfPartF.getFirst() (evalPoint[0],2);
1407  if (test/Lc (test) != tmp/Lc (tmp))
1408    return 0;
1409  else
1410    return 1;
1411}
1412
1413CFList
1414precomputeLeadingCoeff (const CanonicalForm& LCF, const CFList& LCFFactors,
1415                        const Variable& alpha, const CFList& evaluation,
1416                        CFList* & differentSecondVarLCs, int lSecondVarLCs,
1417                        Variable& y
1418                       )
1419{
1420  y= Variable (1);
1421  if (LCF.inCoeffDomain())
1422  {
1423    CFList result;
1424    for (int i= 1; i <= LCFFactors.length() + 1; i++)
1425      result.append (1);
1426    return result;
1427  }
1428
1429  CFMap N;
1430  CanonicalForm F= compress (LCF, N);
1431  if (LCF.isUnivariate())
1432  {
1433    CFList result;
1434    int LCFLevel= LCF.level();
1435    bool found= false;
1436    if (LCFLevel == 2)
1437    {
1438    //bivariate leading coefficients are already the true leading coefficients
1439      result= LCFFactors;
1440      found= true;
1441    }
1442    else
1443    {
1444      CFListIterator j;
1445      for (int i= 0; i < lSecondVarLCs; i++)
1446      {
1447        for (j= differentSecondVarLCs[i]; j.hasItem(); j++)
1448        {
1449          if (j.getItem().level() == LCFLevel)
1450          {
1451            found= true;
1452            break;
1453          }
1454        }
1455        if (found)
1456        {
1457          result= differentSecondVarLCs [i];
1458          break;
1459        }
1460      }
1461      if (!found)
1462        result= LCFFactors;
1463    }
1464    if (found)
1465      result.insert (Lc (LCF));
1466    else
1467      result.append (LCF);
1468    return result;
1469  }
1470
1471  CFList factors= LCFFactors;
1472
1473  CFMap dummy;
1474  for (CFListIterator i= factors; i.hasItem(); i++)
1475    i.getItem()= compress (i.getItem(), dummy);
1476
1477  CanonicalForm sqrfPartF;
1478  CFFList * bufSqrfFactors= new CFFList [factors.length()];
1479  CFList evalSqrfPartF, bufFactors;
1480  CFArray evalPoint= CFArray (evaluation.length() - 1);
1481  CFListIterator iter= evaluation;
1482  for (int i= evaluation.length() - 2; i > -1; i--, iter++)
1483    evalPoint[i]= iter.getItem();
1484
1485  int pass= testFactors (F, factors, alpha, sqrfPartF,
1486                         bufFactors, bufSqrfFactors, evalSqrfPartF, evalPoint);
1487
1488  bool foundDifferent= false;
1489  Variable z, x= y;
1490  int j= 0;
1491  if (!pass)
1492  {
1493    int lev;
1494    // LCF is non-constant here
1495    for (int i= 1; i <= LCF.level(); i++)
1496    {
1497      if(degree (LCF, i) > 0)
1498      {
1499        lev= i - 1;
1500        break;
1501      }
1502    }
1503    CFList bufBufFactors;
1504    CanonicalForm bufF, swap;
1505    CFArray buf;
1506    for (int i= 0; i < lSecondVarLCs; i++)
1507    {
1508      if (!differentSecondVarLCs [i].isEmpty())
1509      {
1510        bool allConstant= true;
1511        for (iter= differentSecondVarLCs[i]; iter.hasItem(); iter++)
1512        {
1513          if (!iter.getItem().inCoeffDomain())
1514          {
1515            allConstant= false;
1516            y= Variable (iter.getItem().level());
1517          }
1518        }
1519        if (allConstant)
1520          continue;
1521
1522        bufFactors= differentSecondVarLCs [i];
1523        for (iter= bufFactors; iter.hasItem(); iter++)
1524          iter.getItem()= swapvar (iter.getItem(), x, y);
1525        bufF= F;
1526        z= Variable (y.level() - lev);
1527        bufF= swapvar (bufF, x, z);
1528        bufBufFactors= bufFactors;
1529        evalPoint= CFArray (evaluation.length() - 1);
1530        buf= CFArray (evaluation.length());
1531        iter= evaluation;
1532        int k= evaluation.length() - 1;
1533        for (; iter.hasItem(); iter++, k--)
1534          buf[k]= iter.getItem();
1535        swap= buf[z.level() - 1];
1536        buf[z.level() - 1]= buf[0];
1537        buf[0]= 0;
1538        int l= 0;
1539        for (k= 0; k < evaluation.length(); k++)
1540        {
1541          if (buf[k].isZero())
1542            continue;
1543          evalPoint[l]= buf[k];
1544          l++;
1545        }
1546        pass= testFactors (bufF, bufBufFactors, alpha, sqrfPartF, bufFactors,
1547                           bufSqrfFactors, evalSqrfPartF, evalPoint);
1548        if (pass)
1549        {
1550          foundDifferent= true;
1551          F= bufF;
1552          CFList l= factors;
1553          for (iter= l; iter.hasItem(); iter++)
1554            iter.getItem()= swapvar (iter.getItem(), x, y);
1555          differentSecondVarLCs [i]= l;
1556          j= i;
1557          break;
1558        }
1559        if (!pass && i == lSecondVarLCs - 1)
1560        {
1561          CFList result;
1562          result.append (LCF);
1563          for (int k= 1; k <= factors.length(); k++)
1564            result.append (LCF);
1565          y= Variable (1);
1566          delete [] bufSqrfFactors;
1567          return result;
1568        }
1569      }
1570    }
1571  }
1572  if (!pass)
1573  {
1574    CFList result;
1575    result.append (LCF);
1576    for (int k= 1; k <= factors.length(); k++)
1577      result.append (LCF);
1578    y= Variable (1);
1579    delete [] bufSqrfFactors;
1580    return result;
1581  }
1582  else
1583    factors= bufFactors;
1584
1585  bufFactors= factors;
1586  CFList evaluation2;
1587  if (y == x)
1588    evaluation2= evaluation;
1589  else
1590  {
1591    CanonicalForm tmp;
1592    evaluation2= evaluation;
1593    int i= evaluation.length() + 1;
1594    for (CFListIterator iter= evaluation2; iter.hasItem(); iter++, i--)
1595    {
1596      if (i == y.level())
1597      {
1598        tmp= iter.getItem();
1599        iter.getItem()= evaluation2.getLast();
1600        evaluation2.removeLast();
1601        evaluation2.append (tmp);
1602        break;
1603      }
1604    }
1605  }
1606
1607  sqrfPartF= shift2Zero (sqrfPartF, evalSqrfPartF, evaluation2, 1);
1608  if (factors.length() > 1)
1609  {
1610    CanonicalForm LC1= LC (evalSqrfPartF.getFirst(), 1);
1611
1612    CFArray leadingCoeffs= CFArray (factors.length());
1613    for (int i= 0; i < factors.length(); i++)
1614      leadingCoeffs[i]= LC1;
1615
1616    for (CFListIterator i= factors; i.hasItem(); i++)
1617    {
1618      i.getItem()= i.getItem() (x + evaluation2.getLast(), x);
1619      i.getItem() *= LC1 (0,2)/Lc (i.getItem());
1620    }
1621    factors.insert (1);
1622
1623    CanonicalForm
1624    newSqrfPartF= evalSqrfPartF.getFirst()*power (LC1, factors.length() - 2);
1625
1626    int liftBound= degree (newSqrfPartF,2) + 1;
1627
1628    CFMatrix M= CFMatrix (liftBound, factors.length() - 1);
1629    CFArray Pi;
1630    CFList diophant;
1631    henselLift122 (newSqrfPartF, factors, liftBound, Pi, diophant, M,
1632                   leadingCoeffs, false);
1633
1634    if (sqrfPartF.level() > 2)
1635    {
1636      int* liftBounds= new int [sqrfPartF.level() - 1];
1637      liftBounds [0]= liftBound;
1638      bool noOneToOne= false;
1639      CFList *leadingCoeffs2= new CFList [sqrfPartF.level()-2];
1640      LC1= LC (evalSqrfPartF.getLast(), 1);
1641      CFList LCs;
1642      for (int i= 0; i < factors.length(); i++)
1643        LCs.append (LC1);
1644      leadingCoeffs2 [sqrfPartF.level() - 3]= LCs;
1645      for (int i= sqrfPartF.level() - 1; i > 2; i--)
1646      {
1647        for (CFListIterator j= LCs; j.hasItem(); j++)
1648          j.getItem()= j.getItem() (0, i + 1);
1649        leadingCoeffs2 [i - 3]= LCs;
1650      }
1651      sqrfPartF= sqrfPartF*power (LC1, factors.length()-1);
1652
1653      int liftBoundsLength= sqrfPartF.level() - 1;
1654      for (int i= 1; i < liftBoundsLength; i++)
1655        liftBounds [i]= degree (sqrfPartF, i + 2) + 1;
1656      evalSqrfPartF= evaluateAtZero (sqrfPartF);
1657      evalSqrfPartF.removeFirst();
1658      factors= nonMonicHenselLift (evalSqrfPartF, factors, leadingCoeffs2,
1659               diophant, Pi, liftBounds, sqrfPartF.level() - 1, noOneToOne);
1660      delete [] leadingCoeffs2;
1661      delete [] liftBounds;
1662    }
1663  }
1664  else
1665    factors= evalSqrfPartF.getLast();
1666
1667  for (CFListIterator iter= factors; iter.hasItem(); iter++)
1668    iter.getItem()= reverseShift (iter.getItem(), evaluation2, 1);
1669
1670  CFList interMedResult=
1671  recoverFactors (reverseShift(evalSqrfPartF.getLast(),evaluation2,1), factors);
1672
1673  CFList result;
1674  CFFListIterator k;
1675  for (int i= 0; i < LCFFactors.length(); i++)
1676  {
1677    CanonicalForm tmp= 1;
1678    for (k= bufSqrfFactors[i]; k.hasItem(); k++)
1679    {
1680      int pos= findItem (bufFactors, k.getItem().factor());
1681      if (pos)
1682        tmp *= power (getItem (interMedResult, pos), k.getItem().exp());
1683    }
1684    result.append (tmp);
1685  }
1686
1687  for (CFListIterator i= result; i.hasItem(); i++)
1688  {
1689    F /= i.getItem();
1690    if (foundDifferent)
1691      i.getItem()= swapvar (i.getItem(), x, z);
1692    i.getItem()= N (i.getItem());
1693  }
1694
1695  if (foundDifferent)
1696  {
1697    CFList l= differentSecondVarLCs [j];
1698    for (CFListIterator i= l; i.hasItem(); i++)
1699      i.getItem()= swapvar (i.getItem(), y, z);
1700    differentSecondVarLCs [j]= l;
1701    F= swapvar (F, x, z);
1702  }
1703
1704  result.insert (N (F));
1705
1706  result= distributeContent (result, differentSecondVarLCs, lSecondVarLCs);
1707
1708  if (!result.getFirst().inCoeffDomain())
1709  {
1710    CFListIterator i= result;
1711    CanonicalForm tmp;
1712    if (foundDifferent)
1713      i.getItem()= swapvar (i.getItem(), Variable (2), y);
1714
1715    tmp= i.getItem();
1716
1717    i++;
1718    for (; i.hasItem(); i++)
1719    {
1720      if (foundDifferent)
1721        i.getItem()= swapvar (i.getItem(), Variable (2), y)*tmp;
1722      else
1723        i.getItem() *= tmp;
1724    }
1725  }
1726  else
1727    y= Variable (1);
1728
1729  delete [] bufSqrfFactors;
1730
1731  return result;
1732}
1733
1734void
1735evaluationWRTDifferentSecondVars (CFList*& Aeval, const CFList& evaluation,
1736                                  const CanonicalForm& A)
1737{
1738  CanonicalForm tmp;
1739  CFList tmp2;
1740  CFListIterator iter;
1741  for (int i= A.level(); i > 2; i--)
1742  {
1743    tmp= A;
1744    tmp2= CFList();
1745    iter= evaluation;
1746    bool preserveDegree= true;
1747    for (int j= A.level(); j > 1; j--, iter++)
1748    {
1749      if (j == i)
1750        continue;
1751      else
1752      {
1753        tmp= tmp (iter.getItem(), j);
1754        tmp2.insert (tmp);
1755        if ((degree (tmp, i) != degree (A, i)) ||
1756            (degree (tmp, 1) != degree (A, 1)))
1757        {
1758          preserveDegree= false;
1759          break;
1760        }
1761        if (!content(tmp).inCoeffDomain() || !content(tmp,1).inCoeffDomain())
1762        {
1763          preserveDegree= false;
1764          break;
1765        }
1766      }
1767    }
1768    if (preserveDegree)
1769      Aeval [i - 3]= tmp2;
1770    else
1771      Aeval [i - 3]= CFList();
1772  }
1773}
1774
1775static inline
1776CanonicalForm prodEval (const CFList& l, const CanonicalForm& evalPoint,
1777                        const Variable& v)
1778{
1779  CanonicalForm result= 1;
1780  for (CFListIterator i= l; i.hasItem(); i++)
1781    result *= i.getItem() (evalPoint, v);
1782  return result;
1783}
1784
1785//recombine bivariate factors in case one bivariate factorization yields less
1786// factors than the other
1787CFList
1788recombination (const CFList& factors1, const CFList& factors2, int s, int thres,
1789               const CanonicalForm& evalPoint, const Variable& x)
1790{
1791  CFList T, S;
1792
1793  T= factors1;
1794  CFList result;
1795  CanonicalForm buf;
1796  int * v= new int [T.length()];
1797  for (int i= 0; i < T.length(); i++)
1798    v[i]= 0;
1799  bool nosubset= false;
1800  CFArray TT;
1801  TT= copy (factors1);
1802  while (T.length() >= 2*s && s <= thres)
1803  {
1804    while (nosubset == false) 
1805    {
1806      if (T.length() == s) 
1807      {
1808        delete [] v;
1809        result.append (prod (T));
1810        return result;
1811      }
1812      S= subset (v, s, TT, nosubset);
1813      if (nosubset) break;
1814      buf= prodEval (S, evalPoint, x);
1815      buf /= Lc (buf);
1816      if (find (factors2, buf))
1817      {
1818        T= Difference (T, S);
1819        result.append (prod (S));
1820        TT= copy (T);
1821        indexUpdate (v, s, T.length(), nosubset);
1822        if (nosubset) break;
1823      }
1824    }
1825    s++;
1826    if (T.length() < 2*s || T.length() == s) 
1827    {
1828      delete [] v;
1829      result.append (prod (T));
1830      return result;
1831    }
1832    for (int i= 0; i < T.length(); i++)
1833      v[i]= 0;
1834    nosubset= false;
1835  }
1836
1837  delete [] v;
1838  if (T.length() < 2*s)
1839  {
1840    result.append (prod (T));
1841    return result;
1842  }
1843
1844  return result;
1845}
1846
1847void
1848factorizationWRTDifferentSecondVars (const CanonicalForm& A, CFList*& Aeval,
1849                                     const ExtensionInfo& info,
1850                                     int& minFactorsLength, bool& irred)
1851{
1852  Variable x= Variable (1);
1853  minFactorsLength= 0;
1854  irred= false;
1855  CFList factors;
1856  Variable v;
1857  for (int j= 0; j < A.level() - 2; j++)
1858  {
1859    if (!Aeval[j].isEmpty())
1860    {
1861      v= Variable (Aeval[j].getFirst().level());
1862      if (CFFactory::gettype() == GaloisFieldDomain)
1863        factors= GFBiSqrfFactorize (Aeval[j].getFirst());
1864      else if (info.getAlpha().level() == 1)
1865        factors= FpBiSqrfFactorize (Aeval[j].getFirst());
1866      else
1867        factors= FqBiSqrfFactorize (Aeval[j].getFirst(), info.getAlpha());
1868
1869      factors.removeFirst();
1870      if (minFactorsLength == 0)
1871        minFactorsLength= factors.length();
1872      else
1873        minFactorsLength= tmin (minFactorsLength, factors.length());
1874
1875      if (factors.length() == 1)
1876      {
1877        irred= true;
1878        return;
1879      }
1880      sortList (factors, x);
1881      Aeval [j]= factors;
1882    }
1883  }
1884}
1885
1886void getLeadingCoeffs (const CanonicalForm& A, CFList*& Aeval,
1887                       const CFList& uniFactors, const CFList& evaluation
1888                      )
1889{
1890  CanonicalForm evalPoint;
1891  int i;
1892  CFListIterator iter, iter2;
1893  Variable v;
1894  CFList l, LCs, buf;
1895  int pos;
1896  for (int j= 0; j < A.level() - 2; j++)
1897  {
1898    if (!Aeval[j].isEmpty())
1899    {
1900      i= A.level();
1901      for (iter= evaluation; iter.hasItem(); iter++, i--)
1902      {
1903        if (i == Aeval[j].getFirst().level())
1904        {
1905          evalPoint= iter.getItem();
1906          break;
1907        }
1908      }
1909
1910      v= Variable (i);
1911      if (Aeval[j].length() > uniFactors.length())
1912        Aeval[j]= recombination (Aeval[j], uniFactors, 1,
1913                                 Aeval[j].length() - uniFactors.length() + 1,
1914                                 evalPoint, v);
1915
1916      l= CFList();
1917      buf= buildUniFactors (Aeval[j], evalPoint, v);
1918      for (iter= uniFactors; iter.hasItem(); iter++)
1919      {
1920        pos= findItem (buf, iter.getItem());
1921        if (pos)
1922          l.append (getItem (Aeval[j], pos));
1923      }
1924      Aeval [j]= l;
1925
1926      LCs= CFList();
1927      for (iter= Aeval[j]; iter.hasItem(); iter++)
1928        LCs.append (LC (iter.getItem(), 1));
1929      normalize (LCs);
1930      Aeval[j]= LCs;
1931    }
1932  }
1933}
1934
1935CFList
1936buildUniFactors (const CFList& biFactors, const CanonicalForm& evalPoint,
1937                 const Variable& y)
1938{
1939  CFList result;
1940  CanonicalForm tmp;
1941  for (CFListIterator i= biFactors; i.hasItem(); i++)
1942  {
1943    tmp= mod (i.getItem(), y - evalPoint);
1944    tmp /= Lc (tmp);
1945    result.append (tmp);
1946  }
1947  return result;
1948}
1949
1950void refineBiFactors (const CanonicalForm& A, CFList& biFactors,
1951                      CFList* const& Aeval, const CFList& evaluation,
1952                      int minFactorsLength)
1953{
1954  CFListIterator iter;
1955  CanonicalForm evalPoint;
1956  int i;
1957  Variable v;
1958  Variable y= Variable (2);
1959  CFList list;
1960  for (int j= 0; j < A.level() - 2; j++)
1961  {
1962    if (Aeval[j].length() == minFactorsLength)
1963    {
1964      i= A.level();
1965
1966      for (iter= evaluation; iter.hasItem(); iter++, i--)
1967      {
1968        if (i == Aeval[j].getFirst().level())
1969        {
1970          evalPoint= iter.getItem();
1971          break;
1972        }
1973      }
1974
1975      v= Variable (i);
1976      list= buildUniFactors (Aeval[j], evalPoint, v);
1977
1978      biFactors= recombination (biFactors, list, 1,
1979                                biFactors.length() - list.length() + 1,
1980                                evaluation.getLast(), y);
1981      return;
1982    }
1983  }
1984}
1985
1986void prepareLeadingCoeffs (CFList*& LCs, int n, const CFList& leadingCoeffs,
1987                           const CFList& biFactors, const CFList& evaluation)
1988{
1989  CFList l= leadingCoeffs;
1990  LCs [n-3]= l;
1991  CFListIterator j;
1992  CFListIterator iter= evaluation;
1993  for (int i= n - 1; i > 2; i--, iter++)
1994  {
1995    for (j= l; j.hasItem(); j++)
1996      j.getItem()= j.getItem() (iter.getItem(), i + 1);
1997    LCs [i - 3]= l;
1998  }
1999  l= LCs [0];
2000  for (CFListIterator i= l; i.hasItem(); i++)
2001    i.getItem()= i.getItem() (iter.getItem(), 3);
2002  CFListIterator ii= biFactors;
2003  CFList normalizeFactor;
2004  for (CFListIterator i= l; i.hasItem(); i++, ii++)
2005    normalizeFactor.append (Lc (LC (ii.getItem(), 1))/Lc (i.getItem()));
2006  for (int i= 0; i < n-2; i++)
2007  {
2008    ii= normalizeFactor;
2009    for (j= LCs [i]; j.hasItem(); j++, ii++)
2010      j.getItem() *= ii.getItem();
2011  }
2012}
2013
2014CFList recoverFactors (const CanonicalForm& F, const CFList& factors)
2015{
2016  CFList result;
2017  CanonicalForm tmp, tmp2;
2018  CanonicalForm G= F;
2019  for (CFListIterator i= factors; i.hasItem(); i++)
2020  {
2021    tmp= i.getItem()/content (i.getItem(), 1);
2022    if (fdivides (tmp, G, tmp2))
2023    {
2024      G= tmp2;
2025      result.append (tmp);
2026    }
2027  }
2028  return result;
2029}
2030
2031CFList recoverFactors (const CanonicalForm& F, const CFList& factors,
2032                       const CFList& evaluation)
2033{
2034  CFList result;
2035  CanonicalForm tmp, tmp2;
2036  CanonicalForm G= F;
2037  for (CFListIterator i= factors; i.hasItem(); i++)
2038  {
2039    tmp= reverseShift (i.getItem(), evaluation);
2040    tmp /= content (tmp, 1);
2041    if (fdivides (tmp, G, tmp2))
2042    {
2043      G= tmp2;
2044      result.append (tmp);
2045    }
2046  }
2047  return result;
2048}
2049
2050CFList
2051extNonMonicFactorRecombination (const CFList& factors, const CanonicalForm& F,
2052                                const ExtensionInfo& info)
2053{
2054  Variable alpha= info.getAlpha();
2055  Variable beta= info.getBeta();
2056  CanonicalForm gamma= info.getGamma();
2057  CanonicalForm delta= info.getDelta();
2058  int k= info.getGFDegree();
2059  CFList source, dest;
2060
2061  int degMipoBeta= 1;
2062  if (!k && beta != Variable(1))
2063    degMipoBeta= degree (getMipo (beta));
2064
2065  CFList T, S;
2066  T= factors;
2067  int s= 1;
2068  CFList result;
2069  CanonicalForm quot, buf= F;
2070
2071  CanonicalForm g;
2072  CanonicalForm buf2;
2073  int * v= new int [T.length()];
2074  for (int i= 0; i < T.length(); i++)
2075    v[i]= 0;
2076  bool noSubset= false;
2077  CFArray TT;
2078  TT= copy (factors);
2079  bool recombination= false;
2080  bool trueFactor= false;
2081  while (T.length() >= 2*s)
2082  {
2083    while (noSubset == false)
2084    {
2085      if (T.length() == s)
2086      {
2087        delete [] v;
2088        if (recombination)
2089        {
2090          g= prod (T);
2091          T.removeFirst();
2092          result.append (g/myContent (g));
2093          g /= Lc (g);
2094          appendTestMapDown (result, g, info, source, dest);
2095          return result;
2096        }
2097        else
2098          return CFList (buf);
2099      }
2100
2101      S= subset (v, s, TT, noSubset);
2102      if (noSubset) break;
2103
2104      g= prod (S);
2105      g /= myContent (g);
2106      if (fdivides (g, buf, quot))
2107      {
2108        buf2= g;
2109        buf2 /= Lc (buf2);
2110        if (!k && beta == Variable (1))
2111        {
2112          if (degree (buf2, alpha) < degMipoBeta)
2113          {
2114            appendTestMapDown (result, buf2, info, source, dest);
2115            buf= quot;
2116            recombination= true;
2117            trueFactor= true;
2118          }
2119        }
2120        else
2121        {
2122          if (!isInExtension (buf2, gamma, k, delta, source, dest))
2123          {
2124            appendTestMapDown (result, buf2, info, source, dest);
2125            buf= quot;
2126            recombination= true;
2127            trueFactor= true;
2128          }
2129        }
2130        if (trueFactor)
2131        {
2132          T= Difference (T, S);
2133
2134          if (T.length() < 2*s || T.length() == s)
2135          {
2136            delete [] v;
2137            buf /= Lc (buf);
2138            appendTestMapDown (result, buf, info, source, dest);
2139            return result;
2140          }
2141          trueFactor= false;
2142          TT= copy (T);
2143          indexUpdate (v, s, T.length(), noSubset);
2144          if (noSubset) break;
2145        }
2146      }
2147    }
2148    s++;
2149    if (T.length() < 2*s || T.length() == s)
2150    {
2151      delete [] v;
2152      appendTestMapDown (result, buf, info, source, dest);
2153      return result;
2154    }
2155    for (int i= 0; i < T.length(); i++)
2156      v[i]= 0;
2157    noSubset= false;
2158  }
2159  if (T.length() < 2*s)
2160    appendMapDown (result, F, info, source, dest);
2161
2162  delete [] v;
2163  return result;
2164}
2165
2166CFList
2167extFactorize (const CanonicalForm& F, const ExtensionInfo& info);
2168
2169CFList
2170multiFactorize (const CanonicalForm& F, const ExtensionInfo& info)
2171{
2172
2173  if (F.inCoeffDomain())
2174    return CFList (F);
2175
2176  // compress and find main Variable
2177  CFMap N;
2178  CanonicalForm A= myCompress (F, N);
2179
2180  A /= Lc (A); // make monic
2181
2182  Variable alpha= info.getAlpha();
2183  Variable beta= info.getBeta();
2184  CanonicalForm gamma= info.getGamma();
2185  CanonicalForm delta= info.getDelta();
2186  bool extension= info.isInExtension();
2187  bool GF= (CFFactory::gettype() == GaloisFieldDomain);
2188  //univariate case
2189  if (F.isUnivariate())
2190  {
2191    if (extension == false)
2192      return uniFactorizer (F, alpha, GF);
2193    else
2194    {
2195      CFList source, dest;
2196      A= mapDown (F, info, source, dest);
2197      return uniFactorizer (A, beta, GF);
2198    }
2199  }
2200
2201  //bivariate case
2202  if (A.level() == 2)
2203  {
2204    CFList buf= biFactorize (F, info);
2205    return buf;
2206  }
2207
2208  Variable x= Variable (1);
2209  Variable y= Variable (2);
2210
2211  // remove content
2212  CFList contentAi;
2213  CanonicalForm lcmCont= lcmContent (A, contentAi);
2214  A /= lcmCont;
2215
2216  // trivial after content removal
2217  CFList contentAFactors;
2218  if (A.inCoeffDomain())
2219  {
2220    for (CFListIterator i= contentAi; i.hasItem(); i++)
2221    {
2222      if (i.getItem().inCoeffDomain())
2223        continue;
2224      else
2225      {
2226        lcmCont /= i.getItem();
2227        contentAFactors=
2228        Union (multiFactorize (lcmCont, info),
2229               multiFactorize (i.getItem(), info));
2230        break;
2231      }
2232    }
2233    decompress (contentAFactors, N);
2234    normalize (contentAFactors);
2235    return contentAFactors;
2236  }
2237
2238  // factorize content
2239  contentAFactors= multiFactorize (lcmCont, info);
2240
2241  // univariate after content removal
2242  CFList factors;
2243  if (A.isUnivariate ())
2244  {
2245    factors= uniFactorizer (A, alpha, GF);
2246    append (factors, contentAFactors);
2247    decompress (factors, N);
2248    return factors;
2249  }
2250
2251  // check main variable
2252  int swapLevel= 0;
2253  CanonicalForm derivZ;
2254  CanonicalForm gcdDerivZ;
2255  CanonicalForm bufA= A;
2256  Variable z;
2257  for (int i= 1; i <= A.level(); i++)
2258  {
2259    z= Variable (i);
2260    derivZ= deriv (bufA, z);
2261    if (derivZ.isZero())
2262    {
2263      if (i == 1)
2264        swapLevel= 1;
2265      else
2266        continue;
2267    }
2268    else
2269    {
2270      if (swapLevel == 1)
2271      {
2272        swapLevel= i;
2273        bufA= swapvar (A, x, z);
2274      }
2275      gcdDerivZ= gcd (bufA, derivZ);
2276      if (degree (gcdDerivZ) > 0 && !derivZ.isZero())
2277      {
2278        CanonicalForm g= bufA/gcdDerivZ;
2279        CFList factorsG=
2280        Union (multiFactorize (g, info),
2281               multiFactorize (gcdDerivZ, info));
2282        appendSwapDecompress (factorsG, contentAFactors, N, swapLevel, x);
2283        normalize (factorsG);
2284        return factorsG;
2285      }
2286      else
2287      {
2288        A= bufA;
2289        break;
2290      }
2291    }
2292  }
2293
2294
2295  CFList Aeval, list, evaluation, bufEvaluation, bufAeval;
2296  bool fail= false;
2297  int swapLevel2= 0;
2298  int level;
2299  int factorNums= 3;
2300  CanonicalForm bivarEval;
2301  CFList biFactors, bufBiFactors;
2302  CanonicalForm evalPoly;
2303  int lift, bufLift;
2304  double logarithm= (double) ilog2 (totaldegree (A));
2305  logarithm /= log2exp;
2306  logarithm= ceil (logarithm);
2307  if (factorNums < (int) logarithm)
2308    factorNums= (int) logarithm;
2309  CFList* bufAeval2= new CFList [A.level() - 2];
2310  CFList* Aeval2= new CFList [A.level() - 2];
2311  int counter;
2312  int differentSecondVar= 0;
2313  // several bivariate factorizations
2314  for (int i= 0; i < factorNums; i++)
2315  {
2316    counter= 0;
2317    bufA= A;
2318    bufAeval= CFList();
2319    bufEvaluation= evalPoints (bufA, bufAeval, alpha, list, GF, fail);
2320    evalPoly= 0;
2321
2322    if (fail && (i == 0))
2323    {
2324      if (!swapLevel)
2325        level= 2;
2326      else
2327        level= swapLevel + 1;
2328
2329      CanonicalForm g;
2330      swapLevel2= newMainVariableSearch (A, Aeval, evaluation, alpha, level, g);
2331
2332      if (!swapLevel2) // need to pass to an extension
2333      {
2334        factors= extFactorize (A, info);
2335        appendSwapDecompress (factors, contentAFactors, N, swapLevel, x);
2336        normalize (factors);
2337        delete [] bufAeval2;
2338        delete [] Aeval2;
2339        return factors;
2340      }
2341      else
2342      {
2343        if (swapLevel2 == -1)
2344        {
2345          CFList factorsG=
2346          Union (multiFactorize (g, info),
2347                 multiFactorize (A/g, info));
2348          appendSwapDecompress (factorsG, contentAFactors, N, swapLevel, x);
2349          normalize (factorsG);
2350          delete [] bufAeval2;
2351          delete [] Aeval2;
2352          return factorsG;
2353        }
2354        fail= false;
2355        bufAeval= Aeval;
2356        bufA= A;
2357        bufEvaluation= evaluation;
2358      }
2359    }
2360    else if (fail && (i > 0))
2361      break;
2362
2363    bivarEval= bufEvaluation.getLast();
2364
2365    evaluationWRTDifferentSecondVars (bufAeval2, bufEvaluation, A);
2366
2367    for (int j= 0; j < A.level() - 2; j++)
2368    {
2369      if (!bufAeval2[j].isEmpty())
2370        counter++;
2371    }
2372
2373    bufLift= degree (A, y) + 1 + degree (LC(A, x), y);
2374
2375    TIMING_START (fac_bi_factorizer);
2376    if (!GF && alpha.level() == 1)
2377      bufBiFactors= FpBiSqrfFactorize (bufAeval.getFirst());
2378    else if (GF)
2379      bufBiFactors= GFBiSqrfFactorize (bufAeval.getFirst());
2380    else
2381      bufBiFactors= FqBiSqrfFactorize (bufAeval.getFirst(), alpha);
2382    TIMING_END_AND_PRINT (fac_bi_factorizer,
2383                          "time for bivariate factorization: ");
2384    bufBiFactors.removeFirst();
2385
2386    if (bufBiFactors.length() == 1)
2387    {
2388      if (extension)
2389      {
2390        CFList source, dest;
2391        A= mapDown (A, info, source, dest);
2392      }
2393      factors.append (A);
2394      appendSwapDecompress (factors, contentAFactors, N, swapLevel,
2395                            swapLevel2, x);
2396      normalize (factors);
2397      delete [] bufAeval2;
2398      delete [] Aeval2;
2399      return factors;
2400    }
2401
2402    if (i == 0)
2403    {
2404      Aeval= bufAeval;
2405      evaluation= bufEvaluation;
2406      biFactors= bufBiFactors;
2407      lift= bufLift;
2408      for (int j= 0; j < A.level() - 2; j++)
2409        Aeval2 [j]= bufAeval2 [j];
2410      differentSecondVar= counter;
2411    }
2412    else
2413    {
2414      if (bufBiFactors.length() < biFactors.length() ||
2415          ((bufLift < lift) && (bufBiFactors.length() == biFactors.length())) ||
2416          counter > differentSecondVar)
2417      {
2418        Aeval= bufAeval;
2419        evaluation= bufEvaluation;
2420        biFactors= bufBiFactors;
2421        lift= bufLift;
2422        for (int j= 0; j < A.level() - 2; j++)
2423          Aeval2 [j]= bufAeval2 [j];
2424        differentSecondVar= counter;
2425      }
2426    }
2427    int k= 0;
2428    for (CFListIterator j= bufEvaluation; j.hasItem(); j++, k++)
2429      evalPoly += j.getItem()*power (x, k);
2430    list.append (evalPoly);
2431  }
2432
2433  delete [] bufAeval2;
2434
2435  sortList (biFactors, x);
2436
2437  int minFactorsLength;
2438  bool irred= false;
2439  factorizationWRTDifferentSecondVars (A, Aeval2, info, minFactorsLength, irred);
2440
2441  if (irred)
2442  {
2443    if (extension)
2444    {
2445      CFList source, dest;
2446      A= mapDown (A, info, source, dest);
2447    }
2448    factors.append (A);
2449    appendSwapDecompress (factors, contentAFactors, N, swapLevel,
2450                          swapLevel2, x);
2451    normalize (factors);
2452    delete [] Aeval2;
2453    return factors;
2454  }
2455
2456  if (minFactorsLength == 0)
2457    minFactorsLength= biFactors.length();
2458  else if (biFactors.length() > minFactorsLength)
2459    refineBiFactors (A, biFactors, Aeval2, evaluation, minFactorsLength);
2460  minFactorsLength= tmin (minFactorsLength, biFactors.length());
2461
2462  if (differentSecondVar == A.level() - 2)
2463  {
2464    bool zeroOccured= false;
2465    for (CFListIterator iter= evaluation; iter.hasItem(); iter++)
2466    {
2467      if (iter.getItem().isZero())
2468      {
2469        zeroOccured= true;
2470        break;
2471      }
2472    }
2473    if (!zeroOccured)
2474    {
2475      factors= sparseHeuristic (A, biFactors, Aeval2, evaluation, minFactorsLength);
2476      if (factors.length() == biFactors.length())
2477      {
2478        if (extension)
2479          factors= extNonMonicFactorRecombination (factors, A, info);
2480
2481        appendSwapDecompress (factors, contentAFactors, N, swapLevel,
2482                              swapLevel2, x);
2483        normalize (factors);
2484        delete [] Aeval2;
2485        return factors;
2486      }
2487      else
2488        factors= CFList();
2489      //TODO case where factors.length() > 0
2490    }
2491  }
2492
2493  CFList uniFactors= buildUniFactors (biFactors, evaluation.getLast(), y);
2494
2495  CFList * oldAeval= new CFList [A.level() - 2]; //TODO use bufAeval2 for this
2496  for (int i= 0; i < A.level() - 2; i++)
2497    oldAeval[i]= Aeval2[i];
2498
2499  getLeadingCoeffs (A, Aeval2, uniFactors, evaluation);
2500
2501  CFList biFactorsLCs;
2502  for (CFListIterator i= biFactors; i.hasItem(); i++)
2503    biFactorsLCs.append (LC (i.getItem(), 1));
2504
2505  Variable v;
2506  CFList leadingCoeffs= precomputeLeadingCoeff (LC (A, 1), biFactorsLCs, alpha,
2507                                          evaluation, Aeval2, A.level() - 2, v);
2508
2509  if (v.level() != 1)
2510  {
2511    A= swapvar (A, y, v);
2512    for (int i= 0; i < A.level() - 2; i++)
2513    {
2514      if (oldAeval[i].isEmpty())
2515        continue;
2516      if (oldAeval[i].getFirst().level() == v.level())
2517      {
2518        biFactors= CFList();
2519        for (CFListIterator iter= oldAeval [i]; iter.hasItem(); iter++)
2520          biFactors.append (swapvar (iter.getItem(), v, y));
2521      }
2522    }
2523    int i= A.level();
2524    CanonicalForm evalPoint;
2525    for (CFListIterator iter= evaluation; iter.hasItem(); iter++, i--)
2526    {
2527      if (i == v.level())
2528      {
2529        evalPoint= iter.getItem();
2530        iter.getItem()= evaluation.getLast();
2531        evaluation.removeLast();
2532        evaluation.append (evalPoint);
2533        break;
2534      }
2535    }
2536  }
2537
2538  CFListIterator iter;
2539  CanonicalForm oldA= A;
2540  CFList oldBiFactors= biFactors;
2541  if (!leadingCoeffs.getFirst().inCoeffDomain())
2542  {
2543    CanonicalForm tmp= power (leadingCoeffs.getFirst(), biFactors.length() - 1);
2544    A *= tmp;
2545    tmp= leadingCoeffs.getFirst();
2546    iter= evaluation;
2547    for (int i= A.level(); i > 2; i--, iter++)
2548      tmp= tmp (iter.getItem(), i);
2549    if (!tmp.inCoeffDomain())
2550    {
2551      for (CFListIterator i= biFactors; i.hasItem(); i++)
2552      {
2553        i.getItem() *= tmp/LC (i.getItem(), 1);
2554        i.getItem() /= Lc (i.getItem());
2555      }
2556    }
2557  }
2558
2559  leadingCoeffs.removeFirst();
2560
2561  //prepare leading coefficients
2562  CFList* leadingCoeffs2= new CFList [A.level() - 2];
2563  prepareLeadingCoeffs (leadingCoeffs2, A.level(), leadingCoeffs, biFactors,
2564                        evaluation);
2565
2566  Aeval= evaluateAtEval (A, evaluation, 2);
2567  CanonicalForm hh= Lc (Aeval.getFirst());
2568  for (iter= Aeval; iter.hasItem(); iter++)
2569    iter.getItem() /= hh;
2570
2571  A /= hh;
2572
2573  A= shift2Zero (A, Aeval, evaluation);
2574
2575  for (iter= biFactors; iter.hasItem(); iter++)
2576    iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
2577
2578  for (int i= 0; i < A.level() - 2; i++)
2579  {
2580    if (i != A.level() - 3)
2581      leadingCoeffs2[i]= CFList();
2582  }
2583  for (iter= leadingCoeffs2[A.level() - 3]; iter.hasItem(); iter++)
2584  {
2585    iter.getItem()= shift2Zero (iter.getItem(), list, evaluation);
2586    for (int i= A.level() - 4; i > -1; i--)
2587    {
2588      if (i + 1 == A.level() - 3)
2589        leadingCoeffs2[i].append (iter.getItem() (0, i + 4));
2590      else
2591        leadingCoeffs2[i].append (leadingCoeffs2[i+1].getLast() (0, i + 4));
2592    }
2593  }
2594
2595  CFArray Pi;
2596  CFList diophant;
2597  int* liftBounds= new int [A.level() - 1];
2598  int liftBoundsLength= A.level() - 1;
2599  for (int i= 0; i < liftBoundsLength; i++)
2600    liftBounds [i]= degree (A, i + 2) + 1;
2601
2602  Aeval.removeFirst();
2603  bool noOneToOne= false;
2604  factors= nonMonicHenselLift (Aeval, biFactors, leadingCoeffs2, diophant,
2605                               Pi, liftBounds, liftBoundsLength, noOneToOne);
2606
2607  if (!noOneToOne)
2608  {
2609    int check= factors.length();
2610    A= oldA;
2611    factors= recoverFactors (A, factors, evaluation);
2612    if (check != factors.length())
2613      noOneToOne= true;
2614
2615    if (extension && !noOneToOne)
2616      factors= extNonMonicFactorRecombination (factors, A, info);
2617  }
2618  if (noOneToOne)
2619  {
2620    A= shift2Zero (oldA, Aeval, evaluation);
2621    biFactors= oldBiFactors;
2622    for (iter= biFactors; iter.hasItem(); iter++)
2623      iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
2624    CanonicalForm LCA= LC (Aeval.getFirst(), 1);
2625    CanonicalForm yToLift= power (y, lift);
2626    CFListIterator i= biFactors;
2627    lift= degree (i.getItem(), 2) + degree (LC (i.getItem(), 1)) + 1;
2628    i++;
2629
2630    for (; i.hasItem(); i++)
2631      lift= tmax (lift, degree (i.getItem(), 2) + degree (LC (i.getItem(), 1)) + 1);
2632
2633    lift= tmax (degree (Aeval.getFirst() , 2) + 1, lift);
2634
2635    i= biFactors;
2636    yToLift= power (y, lift);
2637    CanonicalForm dummy;
2638    for (; i.hasItem(); i++)
2639    {
2640      LCA= LC (i.getItem(), 1);
2641      extgcd (LCA, yToLift, LCA, dummy);
2642      i.getItem()= mod (i.getItem()*LCA, yToLift);
2643    }
2644
2645    liftBoundsLength= F.level() - 1;
2646    liftBounds= liftingBounds (A, lift);
2647
2648    CFList MOD;
2649    bool earlySuccess;
2650    CFList earlyFactors;
2651    TIMING_START (fac_hensel_lift);
2652    CFList liftedFactors= henselLiftAndEarly
2653                          (A, MOD, liftBounds, earlySuccess, earlyFactors,
2654                           Aeval, biFactors, evaluation, info);
2655    TIMING_END_AND_PRINT (fac_hensel_lift, "time for hensel lifting: ");
2656
2657    if (!extension)
2658    {
2659      TIMING_START (fac_factor_recombination);
2660      factors= factorRecombination (A, liftedFactors, MOD);
2661      TIMING_END_AND_PRINT (fac_factor_recombination,
2662                            "time for factor recombination: ");
2663    }
2664    else
2665    {
2666      TIMING_START (fac_factor_recombination);
2667      factors= extFactorRecombination (liftedFactors, A, MOD, info, evaluation);
2668      TIMING_END_AND_PRINT (fac_factor_recombination,
2669                            "time for factor recombination: ");
2670    }
2671
2672    if (earlySuccess)
2673      factors= Union (factors, earlyFactors);
2674    if (!extension)
2675    {
2676      for (CFListIterator i= factors; i.hasItem(); i++)
2677      {
2678        int kk= Aeval.getLast().level();
2679        for (CFListIterator j= evaluation; j.hasItem(); j++, kk--)
2680        {
2681          if (i.getItem().level() < kk)
2682            continue;
2683          i.getItem()= i.getItem() (Variable (kk) - j.getItem(), kk);
2684        }
2685      }
2686    }
2687  }
2688
2689  if (v.level() != 1)
2690  {
2691    for (CFListIterator iter= factors; iter.hasItem(); iter++)
2692      iter.getItem()= swapvar (iter.getItem(), v, y);
2693  }
2694
2695  swap (factors, swapLevel, swapLevel2, x);
2696  append (factors, contentAFactors);
2697  decompress (factors, N);
2698  normalize (factors);
2699
2700  delete[] liftBounds;
2701
2702  return factors;
2703}
2704
2705/// multivariate factorization over an extension of the initial field
2706CFList
2707extFactorize (const CanonicalForm& F, const ExtensionInfo& info)
2708{
2709  CanonicalForm A= F;
2710
2711  Variable alpha= info.getAlpha();
2712  Variable beta= info.getBeta();
2713  int k= info.getGFDegree();
2714  char cGFName= info.getGFName();
2715  CanonicalForm delta= info.getDelta();
2716  bool GF= (CFFactory::gettype() == GaloisFieldDomain);
2717  Variable w= Variable (1);
2718
2719  CFList factors;
2720  if (!GF && alpha == w)  // we are in F_p
2721  {
2722    CFList factors;
2723    bool extension= true;
2724    int p= getCharacteristic();
2725    if (p*p < (1<<16)) // pass to GF if possible
2726    {
2727      setCharacteristic (getCharacteristic(), 2, 'Z');
2728      ExtensionInfo info= ExtensionInfo (extension);
2729      A= A.mapinto();
2730      factors= multiFactorize (A, info);
2731
2732      Variable vBuf= rootOf (gf_mipo);
2733      setCharacteristic (getCharacteristic());
2734      for (CFListIterator j= factors; j.hasItem(); j++)
2735        j.getItem()= GF2FalphaRep (j.getItem(), vBuf);
2736    }
2737    else  // not able to pass to GF, pass to F_p(\alpha)
2738    {
2739      CanonicalForm mipo= randomIrredpoly (2, Variable (1));
2740      Variable v= rootOf (mipo);
2741      ExtensionInfo info= ExtensionInfo (v);
2742      factors= multiFactorize (A, info);
2743    }
2744    return factors;
2745  }
2746  else if (!GF && (alpha != w)) // we are in F_p(\alpha)
2747  {
2748    if (k == 1) // need factorization over F_p
2749    {
2750      int extDeg= degree (getMipo (alpha));
2751      extDeg++;
2752      CanonicalForm mipo= randomIrredpoly (extDeg + 1, Variable (1));
2753      Variable v= rootOf (mipo);
2754      ExtensionInfo info= ExtensionInfo (v);
2755      factors= biFactorize (A, info);
2756    }
2757    else
2758    {
2759      if (beta == Variable (1))
2760      {
2761        Variable v= chooseExtension (alpha, beta, k);
2762        CanonicalForm primElem, imPrimElem;
2763        bool primFail= false;
2764        Variable vBuf;
2765        primElem= primitiveElement (alpha, vBuf, primFail);
2766        ASSERT (!primFail, "failure in integer factorizer");
2767        if (primFail)
2768          ; //ERROR
2769        else
2770          imPrimElem= mapPrimElem (primElem, vBuf, v);
2771
2772        CFList source, dest;
2773        CanonicalForm bufA= mapUp (A, alpha, v, primElem, imPrimElem,
2774                                   source, dest);
2775        ExtensionInfo info= ExtensionInfo (v, alpha, imPrimElem, primElem);
2776        factors= biFactorize (bufA, info);
2777      }
2778      else
2779      {
2780        Variable v= chooseExtension (alpha, beta, k);
2781        CanonicalForm primElem, imPrimElem;
2782        bool primFail= false;
2783        Variable vBuf;
2784        ASSERT (!primFail, "failure in integer factorizer");
2785        if (primFail)
2786          ; //ERROR
2787        else
2788          imPrimElem= mapPrimElem (delta, beta, v);
2789
2790        CFList source, dest;
2791        CanonicalForm bufA= mapDown (A, info, source, dest);
2792        source= CFList();
2793        dest= CFList();
2794        bufA= mapUp (bufA, beta, v, delta, imPrimElem, source, dest);
2795        ExtensionInfo info= ExtensionInfo (v, beta, imPrimElem, delta);
2796        factors= biFactorize (bufA, info);
2797      }
2798    }
2799    return factors;
2800  }
2801  else // we are in GF (p^k)
2802  {
2803    int p= getCharacteristic();
2804    int extensionDeg= getGFDegree();
2805    bool extension= true;
2806    if (k == 1) // need factorization over F_p
2807    {
2808      extensionDeg++;
2809      if (pow ((double) p, (double) extensionDeg) < (1<<16))
2810      // pass to GF(p^k+1)
2811      {
2812        setCharacteristic (p);
2813        Variable vBuf= rootOf (gf_mipo);
2814        A= GF2FalphaRep (A, vBuf);
2815        setCharacteristic (p, extensionDeg, 'Z');
2816        ExtensionInfo info= ExtensionInfo (extension);
2817        factors= multiFactorize (A.mapinto(), info);
2818      }
2819      else // not able to pass to another GF, pass to F_p(\alpha)
2820      {
2821        setCharacteristic (p);
2822        Variable vBuf= rootOf (gf_mipo);
2823        A= GF2FalphaRep (A, vBuf);
2824        Variable v= chooseExtension (vBuf, beta, k);
2825        ExtensionInfo info= ExtensionInfo (v, extension);
2826        factors= multiFactorize (A, info);
2827      }
2828    }
2829    else // need factorization over GF (p^k)
2830    {
2831      if (pow ((double) p, (double) 2*extensionDeg) < (1<<16))
2832      // pass to GF(p^2k)
2833      {
2834        setCharacteristic (p, 2*extensionDeg, 'Z');
2835        ExtensionInfo info= ExtensionInfo (k, cGFName, extension);
2836        factors= multiFactorize (GFMapUp (A, extensionDeg), info);
2837        setCharacteristic (p, extensionDeg, cGFName);
2838      }
2839      else // not able to pass to GF (p^2k), pass to F_p (\alpha)
2840      {
2841        setCharacteristic (p);
2842        Variable v1= rootOf (gf_mipo);
2843        A= GF2FalphaRep (A, v1);
2844        Variable v2= chooseExtension (v1, v1, k);
2845        CanonicalForm primElem, imPrimElem;
2846        bool primFail= false;
2847        Variable vBuf;
2848        primElem= primitiveElement (v1, v1, primFail);
2849        if (primFail)
2850          ; //ERROR
2851        else
2852          imPrimElem= mapPrimElem (primElem, v1, v2);
2853        CFList source, dest;
2854        CanonicalForm bufA= mapUp (A, v1, v2, primElem, imPrimElem,
2855                                     source, dest);
2856        ExtensionInfo info= ExtensionInfo (v2, v1, imPrimElem, primElem);
2857        factors= multiFactorize (bufA, info);
2858        setCharacteristic (p, k, cGFName);
2859        for (CFListIterator i= factors; i.hasItem(); i++)
2860          i.getItem()= Falpha2GFRep (i.getItem());
2861      }
2862    }
2863    return factors;
2864  }
2865}
2866
2867#endif
2868/* HAVE_NTL */
2869
Note: See TracBrowser for help on using the repository browser.