source: git/factory/facFqFactorize.cc @ 2dbf7e

fieker-DuValspielwiese
Last change on this file since 2dbf7e was 6f6320, checked in by Martin Lee <martinlee84@…>, 12 years ago
fix: issues with building factory without NTL
  • Property mode set to 100644
File size: 75.1 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  CFList interMedResult;
1608  CanonicalForm oldSqrfPartF= sqrfPartF;
1609  sqrfPartF= shift2Zero (sqrfPartF, evalSqrfPartF, evaluation2, 1);
1610  if (factors.length() > 1)
1611  {
1612    CanonicalForm LC1= LC (oldSqrfPartF, 1);
1613    CFList leadingCoeffs;
1614    for (int i= 0; i < factors.length(); i++)
1615      leadingCoeffs.append (LC1);
1616
1617    CFList LC1eval= evaluateAtEval (LC1, evaluation2, 1);
1618    CFList oldFactors= factors;
1619    for (CFListIterator i= oldFactors; i.hasItem(); i++)
1620      i.getItem() *= LC1eval.getFirst()/Lc (i.getItem());
1621
1622    bool success= false;
1623    if (LucksWangSparseHeuristic (oldSqrfPartF*power (LC1, factors.length()-1),
1624                                  oldFactors, 1, leadingCoeffs, factors))
1625    {
1626      interMedResult= recoverFactors (oldSqrfPartF, factors);
1627      if (oldFactors.length() == interMedResult.length())
1628        success= true;
1629    }
1630    if (!success)
1631    {
1632      LC1= LC (evalSqrfPartF.getFirst(), 1);
1633
1634      CFArray leadingCoeffs= CFArray (factors.length());
1635      for (int i= 0; i < factors.length(); i++)
1636        leadingCoeffs[i]= LC1;
1637
1638      for (CFListIterator i= factors; i.hasItem(); i++)
1639      {
1640        i.getItem()= i.getItem() (x + evaluation2.getLast(), x);
1641        i.getItem() *= LC1 (0,2)/Lc (i.getItem());
1642      }
1643      factors.insert (1);
1644
1645      CanonicalForm
1646      newSqrfPartF= evalSqrfPartF.getFirst()*power (LC1, factors.length() - 2);
1647
1648      int liftBound= degree (newSqrfPartF,2) + 1;
1649
1650      CFMatrix M= CFMatrix (liftBound, factors.length() - 1);
1651      CFArray Pi;
1652      CFList diophant;
1653      henselLift122 (newSqrfPartF, factors, liftBound, Pi, diophant, M,
1654                     leadingCoeffs, false);
1655
1656      if (sqrfPartF.level() > 2)
1657      {
1658        int* liftBounds= new int [sqrfPartF.level() - 1];
1659        liftBounds [0]= liftBound;
1660        bool noOneToOne= false;
1661        CFList *leadingCoeffs2= new CFList [sqrfPartF.level()-2];
1662        LC1= LC (evalSqrfPartF.getLast(), 1);
1663        CFList LCs;
1664        for (int i= 0; i < factors.length(); i++)
1665          LCs.append (LC1);
1666        leadingCoeffs2 [sqrfPartF.level() - 3]= LCs;
1667        for (int i= sqrfPartF.level() - 1; i > 2; i--)
1668        {
1669          for (CFListIterator j= LCs; j.hasItem(); j++)
1670            j.getItem()= j.getItem() (0, i + 1);
1671          leadingCoeffs2 [i - 3]= LCs;
1672        }
1673        sqrfPartF *= power (LC1, factors.length()-1);
1674
1675        int liftBoundsLength= sqrfPartF.level() - 1;
1676        for (int i= 1; i < liftBoundsLength; i++)
1677          liftBounds [i]= degree (sqrfPartF, i + 2) + 1;
1678        evalSqrfPartF= evaluateAtZero (sqrfPartF);
1679        evalSqrfPartF.removeFirst();
1680        factors= nonMonicHenselLift (evalSqrfPartF, factors, leadingCoeffs2,
1681                 diophant, Pi, liftBounds, sqrfPartF.level() - 1, noOneToOne);
1682        delete [] leadingCoeffs2;
1683        delete [] liftBounds;
1684      }
1685      for (CFListIterator iter= factors; iter.hasItem(); iter++)
1686        iter.getItem()= reverseShift (iter.getItem(), evaluation2, 1);
1687
1688      interMedResult=
1689      recoverFactors (reverseShift(evalSqrfPartF.getLast(),evaluation2,1),
1690                      factors);
1691    }
1692  }
1693  else
1694  {
1695    factors= CFList (oldSqrfPartF);
1696    interMedResult= recoverFactors (oldSqrfPartF, factors);
1697  }
1698
1699  CFList result;
1700  CFFListIterator k;
1701  for (int i= 0; i < LCFFactors.length(); i++)
1702  {
1703    CanonicalForm tmp= 1;
1704    for (k= bufSqrfFactors[i]; k.hasItem(); k++)
1705    {
1706      int pos= findItem (bufFactors, k.getItem().factor());
1707      if (pos)
1708        tmp *= power (getItem (interMedResult, pos), k.getItem().exp());
1709    }
1710    result.append (tmp);
1711  }
1712
1713  for (CFListIterator i= result; i.hasItem(); i++)
1714  {
1715    F /= i.getItem();
1716    if (foundDifferent)
1717      i.getItem()= swapvar (i.getItem(), x, z);
1718    i.getItem()= N (i.getItem());
1719  }
1720
1721  if (foundDifferent)
1722  {
1723    CFList l= differentSecondVarLCs [j];
1724    for (CFListIterator i= l; i.hasItem(); i++)
1725      i.getItem()= swapvar (i.getItem(), y, z);
1726    differentSecondVarLCs [j]= l;
1727    F= swapvar (F, x, z);
1728  }
1729
1730  result.insert (N (F));
1731
1732  result= distributeContent (result, differentSecondVarLCs, lSecondVarLCs);
1733
1734  if (!result.getFirst().inCoeffDomain())
1735  {
1736    CFListIterator i= result;
1737    CanonicalForm tmp;
1738    if (foundDifferent)
1739      i.getItem()= swapvar (i.getItem(), Variable (2), y);
1740
1741    tmp= i.getItem();
1742
1743    i++;
1744    for (; i.hasItem(); i++)
1745    {
1746      if (foundDifferent)
1747        i.getItem()= swapvar (i.getItem(), Variable (2), y)*tmp;
1748      else
1749        i.getItem() *= tmp;
1750    }
1751  }
1752  else
1753    y= Variable (1);
1754
1755  delete [] bufSqrfFactors;
1756
1757  return result;
1758}
1759
1760void
1761evaluationWRTDifferentSecondVars (CFList*& Aeval, const CFList& evaluation,
1762                                  const CanonicalForm& A)
1763{
1764  CanonicalForm tmp;
1765  CFList tmp2;
1766  CFListIterator iter;
1767  for (int i= A.level(); i > 2; i--)
1768  {
1769    tmp= A;
1770    tmp2= CFList();
1771    iter= evaluation;
1772    bool preserveDegree= true;
1773    for (int j= A.level(); j > 1; j--, iter++)
1774    {
1775      if (j == i)
1776        continue;
1777      else
1778      {
1779        tmp= tmp (iter.getItem(), j);
1780        tmp2.insert (tmp);
1781        if ((degree (tmp, i) != degree (A, i)) ||
1782            (degree (tmp, 1) != degree (A, 1)))
1783        {
1784          preserveDegree= false;
1785          break;
1786        }
1787        if (!content(tmp).inCoeffDomain() || !content(tmp,1).inCoeffDomain())
1788        {
1789          preserveDegree= false;
1790          break;
1791        }
1792      }
1793    }
1794    if (preserveDegree)
1795      Aeval [i - 3]= tmp2;
1796    else
1797      Aeval [i - 3]= CFList();
1798  }
1799}
1800
1801#endif
1802
1803static inline
1804CanonicalForm prodEval (const CFList& l, const CanonicalForm& evalPoint,
1805                        const Variable& v)
1806{
1807  CanonicalForm result= 1;
1808  for (CFListIterator i= l; i.hasItem(); i++)
1809    result *= i.getItem() (evalPoint, v);
1810  return result;
1811}
1812
1813//recombine bivariate factors in case one bivariate factorization yields less
1814// factors than the other
1815CFList
1816recombination (const CFList& factors1, const CFList& factors2, int s, int thres,
1817               const CanonicalForm& evalPoint, const Variable& x)
1818{
1819  CFList T, S;
1820
1821  T= factors1;
1822  CFList result;
1823  CanonicalForm buf;
1824  int * v= new int [T.length()];
1825  for (int i= 0; i < T.length(); i++)
1826    v[i]= 0;
1827  bool nosubset= false;
1828  CFArray TT;
1829  TT= copy (factors1);
1830  while (T.length() >= 2*s && s <= thres)
1831  {
1832    while (nosubset == false) 
1833    {
1834      if (T.length() == s) 
1835      {
1836        delete [] v;
1837        result.append (prod (T));
1838        return result;
1839      }
1840      S= subset (v, s, TT, nosubset);
1841      if (nosubset) break;
1842      buf= prodEval (S, evalPoint, x);
1843      buf /= Lc (buf);
1844      if (find (factors2, buf))
1845      {
1846        T= Difference (T, S);
1847        result.append (prod (S));
1848        TT= copy (T);
1849        indexUpdate (v, s, T.length(), nosubset);
1850        if (nosubset) break;
1851      }
1852    }
1853    s++;
1854    if (T.length() < 2*s || T.length() == s) 
1855    {
1856      delete [] v;
1857      result.append (prod (T));
1858      return result;
1859    }
1860    for (int i= 0; i < T.length(); i++)
1861      v[i]= 0;
1862    nosubset= false;
1863  }
1864
1865  delete [] v;
1866  if (T.length() < 2*s)
1867  {
1868    result.append (prod (T));
1869    return result;
1870  }
1871
1872  return result;
1873}
1874
1875#ifdef HAVE_NTL
1876void
1877factorizationWRTDifferentSecondVars (const CanonicalForm& A, CFList*& Aeval,
1878                                     const ExtensionInfo& info,
1879                                     int& minFactorsLength, bool& irred)
1880{
1881  Variable x= Variable (1);
1882  minFactorsLength= 0;
1883  irred= false;
1884  CFList factors;
1885  Variable v;
1886  for (int j= 0; j < A.level() - 2; j++)
1887  {
1888    if (!Aeval[j].isEmpty())
1889    {
1890      v= Variable (Aeval[j].getFirst().level());
1891      if (CFFactory::gettype() == GaloisFieldDomain)
1892        factors= GFBiSqrfFactorize (Aeval[j].getFirst());
1893      else if (info.getAlpha().level() == 1)
1894        factors= FpBiSqrfFactorize (Aeval[j].getFirst());
1895      else
1896        factors= FqBiSqrfFactorize (Aeval[j].getFirst(), info.getAlpha());
1897
1898      factors.removeFirst();
1899      if (minFactorsLength == 0)
1900        minFactorsLength= factors.length();
1901      else
1902        minFactorsLength= tmin (minFactorsLength, factors.length());
1903
1904      if (factors.length() == 1)
1905      {
1906        irred= true;
1907        return;
1908      }
1909      sortList (factors, x);
1910      Aeval [j]= factors;
1911    }
1912  }
1913}
1914
1915void getLeadingCoeffs (const CanonicalForm& A, CFList*& Aeval,
1916                       const CFList& uniFactors, const CFList& evaluation
1917                      )
1918{
1919  CanonicalForm evalPoint;
1920  int i;
1921  CFListIterator iter, iter2;
1922  Variable v;
1923  CFList l, LCs, buf;
1924  int pos;
1925  for (int j= 0; j < A.level() - 2; j++)
1926  {
1927    if (!Aeval[j].isEmpty())
1928    {
1929      i= A.level();
1930      for (iter= evaluation; iter.hasItem(); iter++, i--)
1931      {
1932        if (i == Aeval[j].getFirst().level())
1933        {
1934          evalPoint= iter.getItem();
1935          break;
1936        }
1937      }
1938
1939      v= Variable (i);
1940      if (Aeval[j].length() > uniFactors.length())
1941        Aeval[j]= recombination (Aeval[j], uniFactors, 1,
1942                                 Aeval[j].length() - uniFactors.length() + 1,
1943                                 evalPoint, v);
1944
1945      l= CFList();
1946      buf= buildUniFactors (Aeval[j], evalPoint, v);
1947      for (iter= uniFactors; iter.hasItem(); iter++)
1948      {
1949        pos= findItem (buf, iter.getItem());
1950        if (pos)
1951          l.append (getItem (Aeval[j], pos));
1952      }
1953      Aeval [j]= l;
1954
1955      LCs= CFList();
1956      for (iter= Aeval[j]; iter.hasItem(); iter++)
1957        LCs.append (LC (iter.getItem(), 1));
1958      normalize (LCs);
1959      Aeval[j]= LCs;
1960    }
1961  }
1962}
1963
1964CFList
1965buildUniFactors (const CFList& biFactors, const CanonicalForm& evalPoint,
1966                 const Variable& y)
1967{
1968  CFList result;
1969  CanonicalForm tmp;
1970  for (CFListIterator i= biFactors; i.hasItem(); i++)
1971  {
1972    tmp= mod (i.getItem(), y - evalPoint);
1973    tmp /= Lc (tmp);
1974    result.append (tmp);
1975  }
1976  return result;
1977}
1978
1979void refineBiFactors (const CanonicalForm& A, CFList& biFactors,
1980                      CFList* const& Aeval, const CFList& evaluation,
1981                      int minFactorsLength)
1982{
1983  CFListIterator iter;
1984  CanonicalForm evalPoint;
1985  int i;
1986  Variable v;
1987  Variable y= Variable (2);
1988  CFList list;
1989  for (int j= 0; j < A.level() - 2; j++)
1990  {
1991    if (Aeval[j].length() == minFactorsLength)
1992    {
1993      i= A.level();
1994
1995      for (iter= evaluation; iter.hasItem(); iter++, i--)
1996      {
1997        if (i == Aeval[j].getFirst().level())
1998        {
1999          evalPoint= iter.getItem();
2000          break;
2001        }
2002      }
2003
2004      v= Variable (i);
2005      list= buildUniFactors (Aeval[j], evalPoint, v);
2006
2007      biFactors= recombination (biFactors, list, 1,
2008                                biFactors.length() - list.length() + 1,
2009                                evaluation.getLast(), y);
2010      return;
2011    }
2012  }
2013}
2014
2015void prepareLeadingCoeffs (CFList*& LCs, int n, const CFList& leadingCoeffs,
2016                           const CFList& biFactors, const CFList& evaluation)
2017{
2018  CFList l= leadingCoeffs;
2019  LCs [n-3]= l;
2020  CFListIterator j;
2021  CFListIterator iter= evaluation;
2022  for (int i= n - 1; i > 2; i--, iter++)
2023  {
2024    for (j= l; j.hasItem(); j++)
2025      j.getItem()= j.getItem() (iter.getItem(), i + 1);
2026    LCs [i - 3]= l;
2027  }
2028  l= LCs [0];
2029  for (CFListIterator i= l; i.hasItem(); i++)
2030    i.getItem()= i.getItem() (iter.getItem(), 3);
2031  CFListIterator ii= biFactors;
2032  CFList normalizeFactor;
2033  for (CFListIterator i= l; i.hasItem(); i++, ii++)
2034    normalizeFactor.append (Lc (LC (ii.getItem(), 1))/Lc (i.getItem()));
2035  for (int i= 0; i < n-2; i++)
2036  {
2037    ii= normalizeFactor;
2038    for (j= LCs [i]; j.hasItem(); j++, ii++)
2039      j.getItem() *= ii.getItem();
2040  }
2041}
2042
2043CFList recoverFactors (const CanonicalForm& F, const CFList& factors)
2044{
2045  CFList result;
2046  CanonicalForm tmp, tmp2;
2047  CanonicalForm G= F;
2048  for (CFListIterator i= factors; i.hasItem(); i++)
2049  {
2050    tmp= i.getItem()/content (i.getItem(), 1);
2051    if (fdivides (tmp, G, tmp2))
2052    {
2053      G= tmp2;
2054      result.append (tmp);
2055    }
2056  }
2057  return result;
2058}
2059
2060CFList recoverFactors (const CanonicalForm& F, const CFList& factors,
2061                       const CFList& evaluation)
2062{
2063  CFList result;
2064  CanonicalForm tmp, tmp2;
2065  CanonicalForm G= F;
2066  for (CFListIterator i= factors; i.hasItem(); i++)
2067  {
2068    tmp= reverseShift (i.getItem(), evaluation);
2069    tmp /= content (tmp, 1);
2070    if (fdivides (tmp, G, tmp2))
2071    {
2072      G= tmp2;
2073      result.append (tmp);
2074    }
2075  }
2076  return result;
2077}
2078
2079CFList
2080extNonMonicFactorRecombination (const CFList& factors, const CanonicalForm& F,
2081                                const ExtensionInfo& info)
2082{
2083  Variable alpha= info.getAlpha();
2084  Variable beta= info.getBeta();
2085  CanonicalForm gamma= info.getGamma();
2086  CanonicalForm delta= info.getDelta();
2087  int k= info.getGFDegree();
2088  CFList source, dest;
2089
2090  int degMipoBeta= 1;
2091  if (!k && beta != Variable(1))
2092    degMipoBeta= degree (getMipo (beta));
2093
2094  CFList T, S;
2095  T= factors;
2096  int s= 1;
2097  CFList result;
2098  CanonicalForm quot, buf= F;
2099
2100  CanonicalForm g;
2101  CanonicalForm buf2;
2102  int * v= new int [T.length()];
2103  for (int i= 0; i < T.length(); i++)
2104    v[i]= 0;
2105  bool noSubset= false;
2106  CFArray TT;
2107  TT= copy (factors);
2108  bool recombination= false;
2109  bool trueFactor= false;
2110  while (T.length() >= 2*s)
2111  {
2112    while (noSubset == false)
2113    {
2114      if (T.length() == s)
2115      {
2116        delete [] v;
2117        if (recombination)
2118        {
2119          g= prod (T);
2120          T.removeFirst();
2121          result.append (g/myContent (g));
2122          g /= Lc (g);
2123          appendTestMapDown (result, g, info, source, dest);
2124          return result;
2125        }
2126        else
2127          return CFList (buf);
2128      }
2129
2130      S= subset (v, s, TT, noSubset);
2131      if (noSubset) break;
2132
2133      g= prod (S);
2134      g /= myContent (g);
2135      if (fdivides (g, buf, quot))
2136      {
2137        buf2= g;
2138        buf2 /= Lc (buf2);
2139        if (!k && beta == Variable (1))
2140        {
2141          if (degree (buf2, alpha) < degMipoBeta)
2142          {
2143            appendTestMapDown (result, buf2, info, source, dest);
2144            buf= quot;
2145            recombination= true;
2146            trueFactor= true;
2147          }
2148        }
2149        else
2150        {
2151          if (!isInExtension (buf2, gamma, k, delta, source, dest))
2152          {
2153            appendTestMapDown (result, buf2, info, source, dest);
2154            buf= quot;
2155            recombination= true;
2156            trueFactor= true;
2157          }
2158        }
2159        if (trueFactor)
2160        {
2161          T= Difference (T, S);
2162
2163          if (T.length() < 2*s || T.length() == s)
2164          {
2165            delete [] v;
2166            buf /= Lc (buf);
2167            appendTestMapDown (result, buf, info, source, dest);
2168            return result;
2169          }
2170          trueFactor= false;
2171          TT= copy (T);
2172          indexUpdate (v, s, T.length(), noSubset);
2173          if (noSubset) break;
2174        }
2175      }
2176    }
2177    s++;
2178    if (T.length() < 2*s || T.length() == s)
2179    {
2180      delete [] v;
2181      appendTestMapDown (result, buf, info, source, dest);
2182      return result;
2183    }
2184    for (int i= 0; i < T.length(); i++)
2185      v[i]= 0;
2186    noSubset= false;
2187  }
2188  if (T.length() < 2*s)
2189    appendMapDown (result, F, info, source, dest);
2190
2191  delete [] v;
2192  return result;
2193}
2194
2195CFList
2196extFactorize (const CanonicalForm& F, const ExtensionInfo& info);
2197
2198CFList
2199multiFactorize (const CanonicalForm& F, const ExtensionInfo& info)
2200{
2201
2202  if (F.inCoeffDomain())
2203    return CFList (F);
2204
2205  // compress and find main Variable
2206  CFMap N;
2207  CanonicalForm A= myCompress (F, N);
2208
2209  A /= Lc (A); // make monic
2210
2211  Variable alpha= info.getAlpha();
2212  Variable beta= info.getBeta();
2213  CanonicalForm gamma= info.getGamma();
2214  CanonicalForm delta= info.getDelta();
2215  bool extension= info.isInExtension();
2216  bool GF= (CFFactory::gettype() == GaloisFieldDomain);
2217  //univariate case
2218  if (F.isUnivariate())
2219  {
2220    if (extension == false)
2221      return uniFactorizer (F, alpha, GF);
2222    else
2223    {
2224      CFList source, dest;
2225      A= mapDown (F, info, source, dest);
2226      return uniFactorizer (A, beta, GF);
2227    }
2228  }
2229
2230  //bivariate case
2231  if (A.level() == 2)
2232  {
2233    CFList buf= biFactorize (F, info);
2234    return buf;
2235  }
2236
2237  Variable x= Variable (1);
2238  Variable y= Variable (2);
2239
2240  // remove content
2241  CFList contentAi;
2242  CanonicalForm lcmCont= lcmContent (A, contentAi);
2243  A /= lcmCont;
2244
2245  // trivial after content removal
2246  CFList contentAFactors;
2247  if (A.inCoeffDomain())
2248  {
2249    for (CFListIterator i= contentAi; i.hasItem(); i++)
2250    {
2251      if (i.getItem().inCoeffDomain())
2252        continue;
2253      else
2254      {
2255        lcmCont /= i.getItem();
2256        contentAFactors=
2257        Union (multiFactorize (lcmCont, info),
2258               multiFactorize (i.getItem(), info));
2259        break;
2260      }
2261    }
2262    decompress (contentAFactors, N);
2263    normalize (contentAFactors);
2264    return contentAFactors;
2265  }
2266
2267  // factorize content
2268  contentAFactors= multiFactorize (lcmCont, info);
2269
2270  // univariate after content removal
2271  CFList factors;
2272  if (A.isUnivariate ())
2273  {
2274    factors= uniFactorizer (A, alpha, GF);
2275    append (factors, contentAFactors);
2276    decompress (factors, N);
2277    return factors;
2278  }
2279
2280  // check main variable
2281  int swapLevel= 0;
2282  CanonicalForm derivZ;
2283  CanonicalForm gcdDerivZ;
2284  CanonicalForm bufA= A;
2285  Variable z;
2286  for (int i= 1; i <= A.level(); i++)
2287  {
2288    z= Variable (i);
2289    derivZ= deriv (bufA, z);
2290    if (derivZ.isZero())
2291    {
2292      if (i == 1)
2293        swapLevel= 1;
2294      else
2295        continue;
2296    }
2297    else
2298    {
2299      if (swapLevel == 1)
2300      {
2301        swapLevel= i;
2302        bufA= swapvar (A, x, z);
2303      }
2304      gcdDerivZ= gcd (bufA, derivZ);
2305      if (degree (gcdDerivZ) > 0 && !derivZ.isZero())
2306      {
2307        CanonicalForm g= bufA/gcdDerivZ;
2308        CFList factorsG=
2309        Union (multiFactorize (g, info),
2310               multiFactorize (gcdDerivZ, info));
2311        appendSwapDecompress (factorsG, contentAFactors, N, swapLevel, x);
2312        normalize (factorsG);
2313        return factorsG;
2314      }
2315      else
2316      {
2317        A= bufA;
2318        break;
2319      }
2320    }
2321  }
2322
2323
2324  CFList Aeval, list, evaluation, bufEvaluation, bufAeval;
2325  bool fail= false;
2326  int swapLevel2= 0;
2327  int level;
2328  int factorNums= 3;
2329  CanonicalForm bivarEval;
2330  CFList biFactors, bufBiFactors;
2331  CanonicalForm evalPoly;
2332  int lift, bufLift;
2333  double logarithm= (double) ilog2 (totaldegree (A));
2334  logarithm /= log2exp;
2335  logarithm= ceil (logarithm);
2336  if (factorNums < (int) logarithm)
2337    factorNums= (int) logarithm;
2338  CFList* bufAeval2= new CFList [A.level() - 2];
2339  CFList* Aeval2= new CFList [A.level() - 2];
2340  int counter;
2341  int differentSecondVar= 0;
2342  // several bivariate factorizations
2343  for (int i= 0; i < factorNums; i++)
2344  {
2345    counter= 0;
2346    bufA= A;
2347    bufAeval= CFList();
2348    bufEvaluation= evalPoints (bufA, bufAeval, alpha, list, GF, fail);
2349    evalPoly= 0;
2350
2351    if (fail && (i == 0))
2352    {
2353      if (!swapLevel)
2354        level= 2;
2355      else
2356        level= swapLevel + 1;
2357
2358      CanonicalForm g;
2359      swapLevel2= newMainVariableSearch (A, Aeval, evaluation, alpha, level, g);
2360
2361      if (!swapLevel2) // need to pass to an extension
2362      {
2363        factors= extFactorize (A, info);
2364        appendSwapDecompress (factors, contentAFactors, N, swapLevel, x);
2365        normalize (factors);
2366        delete [] bufAeval2;
2367        delete [] Aeval2;
2368        return factors;
2369      }
2370      else
2371      {
2372        if (swapLevel2 == -1)
2373        {
2374          CFList factorsG=
2375          Union (multiFactorize (g, info),
2376                 multiFactorize (A/g, info));
2377          appendSwapDecompress (factorsG, contentAFactors, N, swapLevel, x);
2378          normalize (factorsG);
2379          delete [] bufAeval2;
2380          delete [] Aeval2;
2381          return factorsG;
2382        }
2383        fail= false;
2384        bufAeval= Aeval;
2385        bufA= A;
2386        bufEvaluation= evaluation;
2387      }
2388    }
2389    else if (fail && (i > 0))
2390      break;
2391
2392    bivarEval= bufEvaluation.getLast();
2393
2394    evaluationWRTDifferentSecondVars (bufAeval2, bufEvaluation, A);
2395
2396    for (int j= 0; j < A.level() - 2; j++)
2397    {
2398      if (!bufAeval2[j].isEmpty())
2399        counter++;
2400    }
2401
2402    bufLift= degree (A, y) + 1 + degree (LC(A, x), y);
2403
2404    TIMING_START (fac_bi_factorizer);
2405    if (!GF && alpha.level() == 1)
2406      bufBiFactors= FpBiSqrfFactorize (bufAeval.getFirst());
2407    else if (GF)
2408      bufBiFactors= GFBiSqrfFactorize (bufAeval.getFirst());
2409    else
2410      bufBiFactors= FqBiSqrfFactorize (bufAeval.getFirst(), alpha);
2411    TIMING_END_AND_PRINT (fac_bi_factorizer,
2412                          "time for bivariate factorization: ");
2413    bufBiFactors.removeFirst();
2414
2415    if (bufBiFactors.length() == 1)
2416    {
2417      if (extension)
2418      {
2419        CFList source, dest;
2420        A= mapDown (A, info, source, dest);
2421      }
2422      factors.append (A);
2423      appendSwapDecompress (factors, contentAFactors, N, swapLevel,
2424                            swapLevel2, x);
2425      normalize (factors);
2426      delete [] bufAeval2;
2427      delete [] Aeval2;
2428      return factors;
2429    }
2430
2431    if (i == 0)
2432    {
2433      Aeval= bufAeval;
2434      evaluation= bufEvaluation;
2435      biFactors= bufBiFactors;
2436      lift= bufLift;
2437      for (int j= 0; j < A.level() - 2; j++)
2438        Aeval2 [j]= bufAeval2 [j];
2439      differentSecondVar= counter;
2440    }
2441    else
2442    {
2443      if (bufBiFactors.length() < biFactors.length() ||
2444          ((bufLift < lift) && (bufBiFactors.length() == biFactors.length())) ||
2445          counter > differentSecondVar)
2446      {
2447        Aeval= bufAeval;
2448        evaluation= bufEvaluation;
2449        biFactors= bufBiFactors;
2450        lift= bufLift;
2451        for (int j= 0; j < A.level() - 2; j++)
2452          Aeval2 [j]= bufAeval2 [j];
2453        differentSecondVar= counter;
2454      }
2455    }
2456    int k= 0;
2457    for (CFListIterator j= bufEvaluation; j.hasItem(); j++, k++)
2458      evalPoly += j.getItem()*power (x, k);
2459    list.append (evalPoly);
2460  }
2461
2462  delete [] bufAeval2;
2463
2464  sortList (biFactors, x);
2465
2466  int minFactorsLength;
2467  bool irred= false;
2468  factorizationWRTDifferentSecondVars (A, Aeval2, info, minFactorsLength, irred);
2469
2470  if (irred)
2471  {
2472    if (extension)
2473    {
2474      CFList source, dest;
2475      A= mapDown (A, info, source, dest);
2476    }
2477    factors.append (A);
2478    appendSwapDecompress (factors, contentAFactors, N, swapLevel,
2479                          swapLevel2, x);
2480    normalize (factors);
2481    delete [] Aeval2;
2482    return factors;
2483  }
2484
2485  if (minFactorsLength == 0)
2486    minFactorsLength= biFactors.length();
2487  else if (biFactors.length() > minFactorsLength)
2488    refineBiFactors (A, biFactors, Aeval2, evaluation, minFactorsLength);
2489  minFactorsLength= tmin (minFactorsLength, biFactors.length());
2490
2491  if (differentSecondVar == A.level() - 2)
2492  {
2493    bool zeroOccured= false;
2494    for (CFListIterator iter= evaluation; iter.hasItem(); iter++)
2495    {
2496      if (iter.getItem().isZero())
2497      {
2498        zeroOccured= true;
2499        break;
2500      }
2501    }
2502    if (!zeroOccured)
2503    {
2504      factors= sparseHeuristic (A, biFactors, Aeval2, evaluation, minFactorsLength);
2505      if (factors.length() == biFactors.length())
2506      {
2507        if (extension)
2508          factors= extNonMonicFactorRecombination (factors, A, info);
2509
2510        appendSwapDecompress (factors, contentAFactors, N, swapLevel,
2511                              swapLevel2, x);
2512        normalize (factors);
2513        delete [] Aeval2;
2514        return factors;
2515      }
2516      else
2517        factors= CFList();
2518      //TODO case where factors.length() > 0
2519    }
2520  }
2521
2522  CFList uniFactors= buildUniFactors (biFactors, evaluation.getLast(), y);
2523
2524  CFList * oldAeval= new CFList [A.level() - 2]; //TODO use bufAeval2 for this
2525  for (int i= 0; i < A.level() - 2; i++)
2526    oldAeval[i]= Aeval2[i];
2527
2528  getLeadingCoeffs (A, Aeval2, uniFactors, evaluation);
2529
2530  CFList biFactorsLCs;
2531  for (CFListIterator i= biFactors; i.hasItem(); i++)
2532    biFactorsLCs.append (LC (i.getItem(), 1));
2533
2534  Variable v;
2535  CFList leadingCoeffs= precomputeLeadingCoeff (LC (A, 1), biFactorsLCs, alpha,
2536                                          evaluation, Aeval2, A.level() - 2, v);
2537
2538  if (v.level() != 1)
2539  {
2540    A= swapvar (A, y, v);
2541    for (int i= 0; i < A.level() - 2; i++)
2542    {
2543      if (oldAeval[i].isEmpty())
2544        continue;
2545      if (oldAeval[i].getFirst().level() == v.level())
2546      {
2547        biFactors= CFList();
2548        for (CFListIterator iter= oldAeval [i]; iter.hasItem(); iter++)
2549          biFactors.append (swapvar (iter.getItem(), v, y));
2550      }
2551    }
2552    int i= A.level();
2553    CanonicalForm evalPoint;
2554    for (CFListIterator iter= evaluation; iter.hasItem(); iter++, i--)
2555    {
2556      if (i == v.level())
2557      {
2558        evalPoint= iter.getItem();
2559        iter.getItem()= evaluation.getLast();
2560        evaluation.removeLast();
2561        evaluation.append (evalPoint);
2562        break;
2563      }
2564    }
2565  }
2566
2567  CFListIterator iter;
2568  CanonicalForm oldA= A;
2569  CFList oldBiFactors= biFactors;
2570  if (!leadingCoeffs.getFirst().inCoeffDomain())
2571  {
2572    CanonicalForm tmp= power (leadingCoeffs.getFirst(), biFactors.length() - 1);
2573    A *= tmp;
2574    tmp= leadingCoeffs.getFirst();
2575    iter= evaluation;
2576    for (int i= A.level(); i > 2; i--, iter++)
2577      tmp= tmp (iter.getItem(), i);
2578    if (!tmp.inCoeffDomain())
2579    {
2580      for (CFListIterator i= biFactors; i.hasItem(); i++)
2581      {
2582        i.getItem() *= tmp/LC (i.getItem(), 1);
2583        i.getItem() /= Lc (i.getItem());
2584      }
2585    }
2586  }
2587
2588  leadingCoeffs.removeFirst();
2589
2590  //prepare leading coefficients
2591  CFList* leadingCoeffs2= new CFList [A.level() - 2];
2592  prepareLeadingCoeffs (leadingCoeffs2, A.level(), leadingCoeffs, biFactors,
2593                        evaluation);
2594
2595  Aeval= evaluateAtEval (A, evaluation, 2);
2596  CanonicalForm hh= Lc (Aeval.getFirst());
2597  for (iter= Aeval; iter.hasItem(); iter++)
2598    iter.getItem() /= hh;
2599
2600  A /= hh;
2601
2602  if (LucksWangSparseHeuristic (A, biFactors, 2, leadingCoeffs2 [A.level() - 3],
2603      factors))
2604  {
2605    int check= factors.length();
2606    factors= recoverFactors (A, factors);
2607
2608    if (check == factors.length())
2609    {
2610      if (extension)
2611        factors= extNonMonicFactorRecombination (factors, A, info);
2612
2613      appendSwapDecompress (factors, contentAFactors, N, swapLevel,
2614                            swapLevel2, x);
2615      normalize (factors);
2616      delete [] Aeval2;
2617      return factors;
2618    }
2619    else
2620      factors= CFList();
2621    //TODO handle this case
2622  }
2623
2624  A= shift2Zero (A, Aeval, evaluation);
2625
2626  for (iter= biFactors; iter.hasItem(); iter++)
2627    iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
2628
2629  for (int i= 0; i < A.level() - 2; i++)
2630  {
2631    if (i != A.level() - 3)
2632      leadingCoeffs2[i]= CFList();
2633  }
2634  for (iter= leadingCoeffs2[A.level() - 3]; iter.hasItem(); iter++)
2635  {
2636    iter.getItem()= shift2Zero (iter.getItem(), list, evaluation);
2637    for (int i= A.level() - 4; i > -1; i--)
2638    {
2639      if (i + 1 == A.level() - 3)
2640        leadingCoeffs2[i].append (iter.getItem() (0, i + 4));
2641      else
2642        leadingCoeffs2[i].append (leadingCoeffs2[i+1].getLast() (0, i + 4));
2643    }
2644  }
2645
2646  CFArray Pi;
2647  CFList diophant;
2648  int* liftBounds= new int [A.level() - 1];
2649  int liftBoundsLength= A.level() - 1;
2650  for (int i= 0; i < liftBoundsLength; i++)
2651    liftBounds [i]= degree (A, i + 2) + 1;
2652
2653  Aeval.removeFirst();
2654  bool noOneToOne= false;
2655  factors= nonMonicHenselLift (Aeval, biFactors, leadingCoeffs2, diophant,
2656                               Pi, liftBounds, liftBoundsLength, noOneToOne);
2657
2658  if (!noOneToOne)
2659  {
2660    int check= factors.length();
2661    A= oldA;
2662    factors= recoverFactors (A, factors, evaluation);
2663    if (check != factors.length())
2664      noOneToOne= true;
2665
2666    if (extension && !noOneToOne)
2667      factors= extNonMonicFactorRecombination (factors, A, info);
2668  }
2669  if (noOneToOne)
2670  {
2671    A= shift2Zero (oldA, Aeval, evaluation);
2672    biFactors= oldBiFactors;
2673    for (iter= biFactors; iter.hasItem(); iter++)
2674      iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
2675    CanonicalForm LCA= LC (Aeval.getFirst(), 1);
2676    CanonicalForm yToLift= power (y, lift);
2677    CFListIterator i= biFactors;
2678    lift= degree (i.getItem(), 2) + degree (LC (i.getItem(), 1)) + 1;
2679    i++;
2680
2681    for (; i.hasItem(); i++)
2682      lift= tmax (lift, degree (i.getItem(), 2) + degree (LC (i.getItem(), 1)) + 1);
2683
2684    lift= tmax (degree (Aeval.getFirst() , 2) + 1, lift);
2685
2686    i= biFactors;
2687    yToLift= power (y, lift);
2688    CanonicalForm dummy;
2689    for (; i.hasItem(); i++)
2690    {
2691      LCA= LC (i.getItem(), 1);
2692      extgcd (LCA, yToLift, LCA, dummy);
2693      i.getItem()= mod (i.getItem()*LCA, yToLift);
2694    }
2695
2696    liftBoundsLength= F.level() - 1;
2697    liftBounds= liftingBounds (A, lift);
2698
2699    CFList MOD;
2700    bool earlySuccess;
2701    CFList earlyFactors;
2702    TIMING_START (fac_hensel_lift);
2703    CFList liftedFactors= henselLiftAndEarly
2704                          (A, MOD, liftBounds, earlySuccess, earlyFactors,
2705                           Aeval, biFactors, evaluation, info);
2706    TIMING_END_AND_PRINT (fac_hensel_lift, "time for hensel lifting: ");
2707
2708    if (!extension)
2709    {
2710      TIMING_START (fac_factor_recombination);
2711      factors= factorRecombination (A, liftedFactors, MOD);
2712      TIMING_END_AND_PRINT (fac_factor_recombination,
2713                            "time for factor recombination: ");
2714    }
2715    else
2716    {
2717      TIMING_START (fac_factor_recombination);
2718      factors= extFactorRecombination (liftedFactors, A, MOD, info, evaluation);
2719      TIMING_END_AND_PRINT (fac_factor_recombination,
2720                            "time for factor recombination: ");
2721    }
2722
2723    if (earlySuccess)
2724      factors= Union (factors, earlyFactors);
2725    if (!extension)
2726    {
2727      for (CFListIterator i= factors; i.hasItem(); i++)
2728      {
2729        int kk= Aeval.getLast().level();
2730        for (CFListIterator j= evaluation; j.hasItem(); j++, kk--)
2731        {
2732          if (i.getItem().level() < kk)
2733            continue;
2734          i.getItem()= i.getItem() (Variable (kk) - j.getItem(), kk);
2735        }
2736      }
2737    }
2738  }
2739
2740  if (v.level() != 1)
2741  {
2742    for (CFListIterator iter= factors; iter.hasItem(); iter++)
2743      iter.getItem()= swapvar (iter.getItem(), v, y);
2744  }
2745
2746  swap (factors, swapLevel, swapLevel2, x);
2747  append (factors, contentAFactors);
2748  decompress (factors, N);
2749  normalize (factors);
2750
2751  delete[] liftBounds;
2752
2753  return factors;
2754}
2755
2756/// multivariate factorization over an extension of the initial field
2757CFList
2758extFactorize (const CanonicalForm& F, const ExtensionInfo& info)
2759{
2760  CanonicalForm A= F;
2761
2762  Variable alpha= info.getAlpha();
2763  Variable beta= info.getBeta();
2764  int k= info.getGFDegree();
2765  char cGFName= info.getGFName();
2766  CanonicalForm delta= info.getDelta();
2767  bool GF= (CFFactory::gettype() == GaloisFieldDomain);
2768  Variable w= Variable (1);
2769
2770  CFList factors;
2771  if (!GF && alpha == w)  // we are in F_p
2772  {
2773    CFList factors;
2774    bool extension= true;
2775    int p= getCharacteristic();
2776    if (p*p < (1<<16)) // pass to GF if possible
2777    {
2778      setCharacteristic (getCharacteristic(), 2, 'Z');
2779      ExtensionInfo info= ExtensionInfo (extension);
2780      A= A.mapinto();
2781      factors= multiFactorize (A, info);
2782
2783      Variable vBuf= rootOf (gf_mipo);
2784      setCharacteristic (getCharacteristic());
2785      for (CFListIterator j= factors; j.hasItem(); j++)
2786        j.getItem()= GF2FalphaRep (j.getItem(), vBuf);
2787    }
2788    else  // not able to pass to GF, pass to F_p(\alpha)
2789    {
2790      CanonicalForm mipo= randomIrredpoly (2, Variable (1));
2791      Variable v= rootOf (mipo);
2792      ExtensionInfo info= ExtensionInfo (v);
2793      factors= multiFactorize (A, info);
2794    }
2795    return factors;
2796  }
2797  else if (!GF && (alpha != w)) // we are in F_p(\alpha)
2798  {
2799    if (k == 1) // need factorization over F_p
2800    {
2801      int extDeg= degree (getMipo (alpha));
2802      extDeg++;
2803      CanonicalForm mipo= randomIrredpoly (extDeg + 1, Variable (1));
2804      Variable v= rootOf (mipo);
2805      ExtensionInfo info= ExtensionInfo (v);
2806      factors= biFactorize (A, info);
2807    }
2808    else
2809    {
2810      if (beta == Variable (1))
2811      {
2812        Variable v= chooseExtension (alpha, beta, k);
2813        CanonicalForm primElem, imPrimElem;
2814        bool primFail= false;
2815        Variable vBuf;
2816        primElem= primitiveElement (alpha, vBuf, primFail);
2817        ASSERT (!primFail, "failure in integer factorizer");
2818        if (primFail)
2819          ; //ERROR
2820        else
2821          imPrimElem= mapPrimElem (primElem, vBuf, v);
2822
2823        CFList source, dest;
2824        CanonicalForm bufA= mapUp (A, alpha, v, primElem, imPrimElem,
2825                                   source, dest);
2826        ExtensionInfo info= ExtensionInfo (v, alpha, imPrimElem, primElem);
2827        factors= biFactorize (bufA, info);
2828      }
2829      else
2830      {
2831        Variable v= chooseExtension (alpha, beta, k);
2832        CanonicalForm primElem, imPrimElem;
2833        bool primFail= false;
2834        Variable vBuf;
2835        ASSERT (!primFail, "failure in integer factorizer");
2836        if (primFail)
2837          ; //ERROR
2838        else
2839          imPrimElem= mapPrimElem (delta, beta, v);
2840
2841        CFList source, dest;
2842        CanonicalForm bufA= mapDown (A, info, source, dest);
2843        source= CFList();
2844        dest= CFList();
2845        bufA= mapUp (bufA, beta, v, delta, imPrimElem, source, dest);
2846        ExtensionInfo info= ExtensionInfo (v, beta, imPrimElem, delta);
2847        factors= biFactorize (bufA, info);
2848      }
2849    }
2850    return factors;
2851  }
2852  else // we are in GF (p^k)
2853  {
2854    int p= getCharacteristic();
2855    int extensionDeg= getGFDegree();
2856    bool extension= true;
2857    if (k == 1) // need factorization over F_p
2858    {
2859      extensionDeg++;
2860      if (pow ((double) p, (double) extensionDeg) < (1<<16))
2861      // pass to GF(p^k+1)
2862      {
2863        setCharacteristic (p);
2864        Variable vBuf= rootOf (gf_mipo);
2865        A= GF2FalphaRep (A, vBuf);
2866        setCharacteristic (p, extensionDeg, 'Z');
2867        ExtensionInfo info= ExtensionInfo (extension);
2868        factors= multiFactorize (A.mapinto(), info);
2869      }
2870      else // not able to pass to another GF, pass to F_p(\alpha)
2871      {
2872        setCharacteristic (p);
2873        Variable vBuf= rootOf (gf_mipo);
2874        A= GF2FalphaRep (A, vBuf);
2875        Variable v= chooseExtension (vBuf, beta, k);
2876        ExtensionInfo info= ExtensionInfo (v, extension);
2877        factors= multiFactorize (A, info);
2878      }
2879    }
2880    else // need factorization over GF (p^k)
2881    {
2882      if (pow ((double) p, (double) 2*extensionDeg) < (1<<16))
2883      // pass to GF(p^2k)
2884      {
2885        setCharacteristic (p, 2*extensionDeg, 'Z');
2886        ExtensionInfo info= ExtensionInfo (k, cGFName, extension);
2887        factors= multiFactorize (GFMapUp (A, extensionDeg), info);
2888        setCharacteristic (p, extensionDeg, cGFName);
2889      }
2890      else // not able to pass to GF (p^2k), pass to F_p (\alpha)
2891      {
2892        setCharacteristic (p);
2893        Variable v1= rootOf (gf_mipo);
2894        A= GF2FalphaRep (A, v1);
2895        Variable v2= chooseExtension (v1, v1, k);
2896        CanonicalForm primElem, imPrimElem;
2897        bool primFail= false;
2898        Variable vBuf;
2899        primElem= primitiveElement (v1, v1, primFail);
2900        if (primFail)
2901          ; //ERROR
2902        else
2903          imPrimElem= mapPrimElem (primElem, v1, v2);
2904        CFList source, dest;
2905        CanonicalForm bufA= mapUp (A, v1, v2, primElem, imPrimElem,
2906                                     source, dest);
2907        ExtensionInfo info= ExtensionInfo (v2, v1, imPrimElem, primElem);
2908        factors= multiFactorize (bufA, info);
2909        setCharacteristic (p, k, cGFName);
2910        for (CFListIterator i= factors; i.hasItem(); i++)
2911          i.getItem()= Falpha2GFRep (i.getItem());
2912      }
2913    }
2914    return factors;
2915  }
2916}
2917
2918#endif
2919/* HAVE_NTL */
2920
Note: See TracBrowser for help on using the repository browser.