source: git/factory/facFqFactorize.cc @ 0851b0

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