source: git/factory/facFqFactorize.cc @ c7b56e2

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