source: git/factory/facFqFactorize.cc @ 35eb6c

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