source: git/factory/facFqFactorize.cc @ f2341ef

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