source: git/factory/facFqFactorize.cc @ ef3f67

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