source: git/factory/facFqFactorize.cc @ e5fdcc4

spielwiese
Last change on this file since e5fdcc4 was d92e66, checked in by Martin Lee <martinlee84@…>, 11 years ago
chg: content computation
  • Property mode set to 100644
File size: 97.5 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                       const CFList& uniFactors, const CFList& evaluation
1941                      )
1942{
1943  CFListIterator iter;
1944  CFList LCs;
1945  for (int j= 0; j < A.level() - 2; j++)
1946  {
1947    if (!Aeval[j].isEmpty())
1948    {
1949      LCs= CFList();
1950      for (iter= Aeval[j]; iter.hasItem(); iter++)
1951        LCs.append (LC (iter.getItem(), 1));
1952      //normalize (LCs);
1953      Aeval[j]= LCs;
1954    }
1955  }
1956}
1957
1958void sortByUniFactors (CFList*& Aeval, int AevalLength,
1959                       const CFList& uniFactors, const CFList& evaluation
1960                      )
1961{
1962  CanonicalForm evalPoint;
1963  int i;
1964  CFListIterator iter, iter2;
1965  Variable v;
1966  CFList LCs, buf;
1967  CFArray l;
1968  int pos, index;
1969  for (int j= 0; j < AevalLength; j++)
1970  {
1971    if (!Aeval[j].isEmpty())
1972    {
1973      i= evaluation.length() + 1;
1974      for (iter= evaluation; iter.hasItem(); iter++, i--)
1975      {
1976        if (i == Aeval[j].getFirst().level())
1977        {
1978          evalPoint= iter.getItem();
1979          break;
1980        }
1981      }
1982
1983      v= Variable (i);
1984      if (Aeval[j].length() > uniFactors.length())
1985        Aeval[j]= recombination (Aeval[j], uniFactors, 1,
1986                                 Aeval[j].length() - uniFactors.length() + 1,
1987                                 evalPoint, v);
1988
1989      buf= buildUniFactors (Aeval[j], evalPoint, v);
1990      l= CFArray (uniFactors.length());
1991      index= 1;
1992      for (iter= buf; iter.hasItem(); iter++, index++)
1993      {
1994        pos= findItem (uniFactors, iter.getItem());
1995        if (pos)
1996          l[pos-1]= getItem (Aeval[j], index);
1997      }
1998      buf= conv (l);
1999      Aeval [j]= buf;
2000
2001      buf= buildUniFactors (Aeval[j], evalPoint, v);
2002    }
2003  }
2004}
2005
2006CFList
2007buildUniFactors (const CFList& biFactors, const CanonicalForm& evalPoint,
2008                 const Variable& y)
2009{
2010  CFList result;
2011  CanonicalForm tmp;
2012  for (CFListIterator i= biFactors; i.hasItem(); i++)
2013  {
2014    tmp= mod (i.getItem(), y - evalPoint);
2015    tmp /= Lc (tmp);
2016    result.append (tmp);
2017  }
2018  return result;
2019}
2020
2021void refineBiFactors (const CanonicalForm& A, CFList& biFactors,
2022                      CFList* const& Aeval, const CFList& evaluation,
2023                      int minFactorsLength)
2024{
2025  CFListIterator iter;
2026  CanonicalForm evalPoint;
2027  int i;
2028  Variable v;
2029  Variable y= Variable (2);
2030  CFList list;
2031  for (int j= 0; j < A.level() - 2; j++)
2032  {
2033    if (Aeval[j].length() == minFactorsLength)
2034    {
2035      i= A.level();
2036
2037      for (iter= evaluation; iter.hasItem(); iter++, i--)
2038      {
2039        if (i == Aeval[j].getFirst().level())
2040        {
2041          evalPoint= iter.getItem();
2042          break;
2043        }
2044      }
2045
2046      v= Variable (i);
2047      list= buildUniFactors (Aeval[j], evalPoint, v);
2048
2049      biFactors= recombination (biFactors, list, 1,
2050                                biFactors.length() - list.length() + 1,
2051                                evaluation.getLast(), y);
2052      return;
2053    }
2054  }
2055}
2056
2057void prepareLeadingCoeffs (CFList*& LCs, int n, const CFList& leadingCoeffs,
2058                           const CFList& biFactors, const CFList& evaluation)
2059{
2060  CFList l= leadingCoeffs;
2061  LCs [n-3]= l;
2062  CFListIterator j;
2063  CFListIterator iter= evaluation;
2064  for (int i= n - 1; i > 2; i--, iter++)
2065  {
2066    for (j= l; j.hasItem(); j++)
2067      j.getItem()= j.getItem() (iter.getItem(), i + 1);
2068    LCs [i - 3]= l;
2069  }
2070  l= LCs [0];
2071  for (CFListIterator i= l; i.hasItem(); i++)
2072    i.getItem()= i.getItem() (iter.getItem(), 3);
2073  CFListIterator ii= biFactors;
2074  CFList normalizeFactor;
2075  for (CFListIterator i= l; i.hasItem(); i++, ii++)
2076    normalizeFactor.append (Lc (LC (ii.getItem(), 1))/Lc (i.getItem()));
2077  for (int i= 0; i < n-2; i++)
2078  {
2079    ii= normalizeFactor;
2080    for (j= LCs [i]; j.hasItem(); j++, ii++)
2081      j.getItem() *= ii.getItem();
2082  }
2083}
2084
2085CFList
2086extNonMonicFactorRecombination (const CFList& factors, const CanonicalForm& F,
2087                                const ExtensionInfo& info)
2088{
2089  Variable alpha= info.getAlpha();
2090  Variable beta= info.getBeta();
2091  CanonicalForm gamma= info.getGamma();
2092  CanonicalForm delta= info.getDelta();
2093  int k= info.getGFDegree();
2094  CFList source, dest;
2095
2096  int degMipoBeta= 1;
2097  if (!k && beta != Variable(1))
2098    degMipoBeta= degree (getMipo (beta));
2099
2100  CFList T, S;
2101  T= factors;
2102  int s= 1;
2103  CFList result;
2104  CanonicalForm quot, buf= F;
2105
2106  CanonicalForm g;
2107  CanonicalForm buf2;
2108  int * v= new int [T.length()];
2109  for (int i= 0; i < T.length(); i++)
2110    v[i]= 0;
2111  bool noSubset= false;
2112  CFArray TT;
2113  TT= copy (factors);
2114  bool recombination= false;
2115  bool trueFactor= false;
2116  while (T.length() >= 2*s)
2117  {
2118    while (noSubset == false)
2119    {
2120      if (T.length() == s)
2121      {
2122        delete [] v;
2123        if (recombination)
2124        {
2125          g= prod (T);
2126          T.removeFirst();
2127          result.append (g/myContent (g));
2128          g /= Lc (g);
2129          appendTestMapDown (result, g, info, source, dest);
2130          return result;
2131        }
2132        else
2133          return CFList (buf/myContent(buf));
2134      }
2135
2136      S= subset (v, s, TT, noSubset);
2137      if (noSubset) break;
2138
2139      g= prod (S);
2140      g /= myContent (g);
2141      if (fdivides (g, buf, quot))
2142      {
2143        buf2= g;
2144        buf2 /= Lc (buf2);
2145        if (!k && beta.level() == 1)
2146        {
2147          if (degree (buf2, alpha) < degMipoBeta)
2148          {
2149            appendTestMapDown (result, buf2, info, source, dest);
2150            buf= quot;
2151            recombination= true;
2152            trueFactor= true;
2153          }
2154        }
2155        else
2156        {
2157          if (!isInExtension (buf2, gamma, k, delta, source, dest))
2158          {
2159            appendTestMapDown (result, buf2, info, source, dest);
2160            buf= quot;
2161            recombination= true;
2162            trueFactor= true;
2163          }
2164        }
2165        if (trueFactor)
2166        {
2167          T= Difference (T, S);
2168
2169          if (T.length() < 2*s || T.length() == s)
2170          {
2171            delete [] v;
2172            buf /= myContent (buf);
2173            buf /= Lc (buf);
2174            appendTestMapDown (result, buf, info, source, dest);
2175            return result;
2176          }
2177          trueFactor= false;
2178          TT= copy (T);
2179          indexUpdate (v, s, T.length(), noSubset);
2180          if (noSubset) break;
2181        }
2182      }
2183    }
2184    s++;
2185    if (T.length() < 2*s || T.length() == s)
2186    {
2187      delete [] v;
2188      appendTestMapDown (result, buf/myContent(buf), info, source, dest);
2189      return result;
2190    }
2191    for (int i= 0; i < T.length(); i++)
2192      v[i]= 0;
2193    noSubset= false;
2194  }
2195  if (T.length() < 2*s)
2196    appendMapDown (result, F/myContent(F), info, source, dest);
2197
2198  delete [] v;
2199  return result;
2200}
2201
2202CFList
2203extFactorize (const CanonicalForm& F, const ExtensionInfo& info);
2204
2205CFList
2206multiFactorize (const CanonicalForm& F, const ExtensionInfo& info)
2207{
2208
2209  if (F.inCoeffDomain())
2210    return CFList (F);
2211
2212  TIMING_START (fac_fq_preprocess_and_content);
2213  // compress and find main Variable
2214  CFMap N;
2215  TIMING_START (fac_fq_compress)
2216  CanonicalForm A= myCompress (F, N);
2217  TIMING_END_AND_PRINT (fac_fq_compress, "time to compress poly over Fq: ")
2218
2219  A /= Lc (A); // make monic
2220
2221  Variable alpha= info.getAlpha();
2222  Variable beta= info.getBeta();
2223  CanonicalForm gamma= info.getGamma();
2224  CanonicalForm delta= info.getDelta();
2225  bool extension= info.isInExtension();
2226  bool GF= (CFFactory::gettype() == GaloisFieldDomain);
2227  //univariate case
2228  if (F.isUnivariate())
2229  {
2230    if (extension == false)
2231      return uniFactorizer (F, alpha, GF);
2232    else
2233    {
2234      CFList source, dest;
2235      A= mapDown (F, info, source, dest);
2236      return uniFactorizer (A, beta, GF);
2237    }
2238  }
2239
2240  //bivariate case
2241  if (A.level() == 2)
2242  {
2243    CFList buf= biFactorize (F, info);
2244    return buf;
2245  }
2246
2247  Variable x= Variable (1);
2248  Variable y= Variable (2);
2249
2250  // remove content
2251  TIMING_START (fac_fq_content);
2252  CFList contentAi;
2253  CanonicalForm lcmCont= lcmContent (A, contentAi);
2254  A /= lcmCont;
2255  TIMING_END_AND_PRINT (fac_fq_content, "time to extract content over Fq: ");
2256
2257  // trivial after content removal
2258  CFList contentAFactors;
2259  if (A.inCoeffDomain())
2260  {
2261    for (CFListIterator i= contentAi; i.hasItem(); i++)
2262    {
2263      if (i.getItem().inCoeffDomain())
2264        continue;
2265      else
2266      {
2267        lcmCont /= i.getItem();
2268        contentAFactors=
2269        Union (multiFactorize (lcmCont, info),
2270               multiFactorize (i.getItem(), info));
2271        break;
2272      }
2273    }
2274    decompress (contentAFactors, N);
2275    if (!extension)
2276      normalize (contentAFactors);
2277    return contentAFactors;
2278  }
2279
2280  // factorize content
2281  TIMING_START (fac_fq_content);
2282  contentAFactors= multiFactorize (lcmCont, info);
2283  TIMING_END_AND_PRINT (fac_fq_content, "time to factor content over Fq: ");
2284
2285  // univariate after content removal
2286  CFList factors;
2287  if (A.isUnivariate ())
2288  {
2289    factors= uniFactorizer (A, alpha, GF);
2290    append (factors, contentAFactors);
2291    decompress (factors, N);
2292    return factors;
2293  }
2294
2295  // check main variable
2296  TIMING_START (fac_fq_check_mainvar);
2297  int swapLevel= 0;
2298  CanonicalForm derivZ;
2299  CanonicalForm gcdDerivZ;
2300  CanonicalForm bufA= A;
2301  Variable z;
2302  for (int i= 1; i <= A.level(); i++)
2303  {
2304    z= Variable (i);
2305    derivZ= deriv (bufA, z);
2306    if (derivZ.isZero())
2307    {
2308      if (i == 1)
2309        swapLevel= 1;
2310      else
2311        continue;
2312    }
2313    else
2314    {
2315      if (swapLevel == 1)
2316      {
2317        swapLevel= i;
2318        bufA= swapvar (A, x, z);
2319      }
2320      gcdDerivZ= gcd (bufA, derivZ);
2321      if (degree (gcdDerivZ) > 0 && !derivZ.isZero())
2322      {
2323        CanonicalForm g= bufA/gcdDerivZ;
2324        CFList factorsG=
2325        Union (multiFactorize (g, info),
2326               multiFactorize (gcdDerivZ, info));
2327        appendSwapDecompress (factorsG, contentAFactors, N, swapLevel, x);
2328        if (!extension)
2329          normalize (factorsG);
2330        return factorsG;
2331      }
2332      else
2333      {
2334        A= bufA;
2335        break;
2336      }
2337    }
2338  }
2339  TIMING_END_AND_PRINT (fac_fq_check_mainvar,
2340                        "time to check main var over Fq: ");
2341  TIMING_END_AND_PRINT (fac_fq_preprocess_and_content,
2342                       "time to preprocess poly and extract content over Fq: ");
2343
2344  CFList Aeval, list, evaluation, bufEvaluation, bufAeval;
2345  bool fail= false;
2346  int swapLevel2= 0;
2347  int level;
2348  int factorNums= 3;
2349  CFList biFactors, bufBiFactors;
2350  CanonicalForm evalPoly;
2351  int lift, bufLift, lengthAeval2= A.level()-2;
2352  double logarithm= (double) ilog2 (totaldegree (A));
2353  logarithm /= log2exp;
2354  logarithm= ceil (logarithm);
2355  if (factorNums < (int) logarithm)
2356    factorNums= (int) logarithm;
2357  CFList* bufAeval2= new CFList [lengthAeval2];
2358  CFList* Aeval2= new CFList [lengthAeval2];
2359  int counter;
2360  int differentSecondVar= 0;
2361  // several bivariate factorizations
2362  TIMING_START (fac_fq_bifactor_total);
2363  for (int i= 0; i < factorNums; i++)
2364  {
2365    counter= 0;
2366    bufA= A;
2367    bufAeval= CFList();
2368    TIMING_START (fac_fq_evaluation);
2369    bufEvaluation= evalPoints (bufA, bufAeval, alpha, list, GF, fail);
2370    TIMING_END_AND_PRINT (fac_fq_evaluation,
2371                          "time to find evaluation point over Fq: ");
2372    evalPoly= 0;
2373
2374    if (fail && (i == 0))
2375    {
2376      if (!swapLevel)
2377        level= 2;
2378      else
2379        level= swapLevel + 1;
2380
2381      CanonicalForm g;
2382      swapLevel2= newMainVariableSearch (A, Aeval, evaluation, alpha, level, g);
2383
2384      if (!swapLevel2) // need to pass to an extension
2385      {
2386        factors= extFactorize (A, info);
2387        appendSwapDecompress (factors, contentAFactors, N, swapLevel, x);
2388        normalize (factors);
2389        delete [] bufAeval2;
2390        delete [] Aeval2;
2391        return factors;
2392      }
2393      else
2394      {
2395        if (swapLevel2 == -1)
2396        {
2397          CFList factorsG=
2398          Union (multiFactorize (g, info),
2399                 multiFactorize (A/g, info));
2400          appendSwapDecompress (factorsG, contentAFactors, N, swapLevel, x);
2401          if (!extension)
2402            normalize (factorsG);
2403          delete [] bufAeval2;
2404          delete [] Aeval2;
2405          return factorsG;
2406        }
2407        fail= false;
2408        bufAeval= Aeval;
2409        bufA= A;
2410        bufEvaluation= evaluation;
2411      }
2412    }
2413    else if (fail && (i > 0))
2414      break;
2415
2416    TIMING_START (fac_fq_evaluation);
2417    evaluationWRTDifferentSecondVars (bufAeval2, bufEvaluation, A);
2418    TIMING_END_AND_PRINT (fac_fq_evaluation,
2419                          "time for evaluation wrt diff second vars over Fq: ");
2420
2421    for (int j= 0; j < lengthAeval2; j++)
2422    {
2423      if (!bufAeval2[j].isEmpty())
2424        counter++;
2425    }
2426
2427    bufLift= degree (A, y) + 1 + degree (LC(A, x), y);
2428
2429    TIMING_START (fac_fq_bi_factorizer);
2430    if (!GF && alpha.level() == 1)
2431      bufBiFactors= FpBiSqrfFactorize (bufAeval.getFirst());
2432    else if (GF)
2433      bufBiFactors= GFBiSqrfFactorize (bufAeval.getFirst());
2434    else
2435      bufBiFactors= FqBiSqrfFactorize (bufAeval.getFirst(), alpha);
2436    TIMING_END_AND_PRINT (fac_fq_bi_factorizer,
2437                          "time for bivariate factorization: ");
2438    bufBiFactors.removeFirst();
2439
2440    if (bufBiFactors.length() == 1)
2441    {
2442      if (extension)
2443      {
2444        CFList source, dest;
2445        A= mapDown (A, info, source, dest);
2446      }
2447      factors.append (A);
2448      appendSwapDecompress (factors, contentAFactors, N, swapLevel,
2449                            swapLevel2, x);
2450      if (!extension)
2451        normalize (factors);
2452      delete [] bufAeval2;
2453      delete [] Aeval2;
2454      return factors;
2455    }
2456
2457    if (i == 0)
2458    {
2459      Aeval= bufAeval;
2460      evaluation= bufEvaluation;
2461      biFactors= bufBiFactors;
2462      lift= bufLift;
2463      for (int j= 0; j < lengthAeval2; j++)
2464        Aeval2 [j]= bufAeval2 [j];
2465      differentSecondVar= counter;
2466    }
2467    else
2468    {
2469      if (bufBiFactors.length() < biFactors.length() ||
2470          ((bufLift < lift) && (bufBiFactors.length() == biFactors.length())) ||
2471          counter > differentSecondVar)
2472      {
2473        Aeval= bufAeval;
2474        evaluation= bufEvaluation;
2475        biFactors= bufBiFactors;
2476        lift= bufLift;
2477        for (int j= 0; j < lengthAeval2; j++)
2478          Aeval2 [j]= bufAeval2 [j];
2479        differentSecondVar= counter;
2480      }
2481    }
2482    int k= 0;
2483    for (CFListIterator j= bufEvaluation; j.hasItem(); j++, k++)
2484      evalPoly += j.getItem()*power (x, k);
2485    list.append (evalPoly);
2486  }
2487
2488  delete [] bufAeval2;
2489
2490  sortList (biFactors, x);
2491
2492  int minFactorsLength;
2493  bool irred= false;
2494  TIMING_START (fac_fq_bi_factorizer);
2495  factorizationWRTDifferentSecondVars (A, Aeval2, info, minFactorsLength,irred);
2496  TIMING_END_AND_PRINT (fac_fq_bi_factorizer,
2497             "time for bivariate factorization wrt diff second vars over Fq: ");
2498
2499  TIMING_END_AND_PRINT (fac_fq_bifactor_total,
2500                        "total time for eval and bivar factors over Fq: ");
2501  if (irred)
2502  {
2503    if (extension)
2504    {
2505      CFList source, dest;
2506      A= mapDown (A, info, source, dest);
2507    }
2508    factors.append (A);
2509    appendSwapDecompress (factors, contentAFactors, N, swapLevel,
2510                          swapLevel2, x);
2511    if (!extension)
2512      normalize (factors);
2513    delete [] Aeval2;
2514    return factors;
2515  }
2516
2517  if (minFactorsLength == 0)
2518    minFactorsLength= biFactors.length();
2519  else if (biFactors.length() > minFactorsLength)
2520    refineBiFactors (A, biFactors, Aeval2, evaluation, minFactorsLength);
2521  minFactorsLength= tmin (minFactorsLength, biFactors.length());
2522
2523  if (differentSecondVar == lengthAeval2)
2524  {
2525    bool zeroOccured= false;
2526    for (CFListIterator iter= evaluation; iter.hasItem(); iter++)
2527    {
2528      if (iter.getItem().isZero())
2529      {
2530        zeroOccured= true;
2531        break;
2532      }
2533    }
2534    if (!zeroOccured)
2535    {
2536      factors= sparseHeuristic (A, biFactors, Aeval2, evaluation,
2537                                minFactorsLength);
2538      if (factors.length() == biFactors.length())
2539      {
2540        if (extension)
2541          factors= extNonMonicFactorRecombination (factors, A, info);
2542
2543        appendSwapDecompress (factors, contentAFactors, N, swapLevel,
2544                              swapLevel2, x);
2545        if (!extension)
2546          normalize (factors);
2547        delete [] Aeval2;
2548        return factors;
2549      }
2550      else
2551        factors= CFList();
2552      //TODO case where factors.length() > 0
2553    }
2554  }
2555
2556  CFList uniFactors= buildUniFactors (biFactors, evaluation.getLast(), y);
2557
2558  sortByUniFactors (Aeval2, lengthAeval2, uniFactors, evaluation);
2559
2560  CFList * oldAeval= new CFList [lengthAeval2]; //TODO use bufAeval2 for this
2561  for (int i= 0; i < lengthAeval2; i++)
2562    oldAeval[i]= Aeval2[i];
2563
2564  getLeadingCoeffs (A, Aeval2, uniFactors, evaluation);
2565
2566  CFList biFactorsLCs;
2567  for (CFListIterator i= biFactors; i.hasItem(); i++)
2568    biFactorsLCs.append (LC (i.getItem(), 1));
2569
2570  Variable v;
2571  TIMING_START (fac_fq_precompute_leadcoeff);
2572  CFList leadingCoeffs= precomputeLeadingCoeff (LC (A, 1), biFactorsLCs, alpha,
2573                                          evaluation, Aeval2, lengthAeval2, v);
2574
2575  if (v.level() != 1)
2576  {
2577    A= swapvar (A, y, v);
2578    int i= A.level();
2579    CanonicalForm evalPoint;
2580    for (CFListIterator iter= evaluation; iter.hasItem(); iter++, i--)
2581    {
2582      if (i == v.level())
2583      {
2584        evalPoint= iter.getItem();
2585        iter.getItem()= evaluation.getLast();
2586        evaluation.removeLast();
2587        evaluation.append (evalPoint);
2588        break;
2589      }
2590    }
2591    for (i= 0; i < lengthAeval2; i++)
2592    {
2593      if (oldAeval[i].isEmpty())
2594        continue;
2595      if (oldAeval[i].getFirst().level() == v.level())
2596      {
2597        CFArray tmp= copy (oldAeval[i]);
2598        oldAeval[i]= biFactors;
2599        for (CFListIterator iter= oldAeval[i]; iter.hasItem(); iter++)
2600          iter.getItem()= swapvar (iter.getItem(), v, y);
2601        for (int ii= 0; ii < tmp.size(); ii++)
2602          tmp[ii]= swapvar (tmp[ii], v, y);
2603        CFArray tmp2= CFArray (tmp.size());
2604        CanonicalForm buf;
2605        for (int ii= 0; ii < tmp.size(); ii++)
2606        {
2607          buf= tmp[ii] (evaluation.getLast(),y);
2608          buf /= Lc (buf);
2609          tmp2[findItem (uniFactors, buf)-1]=tmp[ii];
2610        }
2611        biFactors= CFList();
2612        for (int j= 0; j < tmp2.size(); j++)
2613          biFactors.append (tmp2[j]);
2614      }
2615    }
2616  }
2617
2618  CFListIterator iter;
2619  CanonicalForm oldA= A;
2620  CFList oldBiFactors= biFactors;
2621  if (!leadingCoeffs.getFirst().inCoeffDomain())
2622  {
2623    CanonicalForm tmp= power (leadingCoeffs.getFirst(), biFactors.length() - 1);
2624    A *= tmp;
2625    tmp= leadingCoeffs.getFirst();
2626    iter= evaluation;
2627    for (int i= A.level(); i > 2; i--, iter++)
2628      tmp= tmp (iter.getItem(), i);
2629    if (!tmp.inCoeffDomain())
2630    {
2631      for (CFListIterator i= biFactors; i.hasItem(); i++)
2632      {
2633        i.getItem() *= tmp/LC (i.getItem(), 1);
2634        i.getItem() /= Lc (i.getItem());
2635      }
2636    }
2637  }
2638
2639  CanonicalForm LCmultiplier= leadingCoeffs.getFirst();
2640  bool LCmultiplierIsConst= LCmultiplier.inCoeffDomain();
2641  leadingCoeffs.removeFirst();
2642
2643  //prepare leading coefficients
2644  CFList* leadingCoeffs2= new CFList [lengthAeval2];
2645  prepareLeadingCoeffs (leadingCoeffs2, A.level(), leadingCoeffs, biFactors,
2646                        evaluation);
2647
2648  Aeval= evaluateAtEval (A, evaluation, 2);
2649  CanonicalForm hh= 1/Lc (Aeval.getFirst());
2650  for (iter= Aeval; iter.hasItem(); iter++)
2651    iter.getItem() *= hh;
2652
2653  A *= hh;
2654
2655
2656  CFListIterator iter2;
2657  CFList bufLeadingCoeffs2= leadingCoeffs2[lengthAeval2-1];
2658  bufBiFactors= biFactors;
2659  bufA= A;
2660  CanonicalForm bufLCmultiplier= LCmultiplier;
2661  CanonicalForm testVars;
2662  if (!LCmultiplierIsConst)
2663  {
2664    testVars= Variable (2);
2665    for (int i= 0; i < lengthAeval2; i++)
2666    {
2667      if (!oldAeval[i].isEmpty())
2668        testVars *= oldAeval[i].getFirst().mvar();
2669    }
2670  }
2671  TIMING_END_AND_PRINT(fac_fq_precompute_leadcoeff,
2672                       "time to precompute LC over Fq: ");
2673
2674  TIMING_START (fac_fq_luckswang);
2675  CFList bufFactors= CFList();
2676  bool LCheuristic= false;
2677  if (LucksWangSparseHeuristic (A, biFactors, 2, leadingCoeffs2[lengthAeval2-1],
2678                                 factors))
2679  {
2680    int check= biFactors.length();
2681    int * index= new int [factors.length()];
2682    CFList oldFactors= factors;
2683    factors= recoverFactors (A, factors, index);
2684
2685    if (check == factors.length())
2686    {
2687      if (extension)
2688        factors= extNonMonicFactorRecombination (factors, bufA, info);
2689
2690      if (v.level() != 1)
2691      {
2692        for (iter= factors; iter.hasItem(); iter++)
2693          iter.getItem()= swapvar (iter.getItem(), v, y);
2694      }
2695
2696      appendSwapDecompress (factors, contentAFactors, N, swapLevel,
2697                            swapLevel2, x);
2698      if (!extension)
2699        normalize (factors);
2700      delete [] index;
2701      delete [] Aeval2;
2702      TIMING_END_AND_PRINT (fac_fq_luckswang,
2703                            "time for successful LucksWang over Fq: ");
2704      return factors;
2705    }
2706    else if (factors.length() > 0)
2707    {
2708      int oneCount= 0;
2709      CFList l;
2710      for (int i= 0; i < check; i++)
2711      {
2712        if (index[i] == 1)
2713        {
2714          iter=biFactors;
2715          for (int j=1; j <= i-oneCount; j++)
2716            iter++;
2717          iter.remove (1);
2718          for (int j= 0; j < lengthAeval2; j++)
2719          {
2720            l= leadingCoeffs2[j];
2721            iter= l;
2722            for (int k=1; k <= i-oneCount; k++)
2723              iter++;
2724            iter.remove (1);
2725            leadingCoeffs2[j]=l;
2726          }
2727          oneCount++;
2728        }
2729      }
2730      bufFactors= factors;
2731      factors= CFList();
2732    }
2733    else if (!LCmultiplierIsConst && factors.length() == 0)
2734    {
2735      LCheuristic= true;
2736      factors= oldFactors;
2737      CanonicalForm cont;
2738      CFList contents, LCs;
2739      int index=1;
2740      bool foundTrueMultiplier= false;
2741      for (iter= factors; iter.hasItem(); iter++, index++)
2742      {
2743        cont= content (iter.getItem(), 1);
2744        cont= gcd (cont , LCmultiplier);
2745        contents.append (cont);
2746        if (cont.inCoeffDomain()) // trivial content->LCmultiplier needs to go there
2747        {
2748          foundTrueMultiplier= true;
2749          int index2= 1;
2750          for (iter2= leadingCoeffs2[lengthAeval2-1]; iter2.hasItem(); iter2++,
2751                                                                    index2++)
2752          {
2753            if (index2 == index)
2754              continue;
2755            iter2.getItem() /= LCmultiplier;
2756          }
2757          A= oldA;
2758          leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
2759          for (int i= lengthAeval2-1; i > -1; i--)
2760            leadingCoeffs2[i]= CFList();
2761          prepareLeadingCoeffs (leadingCoeffs2, A.level(), leadingCoeffs,
2762                                biFactors, evaluation );
2763          Aeval= evaluateAtEval (A, evaluation, 2);
2764
2765          hh= 1/Lc (Aeval.getFirst());
2766
2767          for (iter2= Aeval; iter2.hasItem(); iter2++)
2768            iter2.getItem() *= hh;
2769
2770          A *= hh;
2771          break;
2772        }
2773        else
2774          LCs.append (LC (iter.getItem()/cont, 1));
2775      }
2776      if (!foundTrueMultiplier)
2777      {
2778        index= 1;
2779        iter2= factors;
2780        bool foundMultiplier= false;
2781        for (iter= contents; iter.hasItem(); iter++, iter2++, index++)
2782        {
2783          if (fdivides (iter.getItem(), LCmultiplier))
2784          {
2785            if ((LCmultiplier/iter.getItem()).inCoeffDomain() &&
2786                !isOnlyLeadingCoeff(iter2.getItem())) //content divides LCmultiplier completely and factor consists of more terms than just the leading coeff
2787            {
2788              int index2= 1;
2789              for (CFListIterator iter3= leadingCoeffs2[lengthAeval2-1];
2790                   iter3.hasItem(); iter3++, index2++)
2791              {
2792                if (index2 == index)
2793                {
2794                  iter3.getItem() /= LCmultiplier;
2795                  break;
2796                }
2797              }
2798              A /= LCmultiplier;
2799              foundMultiplier= true;
2800              iter.getItem()= 1;
2801            }
2802          }
2803        }
2804        // coming from above: divide out more LCmultiplier if possible
2805        if (foundMultiplier)
2806        {
2807          foundMultiplier= false;
2808          index=1;
2809          iter2= factors;
2810          for (iter= contents; iter.hasItem(); iter++, iter2++, index++)
2811          {
2812            if (!iter.getItem().isOne() &&
2813                fdivides (iter.getItem(), LCmultiplier))
2814            {
2815              if (!isOnlyLeadingCoeff (iter2.getItem())) // factor is more than just leading coeff
2816              {
2817                int index2= 1;
2818                for (iter2= leadingCoeffs2[lengthAeval2-1]; iter2.hasItem();
2819                     iter2++, index2++)
2820                {
2821                  if (index2 == index)
2822                  {
2823                    iter2.getItem() /= iter.getItem();
2824                    foundMultiplier= true;
2825                    break;
2826                  }
2827                }
2828                A /= iter.getItem();
2829                LCmultiplier /= iter.getItem();
2830                iter.getItem()= 1;
2831              }
2832              else if (fdivides (getVars (LCmultiplier), testVars))//factor consists of just leading coeff
2833              {
2834                //TODO maybe use a sqrffree decomposition of LCmultiplier as below
2835                Variable xx= Variable (2);
2836                CanonicalForm vars;
2837                vars= power (xx, degree (LC (getItem(oldBiFactors, index),1),
2838                                          xx));
2839                for (int i= 0; i < lengthAeval2; i++)
2840                {
2841                  if (oldAeval[i].isEmpty())
2842                    continue;
2843                  xx= oldAeval[i].getFirst().mvar();
2844                  vars *= power (xx, degree (LC (getItem(oldAeval[i], index),1),
2845                                             xx));
2846                }
2847                if (myGetVars(content(getItem(leadingCoeffs2[lengthAeval2-1],index),1))
2848                    /myGetVars (LCmultiplier) == vars)
2849                {
2850                  int index2= 1;
2851                  for (iter2= leadingCoeffs2[lengthAeval2-1]; iter2.hasItem();
2852                       iter2++, index2++)
2853                  {
2854                    if (index2 == index)
2855                    {
2856                      iter2.getItem() /= LCmultiplier;
2857                      foundMultiplier= true;
2858                      break;
2859                    }
2860                  }
2861                  A /= LCmultiplier;
2862                  iter.getItem()= 1;
2863                }
2864              }
2865            }
2866          }
2867        }
2868        else
2869        {
2870          CanonicalForm pLCs= prod (LCs);
2871          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
2872          {
2873            A= oldA;
2874            iter2= leadingCoeffs2[lengthAeval2-1];
2875            for (iter= contents; iter.hasItem(); iter++, iter2++)
2876              iter2.getItem() /= iter.getItem();
2877            foundMultiplier= true;
2878          }
2879          if (!foundMultiplier && fdivides (getVars (LCmultiplier), testVars))
2880          {
2881            Variable xx;
2882            CFList vars1;
2883            CFFList sqrfMultiplier= sqrFree (LCmultiplier);
2884            if (sqrfMultiplier.getFirst().factor().inCoeffDomain())
2885              sqrfMultiplier.removeFirst();
2886            sqrfMultiplier= sortCFFListByNumOfVars (sqrfMultiplier);
2887            xx= Variable (2);
2888            for (iter= oldBiFactors; iter.hasItem(); iter++)
2889              vars1.append (power (xx, degree (LC (iter.getItem(),1), xx)));
2890            for (int i= 0; i < lengthAeval2; i++)
2891            {
2892              if (oldAeval[i].isEmpty())
2893                continue;
2894              xx= oldAeval[i].getFirst().mvar();
2895              iter2= vars1;
2896              for (iter= oldAeval[i]; iter.hasItem(); iter++, iter2++)
2897                iter2.getItem() *= power(xx,degree (LC (iter.getItem(),1), xx));
2898            }
2899            CanonicalForm tmp;
2900            iter2= vars1;
2901            for (iter= leadingCoeffs2[lengthAeval2-1]; iter.hasItem(); iter++,
2902                                                                    iter2++)
2903            {
2904              tmp= iter.getItem()/LCmultiplier;
2905              for (int i=1; i <= tmp.level(); i++)
2906              {
2907                if (degree(tmp,i) > 0 &&
2908                    (degree(iter2.getItem(),i) > degree (tmp,i)))
2909                  iter2.getItem() /= power (Variable (i), degree (tmp,i));
2910              }
2911            }
2912            int multi;
2913            for (CFFListIterator ii= sqrfMultiplier; ii.hasItem(); ii++)
2914            {
2915              multi= 0;
2916              for (iter= vars1; iter.hasItem(); iter++)
2917              {
2918                tmp= iter.getItem();
2919                while (fdivides (myGetVars (ii.getItem().factor()), tmp))
2920                {
2921                  multi++;
2922                  tmp /= myGetVars (ii.getItem().factor());
2923                }
2924              }
2925              if (multi == ii.getItem().exp())
2926              {
2927                index= 1;
2928                for (iter= vars1; iter.hasItem(); iter++, index++)
2929                {
2930                  while (fdivides (myGetVars(ii.getItem().factor()),
2931                                   iter.getItem()
2932                                  )
2933                        )
2934                  {
2935                    int index2= 1;
2936                    for (iter2= leadingCoeffs2[lengthAeval2-1]; iter2.hasItem();
2937                         iter2++, index2++)
2938                    {
2939                      if (index2 == index)
2940                        continue;
2941                      else
2942                      {
2943                        tmp= ii.getItem().factor();
2944                        iter2.getItem() /= tmp;
2945                        CFListIterator iter3= evaluation;
2946                        for (int jj= A.level(); jj > 2; jj--, iter3++)
2947                          tmp= tmp (iter3.getItem(), jj);
2948                        if (!tmp.inCoeffDomain())
2949                        {
2950                          int index3= 1;
2951                          for (iter3= biFactors; iter3.hasItem(); iter3++,
2952                                                                  index3++)
2953                          {
2954                            if (index3 == index2)
2955                            {
2956                              iter3.getItem() /= tmp;
2957                              iter3.getItem() /= Lc (iter3.getItem());
2958                              break;
2959                            }
2960                          }
2961                        }
2962                        A /= ii.getItem().factor();
2963                      }
2964                    }
2965                    iter.getItem() /= getVars (ii.getItem().factor());
2966                  }
2967                }
2968              }
2969              else
2970              {
2971                index= 1;
2972                for (iter= vars1; iter.hasItem(); iter++, index++)
2973                {
2974                  if (!fdivides (myGetVars (ii.getItem().factor()),
2975                                 iter.getItem()
2976                                )
2977                     )
2978                  {
2979                    int index2= 1;
2980                    for (iter2= leadingCoeffs2[lengthAeval2-1]; iter2.hasItem();
2981                         iter2++, index2++)
2982                    {
2983                      if (index2 == index)
2984                      {
2985                        tmp= power (ii.getItem().factor(), ii.getItem().exp());
2986                        iter2.getItem() /= tmp;
2987                        A /= tmp;
2988                        CFListIterator iter3= evaluation;
2989                        for (int jj= A.level(); jj > 2; jj--, iter3++)
2990                          tmp= tmp (iter3.getItem(), jj);
2991                        if (!tmp.inCoeffDomain())
2992                        {
2993                          int index3= 1;
2994                          for (iter3= biFactors; iter3.hasItem(); iter3++,
2995                                                                  index3++)
2996                          {
2997                            if (index3 == index2)
2998                            {
2999                              iter3.getItem() /= tmp;
3000                              iter3.getItem() /= Lc (iter3.getItem());
3001                              break;
3002                            }
3003                          }
3004                        }
3005                      }
3006                    }
3007                  }
3008                }
3009              }
3010            }
3011          }
3012        }
3013
3014        // patch everything together again
3015        leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
3016        for (int i= lengthAeval2-1; i > -1; i--)
3017          leadingCoeffs2[i]= CFList();
3018        prepareLeadingCoeffs (leadingCoeffs2,A.level(),leadingCoeffs, biFactors,
3019                              evaluation);
3020        Aeval= evaluateAtEval (A, evaluation, 2);
3021
3022        hh= 1/Lc (Aeval.getFirst());
3023
3024        for (CFListIterator i= Aeval; i.hasItem(); i++)
3025          i.getItem() *= hh;
3026
3027        A *= hh;
3028      }
3029      factors= CFList();
3030      if (!fdivides (LC (oldA,1),prod (leadingCoeffs2[lengthAeval2-1])))
3031      {
3032        LCheuristic= false;
3033        A= bufA;
3034        biFactors= bufBiFactors;
3035        leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
3036        LCmultiplier= bufLCmultiplier;
3037      }
3038    }
3039    else
3040      factors= CFList();
3041    delete [] index;
3042  }
3043  TIMING_END_AND_PRINT (fac_fq_luckswang, "time for LucksWang over Fq: ");
3044
3045  TIMING_START (fac_fq_lcheuristic);
3046  if (!LCheuristic && !LCmultiplierIsConst && bufFactors.isEmpty()
3047      && fdivides (getVars (LCmultiplier), testVars))
3048  {
3049    LCheuristic= true;
3050    int index;
3051    Variable xx;
3052    CFList vars1;
3053    CFFList sqrfMultiplier= sqrFree (LCmultiplier);
3054    if (sqrfMultiplier.getFirst().factor().inCoeffDomain())
3055      sqrfMultiplier.removeFirst();
3056    sqrfMultiplier= sortCFFListByNumOfVars (sqrfMultiplier);
3057    xx= Variable (2);
3058    for (iter= oldBiFactors; iter.hasItem(); iter++)
3059      vars1.append (power (xx, degree (LC (iter.getItem(),1), xx)));
3060    for (int i= 0; i < lengthAeval2; i++)
3061    {
3062      if (oldAeval[i].isEmpty())
3063        continue;
3064      xx= oldAeval[i].getFirst().mvar();
3065      iter2= vars1;
3066      for (iter= oldAeval[i]; iter.hasItem(); iter++, iter2++)
3067        iter2.getItem() *= power (xx, degree (LC (iter.getItem(),1), xx));
3068    }
3069    CanonicalForm tmp;
3070    iter2= vars1;
3071    for (iter= leadingCoeffs2[lengthAeval2-1]; iter.hasItem(); iter++, iter2++)
3072    {
3073      tmp= iter.getItem()/LCmultiplier;
3074      for (int i=1; i <= tmp.level(); i++)
3075      {
3076        if (degree (tmp,i) > 0 && (degree (iter2.getItem(),i) > degree (tmp,i)))
3077          iter2.getItem() /= power (Variable (i), degree (tmp,i));
3078      }
3079    }
3080    int multi;
3081    for (CFFListIterator ii= sqrfMultiplier; ii.hasItem(); ii++)
3082    {
3083      multi= 0;
3084      for (iter= vars1; iter.hasItem(); iter++)
3085      {
3086        tmp= iter.getItem();
3087        while (fdivides (myGetVars (ii.getItem().factor()), tmp))
3088        {
3089          multi++;
3090          tmp /= myGetVars (ii.getItem().factor());
3091        }
3092      }
3093      if (multi == ii.getItem().exp())
3094      {
3095        index= 1;
3096        for (iter= vars1; iter.hasItem(); iter++, index++)
3097        {
3098          while (fdivides (myGetVars (ii.getItem().factor()), iter.getItem()))
3099          {
3100            int index2= 1;
3101            for (iter2= leadingCoeffs2[lengthAeval2-1]; iter2.hasItem();iter2++,
3102                                                                      index2++)
3103            {
3104              if (index2 == index)
3105                continue;
3106              else
3107              {
3108                tmp= ii.getItem().factor();
3109                iter2.getItem() /= tmp;
3110                CFListIterator iter3= evaluation;
3111                for (int jj= A.level(); jj > 2; jj--, iter3++)
3112                  tmp= tmp (iter3.getItem(), jj);
3113                if (!tmp.inCoeffDomain())
3114                {
3115                  int index3= 1;
3116                  for (iter3= biFactors; iter3.hasItem(); iter3++, index3++)
3117                  {
3118                    if (index3 == index2)
3119                    {
3120                      iter3.getItem() /= tmp;
3121                      iter3.getItem() /= Lc (iter3.getItem());
3122                      break;
3123                    }
3124                  }
3125                }
3126                A /= ii.getItem().factor();
3127              }
3128            }
3129            iter.getItem() /= getVars (ii.getItem().factor());
3130          }
3131        }
3132      }
3133      else
3134      {
3135        index= 1;
3136        for (iter= vars1; iter.hasItem(); iter++, index++)
3137        {
3138          if (!fdivides (myGetVars (ii.getItem().factor()), iter.getItem()))
3139          {
3140            int index2= 1;
3141            for (iter2= leadingCoeffs2[lengthAeval2-1];iter2.hasItem();iter2++,
3142                                                                      index2++)
3143            {
3144              if (index2 == index)
3145              {
3146                tmp= power (ii.getItem().factor(), ii.getItem().exp());
3147                iter2.getItem() /= tmp;
3148                A /= tmp;
3149                CFListIterator iter3= evaluation;
3150                for (int jj= A.level(); jj > 2; jj--, iter3++)
3151                  tmp= tmp (iter3.getItem(), jj);
3152                if (!tmp.inCoeffDomain())
3153                {
3154                  int index3= 1;
3155                  for (iter3= biFactors; iter3.hasItem(); iter3++, index3++)
3156                  {
3157                    if (index3 == index2)
3158                    {
3159                      iter3.getItem() /= tmp;
3160                      iter3.getItem() /= Lc (iter3.getItem());
3161                      break;
3162                    }
3163                  }
3164                }
3165              }
3166            }
3167          }
3168        }
3169      }
3170    }
3171
3172    leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
3173    for (int i= lengthAeval2-1; i > -1; i--)
3174      leadingCoeffs2[i]= CFList();
3175    prepareLeadingCoeffs (leadingCoeffs2,A.level(),leadingCoeffs, biFactors,
3176                          evaluation);
3177    Aeval= evaluateAtEval (A, evaluation, 2);
3178
3179    hh= 1/Lc (Aeval.getFirst());
3180
3181    for (CFListIterator i= Aeval; i.hasItem(); i++)
3182      i.getItem() *= hh;
3183
3184    A *= hh;
3185
3186    if (!fdivides (LC (oldA,1),prod (leadingCoeffs2[lengthAeval2-1])))
3187    {
3188      LCheuristic= false;
3189      A= bufA;
3190      biFactors= bufBiFactors;
3191      leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
3192      LCmultiplier= bufLCmultiplier;
3193    }
3194  }
3195  TIMING_END_AND_PRINT (fac_fq_lcheuristic, "time for Lc heuristic over Fq: ");
3196
3197tryAgainWithoutHeu:
3198  TIMING_START (fac_fq_shift_to_zero);
3199  A= shift2Zero (A, Aeval, evaluation);
3200
3201  for (iter= biFactors; iter.hasItem(); iter++)
3202    iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
3203
3204  for (int i= 0; i < lengthAeval2-1; i++)
3205    leadingCoeffs2[i]= CFList();
3206  for (iter= leadingCoeffs2[lengthAeval2-1]; iter.hasItem(); iter++)
3207  {
3208    iter.getItem()= shift2Zero (iter.getItem(), list, evaluation);
3209    for (int i= A.level() - 4; i > -1; i--)
3210    {
3211      if (i + 1 == lengthAeval2-1)
3212        leadingCoeffs2[i].append (iter.getItem() (0, i + 4));
3213      else
3214        leadingCoeffs2[i].append (leadingCoeffs2[i+1].getLast() (0, i + 4));
3215    }
3216  }
3217  TIMING_END_AND_PRINT (fac_fq_shift_to_zero,
3218                        "time to shift evaluation point to zero: ");
3219
3220  CFArray Pi;
3221  CFList diophant;
3222  int* liftBounds= new int [A.level() - 1];
3223  int liftBoundsLength= A.level() - 1;
3224  for (int i= 0; i < liftBoundsLength; i++)
3225    liftBounds [i]= degree (A, i + 2) + 1;
3226
3227  Aeval.removeFirst();
3228  bool noOneToOne= false;
3229  TIMING_START (fac_fq_hensel_lift);
3230  factors= nonMonicHenselLift (Aeval, biFactors, leadingCoeffs2, diophant,
3231                               Pi, liftBounds, liftBoundsLength, noOneToOne);
3232  TIMING_END_AND_PRINT (fac_fq_hensel_lift,
3233                        "time for non monic hensel lifting over Fq: ");
3234
3235  if (!noOneToOne)
3236  {
3237    int check= factors.length();
3238    A= oldA;
3239    TIMING_START (fac_fq_recover_factors);
3240    factors= recoverFactors (A, factors, evaluation);
3241    TIMING_END_AND_PRINT (fac_fq_recover_factors,
3242                          "time to recover factors over Fq: ");
3243    if (check != factors.length())
3244      noOneToOne= true;
3245    else
3246      factors= Union (factors, bufFactors);
3247
3248    if (extension && !noOneToOne)
3249      factors= extNonMonicFactorRecombination (factors, A, info);
3250  }
3251  if (noOneToOne)
3252  {
3253
3254    if (!LCmultiplierIsConst && LCheuristic)
3255    {
3256      A= bufA;
3257      biFactors= bufBiFactors;
3258      leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
3259      delete [] liftBounds;
3260      LCheuristic= false;
3261      goto tryAgainWithoutHeu;
3262      //something probably went wrong in the heuristic
3263    }
3264
3265    A= shift2Zero (oldA, Aeval, evaluation);
3266    biFactors= oldBiFactors;
3267    for (iter= biFactors; iter.hasItem(); iter++)
3268      iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
3269    CanonicalForm LCA= LC (Aeval.getFirst(), 1);
3270    CanonicalForm yToLift= power (y, lift);
3271    CFListIterator i= biFactors;
3272    lift= degree (i.getItem(), 2) + degree (LC (i.getItem(), 1)) + 1;
3273    i++;
3274
3275    for (; i.hasItem(); i++)
3276      lift= tmax (lift,
3277                  degree (i.getItem(), 2) + degree (LC (i.getItem(), 1)) + 1);
3278
3279    lift= tmax (degree (Aeval.getFirst() , 2) + 1, lift);
3280
3281    i= biFactors;
3282    yToLift= power (y, lift);
3283    CanonicalForm dummy;
3284    for (; i.hasItem(); i++)
3285    {
3286      LCA= LC (i.getItem(), 1);
3287      extgcd (LCA, yToLift, LCA, dummy);
3288      i.getItem()= mod (i.getItem()*LCA, yToLift);
3289    }
3290
3291    liftBoundsLength= F.level() - 1;
3292    liftBounds= liftingBounds (A, lift);
3293
3294    CFList MOD;
3295    bool earlySuccess;
3296    CFList earlyFactors, liftedFactors;
3297    TIMING_START (fac_fq_hensel_lift);
3298    liftedFactors= henselLiftAndEarly
3299                   (A, MOD, liftBounds, earlySuccess, earlyFactors,
3300                    Aeval, biFactors, evaluation, info);
3301    TIMING_END_AND_PRINT (fac_fq_hensel_lift,
3302                          "time for hensel lifting over Fq: ");
3303
3304    if (!extension)
3305    {
3306      TIMING_START (fac_fq_factor_recombination);
3307      factors= factorRecombination (A, liftedFactors, MOD);
3308      TIMING_END_AND_PRINT (fac_fq_factor_recombination,
3309                            "time for factor recombination: ");
3310    }
3311    else
3312    {
3313      TIMING_START (fac_fq_factor_recombination);
3314      factors= extFactorRecombination (liftedFactors, A, MOD, info, evaluation);
3315      TIMING_END_AND_PRINT (fac_fq_factor_recombination,
3316                            "time for factor recombination: ");
3317    }
3318
3319    if (earlySuccess)
3320      factors= Union (factors, earlyFactors);
3321    if (!extension)
3322    {
3323      for (CFListIterator i= factors; i.hasItem(); i++)
3324      {
3325        int kk= Aeval.getLast().level();
3326        for (CFListIterator j= evaluation; j.hasItem(); j++, kk--)
3327        {
3328          if (i.getItem().level() < kk)
3329            continue;
3330          i.getItem()= i.getItem() (Variable (kk) - j.getItem(), kk);
3331        }
3332      }
3333    }
3334  }
3335
3336  if (v.level() != 1)
3337  {
3338    for (CFListIterator iter= factors; iter.hasItem(); iter++)
3339      iter.getItem()= swapvar (iter.getItem(), v, y);
3340  }
3341
3342  swap (factors, swapLevel, swapLevel2, x);
3343  append (factors, contentAFactors);
3344  decompress (factors, N);
3345  if (!extension)
3346    normalize (factors);
3347
3348  delete[] liftBounds;
3349
3350  return factors;
3351}
3352
3353/// multivariate factorization over an extension of the initial field
3354CFList
3355extFactorize (const CanonicalForm& F, const ExtensionInfo& info)
3356{
3357  CanonicalForm A= F;
3358
3359  Variable alpha= info.getAlpha();
3360  Variable beta= info.getBeta();
3361  int k= info.getGFDegree();
3362  char cGFName= info.getGFName();
3363  CanonicalForm delta= info.getDelta();
3364  bool GF= (CFFactory::gettype() == GaloisFieldDomain);
3365  Variable w= Variable (1);
3366
3367  CFList factors;
3368  if (!GF && alpha == w)  // we are in F_p
3369  {
3370    CFList factors;
3371    bool extension= true;
3372    int p= getCharacteristic();
3373    if (p < 7)
3374    {
3375      if (p == 2)
3376        setCharacteristic (getCharacteristic(), 6, 'Z');
3377      else if (p == 3)
3378        setCharacteristic (getCharacteristic(), 4, 'Z');
3379      else if (p == 5)
3380        setCharacteristic (getCharacteristic(), 3, 'Z');
3381      ExtensionInfo info= ExtensionInfo (extension);
3382      A= A.mapinto();
3383      factors= multiFactorize (A, info);
3384
3385      CanonicalForm mipo= gf_mipo;
3386      setCharacteristic (getCharacteristic());
3387      Variable vBuf= rootOf (mipo.mapinto());
3388      for (CFListIterator j= factors; j.hasItem(); j++)
3389        j.getItem()= GF2FalphaRep (j.getItem(), vBuf);
3390    }
3391    else if (p >= 7 && p*p < (1<<16)) // pass to GF if possible
3392    {
3393      setCharacteristic (getCharacteristic(), 2, 'Z');
3394      ExtensionInfo info= ExtensionInfo (extension);
3395      A= A.mapinto();
3396      factors= multiFactorize (A, info);
3397
3398      CanonicalForm mipo= gf_mipo;
3399      setCharacteristic (getCharacteristic());
3400      Variable vBuf= rootOf (mipo.mapinto());
3401      for (CFListIterator j= factors; j.hasItem(); j++)
3402        j.getItem()= GF2FalphaRep (j.getItem(), vBuf);
3403    }
3404    else  // not able to pass to GF, pass to F_p(\alpha)
3405    {
3406      CanonicalForm mipo= randomIrredpoly (2, w);
3407      Variable v= rootOf (mipo);
3408      ExtensionInfo info= ExtensionInfo (v);
3409      factors= multiFactorize (A, info);
3410    }
3411    return factors;
3412  }
3413  else if (!GF && (alpha != w)) // we are in F_p(\alpha)
3414  {
3415    if (k == 1) // need factorization over F_p
3416    {
3417      int extDeg= degree (getMipo (alpha));
3418      extDeg++;
3419      CanonicalForm mipo= randomIrredpoly (extDeg + 1, w);
3420      Variable v= rootOf (mipo);
3421      ExtensionInfo info= ExtensionInfo (v);
3422      factors= multiFactorize (A, info);
3423    }
3424    else
3425    {
3426      if (beta == w)
3427      {
3428        Variable v= chooseExtension (alpha, beta, k);
3429        CanonicalForm primElem, imPrimElem;
3430        bool primFail= false;
3431        Variable vBuf;
3432        primElem= primitiveElement (alpha, vBuf, primFail);
3433        ASSERT (!primFail, "failure in integer factorizer");
3434        if (primFail)
3435          ; //ERROR
3436        else
3437          imPrimElem= mapPrimElem (primElem, vBuf, v);
3438
3439        CFList source, dest;
3440        CanonicalForm bufA= mapUp (A, alpha, v, primElem, imPrimElem,
3441                                   source, dest);
3442        ExtensionInfo info= ExtensionInfo (v, alpha, imPrimElem, primElem);
3443        factors= multiFactorize (bufA, info);
3444      }
3445      else
3446      {
3447        Variable v= chooseExtension (alpha, beta, k);
3448        CanonicalForm primElem, imPrimElem;
3449        bool primFail= false;
3450        Variable vBuf;
3451        ASSERT (!primFail, "failure in integer factorizer");
3452        if (primFail)
3453          ; //ERROR
3454        else
3455          imPrimElem= mapPrimElem (delta, beta, v);
3456
3457        CFList source, dest;
3458        CanonicalForm bufA= mapDown (A, info, source, dest);
3459        source= CFList();
3460        dest= CFList();
3461        bufA= mapUp (bufA, beta, v, delta, imPrimElem, source, dest);
3462        ExtensionInfo info= ExtensionInfo (v, beta, imPrimElem, delta);
3463        factors= multiFactorize (bufA, info);
3464      }
3465    }
3466    return factors;
3467  }
3468  else // we are in GF (p^k)
3469  {
3470    int p= getCharacteristic();
3471    int extensionDeg= getGFDegree();
3472    bool extension= true;
3473    if (k == 1) // need factorization over F_p
3474    {
3475      extensionDeg++;
3476      if (pow ((double) p, (double) extensionDeg) < (1<<16))
3477      // pass to GF(p^k+1)
3478      {
3479        CanonicalForm mipo= gf_mipo;
3480        setCharacteristic (p);
3481        Variable vBuf= rootOf (mipo.mapinto());
3482        A= GF2FalphaRep (A, vBuf);
3483        setCharacteristic (p, extensionDeg, 'Z');
3484        ExtensionInfo info= ExtensionInfo (extension);
3485        factors= multiFactorize (A.mapinto(), info);
3486      }
3487      else // not able to pass to another GF, pass to F_p(\alpha)
3488      {
3489        CanonicalForm mipo= gf_mipo;
3490        setCharacteristic (p);
3491        Variable vBuf= rootOf (mipo.mapinto());
3492        A= GF2FalphaRep (A, vBuf);
3493        Variable v= chooseExtension (vBuf, beta, k);
3494        ExtensionInfo info= ExtensionInfo (v, extension);
3495        factors= multiFactorize (A, info);
3496      }
3497    }
3498    else // need factorization over GF (p^k)
3499    {
3500      if (pow ((double) p, (double) 2*extensionDeg) < (1<<16))
3501      // pass to GF(p^2k)
3502      {
3503        setCharacteristic (p, 2*extensionDeg, 'Z');
3504        ExtensionInfo info= ExtensionInfo (k, cGFName, extension);
3505        factors= multiFactorize (GFMapUp (A, extensionDeg), info);
3506        setCharacteristic (p, extensionDeg, cGFName);
3507      }
3508      else // not able to pass to GF (p^2k), pass to F_p (\alpha)
3509      {
3510        CanonicalForm mipo= gf_mipo;
3511        setCharacteristic (p);
3512        Variable v1= rootOf (mipo.mapinto());
3513        A= GF2FalphaRep (A, v1);
3514        Variable v2= chooseExtension (v1, v1, k);
3515        CanonicalForm primElem, imPrimElem;
3516        bool primFail= false;
3517        Variable vBuf;
3518        primElem= primitiveElement (v1, v1, primFail);
3519        if (primFail)
3520          ; //ERROR
3521        else
3522          imPrimElem= mapPrimElem (primElem, v1, v2);
3523        CFList source, dest;
3524        CanonicalForm bufA= mapUp (A, v1, v2, primElem, imPrimElem,
3525                                     source, dest);
3526        ExtensionInfo info= ExtensionInfo (v2, v1, imPrimElem, primElem);
3527        factors= multiFactorize (bufA, info);
3528        setCharacteristic (p, k, cGFName);
3529        for (CFListIterator i= factors; i.hasItem(); i++)
3530          i.getItem()= Falpha2GFRep (i.getItem());
3531      }
3532    }
3533    return factors;
3534  }
3535}
3536
3537#endif
3538/* HAVE_NTL */
3539
Note: See TracBrowser for help on using the repository browser.