source: git/factory/facFqFactorize.cc @ 3c0e63d

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