source: git/factory/facFqFactorize.cc @ 8267b8

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