source: git/factory/facFqFactorize.cc @ c3e25cb

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