source: git/factory/facFqFactorize.cc @ 7762549

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