source: git/factory/facFqFactorize.cc @ c770dc

spielwiese
Last change on this file since c770dc was e4fe2b, checked in by Oleksandr Motsak <motsak@…>, 13 years ago
FIX: Fixed huge BUG in cf_gmp.h CHG: starting to cleanup factory
  • Property mode set to 100644
File size: 70.9 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
34#ifdef HAVE_NTL
35#include <NTL/ZZ_pEX.h>
36#include "NTLconvert.h"
37
38TIMING_DEFINE_PRINT(fac_bi_factorizer)
39TIMING_DEFINE_PRINT(fac_hensel_lift)
40TIMING_DEFINE_PRINT(fac_factor_recombination)
41
42static inline
43CanonicalForm
44listGCD (const CFList& L);
45
46static inline
47CanonicalForm
48myContent (const CanonicalForm& F)
49{
50  CanonicalForm G= swapvar (F, F.mvar(), Variable (1));
51  CFList L;
52  for (CFIterator i= G; i.hasTerms(); i++)
53    L.append (i.coeff());
54  if (L.length() == 2)
55    return swapvar (gcd (L.getFirst(), L.getLast()), F.mvar(), Variable (1));
56  if (L.length() == 1)
57    return LC (F, Variable (1));
58  return swapvar (listGCD (L), F.mvar(), Variable (1));
59}
60
61static inline
62CanonicalForm
63listGCD (const CFList& L)
64{
65  if (L.length() == 1)
66    return L.getFirst();
67  if (L.length() == 2)
68    return gcd (L.getFirst(), L.getLast());
69  else
70  {
71    CFList lHi, lLo;
72    CanonicalForm resultHi, resultLo;
73    int length= L.length()/2;
74    int j= 0;
75    for (CFListIterator i= L; j < length; i++, j++)
76      lHi.append (i.getItem());
77    lLo= Difference (L, lHi);
78    resultHi= listGCD (lHi);
79    resultLo= listGCD (lLo);
80    if (resultHi.isOne() || resultLo.isOne())
81      return 1;
82    return gcd (resultHi, resultLo);
83  }
84}
85
86static inline
87CanonicalForm
88myContent (const CanonicalForm& F, const Variable& x)
89{
90  if (degree (F, x) <= 0)
91    return 1;
92  CanonicalForm G= F;
93  bool swap= false;
94  if (x != F.mvar())
95  {
96    swap= true;
97    G= swapvar (F, x, F.mvar());
98  }
99  CFList L;
100  Variable alpha;
101  for (CFIterator i= G; i.hasTerms(); i++)
102    L.append (i.coeff());
103  if (L.length() == 2)
104  {
105    if (swap)
106      return swapvar (gcd (L.getFirst(), L.getLast()), F.mvar(), x);
107    else
108      return gcd (L.getFirst(), L.getLast());
109  }
110  if (L.length() == 1)
111  {
112    return LC (F, x);
113  }
114  if (swap)
115    return swapvar (listGCD (L), F.mvar(), x);
116  else
117    return listGCD (L);
118}
119
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, quot;
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, quot))
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= quot;
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, quot;
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, quot))
375      {
376        recombination= true;
377        result.append (g);
378        buf= quot;
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, quot;
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, quot))
429    {
430      nBuf= degree (g, y) + degree (LC (g, 1), y);
431      d -= nBuf;
432      e= tmax (e, nBuf);
433      buf= quot;
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, quot;
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, quot))
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= quot;
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= quot;
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, quot;
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, quot))
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= quot;
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, quot;
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, quot))
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= quot;
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= quot;
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
867CanonicalForm lcmContent (const CanonicalForm& A, CFList& contentAi)
868{
869  int i= A.level();
870  contentAi.append (myContent (A, i));
871  contentAi.append (myContent (A, i - 1));
872  CanonicalForm result= lcm (contentAi.getFirst(), contentAi.getLast());
873  for (i= i - 2; i > 0; i--)
874  {
875    contentAi.append (content (A, i));
876    result= lcm (result, contentAi.getLast());
877  }
878  return result;
879}
880
881CFList
882henselLiftAndEarly (CanonicalForm& A, CFList& MOD, int*& liftBounds, bool&
883                    earlySuccess, CFList& earlyFactors, const CFList& Aeval,
884                    const CFList& biFactors, const CFList& evaluation,
885                    const ExtensionInfo& info)
886{
887  bool extension= info.isInExtension();
888  CFList bufFactors= biFactors;
889  bufFactors.insert (LC (Aeval.getFirst(), 1));
890
891  sortList (bufFactors, Variable (1));
892
893  CFList diophant;
894  CFArray Pi;
895  int smallFactorDeg= 11; //tunable parameter
896  CFList result;
897  int adaptedLiftBound= 0;
898  int liftBound= liftBounds[1];
899
900  earlySuccess= false;
901  CFList earlyReconstFactors;
902  CFListIterator j= Aeval;
903  j++;
904  CanonicalForm buf= j.getItem();
905  CFMatrix Mat= CFMatrix (liftBound, bufFactors.length() - 1);
906  MOD= CFList (power (Variable (2), liftBounds[0]));
907  if (smallFactorDeg >= liftBound)
908  {
909    result= henselLift23 (Aeval, bufFactors, liftBounds, diophant, Pi, Mat);
910  }
911  else if (smallFactorDeg >= degree (buf) + 1)
912  {
913    liftBounds[1]= degree (buf) + 1;
914    result= henselLift23 (Aeval, bufFactors, liftBounds, diophant, Pi, Mat);
915    if (Aeval.length() == 2)
916    {
917      if (!extension)
918        earlyFactors= earlyFactorDetect
919                       (buf, result, adaptedLiftBound, earlySuccess,
920                        degree (buf) + 1, MOD, liftBound);
921      else
922        earlyFactors= extEarlyFactorDetect
923                       (buf, result, adaptedLiftBound, earlySuccess,
924                        info, evaluation, degree
925                        (buf) + 1, MOD, liftBound);
926    }
927    else
928    {
929      if (!extension)
930        adaptedLiftBound= liftBoundAdaption (buf, result, earlySuccess,
931                                             degree (buf) + 1, MOD, liftBound);
932      else
933        adaptedLiftBound= extLiftBoundAdaption (buf, result, earlySuccess, info,
934                                                evaluation, degree (buf) + 1,
935                                                MOD, liftBound);
936    }
937    if (!earlySuccess)
938    {
939      result.insert (LC (buf, 1));
940      liftBounds[1]= adaptedLiftBound;
941      liftBound= adaptedLiftBound;
942      henselLiftResume (buf, result, degree (buf) + 1, liftBound,
943                        Pi, diophant, Mat, MOD);
944    }
945    else
946      liftBounds[1]= adaptedLiftBound;
947  }
948  else if (smallFactorDeg < degree (buf) + 1)
949  {
950    liftBounds[1]= smallFactorDeg;
951    result= henselLift23 (Aeval, bufFactors, liftBounds, diophant, Pi, Mat);
952    if (Aeval.length() == 2)
953    {
954      if (!extension)
955        earlyFactors= earlyFactorDetect (buf, result, adaptedLiftBound,
956                                         earlySuccess, smallFactorDeg, MOD,
957                                         liftBound);
958      else
959        earlyFactors= extEarlyFactorDetect (buf, result, adaptedLiftBound,
960                                            earlySuccess, info, evaluation,
961                                            smallFactorDeg, MOD, liftBound);
962    }
963    else
964    {
965      if (!extension)
966        adaptedLiftBound= liftBoundAdaption (buf, result, earlySuccess,
967                                             smallFactorDeg, MOD, liftBound);
968      else
969        adaptedLiftBound= extLiftBoundAdaption (buf, result, earlySuccess, info,
970                                                evaluation, smallFactorDeg, MOD,
971                                                liftBound);
972    }
973
974    if (!earlySuccess)
975    {
976      result.insert (LC (buf, 1));
977      henselLiftResume (buf, result, smallFactorDeg, degree (buf) + 1,
978                        Pi, diophant, Mat, MOD);
979      if (Aeval.length() == 2)
980      {
981         if (!extension)
982           earlyFactors= earlyFactorDetect (buf, result, adaptedLiftBound,
983                                            earlySuccess, degree (buf) + 1,
984                                            MOD, liftBound);
985         else
986           earlyFactors= extEarlyFactorDetect (buf, result, adaptedLiftBound,
987                                               earlySuccess, info, evaluation,
988                                               degree (buf) + 1, MOD,
989                                               liftBound);
990      }
991      else
992      {
993        if (!extension)
994          adaptedLiftBound= liftBoundAdaption (buf, result, earlySuccess,
995                                               degree (buf) + 1, MOD,liftBound);
996        else
997          adaptedLiftBound= extLiftBoundAdaption (buf, result, earlySuccess,
998                                                  info, evaluation,
999                                                  degree (buf) + 1, MOD,
1000                                                  liftBound);
1001      }
1002      if (!earlySuccess)
1003      {
1004        result.insert (LC (buf, 1));
1005        liftBounds[1]= adaptedLiftBound;
1006        liftBound= adaptedLiftBound;
1007        henselLiftResume (buf, result, degree (buf) + 1, liftBound,
1008                          Pi, diophant, Mat, MOD);
1009      }
1010      else
1011        liftBounds[1]= adaptedLiftBound;
1012    }
1013    else
1014      liftBounds[1]= adaptedLiftBound;
1015  }
1016
1017  MOD.append (power (Variable (3), liftBounds[1]));
1018
1019  if (Aeval.length() > 2)
1020  {
1021    CFListIterator j= Aeval;
1022    j++;
1023    CFList bufEval;
1024    bufEval.append (j.getItem());
1025    j++;
1026    int liftBoundsLength= Aeval.getLast().level() - 1;
1027    for (int i= 2; i <= liftBoundsLength && j.hasItem(); i++, j++)
1028    {
1029      earlySuccess= false;
1030      result.insert (LC (bufEval.getFirst(), 1));
1031      bufEval.append (j.getItem());
1032      liftBound= liftBounds[i];
1033      Mat= CFMatrix (liftBounds[i], result.length() - 1);
1034
1035      buf= j.getItem();
1036      if (smallFactorDeg >= liftBound)
1037        result= henselLift (bufEval, result, MOD, diophant, Pi, Mat,
1038                            liftBounds[i -  1], liftBounds[i]);
1039      else if (smallFactorDeg >= degree (buf) + 1)
1040      {
1041        result= henselLift (bufEval, result, MOD, diophant, Pi, Mat,
1042                            liftBounds[i -  1], degree (buf) + 1);
1043
1044        if (Aeval.length() == i + 1)
1045        {
1046          if (!extension)
1047            earlyFactors= earlyFactorDetect
1048                           (buf, result, adaptedLiftBound, earlySuccess,
1049                            degree (buf) + 1, MOD, liftBound);
1050          else
1051            earlyFactors= extEarlyFactorDetect
1052                           (buf, result, adaptedLiftBound, earlySuccess,
1053                            info, evaluation, degree (buf) + 1, MOD, liftBound);
1054        }
1055        else
1056        {
1057          if (!extension)
1058            adaptedLiftBound= liftBoundAdaption
1059                                (buf, result, earlySuccess, degree (buf)
1060                                 + 1,  MOD, liftBound);
1061          else
1062            adaptedLiftBound= extLiftBoundAdaption
1063                                (buf, result, earlySuccess, info, evaluation,
1064                                 degree (buf) + 1, MOD, liftBound);
1065        }
1066
1067        if (!earlySuccess)
1068        {
1069          result.insert (LC (buf, 1));
1070          liftBounds[i]= adaptedLiftBound;
1071          liftBound= adaptedLiftBound;
1072          henselLiftResume (buf, result, degree (buf) + 1, liftBound,
1073                            Pi, diophant, Mat, MOD);
1074        }
1075        else
1076        {
1077          liftBounds[i]= adaptedLiftBound;
1078        }
1079      }
1080      else if (smallFactorDeg < degree (buf) + 1)
1081      {
1082        result= henselLift (bufEval, result, MOD, diophant, Pi, Mat,
1083                            liftBounds[i -  1], smallFactorDeg);
1084
1085        if (Aeval.length() == i + 1)
1086        {
1087          if (!extension)
1088            earlyFactors= earlyFactorDetect
1089                           (buf, result, adaptedLiftBound, earlySuccess,
1090                            smallFactorDeg, MOD, liftBound);
1091          else
1092            earlyFactors= extEarlyFactorDetect
1093                           (buf, result, adaptedLiftBound, earlySuccess,
1094                            info, evaluation, smallFactorDeg, MOD, liftBound);
1095        }
1096        else
1097        {
1098          if (!extension)
1099            adaptedLiftBound= liftBoundAdaption
1100                                (buf, result, earlySuccess,
1101                                 smallFactorDeg, MOD, liftBound);
1102          else
1103            adaptedLiftBound= extLiftBoundAdaption
1104                                (buf, result, earlySuccess, info, evaluation,
1105                                 smallFactorDeg, MOD, liftBound);
1106        }
1107
1108        if (!earlySuccess)
1109        {
1110          result.insert (LC (buf, 1));
1111          henselLiftResume (buf, result, smallFactorDeg,
1112                            degree (buf) + 1, Pi, diophant, Mat, MOD);
1113          if (Aeval.length() == i + 1)
1114          {
1115            if (!extension)
1116              earlyFactors= earlyFactorDetect
1117                             (buf, result, adaptedLiftBound, earlySuccess,
1118                              degree (buf) +  1,  MOD, liftBound);
1119            else
1120              earlyFactors= extEarlyFactorDetect
1121                             (buf, result, adaptedLiftBound, earlySuccess,
1122                              info, evaluation, degree (buf) + 1, MOD,
1123                              liftBound);
1124          }
1125          else
1126          {
1127            if (!extension)
1128              adaptedLiftBound= liftBoundAdaption
1129                                  (buf, result, earlySuccess, degree
1130                                   (buf) +  1,  MOD, liftBound);
1131            else
1132              adaptedLiftBound= extLiftBoundAdaption
1133                                  (buf, result, earlySuccess, info, evaluation,
1134                                   degree (buf) + 1,  MOD, liftBound);
1135          }
1136
1137          if (!earlySuccess)
1138          {
1139            result.insert (LC (buf, 1));
1140            liftBounds[i]= adaptedLiftBound;
1141            liftBound= adaptedLiftBound;
1142            henselLiftResume (buf, result, degree (buf) + 1, liftBound,
1143                              Pi, diophant, Mat, MOD);
1144          }
1145          else
1146            liftBounds[i]= adaptedLiftBound;
1147        }
1148        else
1149          liftBounds[i]= adaptedLiftBound;
1150      }
1151      MOD.append (power (Variable (i + 2), liftBounds[i]));
1152      bufEval.removeFirst();
1153    }
1154    bufFactors= result;
1155  }
1156  else
1157    bufFactors= result;
1158
1159  if (earlySuccess)
1160    A= buf;
1161  return result;
1162}
1163
1164CFList
1165leadingCoeffReconstruction (const CanonicalForm& F, const CFList& factors,
1166                            const CFList& M)
1167{
1168  CanonicalForm quot, buf= F;
1169  CanonicalForm LCBuf= LC (buf, 1);
1170
1171  CFList result;
1172
1173  CanonicalForm tmp;
1174  for (CFListIterator i= factors; i.hasItem(); i++)
1175  {
1176    tmp= i.getItem();
1177    tmp= mulMod (tmp, LCBuf, M);
1178    tmp= tmp/content (tmp, 1);
1179    if (fdivides (tmp, buf, quot))
1180    {
1181      buf= quot;
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  CFFListIterator j;
1201  for (CFFListIterator i= factors1; (n < k && i.hasItem()); i++, n++)
1202  {
1203    m= 1;
1204    for (j= factors2; (m < l && j.hasItem()); j++, m++)
1205    {
1206      g= gcd (i.getItem().factor(), j.getItem().factor());
1207      if (degree (g) > 0)
1208      {
1209        j.getItem()= CFFactor (j.getItem().factor()/g, j.getItem().exp());
1210        i.getItem()= CFFactor (i.getItem().factor()/g, i.getItem().exp());
1211        factors1.append (CFFactor (g, i.getItem().exp()));
1212        factors2.append (CFFactor (g, j.getItem().exp()));
1213      }
1214    }
1215  }
1216}
1217
1218CFList
1219distributeContent (const CFList& L, const CFList* differentSecondVarFactors,
1220                   int length
1221                  )
1222{
1223  CFList l= L;
1224  CanonicalForm content= l.getFirst();
1225
1226  if (content.inCoeffDomain())
1227    return l;
1228
1229  if (l.length() == 1)
1230  {
1231    CFList result;
1232    for (int i= 0; i < length; i++)
1233    {
1234      if (differentSecondVarFactors[i].isEmpty())
1235        continue;
1236      if (result.isEmpty())
1237      {
1238        result= differentSecondVarFactors[i];
1239        for (CFListIterator iter= result; iter.hasItem(); iter++)
1240          content /= iter.getItem();
1241      }
1242      else
1243      {
1244        CFListIterator iter1= result;
1245        for (CFListIterator iter2= differentSecondVarFactors[i]; iter2.hasItem();
1246             iter2++, iter1++)
1247        {
1248          iter1.getItem() *= iter2.getItem();
1249          content /= iter2.getItem();
1250        }
1251      }
1252    }
1253    result.insert (content);
1254    return result;
1255  }
1256
1257  Variable v;
1258  CFListIterator iter1;
1259  CanonicalForm tmp, g;
1260  for (int i= 0; i < length; i++)
1261  {
1262    if (differentSecondVarFactors[i].isEmpty())
1263      continue;
1264    iter1= l;
1265    iter1++;
1266
1267    v= Variable (i + 3);
1268    for (CFListIterator iter2= differentSecondVarFactors[i]; iter2.hasItem();
1269         iter2++, iter1++)
1270    {
1271      if (degree (iter2.getItem(),v) == degree (iter1.getItem(),v))
1272        continue;
1273      tmp= iter1.getItem();
1274      for (int j= tmp.level(); j > 1; j--)
1275      {
1276        if (j == i + 3)
1277          continue;
1278        tmp= tmp (0, j);
1279      }
1280      g= gcd (iter2.getItem(), content);
1281      if (degree (g) > 0)
1282      {
1283        iter2.getItem() /= tmp;
1284        content /= g;
1285        iter1.getItem() *= g;
1286      }
1287    }
1288  }
1289
1290  l.removeFirst();
1291  l.insert (content);
1292  return l;
1293}
1294
1295CFList evaluateAtZero (const CanonicalForm& F)
1296{
1297  CFList result;
1298  CanonicalForm buf= F;
1299  result.insert (buf);
1300  for (int i= F.level(); i > 2; i--)
1301  {
1302    buf= buf (0, i);
1303    result.insert (buf);
1304  }
1305  return result;
1306}
1307
1308int
1309testFactors (const CanonicalForm& G, const CFList& uniFactors,
1310             const Variable& alpha, CanonicalForm& sqrfPartF, CFList& factors,
1311             CFFList*& bufSqrfFactors, CFList& evalSqrfPartF)
1312{
1313  CanonicalForm tmp;
1314  CFListIterator j;
1315  for (CFListIterator i= uniFactors; i.hasItem(); i++)
1316  {
1317    tmp= i.getItem();
1318    if (i.hasItem())
1319      i++;
1320    else
1321      break;
1322    for (j= i; j.hasItem(); j++)
1323    {
1324      if (tmp == j.getItem())
1325        return 0;
1326    }
1327  }
1328
1329  CanonicalForm F= G;
1330  CFFList sqrfFactorization= squarefreeFactorization (F, alpha);
1331
1332  sqrfPartF= 1;
1333  for (CFFListIterator i= sqrfFactorization; i.hasItem(); i++)
1334    sqrfPartF *= i.getItem().factor();
1335
1336  evalSqrfPartF= evaluateAtZero (sqrfPartF);
1337
1338  CanonicalForm test= evalSqrfPartF.getFirst() (0, 2);
1339
1340  if (degree (test) != degree (sqrfPartF, 1))
1341    return 0;
1342
1343  CFFList sqrfFactors;
1344  CFList tmp2;
1345  int k= 0;
1346  factors= uniFactors;
1347  CFFListIterator iter;
1348  for (CFListIterator i= factors; i.hasItem(); i++, k++)
1349  {
1350    tmp= 1;
1351    sqrfFactors= squarefreeFactorization (i.getItem(), alpha);
1352
1353    for (iter= sqrfFactors; iter.hasItem(); iter++)
1354    {
1355      tmp2.append (iter.getItem().factor());
1356      tmp *= iter.getItem().factor();
1357    }
1358    i.getItem()= tmp/Lc(tmp);
1359    bufSqrfFactors [k]= sqrfFactors;
1360  }
1361
1362  for (int i= 0; i < factors.length() - 1; i++)
1363  {
1364    for (k= i + 1; k < factors.length(); k++)
1365    {
1366      gcdFreeBasis (bufSqrfFactors [i], bufSqrfFactors[k]);
1367    }
1368  }
1369
1370  factors= CFList();
1371  for (int i= 0; i < uniFactors.length(); i++)
1372  {
1373    if (i == 0)
1374    {
1375      for (iter= bufSqrfFactors [i]; iter.hasItem(); iter++)
1376      {
1377        if (iter.getItem().factor().inCoeffDomain())
1378          continue;
1379        iter.getItem()= CFFactor (iter.getItem().factor()/
1380                                  Lc (iter.getItem().factor()),
1381                                  iter.getItem().exp());
1382        factors.append (iter.getItem().factor());
1383      }
1384    }
1385    else
1386    {
1387      for (iter= bufSqrfFactors [i]; iter.hasItem(); iter++)
1388      {
1389        if (iter.getItem().factor().inCoeffDomain())
1390          continue;
1391        iter.getItem()= CFFactor (iter.getItem().factor()/
1392                                  Lc (iter.getItem().factor()),
1393                                  iter.getItem().exp());
1394        if (!find (factors, iter.getItem().factor()))
1395          factors.append (iter.getItem().factor());
1396      }
1397    }
1398  }
1399
1400  test= prod (factors);
1401  tmp= evalSqrfPartF.getFirst() (0,2);
1402  if (test/Lc (test) != tmp/Lc (tmp))
1403    return 0;
1404  else
1405    return 1;
1406}
1407
1408CFList
1409precomputeLeadingCoeff (const CanonicalForm& LCF, const CFList& LCFFactors,
1410                        const Variable& alpha, const CFList& evaluation,
1411                        CFList* & differentSecondVarLCs, int length,
1412                        Variable& y
1413                       )
1414{
1415  y= Variable (1);
1416  if (LCF.inCoeffDomain())
1417  {
1418    CFList result;
1419    for (int i= 1; i <= LCFFactors.length() + 1; i++)
1420      result.append (1);
1421    return result;
1422  }
1423
1424  CFMap N;
1425  CanonicalForm F= compress (LCF, N);
1426  if (LCF.isUnivariate())
1427  {
1428    CFList result;
1429    int LCFLevel= LCF.level();
1430    bool found= false;
1431    if (LCFLevel == 2)
1432    {
1433    //bivariate leading coefficients are already the true leading coefficients
1434      result= LCFFactors;
1435      Variable v= Variable (LCF.mvar());
1436      CanonicalForm bla= 1;
1437      for (CFListIterator i= result; i.hasItem(); i++)
1438      {
1439        i.getItem()= i.getItem() (v+evaluation.getLast(), v);
1440        bla *= Lc (i.getItem());
1441      }
1442      found= true;
1443    }
1444    else
1445    {
1446      CFListIterator j;
1447      for (int i= 0; i < length; i++)
1448      {
1449        for (j= differentSecondVarLCs[i]; j.hasItem(); j++)
1450        {
1451          if (j.getItem().level() == LCFLevel)
1452          {
1453            found= true;
1454            break;
1455          }
1456        }
1457        if (found)
1458        {
1459          result= differentSecondVarLCs [i];
1460          break;
1461        }
1462      }
1463      if (!found)
1464        result= LCFFactors;
1465    }
1466    if (found)
1467      result.insert (Lc (LCF));
1468    else
1469      result.append (LCF);
1470    return result;
1471  }
1472
1473  CFList factors= LCFFactors;
1474
1475  CFMap dummy;
1476  for (CFListIterator i= factors; i.hasItem(); i++)
1477  {
1478    i.getItem()= compress (i.getItem(), dummy);
1479    i.getItem()= i.getItem() (Variable (1) + evaluation.getLast(), Variable (1));
1480  }
1481
1482  CanonicalForm sqrfPartF;
1483  CFFList * bufSqrfFactors= new CFFList [factors.length()];
1484  CFList evalSqrfPartF;
1485  CFList bufFactors;
1486  int pass= testFactors (F, factors, alpha, sqrfPartF,
1487                         bufFactors, bufSqrfFactors, evalSqrfPartF);
1488
1489  bool foundDifferent= false;
1490  Variable z;
1491  Variable x= y;
1492  int j= 0;
1493  if (!pass)
1494  {
1495    int lev;
1496    // LCF is non-constant here
1497    for (int i= 1; i <= LCF.level(); i++)
1498    {
1499      if(degree (LCF, i) > 0)
1500      {
1501        lev= i - 1;
1502        break;
1503      }
1504    }
1505    CFListIterator iter;
1506    CFList bufBufFactors;
1507    CanonicalForm bufF;
1508    for (int i= 0; i < length; i++)
1509    {
1510      if (!differentSecondVarLCs [i].isEmpty())
1511      {
1512        bool allConstant= true;
1513        for (iter= differentSecondVarLCs[i]; iter.hasItem(); iter++)
1514        {
1515          if (!iter.getItem().inCoeffDomain())
1516          {
1517            allConstant= false;
1518            y= Variable (iter.getItem().level());
1519          }
1520        }
1521        if (allConstant)
1522          continue;
1523
1524        bufFactors= differentSecondVarLCs [i];
1525        for (iter= bufFactors; iter.hasItem(); iter++)
1526          iter.getItem()= swapvar (iter.getItem(), x, y);
1527        bufF= F;
1528        z= Variable (y.level() - lev);
1529        bufF= swapvar (bufF, x, z);
1530        bufBufFactors= bufFactors;
1531        pass= testFactors (bufF, bufBufFactors, alpha, sqrfPartF, bufFactors,
1532                           bufSqrfFactors, evalSqrfPartF);
1533        if (pass)
1534        {
1535          foundDifferent= true;
1536          F= bufF;
1537          CFList l= factors;
1538          for (iter= l; iter.hasItem(); iter++)
1539            iter.getItem()= swapvar (iter.getItem(), x, y);
1540          differentSecondVarLCs [i]= l;
1541          j= i;
1542          break;
1543        }
1544        if (!pass && i == length - 1)
1545        {
1546          CFList result;
1547          result.append (LCF);
1548          for (int k= 1; k <= factors.length(); k++)
1549            result.append (LCF);
1550          y= Variable (1);
1551          delete [] bufSqrfFactors;
1552          return result;
1553        }
1554      }
1555    }
1556  }
1557  if (!pass)
1558  {
1559    CFList result;
1560    result.append (LCF);
1561    for (int k= 1; k <= factors.length(); k++)
1562      result.append (LCF);
1563    y= Variable (1);
1564    delete [] bufSqrfFactors;
1565    return result;
1566  }
1567  else
1568    factors= bufFactors;
1569
1570  bufFactors= factors;
1571
1572  if (factors.length() > 1)
1573  {
1574    CanonicalForm LC1= LC (evalSqrfPartF.getFirst(), 1);
1575
1576    CFArray leadingCoeffs= CFArray (factors.length());
1577    for (int i= 0; i < factors.length(); i++)
1578      leadingCoeffs[i]= LC1;
1579    for (CFListIterator i= factors; i.hasItem(); i++)
1580      i.getItem() *= LC1 (0,2)/Lc (i.getItem());
1581    factors.insert (1);
1582
1583    CanonicalForm
1584    newSqrfPartF= evalSqrfPartF.getFirst()*power (LC1, factors.length() - 2);
1585
1586    int liftBound= degree (newSqrfPartF,2) + 1;
1587
1588    CFMatrix M= CFMatrix (liftBound, factors.length() - 1);
1589    CFArray Pi;
1590    CFList diophant;
1591    henselLift122 (newSqrfPartF, factors, liftBound, Pi, diophant, M,
1592                   leadingCoeffs, false);
1593
1594    if (sqrfPartF.level() > 2)
1595    {
1596      int* liftBounds= new int [sqrfPartF.level() - 1];
1597      liftBounds [0]= liftBound;
1598      bool noOneToOne= false;
1599      CFList *leadingCoeffs2= new CFList [sqrfPartF.level()-2];
1600      LC1= LC (evalSqrfPartF.getLast(), 1);
1601      CFList LCs;
1602      for (int i= 0; i < factors.length(); i++)
1603        LCs.append (LC1);
1604      leadingCoeffs2 [sqrfPartF.level() - 3]= LCs;
1605      for (int i= sqrfPartF.level() - 1; i > 2; i--)
1606      {
1607        for (CFListIterator j= LCs; j.hasItem(); j++)
1608          j.getItem()= j.getItem() (0, i + 1);
1609        leadingCoeffs2 [i - 3]= LCs;
1610      }
1611      sqrfPartF= sqrfPartF*power (LC1, factors.length()-1);
1612
1613      int liftBoundsLength= sqrfPartF.level() - 1;
1614      for (int i= 1; i < liftBoundsLength; i++)
1615        liftBounds [i]= degree (sqrfPartF, i + 2) + 1;
1616      evalSqrfPartF= evaluateAtZero (sqrfPartF);
1617      evalSqrfPartF.removeFirst();
1618      factors= nonMonicHenselLift (evalSqrfPartF, factors, leadingCoeffs2,
1619               diophant, Pi, liftBounds, sqrfPartF.level() - 1, noOneToOne);
1620      delete [] leadingCoeffs2;
1621      delete [] liftBounds;
1622    }
1623  }
1624  else
1625    factors= evalSqrfPartF.getLast();
1626
1627  CFList interMedResult= recoverFactors (evalSqrfPartF.getLast(), factors);
1628
1629  CFList result;
1630  CFFListIterator k;
1631  for (int i= 0; i < LCFFactors.length(); i++)
1632  {
1633    CanonicalForm tmp= 1;
1634    for (k= bufSqrfFactors[i]; k.hasItem(); k++)
1635    {
1636      int pos= findItem (bufFactors, k.getItem().factor());
1637      if (pos)
1638        tmp *= power (getItem (interMedResult, pos), k.getItem().exp());
1639    }
1640    result.append (tmp);
1641  }
1642
1643  for (CFListIterator i= result; i.hasItem(); i++)
1644  {
1645    F /= i.getItem();
1646    if (foundDifferent)
1647      i.getItem()= swapvar (i.getItem(), x, z);
1648    i.getItem()= N (i.getItem());
1649  }
1650
1651  if (foundDifferent)
1652  {
1653    CFList l= differentSecondVarLCs [j];
1654    for (CFListIterator i= l; i.hasItem(); i++)
1655      i.getItem()= swapvar (i.getItem(), y, z);
1656    differentSecondVarLCs [j]= l;
1657    F= swapvar (F, x, z);
1658  }
1659
1660  result.insert (N (F));
1661
1662  result= distributeContent (result, differentSecondVarLCs, length);
1663
1664  if (!result.getFirst().inCoeffDomain())
1665  {
1666    CFListIterator i= result;
1667    CanonicalForm tmp;
1668    if (foundDifferent)
1669      i.getItem()= swapvar (i.getItem(), Variable (2), y);
1670
1671    tmp= i.getItem();
1672
1673    i++;
1674    for (; i.hasItem(); i++)
1675    {
1676      if (foundDifferent)
1677        i.getItem()= swapvar (i.getItem(), Variable (2), y)*tmp;
1678      else
1679        i.getItem() *= tmp;
1680    }
1681  }
1682  else
1683    y= Variable (1);
1684
1685  delete [] bufSqrfFactors;
1686
1687  return result;
1688}
1689
1690void
1691evaluationWRTDifferentSecondVars (CFList*& Aeval, const CFList& evaluation,
1692                                  const CanonicalForm& A)
1693{
1694  CanonicalForm tmp;
1695  CFList tmp2;
1696  CFListIterator iter;
1697  for (int i= A.level(); i > 2; i--)
1698  {
1699    tmp= A;
1700    tmp2= CFList();
1701    iter= evaluation;
1702    bool preserveDegree= true;
1703    for (int j= A.level(); j > 1; j--, iter++)
1704    {
1705      if (j == i)
1706        continue;
1707      else
1708      {
1709        tmp= tmp (iter.getItem(), j);
1710        tmp2.insert (tmp);
1711        if ((degree (tmp, i) != degree (A, i)) ||
1712            (degree (tmp, 1) != degree (A, 1)))
1713        {
1714          preserveDegree= false;
1715          break;
1716        }
1717        if (!content(tmp).inCoeffDomain() || !content(tmp,1).inCoeffDomain())
1718        {
1719          preserveDegree= false;
1720          break;
1721        }
1722      }
1723    }
1724    if (preserveDegree)
1725      Aeval [i - 3]= tmp2;
1726    else
1727      Aeval [i - 3]= CFList();
1728  }
1729}
1730
1731static inline
1732CanonicalForm prodEval (const CFList& l, const CanonicalForm& evalPoint,
1733                        const Variable& v)
1734{
1735  CanonicalForm result= 1;
1736  for (CFListIterator i= l; i.hasItem(); i++)
1737    result *= i.getItem() (evalPoint, v);
1738  return result;
1739}
1740
1741//recombine bivariate factors in case one bivariate factorization yields less
1742// factors than the other
1743CFList
1744recombination (const CFList& factors1, const CFList& factors2, int s, int thres,
1745               const CanonicalForm& evalPoint, const Variable& x)
1746{
1747  CFList T, S;
1748
1749  T= factors1;
1750  CFList result;
1751  CanonicalForm buf;
1752  int * v= new int [T.length()];
1753  for (int i= 0; i < T.length(); i++)
1754    v[i]= 0;
1755  bool nosubset= false;
1756  CFArray TT;
1757  TT= copy (factors1);
1758  while (T.length() >= 2*s && s <= thres)
1759  {
1760    while (nosubset == false) 
1761    {
1762      if (T.length() == s) 
1763      {
1764        delete [] v;
1765        result.append (prod (T));
1766        return result;
1767      }
1768      S= subset (v, s, TT, nosubset);
1769      if (nosubset) break;
1770      buf= prodEval (S, evalPoint, x);
1771      buf /= Lc (buf);
1772      if (find (factors2, buf))
1773      {
1774        T= Difference (T, S);
1775        result.append (prod (S));
1776        TT= copy (T);
1777        indexUpdate (v, s, T.length(), nosubset);
1778        if (nosubset) break;
1779      }
1780    }
1781    s++;
1782    if (T.length() < 2*s || T.length() == s) 
1783    {
1784      delete [] v;
1785      result.append (prod (T));
1786      return result;
1787    }
1788    for (int i= 0; i < T.length(); i++)
1789      v[i]= 0;
1790    nosubset= false;
1791  }
1792
1793  delete [] v;
1794  if (T.length() < 2*s)
1795  {
1796    result.append (prod (T));
1797    return result;
1798  }
1799
1800  return result;
1801}
1802
1803void
1804factorizationWRTDifferentSecondVars (const CanonicalForm& A, CFList*& Aeval,
1805                                     const ExtensionInfo& info,
1806                                     int& minFactorsLength, bool& irred)
1807{
1808  Variable x= Variable (1);
1809  minFactorsLength= 0;
1810  irred= false;
1811  CFList factors;
1812  Variable v;
1813  for (int j= 0; j < A.level() - 2; j++)
1814  {
1815    if (!Aeval[j].isEmpty())
1816    {
1817      v= Variable (Aeval[j].getFirst().level());
1818      if (CFFactory::gettype() == GaloisFieldDomain)
1819        factors= GFBiSqrfFactorize (Aeval[j].getFirst());
1820      else if (info.getAlpha().level() == 1)
1821        factors= FpBiSqrfFactorize (Aeval[j].getFirst());
1822      else
1823        factors= FqBiSqrfFactorize (Aeval[j].getFirst(), info.getAlpha());
1824
1825      factors.removeFirst();
1826      if (minFactorsLength == 0)
1827        minFactorsLength= factors.length();
1828      else
1829        minFactorsLength= tmin (minFactorsLength, factors.length());
1830
1831      if (factors.length() == 1)
1832      {
1833        irred= true;
1834        return;
1835      }
1836      sortList (factors, x);
1837      Aeval [j]= factors;
1838    }
1839  }
1840}
1841
1842void getLeadingCoeffs (const CanonicalForm& A, CFList*& Aeval,
1843                       const CFList& uniFactors, const CFList& evaluation
1844                      )
1845{
1846  CanonicalForm evalPoint;
1847  int i;
1848  CFListIterator iter, iter2;
1849  Variable v;
1850  CFList l, LCs;
1851  CanonicalForm buf;
1852  for (int j= 0; j < A.level() - 2; j++)
1853  {
1854    if (!Aeval[j].isEmpty())
1855    {
1856      i= A.level();
1857      for (iter= evaluation; iter.hasItem(); iter++, i--)
1858      {
1859        if (i == Aeval[j].getFirst().level())
1860        {
1861          evalPoint= iter.getItem();
1862          break;
1863        }
1864      }
1865
1866      v= Variable (i);
1867      if (Aeval[j].length() > uniFactors.length())
1868        Aeval[j]= recombination (Aeval[j], uniFactors, 1,
1869                                 Aeval[j].length() - uniFactors.length() + 1,
1870                                 evalPoint, v);
1871
1872      l= CFList();
1873      for (iter= uniFactors; iter.hasItem(); iter++)
1874      {
1875        for (iter2= Aeval[j]; iter2.hasItem(); iter2++)
1876        {
1877          buf= mod (iter2.getItem(), v - evalPoint);
1878          buf /= Lc (buf);
1879          if (iter.getItem() == buf)
1880          {
1881            l.append (iter2.getItem());
1882            break;
1883          }
1884        }
1885      }
1886      Aeval [j]= l;
1887
1888      LCs= CFList();
1889      for (iter= Aeval[j]; iter.hasItem(); iter++)
1890        LCs.append (LC (iter.getItem() (v + evalPoint, v), 1));
1891      normalize (LCs);
1892      Aeval[j]= LCs;
1893    }
1894  }
1895}
1896
1897CFList
1898buildUniFactors (const CFList& biFactors, const CanonicalForm& evalPoint,
1899                 const Variable& y)
1900{
1901  CFList result;
1902  CanonicalForm tmp;
1903  for (CFListIterator i= biFactors; i.hasItem(); i++)
1904  {
1905    tmp= mod (i.getItem(), y - evalPoint);
1906    tmp /= Lc (tmp);
1907    result.append (tmp);
1908  }
1909  return result;
1910}
1911
1912void refineBiFactors (const CanonicalForm& A, CFList& biFactors,
1913                      CFList* const& Aeval, const CFList& evaluation,
1914                      int minFactorsLength)
1915{
1916  CFListIterator iter;
1917  CanonicalForm evalPoint;
1918  int i;
1919  Variable v;
1920  Variable y= Variable (2);
1921  CFList list;
1922  for (int j= 0; j < A.level() - 2; j++)
1923  {
1924    if (Aeval[j].length() == minFactorsLength)
1925    {
1926      i= A.level();
1927
1928      for (iter= evaluation; iter.hasItem(); iter++, i--)
1929      {
1930        if (i == Aeval[j].getFirst().level())
1931        {
1932          evalPoint= iter.getItem();
1933          break;
1934        }
1935      }
1936
1937      v= Variable (i);
1938      list= buildUniFactors (Aeval[j], evalPoint, v);
1939
1940      biFactors= recombination (biFactors, list, 1,
1941                                biFactors.length() - list.length() + 1,
1942                                evaluation.getLast(), y);
1943      return;
1944    }
1945  }
1946}
1947
1948void prepareLeadingCoeffs (CFList*& LCs, int n, const CFList& leadingCoeffs,
1949                           const CFList& biFactors)
1950{
1951  CFList l= leadingCoeffs;
1952  LCs [n-3]= l;
1953  CFListIterator j;
1954  for (int i= n - 1; i > 2; i--)
1955  {
1956    for (j= l; j.hasItem(); j++)
1957      j.getItem()= j.getItem() (0, i + 1);
1958    LCs [i - 3]= l;
1959  }
1960  l= LCs [0];
1961  for (CFListIterator i= l; i.hasItem(); i++)
1962    i.getItem()= i.getItem() (0, 3);
1963  CFListIterator ii= biFactors;
1964  CFList normalizeFactor;
1965  for (CFListIterator i= l; i.hasItem(); i++, ii++)
1966    normalizeFactor.append (Lc (LC (ii.getItem(), 1))/Lc (i.getItem()));
1967  for (int i= 0; i < n-2; i++)
1968  {
1969    ii= normalizeFactor;
1970    for (j= LCs [i]; j.hasItem(); j++, ii++)
1971      j.getItem() *= ii.getItem();
1972  }
1973}
1974
1975CFList recoverFactors (const CanonicalForm& F, const CFList& factors)
1976{
1977  CFList result;
1978  CanonicalForm tmp, tmp2;
1979  CanonicalForm G= F;
1980  for (CFListIterator i= factors; i.hasItem(); i++)
1981  {
1982    tmp= i.getItem()/content (i.getItem(), 1);
1983    if (fdivides (tmp, G, tmp2))
1984    {
1985      G= tmp2;
1986      result.append (tmp);
1987    }
1988  }
1989  return result;
1990}
1991
1992CFList recoverFactors (const CanonicalForm& F, const CFList& factors,
1993                       const CFList& evaluation)
1994{
1995  CFList result;
1996  CanonicalForm tmp, tmp2;
1997  CanonicalForm G= F;
1998  for (CFListIterator i= factors; i.hasItem(); i++)
1999  {
2000    tmp= reverseShift (i.getItem(), evaluation);
2001    tmp /= content (tmp, 1);
2002    if (fdivides (tmp, G, tmp2))
2003    {
2004      G= tmp2;
2005      result.append (tmp);
2006    }
2007  }
2008  return result;
2009}
2010
2011CFList
2012extNonMonicFactorRecombination (const CFList& factors, const CanonicalForm& F,
2013                                const ExtensionInfo& info)
2014{
2015  Variable alpha= info.getAlpha();
2016  Variable beta= info.getBeta();
2017  CanonicalForm gamma= info.getGamma();
2018  CanonicalForm delta= info.getDelta();
2019  int k= info.getGFDegree();
2020  CFList source, dest;
2021
2022  int degMipoBeta= 1;
2023  if (!k && beta != Variable(1))
2024    degMipoBeta= degree (getMipo (beta));
2025
2026  CFList T, S;
2027  T= factors;
2028  int s= 1;
2029  CFList result;
2030  CanonicalForm quot, buf= F;
2031
2032  CanonicalForm g;
2033  CanonicalForm buf2;
2034  int * v= new int [T.length()];
2035  for (int i= 0; i < T.length(); i++)
2036    v[i]= 0;
2037  bool noSubset= false;
2038  CFArray TT;
2039  TT= copy (factors);
2040  bool recombination= false;
2041  bool trueFactor= false;
2042  while (T.length() >= 2*s)
2043  {
2044    while (noSubset == false)
2045    {
2046      if (T.length() == s)
2047      {
2048        delete [] v;
2049        if (recombination)
2050        {
2051          g= prod (T);
2052          T.removeFirst();
2053          result.append (g/myContent (g));
2054          g /= Lc (g);
2055          appendTestMapDown (result, g, info, source, dest);
2056          return result;
2057        }
2058        else
2059          return CFList (buf);
2060      }
2061
2062      S= subset (v, s, TT, noSubset);
2063      if (noSubset) break;
2064
2065      g= prod (S);
2066      g /= myContent (g);
2067      if (fdivides (g, buf, quot))
2068      {
2069        buf2= g;
2070        buf2 /= Lc (buf2);
2071        if (!k && beta == Variable (1))
2072        {
2073          if (degree (buf2, alpha) < degMipoBeta)
2074          {
2075            appendTestMapDown (result, buf2, info, source, dest);
2076            buf= quot;
2077            recombination= true;
2078            trueFactor= true;
2079          }
2080        }
2081        else
2082        {
2083          if (!isInExtension (buf2, gamma, k, delta, source, dest))
2084          {
2085            appendTestMapDown (result, buf2, info, source, dest);
2086            buf= quot;
2087            recombination= true;
2088            trueFactor= true;
2089          }
2090        }
2091        if (trueFactor)
2092        {
2093          T= Difference (T, S);
2094
2095          if (T.length() < 2*s || T.length() == s)
2096          {
2097            delete [] v;
2098            buf /= Lc (buf);
2099            appendTestMapDown (result, buf, info, source, dest);
2100            return result;
2101          }
2102          trueFactor= false;
2103          TT= copy (T);
2104          indexUpdate (v, s, T.length(), noSubset);
2105          if (noSubset) break;
2106        }
2107      }
2108    }
2109    s++;
2110    if (T.length() < 2*s || T.length() == s)
2111    {
2112      delete [] v;
2113      appendTestMapDown (result, buf, info, source, dest);
2114      return result;
2115    }
2116    for (int i= 0; i < T.length(); i++)
2117      v[i]= 0;
2118    noSubset= false;
2119  }
2120  if (T.length() < 2*s)
2121    appendMapDown (result, F, info, source, dest);
2122
2123  delete [] v;
2124  return result;
2125}
2126
2127CFList
2128extFactorize (const CanonicalForm& F, const ExtensionInfo& info);
2129
2130CFList
2131multiFactorize (const CanonicalForm& F, const ExtensionInfo& info)
2132{
2133
2134  if (F.inCoeffDomain())
2135    return CFList (F);
2136
2137  // compress and find main Variable
2138  CFMap N;
2139  CanonicalForm A= myCompress (F, N);
2140
2141  A /= Lc (A); // make monic
2142
2143  Variable alpha= info.getAlpha();
2144  Variable beta= info.getBeta();
2145  CanonicalForm gamma= info.getGamma();
2146  CanonicalForm delta= info.getDelta();
2147  bool extension= info.isInExtension();
2148  bool GF= (CFFactory::gettype() == GaloisFieldDomain);
2149  //univariate case
2150  if (F.isUnivariate())
2151  {
2152    if (extension == false)
2153      return uniFactorizer (F, alpha, GF);
2154    else
2155    {
2156      CFList source, dest;
2157      A= mapDown (F, info, source, dest);
2158      return uniFactorizer (A, beta, GF);
2159    }
2160  }
2161
2162  //bivariate case
2163  if (A.level() == 2)
2164  {
2165    CFList buf= biFactorize (F, info);
2166    return buf;
2167  }
2168
2169  Variable x= Variable (1);
2170  Variable y= Variable (2);
2171
2172  // remove content
2173  CFList contentAi;
2174  CanonicalForm lcmCont= lcmContent (A, contentAi);
2175  A /= lcmCont;
2176
2177  // trivial after content removal
2178  CFList contentAFactors;
2179  if (A.inCoeffDomain())
2180  {
2181    for (CFListIterator i= contentAi; i.hasItem(); i++)
2182    {
2183      if (i.getItem().inCoeffDomain())
2184        continue;
2185      else
2186      {
2187        lcmCont /= i.getItem();
2188        contentAFactors=
2189        Union (multiFactorize (lcmCont, info),
2190               multiFactorize (i.getItem(), info));
2191        break;
2192      }
2193    }
2194    decompress (contentAFactors, N);
2195    normalize (contentAFactors);
2196    return contentAFactors;
2197  }
2198
2199  // factorize content
2200  contentAFactors= multiFactorize (lcmCont, info);
2201
2202  // univariate after content removal
2203  CFList factors;
2204  if (A.isUnivariate ())
2205  {
2206    factors= uniFactorizer (A, alpha, GF);
2207    append (factors, contentAFactors);
2208    decompress (factors, N);
2209    return factors;
2210  }
2211
2212  // check main variable
2213  int swapLevel= 0;
2214  CanonicalForm derivZ;
2215  CanonicalForm gcdDerivZ;
2216  CanonicalForm bufA= A;
2217  Variable z;
2218  for (int i= 1; i <= A.level(); i++)
2219  {
2220    z= Variable (i);
2221    derivZ= deriv (bufA, z);
2222    if (derivZ.isZero())
2223    {
2224      if (i == 1)
2225        swapLevel= 1;
2226      else
2227        continue;
2228    }
2229    else
2230    {
2231      if (swapLevel == 1)
2232      {
2233        swapLevel= i;
2234        bufA= swapvar (A, x, z);
2235      }
2236      gcdDerivZ= gcd (bufA, derivZ);
2237      if (degree (gcdDerivZ) > 0 && !derivZ.isZero())
2238      {
2239        CanonicalForm g= bufA/gcdDerivZ;
2240        CFList factorsG=
2241        Union (multiFactorize (g, info),
2242               multiFactorize (gcdDerivZ, info));
2243        appendSwapDecompress (factorsG, contentAFactors, N, swapLevel, x);
2244        normalize (factorsG);
2245        return factorsG;
2246      }
2247      else
2248      {
2249        A= bufA;
2250        break;
2251      }
2252    }
2253  }
2254
2255
2256  CFList Aeval, list, evaluation, bufEvaluation, bufAeval;
2257  bool fail= false;
2258  int swapLevel2= 0;
2259  int level;
2260  int factorNums= 3;
2261  CanonicalForm bivarEval;
2262  CFList biFactors, bufBiFactors;
2263  CanonicalForm evalPoly;
2264  int lift, bufLift;
2265  double logarithm= (double) ilog2 (totaldegree (A));
2266  logarithm /= log2exp;
2267  logarithm= ceil (logarithm);
2268  if (factorNums < (int) logarithm)
2269    factorNums= (int) logarithm;
2270  CFList* bufAeval2= new CFList [A.level() - 2];
2271  CFList* Aeval2= new CFList [A.level() - 2];
2272  int counter;
2273  int differentSecondVar= 0;
2274  // several bivariate factorizations
2275  for (int i= 0; i < factorNums; i++)
2276  {
2277    counter= 0;
2278    bufA= A;
2279    bufAeval= CFList();
2280    bufEvaluation= evalPoints (bufA, bufAeval, alpha, list, GF, fail);
2281    evalPoly= 0;
2282
2283    if (fail && (i == 0))
2284    {
2285      if (!swapLevel)
2286        level= 2;
2287      else
2288        level= swapLevel + 1;
2289
2290      CanonicalForm g;
2291      swapLevel2= newMainVariableSearch (A, Aeval, evaluation, alpha, level, g);
2292
2293      if (!swapLevel2) // need to pass to an extension
2294      {
2295        factors= extFactorize (A, info);
2296        appendSwapDecompress (factors, contentAFactors, N, swapLevel, x);
2297        normalize (factors);
2298        delete [] bufAeval2;
2299        delete [] Aeval2;
2300        return factors;
2301      }
2302      else
2303      {
2304        if (swapLevel2 == -1)
2305        {
2306          CFList factorsG=
2307          Union (multiFactorize (g, info),
2308                 multiFactorize (A/g, info));
2309          appendSwapDecompress (factorsG, contentAFactors, N, swapLevel, x);
2310          normalize (factorsG);
2311          delete [] bufAeval2;
2312          delete [] Aeval2;
2313          return factorsG;
2314        }
2315        fail= false;
2316        bufAeval= Aeval;
2317        bufA= A;
2318        bufEvaluation= evaluation;
2319      }
2320    }
2321    else if (fail && (i > 0))
2322      break;
2323
2324    bivarEval= bufEvaluation.getLast();
2325
2326    evaluationWRTDifferentSecondVars (bufAeval2, bufEvaluation, A);
2327
2328    for (int j= 0; j < A.level() - 2; j++)
2329    {
2330      if (!bufAeval2[j].isEmpty())
2331        counter++;
2332    }
2333
2334    bufLift= degree (A, y) + 1 + degree (LC(A, x), y);
2335
2336    TIMING_START (fac_bi_factorizer);
2337    if (!GF && alpha.level() == 1)
2338      bufBiFactors= FpBiSqrfFactorize (bufAeval.getFirst());
2339    else if (GF)
2340      bufBiFactors= GFBiSqrfFactorize (bufAeval.getFirst());
2341    else
2342      bufBiFactors= FqBiSqrfFactorize (bufAeval.getFirst(), alpha);
2343    TIMING_END_AND_PRINT (fac_bi_factorizer,
2344                          "time for bivariate factorization: ");
2345    bufBiFactors.removeFirst();
2346
2347    if (bufBiFactors.length() == 1)
2348    {
2349      if (extension)
2350      {
2351        CFList source, dest;
2352        A= mapDown (A, info, source, dest);
2353      }
2354      factors.append (A);
2355      appendSwapDecompress (factors, contentAFactors, N, swapLevel,
2356                            swapLevel2, x);
2357      normalize (factors);
2358      delete [] bufAeval2;
2359      delete [] Aeval2;
2360      return factors;
2361    }
2362
2363    if (i == 0)
2364    {
2365      Aeval= bufAeval;
2366      evaluation= bufEvaluation;
2367      biFactors= bufBiFactors;
2368      lift= bufLift;
2369      for (int j= 0; j < A.level() - 2; j++)
2370        Aeval2 [j]= bufAeval2 [j];
2371      differentSecondVar= counter;
2372    }
2373    else
2374    {
2375      if (bufBiFactors.length() < biFactors.length() ||
2376          ((bufLift < lift) && (bufBiFactors.length() == biFactors.length())) ||
2377          counter > differentSecondVar)
2378      {
2379        Aeval= bufAeval;
2380        evaluation= bufEvaluation;
2381        biFactors= bufBiFactors;
2382        lift= bufLift;
2383        for (int j= 0; j < A.level() - 2; j++)
2384          Aeval2 [j]= bufAeval2 [j];
2385        differentSecondVar= counter;
2386      }
2387    }
2388    int k= 0;
2389    for (CFListIterator j= bufEvaluation; j.hasItem(); j++, k++)
2390      evalPoly += j.getItem()*power (x, k);
2391    list.append (evalPoly);
2392  }
2393
2394  delete [] bufAeval2;
2395
2396  sortList (biFactors, x);
2397
2398  int minFactorsLength;
2399  bool irred= false;
2400  factorizationWRTDifferentSecondVars (A, Aeval2, info, minFactorsLength, irred);
2401
2402  if (irred)
2403  {
2404    if (extension)
2405    {
2406      CFList source, dest;
2407      A= mapDown (A, info, source, dest);
2408    }
2409    factors.append (A);
2410    appendSwapDecompress (factors, contentAFactors, N, swapLevel,
2411                          swapLevel2, x);
2412    normalize (factors);
2413    delete [] Aeval2;
2414    return factors;
2415  }
2416
2417  if (minFactorsLength == 0)
2418    minFactorsLength= biFactors.length();
2419  else if (biFactors.length() > minFactorsLength)
2420    refineBiFactors (A, biFactors, Aeval2, evaluation, minFactorsLength);
2421
2422  CFList uniFactors= buildUniFactors (biFactors, evaluation.getLast(), y);
2423
2424  CFList * oldAeval= new CFList [A.level() - 2]; //TODO use bufAeval2 for this
2425  for (int i= 0; i < A.level() - 2; i++)
2426    oldAeval[i]= Aeval2[i];
2427
2428  getLeadingCoeffs (A, Aeval2, uniFactors, evaluation);
2429
2430  CFList biFactorsLCs;
2431  for (CFListIterator i= biFactors; i.hasItem(); i++)
2432    biFactorsLCs.append (LC (i.getItem(), 1));
2433
2434
2435  //shifting to zero
2436  A= shift2Zero (A, Aeval, evaluation);
2437
2438  CanonicalForm hh= Lc (Aeval.getFirst());
2439
2440  for (CFListIterator i= Aeval; i.hasItem(); i++)
2441    i.getItem() /= hh;
2442
2443  A /= hh;
2444
2445  Variable v;
2446  CFList leadingCoeffs= precomputeLeadingCoeff (LC (A, 1), biFactorsLCs, alpha,
2447                                          evaluation, Aeval2, A.level() - 2, v);
2448
2449  if (v.level() != 1)
2450  {
2451    A= swapvar (A, y, v);
2452    for (int i= 0; i < A.level() - 2; i++)
2453    {
2454      if (oldAeval[i].isEmpty())
2455        continue;
2456      if (oldAeval[i].getFirst().level() == v.level())
2457      {
2458        biFactors= CFList();
2459        for (CFListIterator iter= oldAeval [i]; iter.hasItem(); iter++)
2460          biFactors.append (swapvar (iter.getItem(), v, y));
2461      }
2462    }
2463    int i= A.level();
2464    CanonicalForm evalPoint;
2465    for (CFListIterator iter= evaluation; iter.hasItem(); iter++, i--)
2466    {
2467      if (i == v.level())
2468      {
2469        evalPoint= iter.getItem();
2470        iter.getItem()= evaluation.getLast();
2471        evaluation.removeLast();
2472        evaluation.append (evalPoint);
2473        break;
2474      }
2475    }
2476    Aeval= evaluateAtZero (A);
2477  }
2478
2479  CFListIterator iter= biFactors;
2480  for (; iter.hasItem(); iter++)
2481    iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
2482
2483  CanonicalForm oldA= A;
2484  CFList oldBiFactors= biFactors;
2485  if (!leadingCoeffs.getFirst().inCoeffDomain())
2486  {
2487    CanonicalForm tmp= power (leadingCoeffs.getFirst(), biFactors.length() - 1);
2488    A *= tmp;
2489    Aeval= evaluateAtZero (A);
2490    tmp= leadingCoeffs.getFirst();
2491    for (int i= A.level(); i > 2; i--)
2492      tmp= tmp (0, i);
2493    if (!tmp.inCoeffDomain())
2494    {
2495      for (CFListIterator i= biFactors; i.hasItem(); i++)
2496      {
2497        i.getItem() *= tmp/LC (i.getItem(), 1);
2498        i.getItem() /= Lc (i.getItem());
2499      }
2500    }
2501    hh= Lc (Aeval.getFirst());
2502    for (CFListIterator i= Aeval; i.hasItem(); i++)
2503      i.getItem() /= hh;
2504
2505    A /= hh;
2506  }
2507
2508  leadingCoeffs.removeFirst();
2509
2510  //prepare leading coefficients
2511  CFList* leadingCoeffs2= new CFList [A.level() - 2];
2512  prepareLeadingCoeffs (leadingCoeffs2, A.level(), leadingCoeffs, biFactors);
2513
2514  CFArray Pi;
2515  CFList diophant;
2516  int* liftBounds= new int [A.level() - 1];
2517  int liftBoundsLength= A.level() - 1;
2518  for (int i= 0; i < liftBoundsLength; i++)
2519    liftBounds [i]= degree (A, i + 2) + 1;
2520
2521  Aeval.removeFirst();
2522  bool noOneToOne= false;
2523  factors= nonMonicHenselLift (Aeval, biFactors, leadingCoeffs2, diophant,
2524                               Pi, liftBounds, liftBoundsLength, noOneToOne);
2525
2526
2527  if (!noOneToOne)
2528  {
2529    int check= factors.length();
2530    A= reverseShift (oldA, evaluation);
2531    factors= recoverFactors (A, factors, evaluation);
2532    if (check != factors.length())
2533      noOneToOne= true;
2534
2535    if (extension && !noOneToOne)
2536      factors= extNonMonicFactorRecombination (factors, A, info);
2537  }
2538  if (noOneToOne)
2539  {
2540    A= oldA;
2541    Aeval= evaluateAtZero (A);
2542    biFactors= oldBiFactors;
2543    CanonicalForm LCA= LC (Aeval.getFirst(), 1);
2544    CanonicalForm yToLift= power (y, lift);
2545    CFListIterator i= biFactors;
2546    lift= degree (i.getItem(), 2) + degree (LC (i.getItem(), 1)) + 1;
2547    i++;
2548
2549    for (; i.hasItem(); i++)
2550      lift= tmax (lift, degree (i.getItem(), 2) + degree (LC (i.getItem(), 1)) + 1);
2551
2552    lift= tmax (degree (Aeval.getFirst() , 2) + 1, lift);
2553
2554    i= biFactors;
2555    yToLift= power (y, lift);
2556    CanonicalForm dummy;
2557    for (; i.hasItem(); i++)
2558    {
2559      LCA= LC (i.getItem(), 1);
2560      extgcd (LCA, yToLift, LCA, dummy);
2561      i.getItem()= mod (i.getItem()*LCA, yToLift);
2562    }
2563
2564    liftBoundsLength= F.level() - 1;
2565    liftBounds= liftingBounds (A, lift);
2566
2567    CFList MOD;
2568    bool earlySuccess;
2569    CFList earlyFactors;
2570    TIMING_START (fac_hensel_lift);
2571    CFList liftedFactors= henselLiftAndEarly
2572                          (A, MOD, liftBounds, earlySuccess, earlyFactors,
2573                           Aeval, biFactors, evaluation, info);
2574    TIMING_END_AND_PRINT (fac_hensel_lift, "time for hensel lifting: ");
2575
2576    if (!extension)
2577    {
2578      TIMING_START (fac_factor_recombination);
2579      factors= factorRecombination (A, liftedFactors, MOD);
2580      TIMING_END_AND_PRINT (fac_factor_recombination,
2581                            "time for factor recombination: ");
2582    }
2583    else
2584    {
2585      TIMING_START (fac_factor_recombination);
2586      factors= extFactorRecombination (liftedFactors, A, MOD, info, evaluation);
2587      TIMING_END_AND_PRINT (fac_factor_recombination,
2588                            "time for factor recombination: ");
2589    }
2590
2591    if (earlySuccess)
2592      factors= Union (factors, earlyFactors);
2593    if (!extension)
2594    {
2595      for (CFListIterator i= factors; i.hasItem(); i++)
2596      {
2597        int kk= Aeval.getLast().level();
2598        for (CFListIterator j= evaluation; j.hasItem(); j++, kk--)
2599        {
2600          if (i.getItem().level() < kk)
2601            continue;
2602          i.getItem()= i.getItem() (Variable (kk) - j.getItem(), kk);
2603        }
2604      }
2605    }
2606  }
2607
2608
2609
2610  if (v.level() != 1)
2611  {
2612    for (CFListIterator iter= factors; iter.hasItem(); iter++)
2613      iter.getItem()= swapvar (iter.getItem(), v, y);
2614  }
2615
2616  swap (factors, swapLevel, swapLevel2, x);
2617  append (factors, contentAFactors);
2618  decompress (factors, N);
2619  normalize (factors);
2620
2621  delete[] liftBounds;
2622
2623  return factors;
2624}
2625
2626/// multivariate factorization over an extension of the initial field
2627CFList
2628extFactorize (const CanonicalForm& F, const ExtensionInfo& info)
2629{
2630  CanonicalForm A= F;
2631
2632  Variable alpha= info.getAlpha();
2633  Variable beta= info.getBeta();
2634  int k= info.getGFDegree();
2635  char cGFName= info.getGFName();
2636  CanonicalForm delta= info.getDelta();
2637  bool GF= (CFFactory::gettype() == GaloisFieldDomain);
2638  Variable w= Variable (1);
2639
2640  CFList factors;
2641  if (!GF && alpha == w)  // we are in F_p
2642  {
2643    CFList factors;
2644    bool extension= true;
2645    int p= getCharacteristic();
2646    if (p*p < (1<<16)) // pass to GF if possible
2647    {
2648      setCharacteristic (getCharacteristic(), 2, 'Z');
2649      ExtensionInfo info= ExtensionInfo (extension);
2650      A= A.mapinto();
2651      factors= multiFactorize (A, info);
2652
2653      Variable vBuf= rootOf (gf_mipo);
2654      setCharacteristic (getCharacteristic());
2655      for (CFListIterator j= factors; j.hasItem(); j++)
2656        j.getItem()= GF2FalphaRep (j.getItem(), vBuf);
2657    }
2658    else  // not able to pass to GF, pass to F_p(\alpha)
2659    {
2660      CanonicalForm mipo= randomIrredpoly (2, Variable (1));
2661      Variable v= rootOf (mipo);
2662      ExtensionInfo info= ExtensionInfo (v);
2663      factors= multiFactorize (A, info);
2664    }
2665    return factors;
2666  }
2667  else if (!GF && (alpha != w)) // we are in F_p(\alpha)
2668  {
2669    if (k == 1) // need factorization over F_p
2670    {
2671      int extDeg= degree (getMipo (alpha));
2672      extDeg++;
2673      CanonicalForm mipo= randomIrredpoly (extDeg + 1, Variable (1));
2674      Variable v= rootOf (mipo);
2675      ExtensionInfo info= ExtensionInfo (v);
2676      factors= biFactorize (A, info);
2677    }
2678    else
2679    {
2680      if (beta == Variable (1))
2681      {
2682        Variable v= chooseExtension (alpha, beta, k);
2683        CanonicalForm primElem, imPrimElem;
2684        bool primFail= false;
2685        Variable vBuf;
2686        primElem= primitiveElement (alpha, vBuf, primFail);
2687        ASSERT (!primFail, "failure in integer factorizer");
2688        if (primFail)
2689          ; //ERROR
2690        else
2691          imPrimElem= mapPrimElem (primElem, vBuf, v);
2692
2693        CFList source, dest;
2694        CanonicalForm bufA= mapUp (A, alpha, v, primElem, imPrimElem,
2695                                   source, dest);
2696        ExtensionInfo info= ExtensionInfo (v, alpha, imPrimElem, primElem);
2697        factors= biFactorize (bufA, info);
2698      }
2699      else
2700      {
2701        Variable v= chooseExtension (alpha, beta, k);
2702        CanonicalForm primElem, imPrimElem;
2703        bool primFail= false;
2704        Variable vBuf;
2705        ASSERT (!primFail, "failure in integer factorizer");
2706        if (primFail)
2707          ; //ERROR
2708        else
2709          imPrimElem= mapPrimElem (delta, beta, v);
2710
2711        CFList source, dest;
2712        CanonicalForm bufA= mapDown (A, info, source, dest);
2713        source= CFList();
2714        dest= CFList();
2715        bufA= mapUp (bufA, beta, v, delta, imPrimElem, source, dest);
2716        ExtensionInfo info= ExtensionInfo (v, beta, imPrimElem, delta);
2717        factors= biFactorize (bufA, info);
2718      }
2719    }
2720    return factors;
2721  }
2722  else // we are in GF (p^k)
2723  {
2724    int p= getCharacteristic();
2725    int extensionDeg= getGFDegree();
2726    bool extension= true;
2727    if (k == 1) // need factorization over F_p
2728    {
2729      extensionDeg++;
2730      if (pow ((double) p, (double) extensionDeg) < (1<<16))
2731      // pass to GF(p^k+1)
2732      {
2733        setCharacteristic (p);
2734        Variable vBuf= rootOf (gf_mipo);
2735        A= GF2FalphaRep (A, vBuf);
2736        setCharacteristic (p, extensionDeg, 'Z');
2737        ExtensionInfo info= ExtensionInfo (extension);
2738        factors= multiFactorize (A.mapinto(), info);
2739      }
2740      else // not able to pass to another GF, pass to F_p(\alpha)
2741      {
2742        setCharacteristic (p);
2743        Variable vBuf= rootOf (gf_mipo);
2744        A= GF2FalphaRep (A, vBuf);
2745        Variable v= chooseExtension (vBuf, beta, k);
2746        ExtensionInfo info= ExtensionInfo (v, extension);
2747        factors= multiFactorize (A, info);
2748      }
2749    }
2750    else // need factorization over GF (p^k)
2751    {
2752      if (pow ((double) p, (double) 2*extensionDeg) < (1<<16))
2753      // pass to GF(p^2k)
2754      {
2755        setCharacteristic (p, 2*extensionDeg, 'Z');
2756        ExtensionInfo info= ExtensionInfo (k, cGFName, extension);
2757        factors= multiFactorize (GFMapUp (A, extensionDeg), info);
2758        setCharacteristic (p, extensionDeg, cGFName);
2759      }
2760      else // not able to pass to GF (p^2k), pass to F_p (\alpha)
2761      {
2762        setCharacteristic (p);
2763        Variable v1= rootOf (gf_mipo);
2764        A= GF2FalphaRep (A, v1);
2765        Variable v2= chooseExtension (v1, v1, k);
2766        CanonicalForm primElem, imPrimElem;
2767        bool primFail= false;
2768        Variable vBuf;
2769        primElem= primitiveElement (v1, v1, primFail);
2770        if (primFail)
2771          ; //ERROR
2772        else
2773          imPrimElem= mapPrimElem (primElem, v1, v2);
2774        CFList source, dest;
2775        CanonicalForm bufA= mapUp (A, v1, v2, primElem, imPrimElem,
2776                                     source, dest);
2777        ExtensionInfo info= ExtensionInfo (v2, v1, imPrimElem, primElem);
2778        factors= multiFactorize (bufA, info);
2779        setCharacteristic (p, k, cGFName);
2780        for (CFListIterator i= factors; i.hasItem(); i++)
2781          i.getItem()= Falpha2GFRep (i.getItem());
2782      }
2783    }
2784    return factors;
2785  }
2786}
2787
2788#endif
2789/* HAVE_NTL */
2790
Note: See TracBrowser for help on using the repository browser.