source: git/factory/facFqFactorize.cc @ 1101a8

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