source: git/factory/facFqFactorize.cc @ a25f7a7

spielwiese
Last change on this file since a25f7a7 was a25f7a7, checked in by Martin Lee <martinlee84@…>, 12 years ago
chg: deleted some unused variable
  • Property mode set to 100644
File size: 94.7 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;
1330  if (getCharacteristic() > 0)
1331    sqrfFactorization= squarefreeFactorization (F, alpha);
1332  else
1333    sqrfFactorization= sqrFree (F);
1334
1335  sqrfPartF= 1;
1336  for (CFFListIterator i= sqrfFactorization; i.hasItem(); i++)
1337    sqrfPartF *= i.getItem().factor();
1338
1339  evalSqrfPartF= evaluateAtEval (sqrfPartF, evalPoint);
1340
1341  CanonicalForm test= evalSqrfPartF.getFirst() (evalPoint[0], 2);
1342
1343  if (degree (test) != degree (sqrfPartF, 1) || test.inCoeffDomain())
1344    return 0;
1345
1346  CFFList sqrfFactors;
1347  CFList tmp2;
1348  int k= 0;
1349  factors= uniFactors;
1350  CFFListIterator iter;
1351  for (CFListIterator i= factors; i.hasItem(); i++, k++)
1352  {
1353    tmp= 1;
1354    if (getCharacteristic() > 0)
1355      sqrfFactors= squarefreeFactorization (i.getItem(), alpha);
1356    else
1357      sqrfFactors= sqrFree (i.getItem());
1358
1359    for (iter= sqrfFactors; iter.hasItem(); iter++)
1360    {
1361      tmp2.append (iter.getItem().factor());
1362      tmp *= iter.getItem().factor();
1363    }
1364    i.getItem()= tmp/Lc(tmp);
1365    bufSqrfFactors [k]= sqrfFactors;
1366  }
1367
1368  for (int i= 0; i < factors.length() - 1; i++)
1369  {
1370    for (k= i + 1; k < factors.length(); k++)
1371    {
1372      gcdFreeBasis (bufSqrfFactors [i], bufSqrfFactors[k]);
1373    }
1374  }
1375
1376  factors= CFList();
1377  for (int i= 0; i < uniFactors.length(); i++)
1378  {
1379    if (i == 0)
1380    {
1381      for (iter= bufSqrfFactors [i]; iter.hasItem(); iter++)
1382      {
1383        if (iter.getItem().factor().inCoeffDomain())
1384          continue;
1385        iter.getItem()= CFFactor (iter.getItem().factor()/
1386                                  Lc (iter.getItem().factor()),
1387                                  iter.getItem().exp());
1388        factors.append (iter.getItem().factor());
1389      }
1390    }
1391    else
1392    {
1393      for (iter= bufSqrfFactors [i]; iter.hasItem(); iter++)
1394      {
1395        if (iter.getItem().factor().inCoeffDomain())
1396          continue;
1397        iter.getItem()= CFFactor (iter.getItem().factor()/
1398                                  Lc (iter.getItem().factor()),
1399                                  iter.getItem().exp());
1400        if (!find (factors, iter.getItem().factor()))
1401          factors.append (iter.getItem().factor());
1402      }
1403    }
1404  }
1405
1406  test= prod (factors);
1407  tmp= evalSqrfPartF.getFirst() (evalPoint[0],2);
1408  if (test/Lc (test) != tmp/Lc (tmp))
1409    return 0;
1410  else
1411    return 1;
1412}
1413
1414CFList
1415precomputeLeadingCoeff (const CanonicalForm& LCF, const CFList& LCFFactors,
1416                        const Variable& alpha, const CFList& evaluation,
1417                        CFList* & differentSecondVarLCs, int lSecondVarLCs,
1418                        Variable& y
1419                       )
1420{
1421  y= Variable (1);
1422  if (LCF.inCoeffDomain())
1423  {
1424    CFList result;
1425    for (int i= 1; i <= LCFFactors.length() + 1; i++)
1426      result.append (1);
1427    return result;
1428  }
1429
1430  CFMap N, M;
1431  CFArray dummy= CFArray (2);
1432  dummy [0]= LCF;
1433  dummy [1]= Variable (2);
1434  compress (dummy, M, N);
1435  CanonicalForm F= M (LCF);
1436  if (LCF.isUnivariate())
1437  {
1438    CFList result;
1439    int LCFLevel= LCF.level();
1440    bool found= false;
1441    if (LCFLevel == 2)
1442    {
1443    //bivariate leading coefficients are already the true leading coefficients
1444      result= LCFFactors;
1445      found= true;
1446    }
1447    else
1448    {
1449      CFListIterator j;
1450      for (int i= 0; i < lSecondVarLCs; i++)
1451      {
1452        for (j= differentSecondVarLCs[i]; j.hasItem(); j++)
1453        {
1454          if (j.getItem().level() == LCFLevel)
1455          {
1456            found= true;
1457            break;
1458          }
1459        }
1460        if (found)
1461        {
1462          result= differentSecondVarLCs [i];
1463          break;
1464        }
1465      }
1466      if (!found)
1467        result= LCFFactors;
1468    }
1469    if (found)
1470      result.insert (Lc (LCF));
1471    else
1472    {
1473      for (CFListIterator i= result; i.hasItem(); i++)
1474        i.getItem() *= LCF;
1475      result.insert (LCF);
1476    }
1477    return result;
1478  }
1479
1480  CFList factors= LCFFactors;
1481
1482  for (CFListIterator i= factors; i.hasItem(); i++)
1483    i.getItem()= M (i.getItem());
1484
1485  CanonicalForm sqrfPartF;
1486  CFFList * bufSqrfFactors= new CFFList [factors.length()];
1487  CFList evalSqrfPartF, bufFactors;
1488  CFArray evalPoint= CFArray (evaluation.length() - 1);
1489  CFArray buf= CFArray (evaluation.length());
1490  CFArray swap= CFArray (evaluation.length());
1491  CFListIterator iter= evaluation;
1492  CanonicalForm vars=getVars (LCF)*Variable (2);
1493  for (int i= evaluation.length() +1; i > 1; i--, iter++)
1494  {
1495    buf[i-2]=iter.getItem();
1496    if (degree (vars, i) > 0)
1497      swap[M(Variable (i)).level()-1]=buf[i-2];
1498  }
1499  buf= swap;
1500  for (int i= 0; i < evaluation.length() - 1; i++)
1501    evalPoint[i]= buf[i+1];
1502
1503  int pass= testFactors (F, factors, alpha, sqrfPartF,
1504                         bufFactors, bufSqrfFactors, evalSqrfPartF, evalPoint);
1505
1506  bool foundDifferent= false;
1507  Variable z, x= y;
1508  int j= 0;
1509  if (!pass)
1510  {
1511    int lev= 0;
1512    // LCF is non-constant here
1513    CFList bufBufFactors;
1514    CanonicalForm bufF;
1515    for (int i= 0; i < lSecondVarLCs; i++)
1516    {
1517      if (!differentSecondVarLCs [i].isEmpty())
1518      {
1519        bool allConstant= true;
1520        for (iter= differentSecondVarLCs[i]; iter.hasItem(); iter++)
1521        {
1522          if (!iter.getItem().inCoeffDomain())
1523          {
1524            allConstant= false;
1525            y= Variable (iter.getItem().level());
1526            lev= M(y).level();
1527          }
1528        }
1529        if (allConstant)
1530          continue;
1531
1532        bufFactors= differentSecondVarLCs [i];
1533        for (iter= bufFactors; iter.hasItem(); iter++)
1534          iter.getItem()= swapvar (iter.getItem(), x, y);
1535        bufF= F;
1536        z= Variable (lev);
1537        bufF= swapvar (bufF, x, z);
1538        bufBufFactors= bufFactors;
1539        evalPoint= CFArray (evaluation.length() - 1);
1540        for (int k= 0; k < evaluation.length()-1; k++)
1541        {
1542          if (N (Variable (k+1)).level() != y.level())
1543            evalPoint[k]= buf[k+1];
1544          else
1545            evalPoint[k]= buf[0];
1546        }
1547        pass= testFactors (bufF, bufBufFactors, alpha, sqrfPartF, bufFactors,
1548                           bufSqrfFactors, evalSqrfPartF, evalPoint);
1549        if (pass)
1550        {
1551          foundDifferent= true;
1552          F= bufF;
1553          CFList l= factors;
1554          for (iter= l; iter.hasItem(); iter++)
1555            iter.getItem()= swapvar (iter.getItem(), x, y);
1556          differentSecondVarLCs [i]= l;
1557          j= i;
1558          break;
1559        }
1560        if (!pass && i == lSecondVarLCs - 1)
1561        {
1562          CFList result;
1563          result.append (LCF);
1564          for (int k= 1; k <= factors.length(); k++)
1565            result.append (LCF);
1566          y= Variable (1);
1567          delete [] bufSqrfFactors;
1568          return result;
1569        }
1570      }
1571    }
1572  }
1573  if (!pass)
1574  {
1575    CFList result;
1576    result.append (LCF);
1577    for (int k= 1; k <= factors.length(); k++)
1578      result.append (LCF);
1579    y= Variable (1);
1580    delete [] bufSqrfFactors;
1581    return result;
1582  }
1583  else
1584    factors= bufFactors;
1585
1586  bufFactors= factors;
1587
1588  CFMap MM, NN;
1589  dummy [0]= sqrfPartF;
1590  dummy [1]= 1;
1591  compress (dummy, MM, NN);
1592  sqrfPartF= MM (sqrfPartF);
1593  CanonicalForm varsSqrfPartF= getVars (sqrfPartF);
1594  for (CFListIterator iter= factors; iter.hasItem(); iter++)
1595    iter.getItem()= MM (iter.getItem());
1596
1597  CFList evaluation2;
1598  for (int i= 2; i <= varsSqrfPartF.level(); i++)
1599    evaluation2.insert (evalPoint[NN (Variable (i)).level()-2]);
1600
1601  CFList interMedResult;
1602  CanonicalForm oldSqrfPartF= sqrfPartF;
1603  sqrfPartF= shift2Zero (sqrfPartF, evalSqrfPartF, evaluation2);
1604  if (factors.length() > 1)
1605  {
1606    CanonicalForm LC1= LC (oldSqrfPartF, 1);
1607    CFList leadingCoeffs;
1608    for (int i= 0; i < factors.length(); i++)
1609      leadingCoeffs.append (LC1);
1610
1611    CFList LC1eval= evaluateAtEval (LC1, evaluation2, 2);
1612    CFList oldFactors= factors;
1613    for (CFListIterator i= oldFactors; i.hasItem(); i++)
1614      i.getItem() *= LC1eval.getFirst()/Lc (i.getItem());
1615
1616    bool success= false;
1617    CanonicalForm oldSqrfPartFPowLC= oldSqrfPartF*power(LC1,factors.length()-1);
1618    CFList heuResult;
1619    if (size (oldSqrfPartFPowLC)/getNumVars (oldSqrfPartFPowLC) < 500 &&
1620        LucksWangSparseHeuristic (oldSqrfPartFPowLC,
1621                                  oldFactors, 2, leadingCoeffs, heuResult))
1622    {
1623      interMedResult= recoverFactors (oldSqrfPartF, heuResult);
1624      if (oldFactors.length() == interMedResult.length())
1625        success= true;
1626    }
1627    if (!success)
1628    {
1629      LC1= LC (evalSqrfPartF.getFirst(), 1);
1630
1631      CFArray leadingCoeffs= CFArray (factors.length());
1632      for (int i= 0; i < factors.length(); i++)
1633        leadingCoeffs[i]= LC1;
1634
1635      for (CFListIterator i= factors; i.hasItem(); i++)
1636        i.getItem() *= LC1 (0,2)/Lc (i.getItem());
1637      factors.insert (1);
1638
1639      CanonicalForm
1640      newSqrfPartF= evalSqrfPartF.getFirst()*power (LC1, factors.length() - 2);
1641
1642      int liftBound= degree (newSqrfPartF,2) + 1;
1643
1644      CFMatrix M= CFMatrix (liftBound, factors.length() - 1);
1645      CFArray Pi;
1646      CFList diophant;
1647      nonMonicHenselLift12 (newSqrfPartF, factors, liftBound, Pi, diophant, M,
1648                            leadingCoeffs, false);
1649
1650      if (sqrfPartF.level() > 2)
1651      {
1652        int* liftBounds= new int [sqrfPartF.level() - 1];
1653        liftBounds [0]= liftBound;
1654        bool noOneToOne= false;
1655        CFList *leadingCoeffs2= new CFList [sqrfPartF.level()-2];
1656        LC1= LC (evalSqrfPartF.getLast(), 1);
1657        CFList LCs;
1658        for (int i= 0; i < factors.length(); i++)
1659          LCs.append (LC1);
1660        leadingCoeffs2 [sqrfPartF.level() - 3]= LCs;
1661        for (int i= sqrfPartF.level() - 1; i > 2; i--)
1662        {
1663          for (CFListIterator j= LCs; j.hasItem(); j++)
1664            j.getItem()= j.getItem() (0, i + 1);
1665          leadingCoeffs2 [i - 3]= LCs;
1666        }
1667        sqrfPartF *= power (LC1, factors.length()-1);
1668
1669        int liftBoundsLength= sqrfPartF.level() - 1;
1670        for (int i= 1; i < liftBoundsLength; i++)
1671          liftBounds [i]= degree (sqrfPartF, i + 2) + 1;
1672        evalSqrfPartF= evaluateAtZero (sqrfPartF);
1673        evalSqrfPartF.removeFirst();
1674        factors= nonMonicHenselLift (evalSqrfPartF, factors, leadingCoeffs2,
1675                 diophant, Pi, liftBounds, sqrfPartF.level() - 1, noOneToOne);
1676        delete [] leadingCoeffs2;
1677        delete [] liftBounds;
1678      }
1679      for (CFListIterator iter= factors; iter.hasItem(); iter++)
1680        iter.getItem()= reverseShift (iter.getItem(), evaluation2);
1681
1682      interMedResult=
1683      recoverFactors (reverseShift(evalSqrfPartF.getLast(),evaluation2),
1684                      factors);
1685    }
1686  }
1687  else
1688  {
1689    CanonicalForm contF=content (oldSqrfPartF,1);
1690    factors= CFList (oldSqrfPartF/contF);
1691    interMedResult= recoverFactors (oldSqrfPartF, factors);
1692  }
1693
1694  for (CFListIterator iter= interMedResult; iter.hasItem(); iter++)
1695    iter.getItem()= NN (iter.getItem());
1696
1697  CFList result;
1698  CFFListIterator k;
1699  for (int i= 0; i < LCFFactors.length(); i++)
1700  {
1701    CanonicalForm tmp= 1;
1702    for (k= bufSqrfFactors[i]; k.hasItem(); k++)
1703    {
1704      int pos= findItem (bufFactors, k.getItem().factor());
1705      if (pos)
1706        tmp *= power (getItem (interMedResult, pos), k.getItem().exp());
1707    }
1708    result.append (tmp);
1709  }
1710
1711  for (CFListIterator i= result; i.hasItem(); i++)
1712  {
1713    F /= i.getItem();
1714    if (foundDifferent)
1715      i.getItem()= swapvar (i.getItem(), x, z);
1716    i.getItem()= N (i.getItem());
1717  }
1718
1719  if (foundDifferent)
1720  {
1721    CFList l= differentSecondVarLCs [j];
1722    for (CFListIterator i= l; i.hasItem(); i++)
1723      i.getItem()= swapvar (i.getItem(), y, z);
1724    differentSecondVarLCs [j]= l;
1725    F= swapvar (F, x, z);
1726  }
1727
1728  result.insert (N (F));
1729
1730  result= distributeContent (result, differentSecondVarLCs, lSecondVarLCs);
1731
1732  if (!result.getFirst().inCoeffDomain())
1733  {
1734    CFListIterator i= result;
1735    CanonicalForm tmp;
1736    if (foundDifferent)
1737      i.getItem()= swapvar (i.getItem(), Variable (2), y);
1738
1739    tmp= i.getItem();
1740
1741    i++;
1742    for (; i.hasItem(); i++)
1743    {
1744      if (foundDifferent)
1745        i.getItem()= swapvar (i.getItem(), Variable (2), y)*tmp;
1746      else
1747        i.getItem() *= tmp;
1748    }
1749  }
1750  else
1751    y= Variable (1);
1752
1753  delete [] bufSqrfFactors;
1754
1755  return result;
1756}
1757
1758void
1759evaluationWRTDifferentSecondVars (CFList*& Aeval, const CFList& evaluation,
1760                                  const CanonicalForm& A)
1761{
1762  CanonicalForm tmp;
1763  CFList tmp2;
1764  CFListIterator iter;
1765  bool preserveDegree= true;
1766  Variable x= Variable (1);
1767  int j, degAi, degA1= degree (A,1);
1768  for (int i= A.level(); i > 2; i--)
1769  {
1770    tmp= A;
1771    tmp2= CFList();
1772    iter= evaluation;
1773    preserveDegree= true;
1774    degAi= degree (A,i);
1775    for (j= A.level(); j > 1; j--, iter++)
1776    {
1777      if (j == i)
1778        continue;
1779      else
1780      {
1781        tmp= tmp (iter.getItem(), j);
1782        tmp2.insert (tmp);
1783        if ((degree (tmp, i) != degAi) ||
1784            (degree (tmp, 1) != degA1))
1785        {
1786          preserveDegree= false;
1787          break;
1788        }
1789      }
1790    }
1791    if (!content(tmp,1).inCoeffDomain())
1792      preserveDegree= false;
1793    if (!(gcd (deriv (tmp,x), tmp)).inCoeffDomain())
1794      preserveDegree= false;
1795    if (preserveDegree)
1796      Aeval [i - 3]= tmp2;
1797    else
1798      Aeval [i - 3]= CFList();
1799  }
1800}
1801
1802#endif
1803
1804static inline
1805CanonicalForm prodEval (const CFList& l, const CanonicalForm& evalPoint,
1806                        const Variable& v)
1807{
1808  CanonicalForm result= 1;
1809  for (CFListIterator i= l; i.hasItem(); i++)
1810    result *= i.getItem() (evalPoint, v);
1811  return result;
1812}
1813
1814//recombine bivariate factors in case one bivariate factorization yields less
1815// factors than the other
1816CFList
1817recombination (const CFList& factors1, const CFList& factors2, int s, int thres,
1818               const CanonicalForm& evalPoint, const Variable& x)
1819{
1820  CFList T, S;
1821
1822  T= factors1;
1823  CFList result;
1824  CanonicalForm buf;
1825  int * v= new int [T.length()];
1826  for (int i= 0; i < T.length(); i++)
1827    v[i]= 0;
1828  bool nosubset= false;
1829  CFArray TT;
1830  TT= copy (factors1);
1831  while (T.length() >= 2*s && s <= thres)
1832  {
1833    while (nosubset == false)
1834    {
1835      if (T.length() == s)
1836      {
1837        delete [] v;
1838        result.append (prod (T));
1839        return result;
1840      }
1841      S= subset (v, s, TT, nosubset);
1842      if (nosubset) break;
1843      buf= prodEval (S, evalPoint, x);
1844      buf /= Lc (buf);
1845      if (find (factors2, buf))
1846      {
1847        T= Difference (T, S);
1848        result.append (prod (S));
1849        TT= copy (T);
1850        indexUpdate (v, s, T.length(), nosubset);
1851        if (nosubset) break;
1852      }
1853    }
1854    s++;
1855    if (T.length() < 2*s || T.length() == s) 
1856    {
1857      delete [] v;
1858      result.append (prod (T));
1859      return result;
1860    }
1861    for (int i= 0; i < T.length(); i++)
1862      v[i]= 0;
1863    nosubset= false;
1864  }
1865
1866  delete [] v;
1867  if (T.length() < 2*s)
1868  {
1869    result.append (prod (T));
1870    return result;
1871  }
1872
1873  return result;
1874}
1875
1876#ifdef HAVE_NTL
1877void
1878factorizationWRTDifferentSecondVars (const CanonicalForm& A, CFList*& Aeval,
1879                                     const ExtensionInfo& info,
1880                                     int& minFactorsLength, bool& irred)
1881{
1882  Variable x= Variable (1);
1883  minFactorsLength= 0;
1884  irred= false;
1885  CFList factors;
1886  Variable v;
1887  for (int j= 0; j < A.level() - 2; j++)
1888  {
1889    if (!Aeval[j].isEmpty())
1890    {
1891      v= Variable (Aeval[j].getFirst().level());
1892      if (CFFactory::gettype() == GaloisFieldDomain)
1893        factors= GFBiSqrfFactorize (Aeval[j].getFirst());
1894      else if (info.getAlpha().level() == 1)
1895        factors= FpBiSqrfFactorize (Aeval[j].getFirst());
1896      else
1897        factors= FqBiSqrfFactorize (Aeval[j].getFirst(), info.getAlpha());
1898
1899      factors.removeFirst();
1900      if (minFactorsLength == 0)
1901        minFactorsLength= factors.length();
1902      else
1903        minFactorsLength= tmin (minFactorsLength, factors.length());
1904
1905      if (factors.length() == 1)
1906      {
1907        irred= true;
1908        return;
1909      }
1910      sortList (factors, x);
1911      Aeval [j]= factors;
1912    }
1913  }
1914}
1915
1916CFList conv (const CFArray & A)
1917{
1918  CFList result;
1919  for (int i= A.max(); i >= A.min(); i--)
1920    result.insert (A[i]);
1921  return result;
1922}
1923
1924
1925void getLeadingCoeffs (const CanonicalForm& A, CFList*& Aeval,
1926                       const CFList& uniFactors, const CFList& evaluation
1927                      )
1928{
1929  CFListIterator iter;
1930  CFList LCs;
1931  for (int j= 0; j < A.level() - 2; j++)
1932  {
1933    if (!Aeval[j].isEmpty())
1934    {
1935      LCs= CFList();
1936      for (iter= Aeval[j]; iter.hasItem(); iter++)
1937        LCs.append (LC (iter.getItem(), 1));
1938      //normalize (LCs);
1939      Aeval[j]= LCs;
1940    }
1941  }
1942}
1943
1944void sortByUniFactors (CFList*& Aeval, int AevalLength,
1945                       const CFList& uniFactors, const CFList& evaluation
1946                      )
1947{
1948  CanonicalForm evalPoint;
1949  int i;
1950  CFListIterator iter, iter2;
1951  Variable v;
1952  CFList LCs, buf;
1953  CFArray l;
1954  int pos, index;
1955  for (int j= 0; j < AevalLength; j++)
1956  {
1957    if (!Aeval[j].isEmpty())
1958    {
1959      i= evaluation.length() + 1;
1960      for (iter= evaluation; iter.hasItem(); iter++, i--)
1961      {
1962        if (i == Aeval[j].getFirst().level())
1963        {
1964          evalPoint= iter.getItem();
1965          break;
1966        }
1967      }
1968
1969      v= Variable (i);
1970      if (Aeval[j].length() > uniFactors.length())
1971        Aeval[j]= recombination (Aeval[j], uniFactors, 1,
1972                                 Aeval[j].length() - uniFactors.length() + 1,
1973                                 evalPoint, v);
1974
1975      buf= buildUniFactors (Aeval[j], evalPoint, v);
1976      l= CFArray (uniFactors.length());
1977      index= 1;
1978      for (iter= buf; iter.hasItem(); iter++, index++)
1979      {
1980        pos= findItem (uniFactors, iter.getItem());
1981        if (pos)
1982          l[pos-1]= getItem (Aeval[j], index);
1983      }
1984      buf= conv (l);
1985      Aeval [j]= buf;
1986
1987      buf= buildUniFactors (Aeval[j], evalPoint, v);
1988    }
1989  }
1990}
1991
1992CFList
1993buildUniFactors (const CFList& biFactors, const CanonicalForm& evalPoint,
1994                 const Variable& y)
1995{
1996  CFList result;
1997  CanonicalForm tmp;
1998  for (CFListIterator i= biFactors; i.hasItem(); i++)
1999  {
2000    tmp= mod (i.getItem(), y - evalPoint);
2001    tmp /= Lc (tmp);
2002    result.append (tmp);
2003  }
2004  return result;
2005}
2006
2007void refineBiFactors (const CanonicalForm& A, CFList& biFactors,
2008                      CFList* const& Aeval, const CFList& evaluation,
2009                      int minFactorsLength)
2010{
2011  CFListIterator iter;
2012  CanonicalForm evalPoint;
2013  int i;
2014  Variable v;
2015  Variable y= Variable (2);
2016  CFList list;
2017  for (int j= 0; j < A.level() - 2; j++)
2018  {
2019    if (Aeval[j].length() == minFactorsLength)
2020    {
2021      i= A.level();
2022
2023      for (iter= evaluation; iter.hasItem(); iter++, i--)
2024      {
2025        if (i == Aeval[j].getFirst().level())
2026        {
2027          evalPoint= iter.getItem();
2028          break;
2029        }
2030      }
2031
2032      v= Variable (i);
2033      list= buildUniFactors (Aeval[j], evalPoint, v);
2034
2035      biFactors= recombination (biFactors, list, 1,
2036                                biFactors.length() - list.length() + 1,
2037                                evaluation.getLast(), y);
2038      return;
2039    }
2040  }
2041}
2042
2043void prepareLeadingCoeffs (CFList*& LCs, int n, const CFList& leadingCoeffs,
2044                           const CFList& biFactors, const CFList& evaluation)
2045{
2046  CFList l= leadingCoeffs;
2047  LCs [n-3]= l;
2048  CFListIterator j;
2049  CFListIterator iter= evaluation;
2050  for (int i= n - 1; i > 2; i--, iter++)
2051  {
2052    for (j= l; j.hasItem(); j++)
2053      j.getItem()= j.getItem() (iter.getItem(), i + 1);
2054    LCs [i - 3]= l;
2055  }
2056  l= LCs [0];
2057  for (CFListIterator i= l; i.hasItem(); i++)
2058    i.getItem()= i.getItem() (iter.getItem(), 3);
2059  CFListIterator ii= biFactors;
2060  CFList normalizeFactor;
2061  for (CFListIterator i= l; i.hasItem(); i++, ii++)
2062    normalizeFactor.append (Lc (LC (ii.getItem(), 1))/Lc (i.getItem()));
2063  for (int i= 0; i < n-2; i++)
2064  {
2065    ii= normalizeFactor;
2066    for (j= LCs [i]; j.hasItem(); j++, ii++)
2067      j.getItem() *= ii.getItem();
2068  }
2069}
2070
2071CFList
2072extNonMonicFactorRecombination (const CFList& factors, const CanonicalForm& F,
2073                                const ExtensionInfo& info)
2074{
2075  Variable alpha= info.getAlpha();
2076  Variable beta= info.getBeta();
2077  CanonicalForm gamma= info.getGamma();
2078  CanonicalForm delta= info.getDelta();
2079  int k= info.getGFDegree();
2080  CFList source, dest;
2081
2082  int degMipoBeta= 1;
2083  if (!k && beta != Variable(1))
2084    degMipoBeta= degree (getMipo (beta));
2085
2086  CFList T, S;
2087  T= factors;
2088  int s= 1;
2089  CFList result;
2090  CanonicalForm quot, buf= F;
2091
2092  CanonicalForm g;
2093  CanonicalForm buf2;
2094  int * v= new int [T.length()];
2095  for (int i= 0; i < T.length(); i++)
2096    v[i]= 0;
2097  bool noSubset= false;
2098  CFArray TT;
2099  TT= copy (factors);
2100  bool recombination= false;
2101  bool trueFactor= false;
2102  while (T.length() >= 2*s)
2103  {
2104    while (noSubset == false)
2105    {
2106      if (T.length() == s)
2107      {
2108        delete [] v;
2109        if (recombination)
2110        {
2111          g= prod (T);
2112          T.removeFirst();
2113          result.append (g/myContent (g));
2114          g /= Lc (g);
2115          appendTestMapDown (result, g, info, source, dest);
2116          return result;
2117        }
2118        else
2119          return CFList (buf/myContent(buf));
2120      }
2121
2122      S= subset (v, s, TT, noSubset);
2123      if (noSubset) break;
2124
2125      g= prod (S);
2126      g /= myContent (g);
2127      if (fdivides (g, buf, quot))
2128      {
2129        buf2= g;
2130        buf2 /= Lc (buf2);
2131        if (!k && beta.level() == 1)
2132        {
2133          if (degree (buf2, alpha) < degMipoBeta)
2134          {
2135            appendTestMapDown (result, buf2, info, source, dest);
2136            buf= quot;
2137            recombination= true;
2138            trueFactor= true;
2139          }
2140        }
2141        else
2142        {
2143          if (!isInExtension (buf2, gamma, k, delta, source, dest))
2144          {
2145            appendTestMapDown (result, buf2, info, source, dest);
2146            buf= quot;
2147            recombination= true;
2148            trueFactor= true;
2149          }
2150        }
2151        if (trueFactor)
2152        {
2153          T= Difference (T, S);
2154
2155          if (T.length() < 2*s || T.length() == s)
2156          {
2157            delete [] v;
2158            buf /= myContent (buf);
2159            buf /= Lc (buf);
2160            appendTestMapDown (result, buf, info, source, dest);
2161            return result;
2162          }
2163          trueFactor= false;
2164          TT= copy (T);
2165          indexUpdate (v, s, T.length(), noSubset);
2166          if (noSubset) break;
2167        }
2168      }
2169    }
2170    s++;
2171    if (T.length() < 2*s || T.length() == s)
2172    {
2173      delete [] v;
2174      appendTestMapDown (result, buf/myContent(buf), info, source, dest);
2175      return result;
2176    }
2177    for (int i= 0; i < T.length(); i++)
2178      v[i]= 0;
2179    noSubset= false;
2180  }
2181  if (T.length() < 2*s)
2182    appendMapDown (result, F/myContent(F), info, source, dest);
2183
2184  delete [] v;
2185  return result;
2186}
2187
2188CFList
2189extFactorize (const CanonicalForm& F, const ExtensionInfo& info);
2190
2191CFList
2192multiFactorize (const CanonicalForm& F, const ExtensionInfo& info)
2193{
2194
2195  if (F.inCoeffDomain())
2196    return CFList (F);
2197
2198  // compress and find main Variable
2199  CFMap N;
2200  CanonicalForm A= myCompress (F, N);
2201
2202  A /= Lc (A); // make monic
2203
2204  Variable alpha= info.getAlpha();
2205  Variable beta= info.getBeta();
2206  CanonicalForm gamma= info.getGamma();
2207  CanonicalForm delta= info.getDelta();
2208  bool extension= info.isInExtension();
2209  bool GF= (CFFactory::gettype() == GaloisFieldDomain);
2210  //univariate case
2211  if (F.isUnivariate())
2212  {
2213    if (extension == false)
2214      return uniFactorizer (F, alpha, GF);
2215    else
2216    {
2217      CFList source, dest;
2218      A= mapDown (F, info, source, dest);
2219      return uniFactorizer (A, beta, GF);
2220    }
2221  }
2222
2223  //bivariate case
2224  if (A.level() == 2)
2225  {
2226    CFList buf= biFactorize (F, info);
2227    return buf;
2228  }
2229
2230  Variable x= Variable (1);
2231  Variable y= Variable (2);
2232
2233  // remove content
2234  CFList contentAi;
2235  CanonicalForm lcmCont= lcmContent (A, contentAi);
2236  A /= lcmCont;
2237
2238  // trivial after content removal
2239  CFList contentAFactors;
2240  if (A.inCoeffDomain())
2241  {
2242    for (CFListIterator i= contentAi; i.hasItem(); i++)
2243    {
2244      if (i.getItem().inCoeffDomain())
2245        continue;
2246      else
2247      {
2248        lcmCont /= i.getItem();
2249        contentAFactors=
2250        Union (multiFactorize (lcmCont, info),
2251               multiFactorize (i.getItem(), info));
2252        break;
2253      }
2254    }
2255    decompress (contentAFactors, N);
2256    if (!extension)
2257      normalize (contentAFactors);
2258    return contentAFactors;
2259  }
2260
2261  // factorize content
2262  contentAFactors= multiFactorize (lcmCont, info);
2263
2264  // univariate after content removal
2265  CFList factors;
2266  if (A.isUnivariate ())
2267  {
2268    factors= uniFactorizer (A, alpha, GF);
2269    append (factors, contentAFactors);
2270    decompress (factors, N);
2271    return factors;
2272  }
2273
2274  // check main variable
2275  int swapLevel= 0;
2276  CanonicalForm derivZ;
2277  CanonicalForm gcdDerivZ;
2278  CanonicalForm bufA= A;
2279  Variable z;
2280  for (int i= 1; i <= A.level(); i++)
2281  {
2282    z= Variable (i);
2283    derivZ= deriv (bufA, z);
2284    if (derivZ.isZero())
2285    {
2286      if (i == 1)
2287        swapLevel= 1;
2288      else
2289        continue;
2290    }
2291    else
2292    {
2293      if (swapLevel == 1)
2294      {
2295        swapLevel= i;
2296        bufA= swapvar (A, x, z);
2297      }
2298      gcdDerivZ= gcd (bufA, derivZ);
2299      if (degree (gcdDerivZ) > 0 && !derivZ.isZero())
2300      {
2301        CanonicalForm g= bufA/gcdDerivZ;
2302        CFList factorsG=
2303        Union (multiFactorize (g, info),
2304               multiFactorize (gcdDerivZ, info));
2305        appendSwapDecompress (factorsG, contentAFactors, N, swapLevel, x);
2306        if (!extension)
2307          normalize (factorsG);
2308        return factorsG;
2309      }
2310      else
2311      {
2312        A= bufA;
2313        break;
2314      }
2315    }
2316  }
2317
2318
2319  CFList Aeval, list, evaluation, bufEvaluation, bufAeval;
2320  bool fail= false;
2321  int swapLevel2= 0;
2322  int level;
2323  int factorNums= 3;
2324  CFList biFactors, bufBiFactors;
2325  CanonicalForm evalPoly;
2326  int lift, bufLift, lengthAeval2= A.level()-2;
2327  double logarithm= (double) ilog2 (totaldegree (A));
2328  logarithm /= log2exp;
2329  logarithm= ceil (logarithm);
2330  if (factorNums < (int) logarithm)
2331    factorNums= (int) logarithm;
2332  CFList* bufAeval2= new CFList [lengthAeval2];
2333  CFList* Aeval2= new CFList [lengthAeval2];
2334  int counter;
2335  int differentSecondVar= 0;
2336  // several bivariate factorizations
2337  for (int i= 0; i < factorNums; i++)
2338  {
2339    counter= 0;
2340    bufA= A;
2341    bufAeval= CFList();
2342    bufEvaluation= evalPoints (bufA, bufAeval, alpha, list, GF, fail);
2343    evalPoly= 0;
2344
2345    if (fail && (i == 0))
2346    {
2347      if (!swapLevel)
2348        level= 2;
2349      else
2350        level= swapLevel + 1;
2351
2352      CanonicalForm g;
2353      swapLevel2= newMainVariableSearch (A, Aeval, evaluation, alpha, level, g);
2354
2355      if (!swapLevel2) // need to pass to an extension
2356      {
2357        factors= extFactorize (A, info);
2358        appendSwapDecompress (factors, contentAFactors, N, swapLevel, x);
2359        normalize (factors);
2360        delete [] bufAeval2;
2361        delete [] Aeval2;
2362        return factors;
2363      }
2364      else
2365      {
2366        if (swapLevel2 == -1)
2367        {
2368          CFList factorsG=
2369          Union (multiFactorize (g, info),
2370                 multiFactorize (A/g, info));
2371          appendSwapDecompress (factorsG, contentAFactors, N, swapLevel, x);
2372          if (!extension)
2373            normalize (factorsG);
2374          delete [] bufAeval2;
2375          delete [] Aeval2;
2376          return factorsG;
2377        }
2378        fail= false;
2379        bufAeval= Aeval;
2380        bufA= A;
2381        bufEvaluation= evaluation;
2382      }
2383    }
2384    else if (fail && (i > 0))
2385      break;
2386
2387    evaluationWRTDifferentSecondVars (bufAeval2, bufEvaluation, A);
2388
2389    for (int j= 0; j < lengthAeval2; j++)
2390    {
2391      if (!bufAeval2[j].isEmpty())
2392        counter++;
2393    }
2394
2395    bufLift= degree (A, y) + 1 + degree (LC(A, x), y);
2396
2397    TIMING_START (fac_fq_bi_factorizer);
2398    if (!GF && alpha.level() == 1)
2399      bufBiFactors= FpBiSqrfFactorize (bufAeval.getFirst());
2400    else if (GF)
2401      bufBiFactors= GFBiSqrfFactorize (bufAeval.getFirst());
2402    else
2403      bufBiFactors= FqBiSqrfFactorize (bufAeval.getFirst(), alpha);
2404    TIMING_END_AND_PRINT (fac_fq_bi_factorizer,
2405                          "time for bivariate factorization: ");
2406    bufBiFactors.removeFirst();
2407
2408    if (bufBiFactors.length() == 1)
2409    {
2410      if (extension)
2411      {
2412        CFList source, dest;
2413        A= mapDown (A, info, source, dest);
2414      }
2415      factors.append (A);
2416      appendSwapDecompress (factors, contentAFactors, N, swapLevel,
2417                            swapLevel2, x);
2418      if (!extension)
2419        normalize (factors);
2420      delete [] bufAeval2;
2421      delete [] Aeval2;
2422      return factors;
2423    }
2424
2425    if (i == 0)
2426    {
2427      Aeval= bufAeval;
2428      evaluation= bufEvaluation;
2429      biFactors= bufBiFactors;
2430      lift= bufLift;
2431      for (int j= 0; j < lengthAeval2; j++)
2432        Aeval2 [j]= bufAeval2 [j];
2433      differentSecondVar= counter;
2434    }
2435    else
2436    {
2437      if (bufBiFactors.length() < biFactors.length() ||
2438          ((bufLift < lift) && (bufBiFactors.length() == biFactors.length())) ||
2439          counter > differentSecondVar)
2440      {
2441        Aeval= bufAeval;
2442        evaluation= bufEvaluation;
2443        biFactors= bufBiFactors;
2444        lift= bufLift;
2445        for (int j= 0; j < lengthAeval2; j++)
2446          Aeval2 [j]= bufAeval2 [j];
2447        differentSecondVar= counter;
2448      }
2449    }
2450    int k= 0;
2451    for (CFListIterator j= bufEvaluation; j.hasItem(); j++, k++)
2452      evalPoly += j.getItem()*power (x, k);
2453    list.append (evalPoly);
2454  }
2455
2456  delete [] bufAeval2;
2457
2458  sortList (biFactors, x);
2459
2460  int minFactorsLength;
2461  bool irred= false;
2462  factorizationWRTDifferentSecondVars (A, Aeval2, info, minFactorsLength,irred);
2463
2464  if (irred)
2465  {
2466    if (extension)
2467    {
2468      CFList source, dest;
2469      A= mapDown (A, info, source, dest);
2470    }
2471    factors.append (A);
2472    appendSwapDecompress (factors, contentAFactors, N, swapLevel,
2473                          swapLevel2, x);
2474    if (!extension)
2475      normalize (factors);
2476    delete [] Aeval2;
2477    return factors;
2478  }
2479
2480  if (minFactorsLength == 0)
2481    minFactorsLength= biFactors.length();
2482  else if (biFactors.length() > minFactorsLength)
2483    refineBiFactors (A, biFactors, Aeval2, evaluation, minFactorsLength);
2484  minFactorsLength= tmin (minFactorsLength, biFactors.length());
2485
2486  if (differentSecondVar == lengthAeval2)
2487  {
2488    bool zeroOccured= false;
2489    for (CFListIterator iter= evaluation; iter.hasItem(); iter++)
2490    {
2491      if (iter.getItem().isZero())
2492      {
2493        zeroOccured= true;
2494        break;
2495      }
2496    }
2497    if (!zeroOccured)
2498    {
2499      factors= sparseHeuristic (A, biFactors, Aeval2, evaluation,
2500                                minFactorsLength);
2501      if (factors.length() == biFactors.length())
2502      {
2503        if (extension)
2504          factors= extNonMonicFactorRecombination (factors, A, info);
2505
2506        appendSwapDecompress (factors, contentAFactors, N, swapLevel,
2507                              swapLevel2, x);
2508        if (!extension)
2509          normalize (factors);
2510        delete [] Aeval2;
2511        return factors;
2512      }
2513      else
2514        factors= CFList();
2515      //TODO case where factors.length() > 0
2516    }
2517  }
2518
2519  CFList uniFactors= buildUniFactors (biFactors, evaluation.getLast(), y);
2520
2521  sortByUniFactors (Aeval2, lengthAeval2, uniFactors, evaluation);
2522
2523  CFList * oldAeval= new CFList [lengthAeval2]; //TODO use bufAeval2 for this
2524  for (int i= 0; i < lengthAeval2; i++)
2525    oldAeval[i]= Aeval2[i];
2526
2527  getLeadingCoeffs (A, Aeval2, uniFactors, evaluation);
2528
2529  CFList biFactorsLCs;
2530  for (CFListIterator i= biFactors; i.hasItem(); i++)
2531    biFactorsLCs.append (LC (i.getItem(), 1));
2532
2533  Variable v;
2534  CFList leadingCoeffs= precomputeLeadingCoeff (LC (A, 1), biFactorsLCs, alpha,
2535                                          evaluation, Aeval2, lengthAeval2, v);
2536
2537  if (v.level() != 1)
2538  {
2539    A= swapvar (A, y, v);
2540    int i= A.level();
2541    CanonicalForm evalPoint;
2542    for (CFListIterator iter= evaluation; iter.hasItem(); iter++, i--)
2543    {
2544      if (i == v.level())
2545      {
2546        evalPoint= iter.getItem();
2547        iter.getItem()= evaluation.getLast();
2548        evaluation.removeLast();
2549        evaluation.append (evalPoint);
2550        break;
2551      }
2552    }
2553    for (i= 0; i < lengthAeval2; i++)
2554    {
2555      if (oldAeval[i].isEmpty())
2556        continue;
2557      if (oldAeval[i].getFirst().level() == v.level())
2558      {
2559        CFArray tmp= copy (oldAeval[i]);
2560        oldAeval[i]= biFactors;
2561        for (CFListIterator iter= oldAeval[i]; iter.hasItem(); iter++)
2562          iter.getItem()= swapvar (iter.getItem(), v, y);
2563        for (int ii= 0; ii < tmp.size(); ii++)
2564          tmp[ii]= swapvar (tmp[ii], v, y);
2565        CFArray tmp2= CFArray (tmp.size());
2566        CanonicalForm buf;
2567        for (int ii= 0; ii < tmp.size(); ii++)
2568        {
2569          buf= tmp[ii] (evaluation.getLast(),y);
2570          buf /= Lc (buf);
2571          tmp2[findItem (uniFactors, buf)-1]=tmp[ii];
2572        }
2573        biFactors= CFList();
2574        for (int j= 0; j < tmp2.size(); j++)
2575          biFactors.append (tmp2[j]);
2576      }
2577    }
2578  }
2579
2580  CFListIterator iter;
2581  CanonicalForm oldA= A;
2582  CFList oldBiFactors= biFactors;
2583  if (!leadingCoeffs.getFirst().inCoeffDomain())
2584  {
2585    CanonicalForm tmp= power (leadingCoeffs.getFirst(), biFactors.length() - 1);
2586    A *= tmp;
2587    tmp= leadingCoeffs.getFirst();
2588    iter= evaluation;
2589    for (int i= A.level(); i > 2; i--, iter++)
2590      tmp= tmp (iter.getItem(), i);
2591    if (!tmp.inCoeffDomain())
2592    {
2593      for (CFListIterator i= biFactors; i.hasItem(); i++)
2594      {
2595        i.getItem() *= tmp/LC (i.getItem(), 1);
2596        i.getItem() /= Lc (i.getItem());
2597      }
2598    }
2599  }
2600
2601  CanonicalForm LCmultiplier= leadingCoeffs.getFirst();
2602  bool LCmultiplierIsConst= LCmultiplier.inCoeffDomain();
2603  leadingCoeffs.removeFirst();
2604
2605  //prepare leading coefficients
2606  CFList* leadingCoeffs2= new CFList [lengthAeval2];
2607  prepareLeadingCoeffs (leadingCoeffs2, A.level(), leadingCoeffs, biFactors,
2608                        evaluation);
2609
2610  Aeval= evaluateAtEval (A, evaluation, 2);
2611  CanonicalForm hh= 1/Lc (Aeval.getFirst());
2612  for (iter= Aeval; iter.hasItem(); iter++)
2613    iter.getItem() *= hh;
2614
2615  A *= hh;
2616
2617
2618  CFListIterator iter2;
2619  CFList bufLeadingCoeffs2= leadingCoeffs2[lengthAeval2-1];
2620  bufBiFactors= biFactors;
2621  bufA= A;
2622  CanonicalForm bufLCmultiplier= LCmultiplier;
2623  CanonicalForm testVars;
2624  if (!LCmultiplierIsConst)
2625  {
2626    testVars= Variable (2);
2627    for (int i= 0; i < lengthAeval2; i++)
2628    {
2629      if (!oldAeval[i].isEmpty())
2630        testVars *= oldAeval[i].getFirst().mvar();
2631    }
2632  }
2633  CFList bufFactors= CFList();
2634  bool LCheuristic= false;
2635  if (LucksWangSparseHeuristic (A, biFactors, 2, leadingCoeffs2[lengthAeval2-1],
2636                                 factors))
2637  {
2638    int check= biFactors.length();
2639    int * index= new int [factors.length()];
2640    CFList oldFactors= factors;
2641    factors= recoverFactors (A, factors, index);
2642
2643    if (check == factors.length())
2644    {
2645      if (extension)
2646        factors= extNonMonicFactorRecombination (factors, bufA, info);
2647
2648      if (v.level() != 1)
2649      {
2650        for (iter= factors; iter.hasItem(); iter++)
2651          iter.getItem()= swapvar (iter.getItem(), v, y);
2652      }
2653
2654      appendSwapDecompress (factors, contentAFactors, N, swapLevel,
2655                            swapLevel2, x);
2656      if (!extension)
2657        normalize (factors);
2658      delete [] index;
2659      delete [] Aeval2;
2660      return factors;
2661    }
2662    else if (factors.length() > 0)
2663    {
2664      int oneCount= 0;
2665      CFList l;
2666      for (int i= 0; i < check; i++)
2667      {
2668        if (index[i] == 1)
2669        {
2670          iter=biFactors;
2671          for (int j=1; j <= i-oneCount; j++)
2672            iter++;
2673          iter.remove (1);
2674          for (int j= 0; j < lengthAeval2; j++)
2675          {
2676            l= leadingCoeffs2[j];
2677            iter= l;
2678            for (int k=1; k <= i-oneCount; k++)
2679              iter++;
2680            iter.remove (1);
2681            leadingCoeffs2[j]=l;
2682          }
2683          oneCount++;
2684        }
2685      }
2686      bufFactors= factors;
2687      factors= CFList();
2688    }
2689    else if (!LCmultiplierIsConst && factors.length() == 0)
2690    {
2691      LCheuristic= true;
2692      factors= oldFactors;
2693      CanonicalForm cont;
2694      CFList contents, LCs;
2695      int index=1;
2696      bool foundTrueMultiplier= false;
2697      for (iter= factors; iter.hasItem(); iter++, index++)
2698      {
2699        cont= content (iter.getItem(), 1);
2700        cont= gcd (cont , LCmultiplier);
2701        contents.append (cont);
2702        if (cont.inCoeffDomain()) // trivial content->LCmultiplier needs to go there
2703        {
2704          foundTrueMultiplier= true;
2705          int index2= 1;
2706          for (iter2= leadingCoeffs2[lengthAeval2-1]; iter2.hasItem(); iter2++,
2707                                                                    index2++)
2708          {
2709            if (index2 == index)
2710              continue;
2711            iter2.getItem() /= LCmultiplier;
2712          }
2713          A= oldA;
2714          leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
2715          for (int i= lengthAeval2-1; i > -1; i--)
2716            leadingCoeffs2[i]= CFList();
2717          prepareLeadingCoeffs (leadingCoeffs2, A.level(), leadingCoeffs,
2718                                biFactors, evaluation );
2719          Aeval= evaluateAtEval (A, evaluation, 2);
2720
2721          hh= 1/Lc (Aeval.getFirst());
2722
2723          for (iter2= Aeval; iter2.hasItem(); iter2++)
2724            iter2.getItem() *= hh;
2725
2726          A *= hh;
2727          break;
2728        }
2729        else
2730          LCs.append (LC (iter.getItem()/cont, 1));
2731      }
2732      if (!foundTrueMultiplier)
2733      {
2734        index= 1;
2735        iter2= factors;
2736        bool foundMultiplier= false;
2737        for (iter= contents; iter.hasItem(); iter++, iter2++, index++)
2738        {
2739          if (fdivides (iter.getItem(), LCmultiplier))
2740          {
2741            if ((LCmultiplier/iter.getItem()).inCoeffDomain() &&
2742                !isOnlyLeadingCoeff(iter2.getItem())) //content divides LCmultiplier completely and factor consists of more terms than just the leading coeff
2743            {
2744              int index2= 1;
2745              for (CFListIterator iter3= leadingCoeffs2[lengthAeval2-1];
2746                   iter3.hasItem(); iter3++, index2++)
2747              {
2748                if (index2 == index)
2749                {
2750                  iter3.getItem() /= LCmultiplier;
2751                  break;
2752                }
2753              }
2754              A /= LCmultiplier;
2755              foundMultiplier= true;
2756              iter.getItem()= 1;
2757            }
2758          }
2759        }
2760        // coming from above: divide out more LCmultiplier if possible
2761        if (foundMultiplier)
2762        {
2763          foundMultiplier= false;
2764          index=1;
2765          iter2= factors;
2766          for (iter= contents; iter.hasItem(); iter++, iter2++, index++)
2767          {
2768            if (!iter.getItem().isOne() &&
2769                fdivides (iter.getItem(), LCmultiplier))
2770            {
2771              if (!isOnlyLeadingCoeff (iter2.getItem())) // factor is more than just leading coeff
2772              {
2773                int index2= 1;
2774                for (iter2= leadingCoeffs2[lengthAeval2-1]; iter2.hasItem();
2775                     iter2++, index2++)
2776                {
2777                  if (index2 == index)
2778                  {
2779                    iter2.getItem() /= iter.getItem();
2780                    foundMultiplier= true;
2781                    break;
2782                  }
2783                }
2784                A /= iter.getItem();
2785                LCmultiplier /= iter.getItem();
2786                iter.getItem()= 1;
2787              }
2788              else if (fdivides (getVars (LCmultiplier), testVars))//factor consists of just leading coeff
2789              {
2790                //TODO maybe use a sqrffree decomposition of LCmultiplier as below
2791                Variable xx= Variable (2);
2792                CanonicalForm vars;
2793                vars= power (xx, degree (LC (getItem(oldBiFactors, index),1),
2794                                          xx));
2795                for (int i= 0; i < lengthAeval2; i++)
2796                {
2797                  if (oldAeval[i].isEmpty())
2798                    continue;
2799                  xx= oldAeval[i].getFirst().mvar();
2800                  vars *= power (xx, degree (LC (getItem(oldAeval[i], index),1),
2801                                             xx));
2802                }
2803                if (myGetVars(content(getItem(leadingCoeffs2[lengthAeval2-1],index),1))
2804                    /myGetVars (LCmultiplier) == vars)
2805                {
2806                  int index2= 1;
2807                  for (iter2= leadingCoeffs2[lengthAeval2-1]; iter2.hasItem();
2808                       iter2++, index2++)
2809                  {
2810                    if (index2 == index)
2811                    {
2812                      iter2.getItem() /= LCmultiplier;
2813                      foundMultiplier= true;
2814                      break;
2815                    }
2816                  }
2817                  A /= LCmultiplier;
2818                  iter.getItem()= 1;
2819                }
2820              }
2821            }
2822          }
2823        }
2824        else
2825        {
2826          CanonicalForm pLCs= prod (LCs);
2827          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
2828          {
2829            A= oldA;
2830            iter2= leadingCoeffs2[lengthAeval2-1];
2831            for (iter= contents; iter.hasItem(); iter++, iter2++)
2832              iter2.getItem() /= iter.getItem();
2833            foundMultiplier= true;
2834          }
2835          if (!foundMultiplier && fdivides (getVars (LCmultiplier), testVars))
2836          {
2837            Variable xx;
2838            CFList vars1;
2839            CFFList sqrfMultiplier= sqrFree (LCmultiplier);
2840            if (sqrfMultiplier.getFirst().factor().inCoeffDomain())
2841              sqrfMultiplier.removeFirst();
2842            sqrfMultiplier= sortCFFListByNumOfVars (sqrfMultiplier);
2843            xx= Variable (2);
2844            for (iter= oldBiFactors; iter.hasItem(); iter++)
2845              vars1.append (power (xx, degree (LC (iter.getItem(),1), xx)));
2846            for (int i= 0; i < lengthAeval2; i++)
2847            {
2848              if (oldAeval[i].isEmpty())
2849                continue;
2850              xx= oldAeval[i].getFirst().mvar();
2851              iter2= vars1;
2852              for (iter= oldAeval[i]; iter.hasItem(); iter++, iter2++)
2853                iter2.getItem() *= power(xx,degree (LC (iter.getItem(),1), xx));
2854            }
2855            CanonicalForm tmp;
2856            iter2= vars1;
2857            for (iter= leadingCoeffs2[lengthAeval2-1]; iter.hasItem(); iter++,
2858                                                                    iter2++)
2859            {
2860              tmp= iter.getItem()/LCmultiplier;
2861              for (int i=1; i <= tmp.level(); i++)
2862              {
2863                if (degree(tmp,i) > 0 &&
2864                    (degree(iter2.getItem(),i) > degree (tmp,i)))
2865                  iter2.getItem() /= power (Variable (i), degree (tmp,i));
2866              }
2867            }
2868            int multi;
2869            for (CFFListIterator ii= sqrfMultiplier; ii.hasItem(); ii++)
2870            {
2871              multi= 0;
2872              for (iter= vars1; iter.hasItem(); iter++)
2873              {
2874                tmp= iter.getItem();
2875                while (fdivides (myGetVars (ii.getItem().factor()), tmp))
2876                {
2877                  multi++;
2878                  tmp /= myGetVars (ii.getItem().factor());
2879                }
2880              }
2881              if (multi == ii.getItem().exp())
2882              {
2883                index= 1;
2884                for (iter= vars1; iter.hasItem(); iter++, index++)
2885                {
2886                  while (fdivides (myGetVars(ii.getItem().factor()),
2887                                   iter.getItem()
2888                                  )
2889                        )
2890                  {
2891                    int index2= 1;
2892                    for (iter2= leadingCoeffs2[lengthAeval2-1]; iter2.hasItem();
2893                         iter2++, index2++)
2894                    {
2895                      if (index2 == index)
2896                        continue;
2897                      else
2898                      {
2899                        tmp= ii.getItem().factor();
2900                        iter2.getItem() /= tmp;
2901                        CFListIterator iter3= evaluation;
2902                        for (int jj= A.level(); jj > 2; jj--, iter3++)
2903                          tmp= tmp (iter3.getItem(), jj);
2904                        if (!tmp.inCoeffDomain())
2905                        {
2906                          int index3= 1;
2907                          for (iter3= biFactors; iter3.hasItem(); iter3++,
2908                                                                  index3++)
2909                          {
2910                            if (index3 == index2)
2911                            {
2912                              iter3.getItem() /= tmp;
2913                              iter3.getItem() /= Lc (iter3.getItem());
2914                              break;
2915                            }
2916                          }
2917                        }
2918                        A /= ii.getItem().factor();
2919                      }
2920                    }
2921                    iter.getItem() /= getVars (ii.getItem().factor());
2922                  }
2923                }
2924              }
2925              else
2926              {
2927                index= 1;
2928                for (iter= vars1; iter.hasItem(); iter++, index++)
2929                {
2930                  if (!fdivides (myGetVars (ii.getItem().factor()),
2931                                 iter.getItem()
2932                                )
2933                     )
2934                  {
2935                    int index2= 1;
2936                    for (iter2= leadingCoeffs2[lengthAeval2-1]; iter2.hasItem();
2937                         iter2++, index2++)
2938                    {
2939                      if (index2 == index)
2940                      {
2941                        tmp= power (ii.getItem().factor(), ii.getItem().exp());
2942                        iter2.getItem() /= tmp;
2943                        A /= tmp;
2944                        CFListIterator iter3= evaluation;
2945                        for (int jj= A.level(); jj > 2; jj--, iter3++)
2946                          tmp= tmp (iter3.getItem(), jj);
2947                        if (!tmp.inCoeffDomain())
2948                        {
2949                          int index3= 1;
2950                          for (iter3= biFactors; iter3.hasItem(); iter3++,
2951                                                                  index3++)
2952                          {
2953                            if (index3 == index2)
2954                            {
2955                              iter3.getItem() /= tmp;
2956                              iter3.getItem() /= Lc (iter3.getItem());
2957                              break;
2958                            }
2959                          }
2960                        }
2961                      }
2962                    }
2963                  }
2964                }
2965              }
2966            }
2967          }
2968        }
2969
2970        // patch everything together again
2971        leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
2972        for (int i= lengthAeval2-1; i > -1; i--)
2973          leadingCoeffs2[i]= CFList();
2974        prepareLeadingCoeffs (leadingCoeffs2,A.level(),leadingCoeffs, biFactors,
2975                              evaluation);
2976        Aeval= evaluateAtEval (A, evaluation, 2);
2977
2978        hh= 1/Lc (Aeval.getFirst());
2979
2980        for (CFListIterator i= Aeval; i.hasItem(); i++)
2981          i.getItem() *= hh;
2982
2983        A *= hh;
2984      }
2985      factors= CFList();
2986      if (!fdivides (LC (oldA,1),prod (leadingCoeffs2[lengthAeval2-1])))
2987      {
2988        LCheuristic= false;
2989        A= bufA;
2990        biFactors= bufBiFactors;
2991        leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
2992        LCmultiplier= bufLCmultiplier;
2993      }
2994    }
2995    else
2996      factors= CFList();
2997    delete [] index;
2998  }
2999
3000  if (!LCheuristic && !LCmultiplierIsConst && bufFactors.isEmpty()
3001      && fdivides (getVars (LCmultiplier), testVars))
3002  {
3003    LCheuristic= true;
3004    int index;
3005    Variable xx;
3006    CFList vars1;
3007    CFFList sqrfMultiplier= sqrFree (LCmultiplier);
3008    if (sqrfMultiplier.getFirst().factor().inCoeffDomain())
3009      sqrfMultiplier.removeFirst();
3010    sqrfMultiplier= sortCFFListByNumOfVars (sqrfMultiplier);
3011    xx= Variable (2);
3012    for (iter= oldBiFactors; iter.hasItem(); iter++)
3013      vars1.append (power (xx, degree (LC (iter.getItem(),1), xx)));
3014    for (int i= 0; i < lengthAeval2; i++)
3015    {
3016      if (oldAeval[i].isEmpty())
3017        continue;
3018      xx= oldAeval[i].getFirst().mvar();
3019      iter2= vars1;
3020      for (iter= oldAeval[i]; iter.hasItem(); iter++, iter2++)
3021        iter2.getItem() *= power (xx, degree (LC (iter.getItem(),1), xx));
3022    }
3023    CanonicalForm tmp;
3024    iter2= vars1;
3025    for (iter= leadingCoeffs2[lengthAeval2-1]; iter.hasItem(); iter++, iter2++)
3026    {
3027      tmp= iter.getItem()/LCmultiplier;
3028      for (int i=1; i <= tmp.level(); i++)
3029      {
3030        if (degree (tmp,i) > 0 && (degree (iter2.getItem(),i) > degree (tmp,i)))
3031          iter2.getItem() /= power (Variable (i), degree (tmp,i));
3032      }
3033    }
3034    int multi;
3035    for (CFFListIterator ii= sqrfMultiplier; ii.hasItem(); ii++)
3036    {
3037      multi= 0;
3038      for (iter= vars1; iter.hasItem(); iter++)
3039      {
3040        tmp= iter.getItem();
3041        while (fdivides (myGetVars (ii.getItem().factor()), tmp))
3042        {
3043          multi++;
3044          tmp /= myGetVars (ii.getItem().factor());
3045        }
3046      }
3047      if (multi == ii.getItem().exp())
3048      {
3049        index= 1;
3050        for (iter= vars1; iter.hasItem(); iter++, index++)
3051        {
3052          while (fdivides (myGetVars (ii.getItem().factor()), iter.getItem()))
3053          {
3054            int index2= 1;
3055            for (iter2= leadingCoeffs2[lengthAeval2-1]; iter2.hasItem();iter2++,
3056                                                                      index2++)
3057            {
3058              if (index2 == index)
3059                continue;
3060              else
3061              {
3062                tmp= ii.getItem().factor();
3063                iter2.getItem() /= tmp;
3064                CFListIterator iter3= evaluation;
3065                for (int jj= A.level(); jj > 2; jj--, iter3++)
3066                  tmp= tmp (iter3.getItem(), jj);
3067                if (!tmp.inCoeffDomain())
3068                {
3069                  int index3= 1;
3070                  for (iter3= biFactors; iter3.hasItem(); iter3++, index3++)
3071                  {
3072                    if (index3 == index2)
3073                    {
3074                      iter3.getItem() /= tmp;
3075                      iter3.getItem() /= Lc (iter3.getItem());
3076                      break;
3077                    }
3078                  }
3079                }
3080                A /= ii.getItem().factor();
3081              }
3082            }
3083            iter.getItem() /= getVars (ii.getItem().factor());
3084          }
3085        }
3086      }
3087      else
3088      {
3089        index= 1;
3090        for (iter= vars1; iter.hasItem(); iter++, index++)
3091        {
3092          if (!fdivides (myGetVars (ii.getItem().factor()), iter.getItem()))
3093          {
3094            int index2= 1;
3095            for (iter2= leadingCoeffs2[lengthAeval2-1];iter2.hasItem();iter2++,
3096                                                                      index2++)
3097            {
3098              if (index2 == index)
3099              {
3100                tmp= power (ii.getItem().factor(), ii.getItem().exp());
3101                iter2.getItem() /= tmp;
3102                A /= tmp;
3103                CFListIterator iter3= evaluation;
3104                for (int jj= A.level(); jj > 2; jj--, iter3++)
3105                  tmp= tmp (iter3.getItem(), jj);
3106                if (!tmp.inCoeffDomain())
3107                {
3108                  int index3= 1;
3109                  for (iter3= biFactors; iter3.hasItem(); iter3++, index3++)
3110                  {
3111                    if (index3 == index2)
3112                    {
3113                      iter3.getItem() /= tmp;
3114                      iter3.getItem() /= Lc (iter3.getItem());
3115                      break;
3116                    }
3117                  }
3118                }
3119              }
3120            }
3121          }
3122        }
3123      }
3124    }
3125
3126    leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
3127    for (int i= lengthAeval2-1; i > -1; i--)
3128      leadingCoeffs2[i]= CFList();
3129    prepareLeadingCoeffs (leadingCoeffs2,A.level(),leadingCoeffs, biFactors,
3130                          evaluation);
3131    Aeval= evaluateAtEval (A, evaluation, 2);
3132
3133    hh= 1/Lc (Aeval.getFirst());
3134
3135    for (CFListIterator i= Aeval; i.hasItem(); i++)
3136      i.getItem() *= hh;
3137
3138    A *= hh;
3139
3140    if (!fdivides (LC (oldA,1),prod (leadingCoeffs2[lengthAeval2-1])))
3141    {
3142      LCheuristic= false;
3143      A= bufA;
3144      biFactors= bufBiFactors;
3145      leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
3146      LCmultiplier= bufLCmultiplier;
3147    }
3148  }
3149
3150tryAgainWithoutHeu:
3151  A= shift2Zero (A, Aeval, evaluation);
3152
3153  for (iter= biFactors; iter.hasItem(); iter++)
3154    iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
3155
3156  for (int i= 0; i < lengthAeval2-1; i++)
3157    leadingCoeffs2[i]= CFList();
3158  for (iter= leadingCoeffs2[lengthAeval2-1]; iter.hasItem(); iter++)
3159  {
3160    iter.getItem()= shift2Zero (iter.getItem(), list, evaluation);
3161    for (int i= A.level() - 4; i > -1; i--)
3162    {
3163      if (i + 1 == lengthAeval2-1)
3164        leadingCoeffs2[i].append (iter.getItem() (0, i + 4));
3165      else
3166        leadingCoeffs2[i].append (leadingCoeffs2[i+1].getLast() (0, i + 4));
3167    }
3168  }
3169
3170  CFArray Pi;
3171  CFList diophant;
3172  int* liftBounds= new int [A.level() - 1];
3173  int liftBoundsLength= A.level() - 1;
3174  for (int i= 0; i < liftBoundsLength; i++)
3175    liftBounds [i]= degree (A, i + 2) + 1;
3176
3177  Aeval.removeFirst();
3178  bool noOneToOne= false;
3179  factors= nonMonicHenselLift (Aeval, biFactors, leadingCoeffs2, diophant,
3180                               Pi, liftBounds, liftBoundsLength, noOneToOne);
3181
3182  if (!noOneToOne)
3183  {
3184    int check= factors.length();
3185    A= oldA;
3186    factors= recoverFactors (A, factors, evaluation);
3187    if (check != factors.length())
3188      noOneToOne= true;
3189    else
3190      factors= Union (factors, bufFactors);
3191
3192    if (extension && !noOneToOne)
3193      factors= extNonMonicFactorRecombination (factors, A, info);
3194  }
3195  if (noOneToOne)
3196  {
3197
3198    if (!LCmultiplierIsConst && LCheuristic)
3199    {
3200      A= bufA;
3201      biFactors= bufBiFactors;
3202      leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
3203      delete [] liftBounds;
3204      LCheuristic= false;
3205      goto tryAgainWithoutHeu;
3206      //something probably went wrong in the heuristic
3207    }
3208
3209    A= shift2Zero (oldA, Aeval, evaluation);
3210    biFactors= oldBiFactors;
3211    for (iter= biFactors; iter.hasItem(); iter++)
3212      iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
3213    CanonicalForm LCA= LC (Aeval.getFirst(), 1);
3214    CanonicalForm yToLift= power (y, lift);
3215    CFListIterator i= biFactors;
3216    lift= degree (i.getItem(), 2) + degree (LC (i.getItem(), 1)) + 1;
3217    i++;
3218
3219    for (; i.hasItem(); i++)
3220      lift= tmax (lift,
3221                  degree (i.getItem(), 2) + degree (LC (i.getItem(), 1)) + 1);
3222
3223    lift= tmax (degree (Aeval.getFirst() , 2) + 1, lift);
3224
3225    i= biFactors;
3226    yToLift= power (y, lift);
3227    CanonicalForm dummy;
3228    for (; i.hasItem(); i++)
3229    {
3230      LCA= LC (i.getItem(), 1);
3231      extgcd (LCA, yToLift, LCA, dummy);
3232      i.getItem()= mod (i.getItem()*LCA, yToLift);
3233    }
3234
3235    liftBoundsLength= F.level() - 1;
3236    liftBounds= liftingBounds (A, lift);
3237
3238    CFList MOD;
3239    bool earlySuccess;
3240    CFList earlyFactors, liftedFactors;
3241    TIMING_START (fac_fq_hensel_lift);
3242    liftedFactors= henselLiftAndEarly
3243                   (A, MOD, liftBounds, earlySuccess, earlyFactors,
3244                    Aeval, biFactors, evaluation, info);
3245    TIMING_END_AND_PRINT (fac_fq_hensel_lift, "time for hensel lifting: ");
3246
3247    if (!extension)
3248    {
3249      TIMING_START (fac_fq_factor_recombination);
3250      factors= factorRecombination (A, liftedFactors, MOD);
3251      TIMING_END_AND_PRINT (fac_fq_factor_recombination,
3252                            "time for factor recombination: ");
3253    }
3254    else
3255    {
3256      TIMING_START (fac_fq_factor_recombination);
3257      factors= extFactorRecombination (liftedFactors, A, MOD, info, evaluation);
3258      TIMING_END_AND_PRINT (fac_fq_factor_recombination,
3259                            "time for factor recombination: ");
3260    }
3261
3262    if (earlySuccess)
3263      factors= Union (factors, earlyFactors);
3264    if (!extension)
3265    {
3266      for (CFListIterator i= factors; i.hasItem(); i++)
3267      {
3268        int kk= Aeval.getLast().level();
3269        for (CFListIterator j= evaluation; j.hasItem(); j++, kk--)
3270        {
3271          if (i.getItem().level() < kk)
3272            continue;
3273          i.getItem()= i.getItem() (Variable (kk) - j.getItem(), kk);
3274        }
3275      }
3276    }
3277  }
3278
3279  if (v.level() != 1)
3280  {
3281    for (CFListIterator iter= factors; iter.hasItem(); iter++)
3282      iter.getItem()= swapvar (iter.getItem(), v, y);
3283  }
3284
3285  swap (factors, swapLevel, swapLevel2, x);
3286  append (factors, contentAFactors);
3287  decompress (factors, N);
3288  if (!extension)
3289    normalize (factors);
3290
3291  delete[] liftBounds;
3292
3293  return factors;
3294}
3295
3296/// multivariate factorization over an extension of the initial field
3297CFList
3298extFactorize (const CanonicalForm& F, const ExtensionInfo& info)
3299{
3300  CanonicalForm A= F;
3301
3302  Variable alpha= info.getAlpha();
3303  Variable beta= info.getBeta();
3304  int k= info.getGFDegree();
3305  char cGFName= info.getGFName();
3306  CanonicalForm delta= info.getDelta();
3307  bool GF= (CFFactory::gettype() == GaloisFieldDomain);
3308  Variable w= Variable (1);
3309
3310  CFList factors;
3311  if (!GF && alpha == w)  // we are in F_p
3312  {
3313    CFList factors;
3314    bool extension= true;
3315    int p= getCharacteristic();
3316    if (p < 7)
3317    {
3318      if (p == 2)
3319        setCharacteristic (getCharacteristic(), 6, 'Z');
3320      else if (p == 3)
3321        setCharacteristic (getCharacteristic(), 4, 'Z');
3322      else if (p == 5)
3323        setCharacteristic (getCharacteristic(), 3, 'Z');
3324      ExtensionInfo info= ExtensionInfo (extension);
3325      A= A.mapinto();
3326      factors= multiFactorize (A, info);
3327
3328      CanonicalForm mipo= gf_mipo;
3329      setCharacteristic (getCharacteristic());
3330      Variable vBuf= rootOf (mipo.mapinto());
3331      for (CFListIterator j= factors; j.hasItem(); j++)
3332        j.getItem()= GF2FalphaRep (j.getItem(), vBuf);
3333    }
3334    else if (p >= 7 && p*p < (1<<16)) // pass to GF if possible
3335    {
3336      setCharacteristic (getCharacteristic(), 2, 'Z');
3337      ExtensionInfo info= ExtensionInfo (extension);
3338      A= A.mapinto();
3339      factors= multiFactorize (A, info);
3340
3341      CanonicalForm mipo= gf_mipo;
3342      setCharacteristic (getCharacteristic());
3343      Variable vBuf= rootOf (mipo.mapinto());
3344      for (CFListIterator j= factors; j.hasItem(); j++)
3345        j.getItem()= GF2FalphaRep (j.getItem(), vBuf);
3346    }
3347    else  // not able to pass to GF, pass to F_p(\alpha)
3348    {
3349      CanonicalForm mipo= randomIrredpoly (2, w);
3350      Variable v= rootOf (mipo);
3351      ExtensionInfo info= ExtensionInfo (v);
3352      factors= multiFactorize (A, info);
3353    }
3354    return factors;
3355  }
3356  else if (!GF && (alpha != w)) // we are in F_p(\alpha)
3357  {
3358    if (k == 1) // need factorization over F_p
3359    {
3360      int extDeg= degree (getMipo (alpha));
3361      extDeg++;
3362      CanonicalForm mipo= randomIrredpoly (extDeg + 1, w);
3363      Variable v= rootOf (mipo);
3364      ExtensionInfo info= ExtensionInfo (v);
3365      factors= multiFactorize (A, info);
3366    }
3367    else
3368    {
3369      if (beta == w)
3370      {
3371        Variable v= chooseExtension (alpha, beta, k);
3372        CanonicalForm primElem, imPrimElem;
3373        bool primFail= false;
3374        Variable vBuf;
3375        primElem= primitiveElement (alpha, vBuf, primFail);
3376        ASSERT (!primFail, "failure in integer factorizer");
3377        if (primFail)
3378          ; //ERROR
3379        else
3380          imPrimElem= mapPrimElem (primElem, vBuf, v);
3381
3382        CFList source, dest;
3383        CanonicalForm bufA= mapUp (A, alpha, v, primElem, imPrimElem,
3384                                   source, dest);
3385        ExtensionInfo info= ExtensionInfo (v, alpha, imPrimElem, primElem);
3386        factors= multiFactorize (bufA, info);
3387      }
3388      else
3389      {
3390        Variable v= chooseExtension (alpha, beta, k);
3391        CanonicalForm primElem, imPrimElem;
3392        bool primFail= false;
3393        Variable vBuf;
3394        ASSERT (!primFail, "failure in integer factorizer");
3395        if (primFail)
3396          ; //ERROR
3397        else
3398          imPrimElem= mapPrimElem (delta, beta, v);
3399
3400        CFList source, dest;
3401        CanonicalForm bufA= mapDown (A, info, source, dest);
3402        source= CFList();
3403        dest= CFList();
3404        bufA= mapUp (bufA, beta, v, delta, imPrimElem, source, dest);
3405        ExtensionInfo info= ExtensionInfo (v, beta, imPrimElem, delta);
3406        factors= multiFactorize (bufA, info);
3407      }
3408    }
3409    return factors;
3410  }
3411  else // we are in GF (p^k)
3412  {
3413    int p= getCharacteristic();
3414    int extensionDeg= getGFDegree();
3415    bool extension= true;
3416    if (k == 1) // need factorization over F_p
3417    {
3418      extensionDeg++;
3419      if (pow ((double) p, (double) extensionDeg) < (1<<16))
3420      // pass to GF(p^k+1)
3421      {
3422        CanonicalForm mipo= gf_mipo;
3423        setCharacteristic (p);
3424        Variable vBuf= rootOf (mipo.mapinto());
3425        A= GF2FalphaRep (A, vBuf);
3426        setCharacteristic (p, extensionDeg, 'Z');
3427        ExtensionInfo info= ExtensionInfo (extension);
3428        factors= multiFactorize (A.mapinto(), info);
3429      }
3430      else // not able to pass to another GF, pass to F_p(\alpha)
3431      {
3432        CanonicalForm mipo= gf_mipo;
3433        setCharacteristic (p);
3434        Variable vBuf= rootOf (mipo.mapinto());
3435        A= GF2FalphaRep (A, vBuf);
3436        Variable v= chooseExtension (vBuf, beta, k);
3437        ExtensionInfo info= ExtensionInfo (v, extension);
3438        factors= multiFactorize (A, info);
3439      }
3440    }
3441    else // need factorization over GF (p^k)
3442    {
3443      if (pow ((double) p, (double) 2*extensionDeg) < (1<<16))
3444      // pass to GF(p^2k)
3445      {
3446        setCharacteristic (p, 2*extensionDeg, 'Z');
3447        ExtensionInfo info= ExtensionInfo (k, cGFName, extension);
3448        factors= multiFactorize (GFMapUp (A, extensionDeg), info);
3449        setCharacteristic (p, extensionDeg, cGFName);
3450      }
3451      else // not able to pass to GF (p^2k), pass to F_p (\alpha)
3452      {
3453        CanonicalForm mipo= gf_mipo;
3454        setCharacteristic (p);
3455        Variable v1= rootOf (mipo.mapinto());
3456        A= GF2FalphaRep (A, v1);
3457        Variable v2= chooseExtension (v1, v1, k);
3458        CanonicalForm primElem, imPrimElem;
3459        bool primFail= false;
3460        Variable vBuf;
3461        primElem= primitiveElement (v1, v1, primFail);
3462        if (primFail)
3463          ; //ERROR
3464        else
3465          imPrimElem= mapPrimElem (primElem, v1, v2);
3466        CFList source, dest;
3467        CanonicalForm bufA= mapUp (A, v1, v2, primElem, imPrimElem,
3468                                     source, dest);
3469        ExtensionInfo info= ExtensionInfo (v2, v1, imPrimElem, primElem);
3470        factors= multiFactorize (bufA, info);
3471        setCharacteristic (p, k, cGFName);
3472        for (CFListIterator i= factors; i.hasItem(); i++)
3473          i.getItem()= Falpha2GFRep (i.getItem());
3474      }
3475    }
3476    return factors;
3477  }
3478}
3479
3480#endif
3481/* HAVE_NTL */
3482
Note: See TracBrowser for help on using the repository browser.