source: git/factory/facFqFactorize.cc @ 78a4f8b

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