source: git/factory/facFqFactorize.cc @ 86faff

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