source: git/factory/facFqFactorize.cc @ e3cb321

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