source: git/factory/facFqFactorize.cc @ 91788c0

spielwiese
Last change on this file since 91788c0 was 91788c0, checked in by Martin Lee <martinlee84@…>, 12 years ago
add: code for sparse heuristic lifting a la Lucks/Wang moved: code for other sparse heuristic to facSparseHensel rm: unused function leadingCoeffReconstruction from facFqFactorize.cc
  • Property mode set to 100644
File size: 71.3 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
1281int
1282testFactors (const CanonicalForm& G, const CFList& uniFactors,
1283             const Variable& alpha, CanonicalForm& sqrfPartF, CFList& factors,
1284             CFFList*& bufSqrfFactors, CFList& evalSqrfPartF)
1285{
1286  CanonicalForm tmp;
1287  CFListIterator j;
1288  for (CFListIterator i= uniFactors; i.hasItem(); i++)
1289  {
1290    tmp= i.getItem();
1291    if (i.hasItem())
1292      i++;
1293    else
1294      break;
1295    for (j= i; j.hasItem(); j++)
1296    {
1297      if (tmp == j.getItem())
1298        return 0;
1299    }
1300  }
1301
1302  CanonicalForm F= G;
1303  CFFList sqrfFactorization= squarefreeFactorization (F, alpha);
1304
1305  sqrfPartF= 1;
1306  for (CFFListIterator i= sqrfFactorization; i.hasItem(); i++)
1307    sqrfPartF *= i.getItem().factor();
1308
1309  evalSqrfPartF= evaluateAtZero (sqrfPartF);
1310
1311  CanonicalForm test= evalSqrfPartF.getFirst() (0, 2);
1312
1313  if (degree (test) != degree (sqrfPartF, 1))
1314    return 0;
1315
1316  CFFList sqrfFactors;
1317  CFList tmp2;
1318  int k= 0;
1319  factors= uniFactors;
1320  CFFListIterator iter;
1321  for (CFListIterator i= factors; i.hasItem(); i++, k++)
1322  {
1323    tmp= 1;
1324    sqrfFactors= squarefreeFactorization (i.getItem(), alpha);
1325
1326    for (iter= sqrfFactors; iter.hasItem(); iter++)
1327    {
1328      tmp2.append (iter.getItem().factor());
1329      tmp *= iter.getItem().factor();
1330    }
1331    i.getItem()= tmp/Lc(tmp);
1332    bufSqrfFactors [k]= sqrfFactors;
1333  }
1334
1335  for (int i= 0; i < factors.length() - 1; i++)
1336  {
1337    for (k= i + 1; k < factors.length(); k++)
1338    {
1339      gcdFreeBasis (bufSqrfFactors [i], bufSqrfFactors[k]);
1340    }
1341  }
1342
1343  factors= CFList();
1344  for (int i= 0; i < uniFactors.length(); i++)
1345  {
1346    if (i == 0)
1347    {
1348      for (iter= bufSqrfFactors [i]; iter.hasItem(); iter++)
1349      {
1350        if (iter.getItem().factor().inCoeffDomain())
1351          continue;
1352        iter.getItem()= CFFactor (iter.getItem().factor()/
1353                                  Lc (iter.getItem().factor()),
1354                                  iter.getItem().exp());
1355        factors.append (iter.getItem().factor());
1356      }
1357    }
1358    else
1359    {
1360      for (iter= bufSqrfFactors [i]; iter.hasItem(); iter++)
1361      {
1362        if (iter.getItem().factor().inCoeffDomain())
1363          continue;
1364        iter.getItem()= CFFactor (iter.getItem().factor()/
1365                                  Lc (iter.getItem().factor()),
1366                                  iter.getItem().exp());
1367        if (!find (factors, iter.getItem().factor()))
1368          factors.append (iter.getItem().factor());
1369      }
1370    }
1371  }
1372
1373  test= prod (factors);
1374  tmp= evalSqrfPartF.getFirst() (0,2);
1375  if (test/Lc (test) != tmp/Lc (tmp))
1376    return 0;
1377  else
1378    return 1;
1379}
1380
1381CFList
1382precomputeLeadingCoeff (const CanonicalForm& LCF, const CFList& LCFFactors,
1383                        const Variable& alpha, const CFList& evaluation,
1384                        CFList* & differentSecondVarLCs, int length,
1385                        Variable& y
1386                       )
1387{
1388  y= Variable (1);
1389  if (LCF.inCoeffDomain())
1390  {
1391    CFList result;
1392    for (int i= 1; i <= LCFFactors.length() + 1; i++)
1393      result.append (1);
1394    return result;
1395  }
1396
1397  CFMap N;
1398  CanonicalForm F= compress (LCF, N);
1399  if (LCF.isUnivariate())
1400  {
1401    CFList result;
1402    int LCFLevel= LCF.level();
1403    bool found= false;
1404    if (LCFLevel == 2)
1405    {
1406    //bivariate leading coefficients are already the true leading coefficients
1407      result= LCFFactors;
1408      Variable v= Variable (LCF.mvar());
1409      CanonicalForm bla= 1;
1410      for (CFListIterator i= result; i.hasItem(); i++)
1411      {
1412        i.getItem()= i.getItem() (v+evaluation.getLast(), v);
1413        bla *= Lc (i.getItem());
1414      }
1415      found= true;
1416    }
1417    else
1418    {
1419      CFListIterator j;
1420      for (int i= 0; i < length; i++)
1421      {
1422        for (j= differentSecondVarLCs[i]; j.hasItem(); j++)
1423        {
1424          if (j.getItem().level() == LCFLevel)
1425          {
1426            found= true;
1427            break;
1428          }
1429        }
1430        if (found)
1431        {
1432          result= differentSecondVarLCs [i];
1433          break;
1434        }
1435      }
1436      if (!found)
1437        result= LCFFactors;
1438    }
1439    if (found)
1440      result.insert (Lc (LCF));
1441    else
1442      result.append (LCF);
1443    return result;
1444  }
1445
1446  CFList factors= LCFFactors;
1447
1448  CFMap dummy;
1449  for (CFListIterator i= factors; i.hasItem(); i++)
1450  {
1451    i.getItem()= compress (i.getItem(), dummy);
1452    i.getItem()= i.getItem() (Variable (1) + evaluation.getLast(), Variable (1));
1453  }
1454
1455  CanonicalForm sqrfPartF;
1456  CFFList * bufSqrfFactors= new CFFList [factors.length()];
1457  CFList evalSqrfPartF;
1458  CFList bufFactors;
1459  int pass= testFactors (F, factors, alpha, sqrfPartF,
1460                         bufFactors, bufSqrfFactors, evalSqrfPartF);
1461
1462  bool foundDifferent= false;
1463  Variable z;
1464  Variable x= y;
1465  int j= 0;
1466  if (!pass)
1467  {
1468    int lev;
1469    // LCF is non-constant here
1470    for (int i= 1; i <= LCF.level(); i++)
1471    {
1472      if(degree (LCF, i) > 0)
1473      {
1474        lev= i - 1;
1475        break;
1476      }
1477    }
1478    CFListIterator iter;
1479    CFList bufBufFactors;
1480    CanonicalForm bufF;
1481    for (int i= 0; i < length; i++)
1482    {
1483      if (!differentSecondVarLCs [i].isEmpty())
1484      {
1485        bool allConstant= true;
1486        for (iter= differentSecondVarLCs[i]; iter.hasItem(); iter++)
1487        {
1488          if (!iter.getItem().inCoeffDomain())
1489          {
1490            allConstant= false;
1491            y= Variable (iter.getItem().level());
1492          }
1493        }
1494        if (allConstant)
1495          continue;
1496
1497        bufFactors= differentSecondVarLCs [i];
1498        for (iter= bufFactors; iter.hasItem(); iter++)
1499          iter.getItem()= swapvar (iter.getItem(), x, y);
1500        bufF= F;
1501        z= Variable (y.level() - lev);
1502        bufF= swapvar (bufF, x, z);
1503        bufBufFactors= bufFactors;
1504        pass= testFactors (bufF, bufBufFactors, alpha, sqrfPartF, bufFactors,
1505                           bufSqrfFactors, evalSqrfPartF);
1506        if (pass)
1507        {
1508          foundDifferent= true;
1509          F= bufF;
1510          CFList l= factors;
1511          for (iter= l; iter.hasItem(); iter++)
1512            iter.getItem()= swapvar (iter.getItem(), x, y);
1513          differentSecondVarLCs [i]= l;
1514          j= i;
1515          break;
1516        }
1517        if (!pass && i == length - 1)
1518        {
1519          CFList result;
1520          result.append (LCF);
1521          for (int k= 1; k <= factors.length(); k++)
1522            result.append (LCF);
1523          y= Variable (1);
1524          delete [] bufSqrfFactors;
1525          return result;
1526        }
1527      }
1528    }
1529  }
1530  if (!pass)
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    delete [] bufSqrfFactors;
1538    return result;
1539  }
1540  else
1541    factors= bufFactors;
1542
1543  bufFactors= factors;
1544
1545  if (factors.length() > 1)
1546  {
1547    CanonicalForm LC1= LC (evalSqrfPartF.getFirst(), 1);
1548
1549    CFArray leadingCoeffs= CFArray (factors.length());
1550    for (int i= 0; i < factors.length(); i++)
1551      leadingCoeffs[i]= LC1;
1552    for (CFListIterator i= factors; i.hasItem(); i++)
1553      i.getItem() *= LC1 (0,2)/Lc (i.getItem());
1554    factors.insert (1);
1555
1556    CanonicalForm
1557    newSqrfPartF= evalSqrfPartF.getFirst()*power (LC1, factors.length() - 2);
1558
1559    int liftBound= degree (newSqrfPartF,2) + 1;
1560
1561    CFMatrix M= CFMatrix (liftBound, factors.length() - 1);
1562    CFArray Pi;
1563    CFList diophant;
1564    henselLift122 (newSqrfPartF, factors, liftBound, Pi, diophant, M,
1565                   leadingCoeffs, false);
1566
1567    if (sqrfPartF.level() > 2)
1568    {
1569      int* liftBounds= new int [sqrfPartF.level() - 1];
1570      liftBounds [0]= liftBound;
1571      bool noOneToOne= false;
1572      CFList *leadingCoeffs2= new CFList [sqrfPartF.level()-2];
1573      LC1= LC (evalSqrfPartF.getLast(), 1);
1574      CFList LCs;
1575      for (int i= 0; i < factors.length(); i++)
1576        LCs.append (LC1);
1577      leadingCoeffs2 [sqrfPartF.level() - 3]= LCs;
1578      for (int i= sqrfPartF.level() - 1; i > 2; i--)
1579      {
1580        for (CFListIterator j= LCs; j.hasItem(); j++)
1581          j.getItem()= j.getItem() (0, i + 1);
1582        leadingCoeffs2 [i - 3]= LCs;
1583      }
1584      sqrfPartF= sqrfPartF*power (LC1, factors.length()-1);
1585
1586      int liftBoundsLength= sqrfPartF.level() - 1;
1587      for (int i= 1; i < liftBoundsLength; i++)
1588        liftBounds [i]= degree (sqrfPartF, i + 2) + 1;
1589      evalSqrfPartF= evaluateAtZero (sqrfPartF);
1590      evalSqrfPartF.removeFirst();
1591      factors= nonMonicHenselLift (evalSqrfPartF, factors, leadingCoeffs2,
1592               diophant, Pi, liftBounds, sqrfPartF.level() - 1, noOneToOne);
1593      delete [] leadingCoeffs2;
1594      delete [] liftBounds;
1595    }
1596  }
1597  else
1598    factors= evalSqrfPartF.getLast();
1599
1600  CFList interMedResult= recoverFactors (evalSqrfPartF.getLast(), factors);
1601
1602  CFList result;
1603  CFFListIterator k;
1604  for (int i= 0; i < LCFFactors.length(); i++)
1605  {
1606    CanonicalForm tmp= 1;
1607    for (k= bufSqrfFactors[i]; k.hasItem(); k++)
1608    {
1609      int pos= findItem (bufFactors, k.getItem().factor());
1610      if (pos)
1611        tmp *= power (getItem (interMedResult, pos), k.getItem().exp());
1612    }
1613    result.append (tmp);
1614  }
1615
1616  for (CFListIterator i= result; i.hasItem(); i++)
1617  {
1618    F /= i.getItem();
1619    if (foundDifferent)
1620      i.getItem()= swapvar (i.getItem(), x, z);
1621    i.getItem()= N (i.getItem());
1622  }
1623
1624  if (foundDifferent)
1625  {
1626    CFList l= differentSecondVarLCs [j];
1627    for (CFListIterator i= l; i.hasItem(); i++)
1628      i.getItem()= swapvar (i.getItem(), y, z);
1629    differentSecondVarLCs [j]= l;
1630    F= swapvar (F, x, z);
1631  }
1632
1633  result.insert (N (F));
1634
1635  result= distributeContent (result, differentSecondVarLCs, length);
1636
1637  if (!result.getFirst().inCoeffDomain())
1638  {
1639    CFListIterator i= result;
1640    CanonicalForm tmp;
1641    if (foundDifferent)
1642      i.getItem()= swapvar (i.getItem(), Variable (2), y);
1643
1644    tmp= i.getItem();
1645
1646    i++;
1647    for (; i.hasItem(); i++)
1648    {
1649      if (foundDifferent)
1650        i.getItem()= swapvar (i.getItem(), Variable (2), y)*tmp;
1651      else
1652        i.getItem() *= tmp;
1653    }
1654  }
1655  else
1656    y= Variable (1);
1657
1658  delete [] bufSqrfFactors;
1659
1660  return result;
1661}
1662
1663void
1664evaluationWRTDifferentSecondVars (CFList*& Aeval, const CFList& evaluation,
1665                                  const CanonicalForm& A)
1666{
1667  CanonicalForm tmp;
1668  CFList tmp2;
1669  CFListIterator iter;
1670  for (int i= A.level(); i > 2; i--)
1671  {
1672    tmp= A;
1673    tmp2= CFList();
1674    iter= evaluation;
1675    bool preserveDegree= true;
1676    for (int j= A.level(); j > 1; j--, iter++)
1677    {
1678      if (j == i)
1679        continue;
1680      else
1681      {
1682        tmp= tmp (iter.getItem(), j);
1683        tmp2.insert (tmp);
1684        if ((degree (tmp, i) != degree (A, i)) ||
1685            (degree (tmp, 1) != degree (A, 1)))
1686        {
1687          preserveDegree= false;
1688          break;
1689        }
1690        if (!content(tmp).inCoeffDomain() || !content(tmp,1).inCoeffDomain())
1691        {
1692          preserveDegree= false;
1693          break;
1694        }
1695      }
1696    }
1697    if (preserveDegree)
1698      Aeval [i - 3]= tmp2;
1699    else
1700      Aeval [i - 3]= CFList();
1701  }
1702}
1703
1704static inline
1705CanonicalForm prodEval (const CFList& l, const CanonicalForm& evalPoint,
1706                        const Variable& v)
1707{
1708  CanonicalForm result= 1;
1709  for (CFListIterator i= l; i.hasItem(); i++)
1710    result *= i.getItem() (evalPoint, v);
1711  return result;
1712}
1713
1714//recombine bivariate factors in case one bivariate factorization yields less
1715// factors than the other
1716CFList
1717recombination (const CFList& factors1, const CFList& factors2, int s, int thres,
1718               const CanonicalForm& evalPoint, const Variable& x)
1719{
1720  CFList T, S;
1721
1722  T= factors1;
1723  CFList result;
1724  CanonicalForm buf;
1725  int * v= new int [T.length()];
1726  for (int i= 0; i < T.length(); i++)
1727    v[i]= 0;
1728  bool nosubset= false;
1729  CFArray TT;
1730  TT= copy (factors1);
1731  while (T.length() >= 2*s && s <= thres)
1732  {
1733    while (nosubset == false) 
1734    {
1735      if (T.length() == s) 
1736      {
1737        delete [] v;
1738        result.append (prod (T));
1739        return result;
1740      }
1741      S= subset (v, s, TT, nosubset);
1742      if (nosubset) break;
1743      buf= prodEval (S, evalPoint, x);
1744      buf /= Lc (buf);
1745      if (find (factors2, buf))
1746      {
1747        T= Difference (T, S);
1748        result.append (prod (S));
1749        TT= copy (T);
1750        indexUpdate (v, s, T.length(), nosubset);
1751        if (nosubset) break;
1752      }
1753    }
1754    s++;
1755    if (T.length() < 2*s || T.length() == s) 
1756    {
1757      delete [] v;
1758      result.append (prod (T));
1759      return result;
1760    }
1761    for (int i= 0; i < T.length(); i++)
1762      v[i]= 0;
1763    nosubset= false;
1764  }
1765
1766  delete [] v;
1767  if (T.length() < 2*s)
1768  {
1769    result.append (prod (T));
1770    return result;
1771  }
1772
1773  return result;
1774}
1775
1776void
1777factorizationWRTDifferentSecondVars (const CanonicalForm& A, CFList*& Aeval,
1778                                     const ExtensionInfo& info,
1779                                     int& minFactorsLength, bool& irred)
1780{
1781  Variable x= Variable (1);
1782  minFactorsLength= 0;
1783  irred= false;
1784  CFList factors;
1785  Variable v;
1786  for (int j= 0; j < A.level() - 2; j++)
1787  {
1788    if (!Aeval[j].isEmpty())
1789    {
1790      v= Variable (Aeval[j].getFirst().level());
1791      if (CFFactory::gettype() == GaloisFieldDomain)
1792        factors= GFBiSqrfFactorize (Aeval[j].getFirst());
1793      else if (info.getAlpha().level() == 1)
1794        factors= FpBiSqrfFactorize (Aeval[j].getFirst());
1795      else
1796        factors= FqBiSqrfFactorize (Aeval[j].getFirst(), info.getAlpha());
1797
1798      factors.removeFirst();
1799      if (minFactorsLength == 0)
1800        minFactorsLength= factors.length();
1801      else
1802        minFactorsLength= tmin (minFactorsLength, factors.length());
1803
1804      if (factors.length() == 1)
1805      {
1806        irred= true;
1807        return;
1808      }
1809      sortList (factors, x);
1810      Aeval [j]= factors;
1811    }
1812  }
1813}
1814
1815void getLeadingCoeffs (const CanonicalForm& A, CFList*& Aeval,
1816                       const CFList& uniFactors, const CFList& evaluation
1817                      )
1818{
1819  CanonicalForm evalPoint;
1820  int i;
1821  CFListIterator iter, iter2;
1822  Variable v;
1823  CFList l, LCs;
1824  CanonicalForm buf;
1825  for (int j= 0; j < A.level() - 2; j++)
1826  {
1827    if (!Aeval[j].isEmpty())
1828    {
1829      i= A.level();
1830      for (iter= evaluation; iter.hasItem(); iter++, i--)
1831      {
1832        if (i == Aeval[j].getFirst().level())
1833        {
1834          evalPoint= iter.getItem();
1835          break;
1836        }
1837      }
1838
1839      v= Variable (i);
1840      if (Aeval[j].length() > uniFactors.length())
1841        Aeval[j]= recombination (Aeval[j], uniFactors, 1,
1842                                 Aeval[j].length() - uniFactors.length() + 1,
1843                                 evalPoint, v);
1844
1845      l= CFList();
1846      for (iter= uniFactors; iter.hasItem(); iter++)
1847      {
1848        for (iter2= Aeval[j]; iter2.hasItem(); iter2++)
1849        {
1850          buf= mod (iter2.getItem(), v - evalPoint);
1851          buf /= Lc (buf);
1852          if (iter.getItem() == buf)
1853          {
1854            l.append (iter2.getItem());
1855            break;
1856          }
1857        }
1858      }
1859      Aeval [j]= l;
1860
1861      LCs= CFList();
1862      for (iter= Aeval[j]; iter.hasItem(); iter++)
1863        LCs.append (LC (iter.getItem() (v + evalPoint, v), 1));
1864      normalize (LCs);
1865      Aeval[j]= LCs;
1866    }
1867  }
1868}
1869
1870CFList
1871buildUniFactors (const CFList& biFactors, const CanonicalForm& evalPoint,
1872                 const Variable& y)
1873{
1874  CFList result;
1875  CanonicalForm tmp;
1876  for (CFListIterator i= biFactors; i.hasItem(); i++)
1877  {
1878    tmp= mod (i.getItem(), y - evalPoint);
1879    tmp /= Lc (tmp);
1880    result.append (tmp);
1881  }
1882  return result;
1883}
1884
1885void refineBiFactors (const CanonicalForm& A, CFList& biFactors,
1886                      CFList* const& Aeval, const CFList& evaluation,
1887                      int minFactorsLength)
1888{
1889  CFListIterator iter;
1890  CanonicalForm evalPoint;
1891  int i;
1892  Variable v;
1893  Variable y= Variable (2);
1894  CFList list;
1895  for (int j= 0; j < A.level() - 2; j++)
1896  {
1897    if (Aeval[j].length() == minFactorsLength)
1898    {
1899      i= A.level();
1900
1901      for (iter= evaluation; iter.hasItem(); iter++, i--)
1902      {
1903        if (i == Aeval[j].getFirst().level())
1904        {
1905          evalPoint= iter.getItem();
1906          break;
1907        }
1908      }
1909
1910      v= Variable (i);
1911      list= buildUniFactors (Aeval[j], evalPoint, v);
1912
1913      biFactors= recombination (biFactors, list, 1,
1914                                biFactors.length() - list.length() + 1,
1915                                evaluation.getLast(), y);
1916      return;
1917    }
1918  }
1919}
1920
1921void prepareLeadingCoeffs (CFList*& LCs, int n, const CFList& leadingCoeffs,
1922                           const CFList& biFactors)
1923{
1924  CFList l= leadingCoeffs;
1925  LCs [n-3]= l;
1926  CFListIterator j;
1927  for (int i= n - 1; i > 2; i--)
1928  {
1929    for (j= l; j.hasItem(); j++)
1930      j.getItem()= j.getItem() (0, i + 1);
1931    LCs [i - 3]= l;
1932  }
1933  l= LCs [0];
1934  for (CFListIterator i= l; i.hasItem(); i++)
1935    i.getItem()= i.getItem() (0, 3);
1936  CFListIterator ii= biFactors;
1937  CFList normalizeFactor;
1938  for (CFListIterator i= l; i.hasItem(); i++, ii++)
1939    normalizeFactor.append (Lc (LC (ii.getItem(), 1))/Lc (i.getItem()));
1940  for (int i= 0; i < n-2; i++)
1941  {
1942    ii= normalizeFactor;
1943    for (j= LCs [i]; j.hasItem(); j++, ii++)
1944      j.getItem() *= ii.getItem();
1945  }
1946}
1947
1948CFList recoverFactors (const CanonicalForm& F, const CFList& factors)
1949{
1950  CFList result;
1951  CanonicalForm tmp, tmp2;
1952  CanonicalForm G= F;
1953  for (CFListIterator i= factors; i.hasItem(); i++)
1954  {
1955    tmp= i.getItem()/content (i.getItem(), 1);
1956    if (fdivides (tmp, G, tmp2))
1957    {
1958      G= tmp2;
1959      result.append (tmp);
1960    }
1961  }
1962  return result;
1963}
1964
1965CFList recoverFactors (const CanonicalForm& F, const CFList& factors,
1966                       const CFList& evaluation)
1967{
1968  CFList result;
1969  CanonicalForm tmp, tmp2;
1970  CanonicalForm G= F;
1971  for (CFListIterator i= factors; i.hasItem(); i++)
1972  {
1973    tmp= reverseShift (i.getItem(), evaluation);
1974    tmp /= content (tmp, 1);
1975    if (fdivides (tmp, G, tmp2))
1976    {
1977      G= tmp2;
1978      result.append (tmp);
1979    }
1980  }
1981  return result;
1982}
1983
1984CFList
1985extNonMonicFactorRecombination (const CFList& factors, const CanonicalForm& F,
1986                                const ExtensionInfo& info)
1987{
1988  Variable alpha= info.getAlpha();
1989  Variable beta= info.getBeta();
1990  CanonicalForm gamma= info.getGamma();
1991  CanonicalForm delta= info.getDelta();
1992  int k= info.getGFDegree();
1993  CFList source, dest;
1994
1995  int degMipoBeta= 1;
1996  if (!k && beta != Variable(1))
1997    degMipoBeta= degree (getMipo (beta));
1998
1999  CFList T, S;
2000  T= factors;
2001  int s= 1;
2002  CFList result;
2003  CanonicalForm quot, buf= F;
2004
2005  CanonicalForm g;
2006  CanonicalForm buf2;
2007  int * v= new int [T.length()];
2008  for (int i= 0; i < T.length(); i++)
2009    v[i]= 0;
2010  bool noSubset= false;
2011  CFArray TT;
2012  TT= copy (factors);
2013  bool recombination= false;
2014  bool trueFactor= false;
2015  while (T.length() >= 2*s)
2016  {
2017    while (noSubset == false)
2018    {
2019      if (T.length() == s)
2020      {
2021        delete [] v;
2022        if (recombination)
2023        {
2024          g= prod (T);
2025          T.removeFirst();
2026          result.append (g/myContent (g));
2027          g /= Lc (g);
2028          appendTestMapDown (result, g, info, source, dest);
2029          return result;
2030        }
2031        else
2032          return CFList (buf);
2033      }
2034
2035      S= subset (v, s, TT, noSubset);
2036      if (noSubset) break;
2037
2038      g= prod (S);
2039      g /= myContent (g);
2040      if (fdivides (g, buf, quot))
2041      {
2042        buf2= g;
2043        buf2 /= Lc (buf2);
2044        if (!k && beta == Variable (1))
2045        {
2046          if (degree (buf2, alpha) < degMipoBeta)
2047          {
2048            appendTestMapDown (result, buf2, info, source, dest);
2049            buf= quot;
2050            recombination= true;
2051            trueFactor= true;
2052          }
2053        }
2054        else
2055        {
2056          if (!isInExtension (buf2, gamma, k, delta, source, dest))
2057          {
2058            appendTestMapDown (result, buf2, info, source, dest);
2059            buf= quot;
2060            recombination= true;
2061            trueFactor= true;
2062          }
2063        }
2064        if (trueFactor)
2065        {
2066          T= Difference (T, S);
2067
2068          if (T.length() < 2*s || T.length() == s)
2069          {
2070            delete [] v;
2071            buf /= Lc (buf);
2072            appendTestMapDown (result, buf, info, source, dest);
2073            return result;
2074          }
2075          trueFactor= false;
2076          TT= copy (T);
2077          indexUpdate (v, s, T.length(), noSubset);
2078          if (noSubset) break;
2079        }
2080      }
2081    }
2082    s++;
2083    if (T.length() < 2*s || T.length() == s)
2084    {
2085      delete [] v;
2086      appendTestMapDown (result, buf, info, source, dest);
2087      return result;
2088    }
2089    for (int i= 0; i < T.length(); i++)
2090      v[i]= 0;
2091    noSubset= false;
2092  }
2093  if (T.length() < 2*s)
2094    appendMapDown (result, F, info, source, dest);
2095
2096  delete [] v;
2097  return result;
2098}
2099
2100CFList
2101extFactorize (const CanonicalForm& F, const ExtensionInfo& info);
2102
2103CFList
2104multiFactorize (const CanonicalForm& F, const ExtensionInfo& info)
2105{
2106
2107  if (F.inCoeffDomain())
2108    return CFList (F);
2109
2110  // compress and find main Variable
2111  CFMap N;
2112  CanonicalForm A= myCompress (F, N);
2113
2114  A /= Lc (A); // make monic
2115
2116  Variable alpha= info.getAlpha();
2117  Variable beta= info.getBeta();
2118  CanonicalForm gamma= info.getGamma();
2119  CanonicalForm delta= info.getDelta();
2120  bool extension= info.isInExtension();
2121  bool GF= (CFFactory::gettype() == GaloisFieldDomain);
2122  //univariate case
2123  if (F.isUnivariate())
2124  {
2125    if (extension == false)
2126      return uniFactorizer (F, alpha, GF);
2127    else
2128    {
2129      CFList source, dest;
2130      A= mapDown (F, info, source, dest);
2131      return uniFactorizer (A, beta, GF);
2132    }
2133  }
2134
2135  //bivariate case
2136  if (A.level() == 2)
2137  {
2138    CFList buf= biFactorize (F, info);
2139    return buf;
2140  }
2141
2142  Variable x= Variable (1);
2143  Variable y= Variable (2);
2144
2145  // remove content
2146  CFList contentAi;
2147  CanonicalForm lcmCont= lcmContent (A, contentAi);
2148  A /= lcmCont;
2149
2150  // trivial after content removal
2151  CFList contentAFactors;
2152  if (A.inCoeffDomain())
2153  {
2154    for (CFListIterator i= contentAi; i.hasItem(); i++)
2155    {
2156      if (i.getItem().inCoeffDomain())
2157        continue;
2158      else
2159      {
2160        lcmCont /= i.getItem();
2161        contentAFactors=
2162        Union (multiFactorize (lcmCont, info),
2163               multiFactorize (i.getItem(), info));
2164        break;
2165      }
2166    }
2167    decompress (contentAFactors, N);
2168    normalize (contentAFactors);
2169    return contentAFactors;
2170  }
2171
2172  // factorize content
2173  contentAFactors= multiFactorize (lcmCont, info);
2174
2175  // univariate after content removal
2176  CFList factors;
2177  if (A.isUnivariate ())
2178  {
2179    factors= uniFactorizer (A, alpha, GF);
2180    append (factors, contentAFactors);
2181    decompress (factors, N);
2182    return factors;
2183  }
2184
2185  // check main variable
2186  int swapLevel= 0;
2187  CanonicalForm derivZ;
2188  CanonicalForm gcdDerivZ;
2189  CanonicalForm bufA= A;
2190  Variable z;
2191  for (int i= 1; i <= A.level(); i++)
2192  {
2193    z= Variable (i);
2194    derivZ= deriv (bufA, z);
2195    if (derivZ.isZero())
2196    {
2197      if (i == 1)
2198        swapLevel= 1;
2199      else
2200        continue;
2201    }
2202    else
2203    {
2204      if (swapLevel == 1)
2205      {
2206        swapLevel= i;
2207        bufA= swapvar (A, x, z);
2208      }
2209      gcdDerivZ= gcd (bufA, derivZ);
2210      if (degree (gcdDerivZ) > 0 && !derivZ.isZero())
2211      {
2212        CanonicalForm g= bufA/gcdDerivZ;
2213        CFList factorsG=
2214        Union (multiFactorize (g, info),
2215               multiFactorize (gcdDerivZ, info));
2216        appendSwapDecompress (factorsG, contentAFactors, N, swapLevel, x);
2217        normalize (factorsG);
2218        return factorsG;
2219      }
2220      else
2221      {
2222        A= bufA;
2223        break;
2224      }
2225    }
2226  }
2227
2228
2229  CFList Aeval, list, evaluation, bufEvaluation, bufAeval;
2230  bool fail= false;
2231  int swapLevel2= 0;
2232  int level;
2233  int factorNums= 3;
2234  CanonicalForm bivarEval;
2235  CFList biFactors, bufBiFactors;
2236  CanonicalForm evalPoly;
2237  int lift, bufLift;
2238  double logarithm= (double) ilog2 (totaldegree (A));
2239  logarithm /= log2exp;
2240  logarithm= ceil (logarithm);
2241  if (factorNums < (int) logarithm)
2242    factorNums= (int) logarithm;
2243  CFList* bufAeval2= new CFList [A.level() - 2];
2244  CFList* Aeval2= new CFList [A.level() - 2];
2245  int counter;
2246  int differentSecondVar= 0;
2247  // several bivariate factorizations
2248  for (int i= 0; i < factorNums; i++)
2249  {
2250    counter= 0;
2251    bufA= A;
2252    bufAeval= CFList();
2253    bufEvaluation= evalPoints (bufA, bufAeval, alpha, list, GF, fail);
2254    evalPoly= 0;
2255
2256    if (fail && (i == 0))
2257    {
2258      if (!swapLevel)
2259        level= 2;
2260      else
2261        level= swapLevel + 1;
2262
2263      CanonicalForm g;
2264      swapLevel2= newMainVariableSearch (A, Aeval, evaluation, alpha, level, g);
2265
2266      if (!swapLevel2) // need to pass to an extension
2267      {
2268        factors= extFactorize (A, info);
2269        appendSwapDecompress (factors, contentAFactors, N, swapLevel, x);
2270        normalize (factors);
2271        delete [] bufAeval2;
2272        delete [] Aeval2;
2273        return factors;
2274      }
2275      else
2276      {
2277        if (swapLevel2 == -1)
2278        {
2279          CFList factorsG=
2280          Union (multiFactorize (g, info),
2281                 multiFactorize (A/g, info));
2282          appendSwapDecompress (factorsG, contentAFactors, N, swapLevel, x);
2283          normalize (factorsG);
2284          delete [] bufAeval2;
2285          delete [] Aeval2;
2286          return factorsG;
2287        }
2288        fail= false;
2289        bufAeval= Aeval;
2290        bufA= A;
2291        bufEvaluation= evaluation;
2292      }
2293    }
2294    else if (fail && (i > 0))
2295      break;
2296
2297    bivarEval= bufEvaluation.getLast();
2298
2299    evaluationWRTDifferentSecondVars (bufAeval2, bufEvaluation, A);
2300
2301    for (int j= 0; j < A.level() - 2; j++)
2302    {
2303      if (!bufAeval2[j].isEmpty())
2304        counter++;
2305    }
2306
2307    bufLift= degree (A, y) + 1 + degree (LC(A, x), y);
2308
2309    TIMING_START (fac_bi_factorizer);
2310    if (!GF && alpha.level() == 1)
2311      bufBiFactors= FpBiSqrfFactorize (bufAeval.getFirst());
2312    else if (GF)
2313      bufBiFactors= GFBiSqrfFactorize (bufAeval.getFirst());
2314    else
2315      bufBiFactors= FqBiSqrfFactorize (bufAeval.getFirst(), alpha);
2316    TIMING_END_AND_PRINT (fac_bi_factorizer,
2317                          "time for bivariate factorization: ");
2318    bufBiFactors.removeFirst();
2319
2320    if (bufBiFactors.length() == 1)
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 [] bufAeval2;
2332      delete [] Aeval2;
2333      return factors;
2334    }
2335
2336    if (i == 0)
2337    {
2338      Aeval= bufAeval;
2339      evaluation= bufEvaluation;
2340      biFactors= bufBiFactors;
2341      lift= bufLift;
2342      for (int j= 0; j < A.level() - 2; j++)
2343        Aeval2 [j]= bufAeval2 [j];
2344      differentSecondVar= counter;
2345    }
2346    else
2347    {
2348      if (bufBiFactors.length() < biFactors.length() ||
2349          ((bufLift < lift) && (bufBiFactors.length() == biFactors.length())) ||
2350          counter > differentSecondVar)
2351      {
2352        Aeval= bufAeval;
2353        evaluation= bufEvaluation;
2354        biFactors= bufBiFactors;
2355        lift= bufLift;
2356        for (int j= 0; j < A.level() - 2; j++)
2357          Aeval2 [j]= bufAeval2 [j];
2358        differentSecondVar= counter;
2359      }
2360    }
2361    int k= 0;
2362    for (CFListIterator j= bufEvaluation; j.hasItem(); j++, k++)
2363      evalPoly += j.getItem()*power (x, k);
2364    list.append (evalPoly);
2365  }
2366
2367  delete [] bufAeval2;
2368
2369  sortList (biFactors, x);
2370
2371  int minFactorsLength;
2372  bool irred= false;
2373  factorizationWRTDifferentSecondVars (A, Aeval2, info, minFactorsLength, irred);
2374
2375  if (irred)
2376  {
2377    if (extension)
2378    {
2379      CFList source, dest;
2380      A= mapDown (A, info, source, dest);
2381    }
2382    factors.append (A);
2383    appendSwapDecompress (factors, contentAFactors, N, swapLevel,
2384                          swapLevel2, x);
2385    normalize (factors);
2386    delete [] Aeval2;
2387    return factors;
2388  }
2389
2390  if (minFactorsLength == 0)
2391    minFactorsLength= biFactors.length();
2392  else if (biFactors.length() > minFactorsLength)
2393    refineBiFactors (A, biFactors, Aeval2, evaluation, minFactorsLength);
2394  minFactorsLength= tmin (minFactorsLength, biFactors.length());
2395
2396  if (differentSecondVar == A.level() - 2)
2397  {
2398    bool zeroOccured= false;
2399    for (CFListIterator iter= evaluation; iter.hasItem(); iter++)
2400    {
2401      if (iter.getItem().isZero())
2402      {
2403        zeroOccured= true;
2404        break;
2405      }
2406    }
2407    if (!zeroOccured)
2408    {
2409      factors= sparseHeuristic (A, biFactors, Aeval2, evaluation, minFactorsLength);
2410      if (factors.length() == biFactors.length())
2411      {
2412        if (extension)
2413          factors= extNonMonicFactorRecombination (factors, A, info);
2414
2415        appendSwapDecompress (factors, contentAFactors, N, swapLevel,
2416                              swapLevel2, x);
2417        normalize (factors);
2418        delete [] Aeval2;
2419        return factors;
2420      }
2421      else
2422        factors= CFList();
2423      //TODO case where factors.length() > 0
2424    }
2425  }
2426
2427  CFList uniFactors= buildUniFactors (biFactors, evaluation.getLast(), y);
2428
2429  CFList * oldAeval= new CFList [A.level() - 2]; //TODO use bufAeval2 for this
2430  for (int i= 0; i < A.level() - 2; i++)
2431    oldAeval[i]= Aeval2[i];
2432
2433  getLeadingCoeffs (A, Aeval2, uniFactors, evaluation);
2434
2435  CFList biFactorsLCs;
2436  for (CFListIterator i= biFactors; i.hasItem(); i++)
2437    biFactorsLCs.append (LC (i.getItem(), 1));
2438
2439
2440  //shifting to zero
2441  A= shift2Zero (A, Aeval, evaluation);
2442
2443  CanonicalForm hh= Lc (Aeval.getFirst());
2444
2445  for (CFListIterator i= Aeval; i.hasItem(); i++)
2446    i.getItem() /= hh;
2447
2448  A /= hh;
2449
2450  Variable v;
2451  CFList leadingCoeffs= precomputeLeadingCoeff (LC (A, 1), biFactorsLCs, alpha,
2452                                          evaluation, Aeval2, A.level() - 2, v);
2453
2454  if (v.level() != 1)
2455  {
2456    A= swapvar (A, y, v);
2457    for (int i= 0; i < A.level() - 2; i++)
2458    {
2459      if (oldAeval[i].isEmpty())
2460        continue;
2461      if (oldAeval[i].getFirst().level() == v.level())
2462      {
2463        biFactors= CFList();
2464        for (CFListIterator iter= oldAeval [i]; iter.hasItem(); iter++)
2465          biFactors.append (swapvar (iter.getItem(), v, y));
2466      }
2467    }
2468    int i= A.level();
2469    CanonicalForm evalPoint;
2470    for (CFListIterator iter= evaluation; iter.hasItem(); iter++, i--)
2471    {
2472      if (i == v.level())
2473      {
2474        evalPoint= iter.getItem();
2475        iter.getItem()= evaluation.getLast();
2476        evaluation.removeLast();
2477        evaluation.append (evalPoint);
2478        break;
2479      }
2480    }
2481    Aeval= evaluateAtZero (A);
2482  }
2483
2484  CFListIterator iter= biFactors;
2485  for (; iter.hasItem(); iter++)
2486    iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
2487
2488  CanonicalForm oldA= A;
2489  CFList oldBiFactors= biFactors;
2490  if (!leadingCoeffs.getFirst().inCoeffDomain())
2491  {
2492    CanonicalForm tmp= power (leadingCoeffs.getFirst(), biFactors.length() - 1);
2493    A *= tmp;
2494    Aeval= evaluateAtZero (A);
2495    tmp= leadingCoeffs.getFirst();
2496    for (int i= A.level(); i > 2; i--)
2497      tmp= tmp (0, i);
2498    if (!tmp.inCoeffDomain())
2499    {
2500      for (CFListIterator i= biFactors; i.hasItem(); i++)
2501      {
2502        i.getItem() *= tmp/LC (i.getItem(), 1);
2503        i.getItem() /= Lc (i.getItem());
2504      }
2505    }
2506    hh= Lc (Aeval.getFirst());
2507    for (CFListIterator i= Aeval; i.hasItem(); i++)
2508      i.getItem() /= hh;
2509
2510    A /= hh;
2511  }
2512
2513  leadingCoeffs.removeFirst();
2514
2515  //prepare leading coefficients
2516  CFList* leadingCoeffs2= new CFList [A.level() - 2];
2517  prepareLeadingCoeffs (leadingCoeffs2, A.level(), leadingCoeffs, biFactors);
2518
2519  CFArray Pi;
2520  CFList diophant;
2521  int* liftBounds= new int [A.level() - 1];
2522  int liftBoundsLength= A.level() - 1;
2523  for (int i= 0; i < liftBoundsLength; i++)
2524    liftBounds [i]= degree (A, i + 2) + 1;
2525
2526  Aeval.removeFirst();
2527  bool noOneToOne= false;
2528  factors= nonMonicHenselLift (Aeval, biFactors, leadingCoeffs2, diophant,
2529                               Pi, liftBounds, liftBoundsLength, noOneToOne);
2530
2531
2532  if (!noOneToOne)
2533  {
2534    int check= factors.length();
2535    A= reverseShift (oldA, evaluation);
2536    factors= recoverFactors (A, factors, evaluation);
2537    if (check != factors.length())
2538      noOneToOne= true;
2539
2540    if (extension && !noOneToOne)
2541      factors= extNonMonicFactorRecombination (factors, A, info);
2542  }
2543  if (noOneToOne)
2544  {
2545    A= oldA;
2546    Aeval= evaluateAtZero (A);
2547    biFactors= oldBiFactors;
2548    CanonicalForm LCA= LC (Aeval.getFirst(), 1);
2549    CanonicalForm yToLift= power (y, lift);
2550    CFListIterator i= biFactors;
2551    lift= degree (i.getItem(), 2) + degree (LC (i.getItem(), 1)) + 1;
2552    i++;
2553
2554    for (; i.hasItem(); i++)
2555      lift= tmax (lift, degree (i.getItem(), 2) + degree (LC (i.getItem(), 1)) + 1);
2556
2557    lift= tmax (degree (Aeval.getFirst() , 2) + 1, lift);
2558
2559    i= biFactors;
2560    yToLift= power (y, lift);
2561    CanonicalForm dummy;
2562    for (; i.hasItem(); i++)
2563    {
2564      LCA= LC (i.getItem(), 1);
2565      extgcd (LCA, yToLift, LCA, dummy);
2566      i.getItem()= mod (i.getItem()*LCA, yToLift);
2567    }
2568
2569    liftBoundsLength= F.level() - 1;
2570    liftBounds= liftingBounds (A, lift);
2571
2572    CFList MOD;
2573    bool earlySuccess;
2574    CFList earlyFactors;
2575    TIMING_START (fac_hensel_lift);
2576    CFList liftedFactors= henselLiftAndEarly
2577                          (A, MOD, liftBounds, earlySuccess, earlyFactors,
2578                           Aeval, biFactors, evaluation, info);
2579    TIMING_END_AND_PRINT (fac_hensel_lift, "time for hensel lifting: ");
2580
2581    if (!extension)
2582    {
2583      TIMING_START (fac_factor_recombination);
2584      factors= factorRecombination (A, liftedFactors, MOD);
2585      TIMING_END_AND_PRINT (fac_factor_recombination,
2586                            "time for factor recombination: ");
2587    }
2588    else
2589    {
2590      TIMING_START (fac_factor_recombination);
2591      factors= extFactorRecombination (liftedFactors, A, MOD, info, evaluation);
2592      TIMING_END_AND_PRINT (fac_factor_recombination,
2593                            "time for factor recombination: ");
2594    }
2595
2596    if (earlySuccess)
2597      factors= Union (factors, earlyFactors);
2598    if (!extension)
2599    {
2600      for (CFListIterator i= factors; i.hasItem(); i++)
2601      {
2602        int kk= Aeval.getLast().level();
2603        for (CFListIterator j= evaluation; j.hasItem(); j++, kk--)
2604        {
2605          if (i.getItem().level() < kk)
2606            continue;
2607          i.getItem()= i.getItem() (Variable (kk) - j.getItem(), kk);
2608        }
2609      }
2610    }
2611  }
2612
2613
2614
2615  if (v.level() != 1)
2616  {
2617    for (CFListIterator iter= factors; iter.hasItem(); iter++)
2618      iter.getItem()= swapvar (iter.getItem(), v, y);
2619  }
2620
2621  swap (factors, swapLevel, swapLevel2, x);
2622  append (factors, contentAFactors);
2623  decompress (factors, N);
2624  normalize (factors);
2625
2626  delete[] liftBounds;
2627
2628  return factors;
2629}
2630
2631/// multivariate factorization over an extension of the initial field
2632CFList
2633extFactorize (const CanonicalForm& F, const ExtensionInfo& info)
2634{
2635  CanonicalForm A= F;
2636
2637  Variable alpha= info.getAlpha();
2638  Variable beta= info.getBeta();
2639  int k= info.getGFDegree();
2640  char cGFName= info.getGFName();
2641  CanonicalForm delta= info.getDelta();
2642  bool GF= (CFFactory::gettype() == GaloisFieldDomain);
2643  Variable w= Variable (1);
2644
2645  CFList factors;
2646  if (!GF && alpha == w)  // we are in F_p
2647  {
2648    CFList factors;
2649    bool extension= true;
2650    int p= getCharacteristic();
2651    if (p*p < (1<<16)) // pass to GF if possible
2652    {
2653      setCharacteristic (getCharacteristic(), 2, 'Z');
2654      ExtensionInfo info= ExtensionInfo (extension);
2655      A= A.mapinto();
2656      factors= multiFactorize (A, info);
2657
2658      Variable vBuf= rootOf (gf_mipo);
2659      setCharacteristic (getCharacteristic());
2660      for (CFListIterator j= factors; j.hasItem(); j++)
2661        j.getItem()= GF2FalphaRep (j.getItem(), vBuf);
2662    }
2663    else  // not able to pass to GF, pass to F_p(\alpha)
2664    {
2665      CanonicalForm mipo= randomIrredpoly (2, Variable (1));
2666      Variable v= rootOf (mipo);
2667      ExtensionInfo info= ExtensionInfo (v);
2668      factors= multiFactorize (A, info);
2669    }
2670    return factors;
2671  }
2672  else if (!GF && (alpha != w)) // we are in F_p(\alpha)
2673  {
2674    if (k == 1) // need factorization over F_p
2675    {
2676      int extDeg= degree (getMipo (alpha));
2677      extDeg++;
2678      CanonicalForm mipo= randomIrredpoly (extDeg + 1, Variable (1));
2679      Variable v= rootOf (mipo);
2680      ExtensionInfo info= ExtensionInfo (v);
2681      factors= biFactorize (A, info);
2682    }
2683    else
2684    {
2685      if (beta == Variable (1))
2686      {
2687        Variable v= chooseExtension (alpha, beta, k);
2688        CanonicalForm primElem, imPrimElem;
2689        bool primFail= false;
2690        Variable vBuf;
2691        primElem= primitiveElement (alpha, vBuf, primFail);
2692        ASSERT (!primFail, "failure in integer factorizer");
2693        if (primFail)
2694          ; //ERROR
2695        else
2696          imPrimElem= mapPrimElem (primElem, vBuf, v);
2697
2698        CFList source, dest;
2699        CanonicalForm bufA= mapUp (A, alpha, v, primElem, imPrimElem,
2700                                   source, dest);
2701        ExtensionInfo info= ExtensionInfo (v, alpha, imPrimElem, primElem);
2702        factors= biFactorize (bufA, info);
2703      }
2704      else
2705      {
2706        Variable v= chooseExtension (alpha, beta, k);
2707        CanonicalForm primElem, imPrimElem;
2708        bool primFail= false;
2709        Variable vBuf;
2710        ASSERT (!primFail, "failure in integer factorizer");
2711        if (primFail)
2712          ; //ERROR
2713        else
2714          imPrimElem= mapPrimElem (delta, beta, v);
2715
2716        CFList source, dest;
2717        CanonicalForm bufA= mapDown (A, info, source, dest);
2718        source= CFList();
2719        dest= CFList();
2720        bufA= mapUp (bufA, beta, v, delta, imPrimElem, source, dest);
2721        ExtensionInfo info= ExtensionInfo (v, beta, imPrimElem, delta);
2722        factors= biFactorize (bufA, info);
2723      }
2724    }
2725    return factors;
2726  }
2727  else // we are in GF (p^k)
2728  {
2729    int p= getCharacteristic();
2730    int extensionDeg= getGFDegree();
2731    bool extension= true;
2732    if (k == 1) // need factorization over F_p
2733    {
2734      extensionDeg++;
2735      if (pow ((double) p, (double) extensionDeg) < (1<<16))
2736      // pass to GF(p^k+1)
2737      {
2738        setCharacteristic (p);
2739        Variable vBuf= rootOf (gf_mipo);
2740        A= GF2FalphaRep (A, vBuf);
2741        setCharacteristic (p, extensionDeg, 'Z');
2742        ExtensionInfo info= ExtensionInfo (extension);
2743        factors= multiFactorize (A.mapinto(), info);
2744      }
2745      else // not able to pass to another GF, pass to F_p(\alpha)
2746      {
2747        setCharacteristic (p);
2748        Variable vBuf= rootOf (gf_mipo);
2749        A= GF2FalphaRep (A, vBuf);
2750        Variable v= chooseExtension (vBuf, beta, k);
2751        ExtensionInfo info= ExtensionInfo (v, extension);
2752        factors= multiFactorize (A, info);
2753      }
2754    }
2755    else // need factorization over GF (p^k)
2756    {
2757      if (pow ((double) p, (double) 2*extensionDeg) < (1<<16))
2758      // pass to GF(p^2k)
2759      {
2760        setCharacteristic (p, 2*extensionDeg, 'Z');
2761        ExtensionInfo info= ExtensionInfo (k, cGFName, extension);
2762        factors= multiFactorize (GFMapUp (A, extensionDeg), info);
2763        setCharacteristic (p, extensionDeg, cGFName);
2764      }
2765      else // not able to pass to GF (p^2k), pass to F_p (\alpha)
2766      {
2767        setCharacteristic (p);
2768        Variable v1= rootOf (gf_mipo);
2769        A= GF2FalphaRep (A, v1);
2770        Variable v2= chooseExtension (v1, v1, k);
2771        CanonicalForm primElem, imPrimElem;
2772        bool primFail= false;
2773        Variable vBuf;
2774        primElem= primitiveElement (v1, v1, primFail);
2775        if (primFail)
2776          ; //ERROR
2777        else
2778          imPrimElem= mapPrimElem (primElem, v1, v2);
2779        CFList source, dest;
2780        CanonicalForm bufA= mapUp (A, v1, v2, primElem, imPrimElem,
2781                                     source, dest);
2782        ExtensionInfo info= ExtensionInfo (v2, v1, imPrimElem, primElem);
2783        factors= multiFactorize (bufA, info);
2784        setCharacteristic (p, k, cGFName);
2785        for (CFListIterator i= factors; i.hasItem(); i++)
2786          i.getItem()= Falpha2GFRep (i.getItem());
2787      }
2788    }
2789    return factors;
2790  }
2791}
2792
2793#endif
2794/* HAVE_NTL */
2795
Note: See TracBrowser for help on using the repository browser.