Changeset 44651b in git


Ignore:
Timestamp:
Jun 17, 2010, 6:19:12 PM (14 years ago)
Author:
Hans Schoenemann <hannes@…>
Branches:
(u'fieker-DuVal', '117eb8c30fc9e991c4decca4832b1d19036c4c65')(u'spielwiese', 'b52fc4b2495505785981d640dcf7eb3e456778ef')
Children:
e558c41b132228287898863201fbd5c35b4231fd
Parents:
d52c121e17973d80d9181edd4a487916a0741038
Message:
index fixed

git-svn-id: file:///usr/local/Singular/svn/trunk@12883 2c84dea3-7e68-4137-9b89-c4e89433aadc
File:
1 edited

Legend:

Unmodified
Added
Removed
  • factory/facFqFactorize.cc

    rd52c12 r44651b  
    11/*****************************************************************************\
    2  * Computer Algebra System SINGULAR   
     2 * Computer Algebra System SINGULAR
    33\*****************************************************************************/
    44/** @file facFqFactorize.cc
    5  * 
     5 *
    66 * This file implements functions for factoring a multivariate polynomial over
    7  * a finite field. 
    8  * 
    9  * ABSTRACT: "Efficient Multivariate Factorization over Finite Fields" by 
    10  * L. Bernardin & M. Monagon. 
     7 * a finite field.
     8 *
     9 * ABSTRACT: "Efficient Multivariate Factorization over Finite Fields" by
     10 * L. Bernardin & M. Monagon.
    1111 *
    1212 * @author Martin Lee
     
    4040
    4141static inline
    42 CanonicalForm 
     42CanonicalForm
    4343listGCD (const CFList& L);
    4444
    4545static inline
    46 CanonicalForm 
     46CanonicalForm
    4747myContent (const CanonicalForm& F)
    4848{
     
    5858    if (GF)
    5959    {
    60       return swapvar (GCD_GF (L.getFirst(), L.getLast()), F.mvar(), 
     60      return swapvar (GCD_GF (L.getFirst(), L.getLast()), F.mvar(),
    6161                      Variable (1));
    6262    }
    6363    else if (!GF && algExt)
    6464    {
    65       return swapvar (GCD_Fp_extension (L.getFirst(), L.getLast(), alpha), 
     65      return swapvar (GCD_Fp_extension (L.getFirst(), L.getLast(), alpha),
    6666                                       F.mvar(), Variable (1));
    6767    }
    6868    else
    69       return swapvar (GCD_small_p (L.getFirst(), L.getLast()), F.mvar(), 
     69      return swapvar (GCD_small_p (L.getFirst(), L.getLast()), F.mvar(),
    7070                     Variable (1));
    7171  }
     
    7878
    7979static inline
    80 CanonicalForm 
     80CanonicalForm
    8181listGCD (const CFList& L)
    8282{
     
    9191      return GCD_GF (L.getFirst(), L.getLast());
    9292    }
    93     else if (!GF && (hasFirstAlgVar (L.getFirst(), alpha) || 
     93    else if (!GF && (hasFirstAlgVar (L.getFirst(), alpha) ||
    9494                     hasFirstAlgVar (L.getLast(), alpha)))
    9595    {
     
    107107    int j= 0;
    108108    for (CFListIterator i= L; j < length; i++, j++)
    109       lHi.append (i.getItem());   
     109      lHi.append (i.getItem());
    110110    lLo= Difference (L, lHi);
    111111    resultHi= listGCD (lHi);
     
    117117      return GCD_GF (resultHi, resultLo);
    118118    }
    119     else if (!GF && (hasFirstAlgVar (resultHi, alpha) || 
     119    else if (!GF && (hasFirstAlgVar (resultHi, alpha) ||
    120120                     hasFirstAlgVar (resultLo, alpha)))
    121121    {
     
    158158    {
    159159      if (swap)
    160         return swapvar(GCD_Fp_extension (L.getFirst(), L.getLast(), alpha), 
     160        return swapvar(GCD_Fp_extension (L.getFirst(), L.getLast(), alpha),
    161161                                         F.mvar(), x);
    162162      else
     
    166166    {
    167167      if (swap)
    168         return swapvar (GCD_small_p (L.getFirst(), L.getLast()), F.mvar(), 
     168        return swapvar (GCD_small_p (L.getFirst(), L.getLast()), F.mvar(),
    169169                        x);
    170170      else
     
    194194    if (GF)
    195195      return (F/GCD_GF (F, G))*G;
    196     else if (!GF && (hasFirstAlgVar (F, alpha) || 
     196    else if (!GF && (hasFirstAlgVar (F, alpha) ||
    197197                     hasFirstAlgVar (G, alpha)))
    198198      return (F/GCD_Fp_extension (F, G, alpha))*G;
     
    203203
    204204
    205 static inline 
     205static inline
    206206CanonicalForm myCompress (const CanonicalForm& F, CFMap& N)
    207207{
     
    210210  int ** swap;
    211211  swap= new int* [n + 1];
    212   for (int i= 0; i <= n; i++) 
     212  for (int i= 0; i <= n; i++)
    213213  {
    214214    degsf[i]= 0;
    215215    swap [i]= new int [2];
     216    swap [i] [0]= 0;
    216217    swap [i] [1]= 0;
    217     swap [i] [2]= 0;
    218218  }
    219219  int i= 1;
    220   n= 1; 
     220  n= 1;
    221221  degsf= degrees (F, degsf);
    222222
    223223  CanonicalForm result= F;
    224   while ( i <= F.level() ) 
     224  while ( i <= F.level() )
    225225  {
    226226    while( degsf[i] == 0 ) i++;
    227     swap[n][1]= i;
    228     swap[n][2]= degsf[i];
     227    swap[n][0]= i;
     228    swap[n][1]= degsf[i];
    229229    if (i != n)
    230230      result= swapvar (result, Variable (n), Variable(i));
     
    235235  n--;
    236236
    237   for (i= 1; i < n; i++)
    238   {
    239     for (int j= 1; j < n - i + 1; j++)
    240     {
    241       if (swap[j][2] < swap[j + 1][2])
    242       {
    243         buf1= swap [j + 1] [1];
    244         buf2= swap [j + 1] [2];
     237  for (i= 1; i < n; i++)
     238  {
     239    for (int j= 1; j < n - i + 1; j++)
     240    {
     241      if (swap[j][1] < swap[j + 1][1])
     242      {
     243        buf1= swap [j + 1] [0];
     244        buf2= swap [j + 1] [1];
     245        swap[j + 1] [0]= swap[j] [0];
    245246        swap[j + 1] [1]= swap[j] [1];
    246         swap[j + 1] [2]= swap[j] [2];
    247         swap[j][1]= buf1;
    248         swap[j][2]= buf2;
     247        swap[j][0]= buf1;
     248        swap[j][1]= buf2;
    249249        result= swapvar (result, Variable (j + 1), Variable (j));
    250       }     
    251     }
    252   }
    253 
    254   for (i= n; i > 0; i--) 
    255   {
    256     if (i != swap[i] [1])
    257       N.newpair (Variable (i), Variable (swap[i] [1]));
     250      }
     251    }
     252  }
     253
     254  for (i= n; i > 0; i--)
     255  {
     256    if (i != swap[i] [0])
     257      N.newpair (Variable (i), Variable (swap[i] [0]));
    258258  }
    259259
     
    266266  return result;
    267267}
    268  
    269 CFList 
     268
     269CFList
    270270monicFactorRecombi (const CFList& factors,const CanonicalForm& F, const
    271                     CanonicalForm& M, const DegreePattern& degs) 
     271                    CanonicalForm& M, const DegreePattern& degs)
    272272{
    273   if (degs.getLength() == 1) 
    274     return CFList(F); 
     273  if (degs.getLength() == 1)
     274    return CFList(F);
    275275
    276276  CFList T, S;
    277  
     277
    278278  T= factors;
    279279
     
    290290  int subsetDeg;
    291291  DegreePattern bufDegs1= degs, bufDegs2;
    292   TT= copy (factors); 
    293   while (T.length() >= 2*s) 
    294   {
    295     while (noSubset == false) 
    296     {
    297       if (T.length() == s) 
     292  TT= copy (factors);
     293  while (T.length() >= 2*s)
     294  {
     295    while (noSubset == false)
     296    {
     297      if (T.length() == s)
    298298      {
    299299        result.append (prodMod (T, M));
     
    303303      if (noSubset) break;
    304304      subsetDeg= subsetDegree (S);
    305       if (!degs.find (subsetDeg)) 
     305      if (!degs.find (subsetDeg))
    306306        continue;
    307       else 
    308       { 
     307      else
     308      {
    309309        g= prodMod0 (S, M);
    310310        gg= mod (g*LCBuf, M); //univariate polys
     
    324324            bufDegs2= DegreePattern (T);
    325325            bufDegs1.intersect (bufDegs2);
    326             bufDegs1.refine (); 
    327             if (T.length() < 2*s || T.length() == s || 
    328                 bufDegs1.getLength() == 1) 
     326            bufDegs1.refine ();
     327            if (T.length() < 2*s || T.length() == s ||
     328                bufDegs1.getLength() == 1)
    329329            {
    330               result.append (prodMod (T, M)); 
    331               return result; 
     330              result.append (prodMod (T, M));
     331              return result;
    332332            }
    333333            TT= copy (T);
    334334            indexUpdate (v, s, T.length(), noSubset);
    335             if (noSubset) break; 
     335            if (noSubset) break;
    336336          }
    337337        }
     
    339339    }
    340340    s++;
    341     if (T.length() < 2*s || T.length() == s) 
     341    if (T.length() < 2*s || T.length() == s)
    342342    {
    343343      result.append (prodMod (T, M));
     
    349349    noSubset= false;
    350350  }
    351   if (T.length() < 2*s) 
    352     result.append (prodMod (T, M)); 
    353 
    354   return result; 
    355 } 
    356 
    357 CFList 
    358 earlyMonicFactorDetect (CanonicalForm& F, CFList& factors, 
     351  if (T.length() < 2*s)
     352    result.append (prodMod (T, M));
     353
     354  return result;
     355}
     356
     357CFList
     358earlyMonicFactorDetect (CanonicalForm& F, CFList& factors,
    359359                        int& adaptedLiftBound, DegreePattern& degs,
    360360                        bool& success, int deg, const int bound)
     
    371371  int e= 0;
    372372  adaptedLiftBound= 0;
    373   for (CFListIterator i= factors; i.hasItem(); i++) 
     373  for (CFListIterator i= factors; i.hasItem(); i++)
    374374  {
    375375    if (!bufDegs1.find (degree (i.getItem(), 1)))
     
    392392          d -= degree (gg) + degree (LC (gg, 1));
    393393          e= tmax (e, degree (gg) + degree (LC (gg, 1)));
    394           LCBuf= LC (buf, Variable (1)); 
     394          LCBuf= LC (buf, Variable (1));
    395395          T= Difference (T, CFList (i.getItem()));
    396396
     
    398398          bufDegs2= DegreePattern (T);
    399399          bufDegs1.intersect (bufDegs2);
    400           bufDegs1.refine (); 
     400          bufDegs1.refine ();
    401401          if (bufDegs1.getLength() <= 1)
    402402          {
    403             result.append (prodMod (T, M)); 
     403            result.append (prodMod (T, M));
    404404            break;
    405405          }
     
    410410  adaptedLiftBound= d;
    411411
    412   if (adaptedLiftBound < deg) 
     412  if (adaptedLiftBound < deg)
    413413  {
    414414    factors= T;
     
    457457
    458458CFList biFactorizer (const CanonicalForm& F, const Variable& alpha,
    459                      CanonicalForm& bivarEval, int& liftBound) 
     459                     CanonicalForm& bivarEval, int& liftBound)
    460460{
    461461  CanonicalForm A= F;
    462462  bool GF= (CFFactory::gettype() == GaloisFieldDomain);
    463463
    464   if (A.isUnivariate()) 
     464  if (A.isUnivariate())
    465465    return uniFactorizer (F, alpha, GF);
    466  
     466
    467467
    468468  CFMap N;
     
    482482  //trivial case
    483483  CFList factors;
    484   if (A.inCoeffDomain()) 
     484  if (A.inCoeffDomain())
    485485  {
    486486    append (factors, contentAyFactors);
     
    489489    return factors;
    490490  }
    491   else if (A.isUnivariate()) 
    492   {
    493     if (A.mvar() == x) 
     491  else if (A.isUnivariate())
     492  {
     493    if (A.mvar() == x)
    494494      factors= uniFactorizer (A, alpha, GF);
    495495    append (factors, contentAyFactors);
     
    503503  DegreePattern degs;
    504504  DegreePattern bufDegs;
    505  
     505
    506506  int factorNums= 5;
    507   if (factorNums < (int) ceil (log (totaldegree (A)))) 
     507  if (factorNums < (int) ceil (log (totaldegree (A))))
    508508    factorNums= (int) ceil (log (totaldegree (A)));
    509   for (int i= 0; i < factorNums; i++) 
    510   {
    511     if (i == 0) 
     509  for (int i= 0; i < factorNums; i++)
     510  {
     511    if (i == 0)
    512512      Aeval= A (bivarEval, y);
    513513    else if (i > 0 && contentAx.inCoeffDomain())
    514514    {
    515       Aeval= A; 
     515      Aeval= A;
    516516      evaluation= evalPoint (A, Aeval, alpha, list, GF, fail);
    517517    }
    518  
    519     if (fail && (i != 0)) 
     518
     519    if (fail && (i != 0))
    520520      break;
    521521
     
    523523    uniFactors= uniFactorizer (Aeval, alpha, GF);
    524524
    525     if (uniFactors.length() == 1) 
    526     { 
     525    if (uniFactors.length() == 1)
     526    {
    527527      append (factors, contentAyFactors);
    528528      if (contentAyFactors.isEmpty())
    529529        factors.append (F/lc(F));
    530       else 
     530      else
    531531      {
    532532        A= A (y - bivarEval, y);
     
    537537          (void) extgcd (LC (A, 1), power (y, liftBound), s, t);
    538538          A *= s;
    539           A= mod (A, power (y, liftBound)); 
     539          A= mod (A, power (y, liftBound));
    540540        }
    541541        factors.append (A);
    542542      }
    543543      decompress (factors, N);
    544       bivarEval= N (bivarEval); 
     544      bivarEval= N (bivarEval);
    545545      return factors;
    546546    }
     
    549549    degs= DegreePattern (uniFactors);
    550550
    551     if (i == 0) 
     551    if (i == 0)
    552552    {
    553553      bufAeval= Aeval;
     
    558558        break;
    559559    }
    560     else 
    561     {
    562       bufDegs.intersect (degs); 
    563       if (uniFactors.length() < bufUniFactors.length()) 
    564       { 
     560    else
     561    {
     562      bufDegs.intersect (degs);
     563      if (uniFactors.length() < bufUniFactors.length())
     564      {
    565565        bufUniFactors= uniFactors;
    566566        bufAeval= Aeval;
     
    574574      if (contentAyFactors.isEmpty())
    575575        factors.append (F/lc(F));
    576       else 
     576      else
    577577      {
    578578        A= A (y - bivarEval, y);
     
    583583          (void) extgcd (LC (A, 1), power (y, liftBound), s, t);
    584584          A *= s;
    585           A= mod (A, power (y, liftBound)); 
     585          A= mod (A, power (y, liftBound));
    586586        }
    587587        factors.append (A);
    588588      }
    589589      decompress (factors, N);
    590       bivarEval= N (bivarEval); 
     590      bivarEval= N (bivarEval);
    591591      return factors;
    592592    }
     
    600600  // Hensel lifting
    601601  CFList diophant;
    602   CFMatrix M= CFMatrix (liftBound, bufUniFactors.length() - 1); 
     602  CFMatrix M= CFMatrix (liftBound, bufUniFactors.length() - 1);
    603603  CFArray Pi;
    604604  bool earlySuccess= false;
     
    639639                          1, Pi, diophant, M);
    640640      earlyFactors= earlyMonicFactorDetect (A, bufUniFactors, newLiftBound,
    641                                              bufDegs, earlySuccess, 
     641                                             bufDegs, earlySuccess,
    642642                                             degree (A, y) + 1, liftBound);
    643643      if (bufDegs.getLength() > 1 && !earlySuccess)
    644644      {
    645         if (newLiftBound > degree (A, y) + 1)
    646         {
     645        if (newLiftBound > degree (A, y) + 1)
     646        {
    647647          if (newLiftBound < newLiftBound)
    648             liftBound= newLiftBound;
    649           bufUniFactors.insert (LC(A, x));
    650           henselLiftResume12 (A, bufUniFactors, degree (A, y) + 1, liftBound,
     648            liftBound= newLiftBound;
     649          bufUniFactors.insert (LC(A, x));
     650          henselLiftResume12 (A, bufUniFactors, degree (A, y) + 1, liftBound,
    651651                              Pi, diophant, M);
    652         }
     652        }
    653653      }
    654654      else if (earlySuccess)
     
    667667    factors= monicFactorRecombi (bufUniFactors, A, MODl, bufDegs);
    668668
    669   if (earlySuccess) 
     669  if (earlySuccess)
    670670    factors= Union (earlyFactors, factors);
    671671  else if (!earlySuccess && bufDegs.getLength() == 1)
     
    679679}
    680680
    681 CFList 
    682 extFactorRecombination (const CFList& factors, const CanonicalForm& F, 
    683                         const CFList& M, const ExtensionInfo& info, 
     681CFList
     682extFactorRecombination (const CFList& factors, const CanonicalForm& F,
     683                        const CFList& M, const ExtensionInfo& info,
    684684                        const CFList& evaluation)
    685 { 
     685{
    686686  Variable alpha= info.getAlpha();
    687687  Variable beta= info.getBeta();
     
    690690  int k= info.getGFDegree();
    691691  CFList source, dest;
    692   if (factors.length() == 1) 
     692  if (factors.length() == 1)
    693693  {
    694694    CanonicalForm buf= reverseShift (F, evaluation);
    695     return CFList (mapDown (buf, info, source, dest)); 
    696   } 
     695    return CFList (mapDown (buf, info, source, dest));
     696  }
    697697  if (factors.length() < 1)
    698698    return CFList();
     
    711711  CanonicalForm buf;
    712712  if (beta != Variable (1))
    713     buf= mapDown (F, gamma, delta, alpha, source, dest); 
     713    buf= mapDown (F, gamma, delta, alpha, source, dest);
    714714  else
    715715    buf= F;
    716716
    717   CanonicalForm g, LCBuf= LC (buf, Variable (1)); 
     717  CanonicalForm g, LCBuf= LC (buf, Variable (1));
    718718  CanonicalForm buf2;
    719719  int v [T.length()];
     
    723723  CFArray TT;
    724724  int subsetDeg;
    725   TT= copy (factors); 
     725  TT= copy (factors);
    726726  bool recombination= false;
    727   while (T.length() >= 2*s) 
    728   {
    729     while (noSubset == false) 
    730     {
    731       if (T.length() == s) 
     727  while (T.length() >= 2*s)
     728  {
     729    while (noSubset == false)
     730    {
     731      if (T.length() == s)
    732732      {
    733733        if (recombination)
     
    757757      S.removeFirst();
    758758      g /= myContent (g);
    759       if (fdivides (g, buf)) 
    760       {
    761         buf2= reverseShift (g, evaluation);
     759      if (fdivides (g, buf))
     760      {
     761        buf2= reverseShift (g, evaluation);
    762762        buf2 /= Lc (buf2);
    763         if (!k && beta == Variable (1))
    764         {
    765           if (degree (buf2, alpha) < degMipoBeta)
    766           { 
    767             appendTestMapDown (result, buf2, info, source, dest);
    768             buf /= g;
    769             LCBuf= LC (buf, Variable (1));
    770             recombination= true;
    771           }
    772         }
    773         else
    774         {
    775           if (!isInExtension (buf2, delta, k))
    776           {
    777             appendTestMapDown (result, buf2, info, source, dest);
    778             buf /= g;
    779             LCBuf= LC (buf, Variable (1));
    780             recombination= true;
    781           }
    782         }
    783         T= Difference (T, S);
    784 
    785         if (T.length() < 2*s || T.length() == s)
    786         {
    787           buf= reverseShift (buf, evaluation);
     763        if (!k && beta == Variable (1))
     764        {
     765          if (degree (buf2, alpha) < degMipoBeta)
     766          {
     767            appendTestMapDown (result, buf2, info, source, dest);
     768            buf /= g;
     769            LCBuf= LC (buf, Variable (1));
     770            recombination= true;
     771          }
     772        }
     773        else
     774        {
     775          if (!isInExtension (buf2, delta, k))
     776          {
     777            appendTestMapDown (result, buf2, info, source, dest);
     778            buf /= g;
     779            LCBuf= LC (buf, Variable (1));
     780            recombination= true;
     781          }
     782        }
     783        T= Difference (T, S);
     784
     785        if (T.length() < 2*s || T.length() == s)
     786        {
     787          buf= reverseShift (buf, evaluation);
    788788          buf /= Lc (buf);
    789           appendTestMapDown (result, buf, info, source, dest);
    790           return result;
    791         }
    792         TT= copy (T);
    793         indexUpdate (v, s, T.length(), noSubset);
    794         if (noSubset) break;       
     789          appendTestMapDown (result, buf, info, source, dest);
     790          return result;
     791        }
     792        TT= copy (T);
     793        indexUpdate (v, s, T.length(), noSubset);
     794        if (noSubset) break;
    795795      }
    796796    }
    797797    s++;
    798     if (T.length() < 2*s || T.length() == s) 
     798    if (T.length() < 2*s || T.length() == s)
    799799    {
    800800      buf= reverseShift (buf, evaluation);
     
    809809  if (T.length() < 2*s)
    810810  {
    811     buf= reverseShift (F, evaluation); 
    812     appendMapDown (result, buf, info, source, dest); 
    813   }
    814 
    815   return result; 
    816 } 
    817 
    818 CFList 
    819 factorRecombination (const CanonicalForm& F, const CFList& factors, 
     811    buf= reverseShift (F, evaluation);
     812    appendMapDown (result, buf, info, source, dest);
     813  }
     814
     815  return result;
     816}
     817
     818CFList
     819factorRecombination (const CanonicalForm& F, const CFList& factors,
    820820                     const CFList& M)
    821821{
    822   if (factors.length() == 1) 
     822  if (factors.length() == 1)
    823823    return CFList(F);
    824824  if (factors.length() < 1)
     
    839839  CFArray TT;
    840840  int subsetDeg;
    841   TT= copy (factors); 
     841  TT= copy (factors);
    842842  Variable y= F.level() - 1;
    843843  bool recombination= false;
    844844  CanonicalForm h;
    845   while (T.length() >= 2*s) 
    846   {
    847     while (noSubset == false) 
    848     {
    849       if (T.length() == s) 
     845  while (T.length() >= 2*s)
     846  {
     847    while (noSubset == false)
     848    {
     849      if (T.length() == s)
    850850      {
    851851        if (recombination)
     
    872872        LCBuf= LC (buf, Variable(1));
    873873        T= Difference (T, S);
    874         if (T.length() < 2*s || T.length() == s)
    875         {
    876           result.append (buf);
    877           return result;
    878         }
    879         TT= copy (T);
    880         indexUpdate (v, s, T.length(), noSubset);
    881         if (noSubset) break;       
     874        if (T.length() < 2*s || T.length() == s)
     875        {
     876          result.append (buf);
     877          return result;
     878        }
     879        TT= copy (T);
     880        indexUpdate (v, s, T.length(), noSubset);
     881        if (noSubset) break;
    882882      }
    883883    }
    884884    s++;
    885     if (T.length() < 2*s || T.length() == s) 
     885    if (T.length() < 2*s || T.length() == s)
    886886    {
    887887      result.append (buf);
     
    893893    noSubset= false;
    894894  }
    895   if (T.length() < 2*s) 
     895  if (T.length() < 2*s)
    896896    result.append (F);
    897897
    898   return result; 
     898  return result;
    899899}
    900900
     
    913913  int e= 0;
    914914  int nBuf;
    915   for (CFListIterator i= factors; i.hasItem(); i++) 
    916   {
    917     g= mulMod (i.getItem(), LCBuf, M); 
     915  for (CFListIterator i= factors; i.hasItem(); i++)
     916  {
     917    g= mulMod (i.getItem(), LCBuf, M);
    918918    g /= myContent (g);
    919919    if (fdivides (g, buf))
     
    923923      e= tmax (e, nBuf);
    924924      buf /= g;
    925       LCBuf= LC (buf, Variable (1)); 
     925      LCBuf= LC (buf, Variable (1));
    926926    }
    927927  }
    928928  adaptedLiftBound= d;
    929929
    930   if (adaptedLiftBound < deg) 
    931   { 
     930  if (adaptedLiftBound < deg)
     931  {
    932932    if (adaptedLiftBound < degree (F) + 1)
    933933    {
     
    939939          success= false;
    940940        }
    941         else 
     941        else
    942942        {
    943943          success= true;
     
    951951      {
    952952        success= true;
    953         adaptedLiftBound= deg; 
     953        adaptedLiftBound= deg;
    954954      }
    955955    }
     
    962962}
    963963
    964 int 
    965 extLiftBoundAdaption (const CanonicalForm& F, const CFList& factors, bool& 
    966                       success, const ExtensionInfo& info, const CFList& eval, 
     964int
     965extLiftBoundAdaption (const CanonicalForm& F, const CFList& factors, bool&
     966                      success, const ExtensionInfo& info, const CFList& eval,
    967967                      const int deg, const CFList& MOD, const int bound)
    968968{
     
    981981  adaptedLiftBound= 0;
    982982  int d= bound;
    983   int e= 0; 
     983  int e= 0;
    984984  int nBuf;
    985985  int degMipoBeta;
     
    989989    degMipoBeta= degree (getMipo (beta));
    990990
    991   for (CFListIterator i= factors; i.hasItem(); i++) 
     991  for (CFListIterator i= factors; i.hasItem(); i++)
    992992  {
    993993    g= mulMod (i.getItem(), LCBuf, M);
     
    997997      gg= reverseShift (g, eval);
    998998      gg /= Lc (gg);
    999       if (!k && beta == Variable (1)) 
     999      if (!k && beta == Variable (1))
    10001000      {
    10011001        if (degree (gg, alpha) < degMipoBeta)
    1002         { 
    1003           buf /= g;
    1004           nBuf= degree (g, y) + degree (LC (g, Variable (1)), y);
    1005           d -= nBuf;
    1006           e= tmax (e, nBuf);
    1007           LCBuf= LC (buf, Variable (1));           
    1008         }
    1009       }
    1010       else
    1011       {
    1012         if (!isInExtension (gg, delta, k))
    10131002        {
    10141003          buf /= g;
     
    10191008        }
    10201009      }
    1021     }
     1010      else
     1011      {
     1012        if (!isInExtension (gg, delta, k))
     1013        {
     1014          buf /= g;
     1015          nBuf= degree (g, y) + degree (LC (g, Variable (1)), y);
     1016          d -= nBuf;
     1017          e= tmax (e, nBuf);
     1018          LCBuf= LC (buf, Variable (1));
     1019        }
     1020      }
     1021    }
    10221022  }
    10231023  adaptedLiftBound= d;
     
    10341034          success= false;
    10351035        }
    1036         else 
     1036        else
    10371037        {
    10381038          success= true;
     
    10431043        }
    10441044      }
    1045       else 
     1045      else
    10461046      {
    10471047        success= true;
    1048         adaptedLiftBound= deg; 
     1048        adaptedLiftBound= deg;
    10491049      }
    10501050    }
     
    10581058}
    10591059
    1060 CFList 
     1060CFList
    10611061earlyFactorDetect (CanonicalForm& F, CFList& factors, int& adaptedLiftBound,
    1062                    bool& success, const int deg, const CFList& MOD, 
     1062                   bool& success, const int deg, const CFList& MOD,
    10631063                   const int bound)
    10641064{
     
    10751075  int e= 0;
    10761076  int nBuf;
    1077   for (CFListIterator i= factors; i.hasItem(); i++) 
     1077  for (CFListIterator i= factors; i.hasItem(); i++)
    10781078  {
    10791079    g= mulMod (i.getItem(), LCBuf, M);
     
    10861086      e= tmax (e, nBuf);
    10871087      buf /= g;
    1088       LCBuf= LC (buf, Variable (1)); 
     1088      LCBuf= LC (buf, Variable (1));
    10891089      T= Difference (T, CFList (i.getItem()));
    10901090    }
     
    10921092  adaptedLiftBound= d;
    10931093
    1094   if (adaptedLiftBound < deg) 
     1094  if (adaptedLiftBound < deg)
    10951095  {
    10961096    if (adaptedLiftBound < degree (F) + 1)
     
    10991099        adaptedLiftBound= tmin (e + 1, deg);
    11001100      else
    1101         adaptedLiftBound= deg; 
     1101        adaptedLiftBound= deg;
    11021102    }
    11031103    factors= T;
     
    11081108}
    11091109
    1110 CFList 
     1110CFList
    11111111extEarlyFactorDetect (CanonicalForm& F, CFList& factors, int& adaptedLiftBound,
    1112                       bool& success, const ExtensionInfo& info, const CFList& 
     1112                      bool& success, const ExtensionInfo& info, const CFList&
    11131113                      eval, const int deg, const CFList& MOD, const int bound)
    11141114{
     
    11381138    degMipoBeta= degree (getMipo (beta));
    11391139
    1140   for (CFListIterator i= factors; i.hasItem(); i++) 
     1140  for (CFListIterator i= factors; i.hasItem(); i++)
    11411141  {
    11421142    g= mulMod (i.getItem(), LCBuf, M);
     
    11461146      gg= reverseShift (g, eval);
    11471147      gg /= Lc (gg);
    1148           if (!k && beta == Variable (1)) 
     1148          if (!k && beta == Variable (1))
    11491149          {
    11501150            if (degree (gg, alpha) < degMipoBeta)
    1151             { 
     1151            {
    11521152              appendTestMapDown (result, gg, info, source, dest);
    11531153              buf /= g;
     
    11551155              d -= nBuf;
    11561156              e= tmax (e, nBuf);
    1157               LCBuf= LC (buf, Variable (1));           
     1157              LCBuf= LC (buf, Variable (1));
    11581158            }
    11591159          }
    1160           else 
     1160          else
    11611161          {
    11621162            if (!isInExtension (gg, delta, k))
     
    11691169              LCBuf= LC (buf, Variable (1));
    11701170            }
    1171           } 
     1171          }
    11721172      T= Difference (T, CFList (i.getItem()));
    11731173    }
     
    11821182        adaptedLiftBound= tmin (e + 1, deg);
    11831183      else
    1184         adaptedLiftBound= deg; 
     1184        adaptedLiftBound= deg;
    11851185    }
    11861186    success= true;
     
    11911191}
    11921192
    1193 CFList 
     1193CFList
    11941194evalPoints (const CanonicalForm& F, CFList & eval, const Variable& alpha,
    1195             CFList& list, const bool& GF, bool& fail) 
    1196 { 
     1195            CFList& list, const bool& GF, bool& fail)
     1196{
    11971197  int k= F.level() - 1;
    11981198  Variable x= Variable (1);
     
    12011201  GFRandom genGF;
    12021202  int p= getCharacteristic ();
    1203   double bound; 
    1204   if (alpha != Variable (1)) 
     1203  double bound;
     1204  if (alpha != Variable (1))
    12051205  {
    12061206    bound= pow ((double) p, (double) degree (getMipo(alpha)));
    12071207    bound= pow ((double) bound, (double) k);
    12081208  }
    1209   else if (GF) 
     1209  else if (GF)
    12101210  {
    12111211    bound= pow ((double) p, (double) getGFDegree());
     
    12171217  CanonicalForm random;
    12181218  CanonicalForm deriv_x, gcd_deriv;
    1219   do 
     1219  do
    12201220  {
    12211221    random= 0;
    12221222    // possible overflow if list.length() does not fit into a int
    1223     if (list.length() >= bound) 
    1224     { 
     1223    if (list.length() >= bound)
     1224    {
    12251225      fail= true;
    12261226      break;
    12271227    }
    1228     for (int i= 0; i < k; i++) 
    1229     { 
    1230       if (GF) 
     1228    for (int i= 0; i < k; i++)
     1229    {
     1230      if (GF)
    12311231      {
    12321232        result.append (genGF.generate());
    12331233        random += result.getLast()*power (x, i);
    12341234      }
    1235       else if (alpha != Variable(1)) 
    1236       {   
     1235      else if (alpha != Variable(1))
     1236      {
    12371237        AlgExtRandomF genAlgExt (alpha);
    12381238        result.append (genAlgExt.generate());
    1239         random += result.getLast()*power (x, i); 
    1240       }
    1241       else 
    1242       { 
     1239        random += result.getLast()*power (x, i);
     1240      }
     1241      else
     1242      {
    12431243        result.append (genFF.generate());
    12441244        random += result.getLast()*power (x, i);
    1245       } 
    1246     }
    1247     if (find (list, random)) 
     1245      }
     1246    }
     1247    if (find (list, random))
    12481248    {
    12491249      result= CFList();
     
    12521252    int l= F.level();
    12531253    eval.insert (F);
    1254     for (CFListIterator i= result; i.hasItem(); i++, l--) 
     1254    for (CFListIterator i= result; i.hasItem(); i++, l--)
    12551255      eval.insert (eval.getFirst()(i.getItem(), l));
    12561256
    1257     if (degree (eval.getFirst()) != degree (F, 1)) 
     1257    if (degree (eval.getFirst()) != degree (F, 1))
    12581258    {
    12591259      if (!find (list, random))
     
    12621262      eval= CFList();
    12631263      continue;
    1264     }     
    1265    
     1264    }
     1265
    12661266    deriv_x= deriv (eval.getFirst(), x);
    12671267    gcd_deriv= gcd (eval.getFirst(), deriv_x);
    1268     if (degree (gcd_deriv) > 0) 
    1269     { 
     1268    if (degree (gcd_deriv) > 0)
     1269    {
    12701270      if (!find (list, random))
    12711271        list.append (random);
     
    12861286    }
    12871287
    1288     if (list.length() >= bound) 
     1288    if (list.length() >= bound)
    12891289    {
    12901290      fail= true;
     
    12931293  } while (find (list, random));
    12941294
    1295   if (!eval.isEmpty()) 
     1295  if (!eval.isEmpty())
    12961296    eval.removeFirst();
    12971297
     
    12991299}
    13001300
    1301 static inline 
     1301static inline
    13021302int newMainVariableSearch (CanonicalForm& A, CFList& Aeval, CFList&
    1303                            evaluation, const Variable& alpha, const int lev) 
    1304 { 
     1303                           evaluation, const Variable& alpha, const int lev)
     1304{
    13051305  Variable x= Variable (1);
    13061306  CanonicalForm derivI, buf;
     
    13121312  Aeval= CFList();
    13131313  evaluation= CFList();
    1314   for (int i= lev; i <= A.level(); i++) 
     1314  for (int i= lev; i <= A.level(); i++)
    13151315  {
    13161316    derivI= deriv (buf, Variable (i));
    13171317    if (!derivI.isZero())
    13181318    {
    1319       buf= swapvar (buf, x, Variable (i)); 
     1319      buf= swapvar (buf, x, Variable (i));
    13201320      Aeval= CFList();
    13211321      evaluation= CFList();
    13221322      fail= false;
    13231323      evaluation= evalPoints (buf, Aeval, alpha, list, GF, fail);
    1324       if (!fail) 
    1325       {
    1326         A= buf;
    1327         swapLevel= i;
    1328         break;
    1329       }
    1330       else 
     1324      if (!fail)
     1325      {
     1326        A= buf;
     1327        swapLevel= i;
     1328        break;
     1329      }
     1330      else
    13311331        buf= A;
    13321332    }
     
    13351335}
    13361336
    1337 static inline 
    1338 CanonicalForm lcmContent (const CanonicalForm& A, CFList& contentAi) 
     1337static inline
     1338CanonicalForm lcmContent (const CanonicalForm& A, CFList& contentAi)
    13391339{
    13401340  int i= A.level();
    13411341  contentAi.append (myContent (A, i));
    13421342  contentAi.append (myContent (A, i - 1));
    1343   CanonicalForm result= myLcm (contentAi.getFirst(), contentAi.getLast()); 
    1344   for (i= i - 2; i > 0; i--) 
     1343  CanonicalForm result= myLcm (contentAi.getFirst(), contentAi.getLast());
     1344  for (i= i - 2; i > 0; i--)
    13451345  {
    13461346    contentAi.append (content (A, i));
     
    13481348  }
    13491349  return result;
    1350 } 
    1351  
     1350}
     1351
    13521352CFList
    13531353henselLiftAndEarly (CanonicalForm& A, CFList& MOD, int*& liftBounds, bool&
    13541354                    earlySuccess, CFList& earlyFactors, const CFList& Aeval,
    1355                     const CFList& biFactors, const CFList& evaluation, 
     1355                    const CFList& biFactors, const CFList& evaluation,
    13561356                    const ExtensionInfo& info)
    13571357{
    13581358  bool extension= info.isInExtension();
    1359   CFList bufFactors= biFactors; 
     1359  CFList bufFactors= biFactors;
    13601360  bufFactors.insert (LC (Aeval.getFirst(), 1));
    13611361
     
    13651365  CFArray Pi;
    13661366  int smallFactorDeg= 11; //tunable parameter
    1367   CFList result; 
     1367  CFList result;
    13681368  int newLiftBound= 0;
    13691369  int adaptedLiftBound= 0;
     
    13891389    {
    13901390      if (!extension)
    1391         earlyFactors= earlyFactorDetect 
     1391        earlyFactors= earlyFactorDetect
    13921392                       (buf, result, adaptedLiftBound, earlySuccess,
    13931393                        degree (buf) + 1, MOD, liftBound);
    13941394      else
    1395         earlyFactors= extEarlyFactorDetect 
     1395        earlyFactors= extEarlyFactorDetect
    13961396                       (buf, result, adaptedLiftBound, earlySuccess,
    1397                         info, evaluation, degree       
     1397                        info, evaluation, degree
    13981398                        (buf) + 1, MOD, liftBound);
    13991399    }
     
    14061406        adaptedLiftBound= extLiftBoundAdaption (buf, result, earlySuccess, info,
    14071407                                                evaluation, degree (buf) + 1,
    1408                                                 MOD, liftBound);       
     1408                                                MOD, liftBound);
    14091409    }
    14101410    if (!earlySuccess)
     
    14131413      liftBounds[1]= adaptedLiftBound;
    14141414      liftBound= adaptedLiftBound;
    1415       henselLiftResume (buf, result, degree (buf) + 1, liftBound, 
     1415      henselLiftResume (buf, result, degree (buf) + 1, liftBound,
    14161416                        Pi, diophant, Mat, MOD);
    1417     } 
     1417    }
    14181418    else
    14191419      liftBounds[1]= adaptedLiftBound;
     
    14261426    {
    14271427      if (!extension)
    1428         earlyFactors= earlyFactorDetect (buf, result, adaptedLiftBound, 
     1428        earlyFactors= earlyFactorDetect (buf, result, adaptedLiftBound,
    14291429                                         earlySuccess, smallFactorDeg, MOD,
    14301430                                         liftBound);
    1431       else 
     1431      else
    14321432        earlyFactors= extEarlyFactorDetect (buf, result, adaptedLiftBound,
    14331433                                            earlySuccess, info, evaluation,
     
    14411441      else
    14421442        adaptedLiftBound= extLiftBoundAdaption (buf, result, earlySuccess, info,
    1443                                                 evaluation, smallFactorDeg, MOD, 
     1443                                                evaluation, smallFactorDeg, MOD,
    14441444                                                liftBound);
    14451445    }
     
    14481448    {
    14491449      result.insert (LC (buf, 1));
    1450       henselLiftResume (buf, result, smallFactorDeg, degree (buf) + 1, 
     1450      henselLiftResume (buf, result, smallFactorDeg, degree (buf) + 1,
    14511451                        Pi, diophant, Mat, MOD);
    14521452      if (Aeval.length() == 2)
     
    14591459           earlyFactors= extEarlyFactorDetect (buf, result, adaptedLiftBound,
    14601460                                               earlySuccess, info, evaluation,
    1461                                                degree (buf) + 1, MOD, 
     1461                                               degree (buf) + 1, MOD,
    14621462                                               liftBound);
    14631463      }
    1464       else 
     1464      else
    14651465      {
    14661466        if (!extension)
    14671467          adaptedLiftBound= liftBoundAdaption (buf, result, earlySuccess,
    1468                                                degree (buf) + 1, MOD,liftBound); 
     1468                                               degree (buf) + 1, MOD,liftBound);
    14691469        else
    1470           adaptedLiftBound= extLiftBoundAdaption (buf, result, earlySuccess, 
     1470          adaptedLiftBound= extLiftBoundAdaption (buf, result, earlySuccess,
    14711471                                                  info, evaluation,
    14721472                                                  degree (buf) + 1, MOD,
     
    14781478        liftBounds[1]= adaptedLiftBound;
    14791479        liftBound= adaptedLiftBound;
    1480         henselLiftResume (buf, result, degree (buf) + 1, liftBound, 
     1480        henselLiftResume (buf, result, degree (buf) + 1, liftBound,
    14811481                          Pi, diophant, Mat, MOD);
    14821482      }
     
    14991499    int liftBoundsLength= Aeval.getLast().level() - 1;
    15001500    for (int i= 2; i <= liftBoundsLength && j.hasItem(); i++, j++)
    1501     { 
     1501    {
    15021502      earlySuccess= false;
    15031503      result.insert (LC (bufEval.getFirst(), 1));
     
    15091509      if (smallFactorDeg >= liftBound)
    15101510        result= henselLift (bufEval, result, MOD, diophant, Pi, Mat,
    1511                             liftBounds[i -  1], liftBounds[i]);
     1511                            liftBounds[i -  1], liftBounds[i]);
    15121512      else if (smallFactorDeg >= degree (buf) + 1)
    15131513      {
    1514         result= henselLift (bufEval, result, MOD, diophant, Pi, Mat,
    1515                             liftBounds[i -  1], degree (buf) + 1);
    1516 
    1517         if (Aeval.length() == i + 1)
    1518         {
    1519           if (!extension)
    1520             earlyFactors= earlyFactorDetect
     1514        result= henselLift (bufEval, result, MOD, diophant, Pi, Mat,
     1515                            liftBounds[i -  1], degree (buf) + 1);
     1516
     1517        if (Aeval.length() == i + 1)
     1518        {
     1519          if (!extension)
     1520            earlyFactors= earlyFactorDetect
    15211521                           (buf, result, adaptedLiftBound, earlySuccess,
    15221522                            degree (buf) + 1, MOD, liftBound);
    1523           else
    1524             earlyFactors= extEarlyFactorDetect
     1523          else
     1524            earlyFactors= extEarlyFactorDetect
    15251525                           (buf, result, adaptedLiftBound, earlySuccess,
    15261526                            info, evaluation, degree (buf) + 1, MOD, liftBound);
    1527         }
    1528         else
    1529         {
    1530           if (!extension)
    1531             adaptedLiftBound= liftBoundAdaption
     1527        }
     1528        else
     1529        {
     1530          if (!extension)
     1531            adaptedLiftBound= liftBoundAdaption
    15321532                                (buf, result, earlySuccess, degree (buf)
    15331533                                 + 1,  MOD, liftBound);
    1534           else
    1535             adaptedLiftBound= extLiftBoundAdaption
    1536                                 (buf, result, earlySuccess, info, evaluation, 
    1537                                  degree (buf) + 1, MOD, liftBound);       
    1538         }
    1539 
    1540         if (!earlySuccess)
    1541         {
    1542           result.insert (LC (buf, 1));
     1534          else
     1535            adaptedLiftBound= extLiftBoundAdaption
     1536                                (buf, result, earlySuccess, info, evaluation,
     1537                                 degree (buf) + 1, MOD, liftBound);
     1538        }
     1539
     1540        if (!earlySuccess)
     1541        {
     1542          result.insert (LC (buf, 1));
    15431543          liftBounds[i]= adaptedLiftBound;
    15441544          liftBound= adaptedLiftBound;
    1545           henselLiftResume (buf, result, degree (buf) + 1, liftBound,
    1546                             Pi, diophant, Mat, MOD);
    1547         } 
    1548         else
    1549         {
    1550           liftBounds[i]= adaptedLiftBound;
    1551         }
     1545          henselLiftResume (buf, result, degree (buf) + 1, liftBound,
     1546                            Pi, diophant, Mat, MOD);
     1547        }
     1548        else
     1549        {
     1550          liftBounds[i]= adaptedLiftBound;
     1551        }
    15521552      }
    15531553      else if (smallFactorDeg < degree (buf) + 1)
    15541554      {
    1555         result= henselLift (bufEval, result, MOD, diophant, Pi, Mat,
    1556                             liftBounds[i -  1], smallFactorDeg);
    1557 
    1558         if (Aeval.length() == i + 1)
    1559         {
    1560           if (!extension)
    1561             earlyFactors= earlyFactorDetect
     1555        result= henselLift (bufEval, result, MOD, diophant, Pi, Mat,
     1556                            liftBounds[i -  1], smallFactorDeg);
     1557
     1558        if (Aeval.length() == i + 1)
     1559        {
     1560          if (!extension)
     1561            earlyFactors= earlyFactorDetect
    15621562                           (buf, result, adaptedLiftBound, earlySuccess,
    15631563                            smallFactorDeg, MOD, liftBound);
    1564           else
    1565             earlyFactors= extEarlyFactorDetect
     1564          else
     1565            earlyFactors= extEarlyFactorDetect
    15661566                           (buf, result, adaptedLiftBound, earlySuccess,
    15671567                            info, evaluation, smallFactorDeg, MOD, liftBound);
    1568         }
    1569         else
    1570         {
    1571           if (!extension)
    1572             adaptedLiftBound= liftBoundAdaption
     1568        }
     1569        else
     1570        {
     1571          if (!extension)
     1572            adaptedLiftBound= liftBoundAdaption
    15731573                                (buf, result, earlySuccess,
    15741574                                 smallFactorDeg, MOD, liftBound);
    1575           else
    1576             adaptedLiftBound= extLiftBoundAdaption
     1575          else
     1576            adaptedLiftBound= extLiftBoundAdaption
    15771577                                (buf, result, earlySuccess, info, evaluation,
    1578                                  smallFactorDeg, MOD, liftBound);         
    1579         }
    1580 
    1581         if (!earlySuccess)
    1582         {
    1583           result.insert (LC (buf, 1));
    1584           henselLiftResume (buf, result, smallFactorDeg,
     1578                                 smallFactorDeg, MOD, liftBound);
     1579        }
     1580
     1581        if (!earlySuccess)
     1582        {
     1583          result.insert (LC (buf, 1));
     1584          henselLiftResume (buf, result, smallFactorDeg,
    15851585                            degree (buf) + 1, Pi, diophant, Mat, MOD);
    1586           if (Aeval.length() == i + 1)
    1587           {
    1588             if (!extension)
    1589               earlyFactors= earlyFactorDetect
     1586          if (Aeval.length() == i + 1)
     1587          {
     1588            if (!extension)
     1589              earlyFactors= earlyFactorDetect
    15901590                             (buf, result, adaptedLiftBound, earlySuccess,
    15911591                              degree (buf) +  1,  MOD, liftBound);
    1592             else
    1593               earlyFactors= extEarlyFactorDetect
     1592            else
     1593              earlyFactors= extEarlyFactorDetect
    15941594                             (buf, result, adaptedLiftBound, earlySuccess,
    1595                               info, evaluation, degree (buf) + 1, MOD, 
     1595                              info, evaluation, degree (buf) + 1, MOD,
    15961596                              liftBound);
    1597           }
    1598           else
    1599           {
    1600             if (!extension)
    1601               adaptedLiftBound= liftBoundAdaption
     1597          }
     1598          else
     1599          {
     1600            if (!extension)
     1601              adaptedLiftBound= liftBoundAdaption
    16021602                                  (buf, result, earlySuccess, degree
    16031603                                   (buf) +  1,  MOD, liftBound);
    1604             else
    1605               adaptedLiftBound= extLiftBoundAdaption
    1606                                   (buf, result, earlySuccess, info, evaluation, 
    1607                                    degree (buf) + 1,  MOD, liftBound);   
    1608           }
    1609 
    1610           if (!earlySuccess)
    1611           {
    1612             result.insert (LC (buf, 1));
     1604            else
     1605              adaptedLiftBound= extLiftBoundAdaption
     1606                                  (buf, result, earlySuccess, info, evaluation,
     1607                                   degree (buf) + 1,  MOD, liftBound);
     1608          }
     1609
     1610          if (!earlySuccess)
     1611          {
     1612            result.insert (LC (buf, 1));
    16131613            liftBounds[i]= adaptedLiftBound;
    16141614            liftBound= adaptedLiftBound;
    1615             henselLiftResume (buf, result, degree (buf) + 1, liftBound,
    1616                               Pi, diophant, Mat, MOD);
    1617           }
    1618           else
    1619             liftBounds[i]= adaptedLiftBound;
    1620         }
    1621         else
    1622           liftBounds[i]= adaptedLiftBound;
     1615            henselLiftResume (buf, result, degree (buf) + 1, liftBound,
     1616                              Pi, diophant, Mat, MOD);
     1617          }
     1618          else
     1619            liftBounds[i]= adaptedLiftBound;
     1620        }
     1621        else
     1622          liftBounds[i]= adaptedLiftBound;
    16231623      }
    16241624      MOD.append (power (Variable (i + 2), liftBounds[i]));
     
    16351635}
    16361636
    1637 CFList 
    1638 extFactorize (const CanonicalForm& F, const ExtensionInfo& info); 
    1639 
    1640 CFList 
    1641 multiFactorize (const CanonicalForm& F, const ExtensionInfo& info) 
     1637CFList
     1638extFactorize (const CanonicalForm& F, const ExtensionInfo& info);
     1639
     1640CFList
     1641multiFactorize (const CanonicalForm& F, const ExtensionInfo& info)
    16421642{
    16431643
     
    16591659  bool GF= (CFFactory::gettype() == GaloisFieldDomain);
    16601660  //univariate case
    1661   if (F.isUnivariate()) 
     1661  if (F.isUnivariate())
    16621662  {
    16631663    if (extension == false)
    16641664      return uniFactorizer (F, alpha, GF);
    1665     else 
    1666     { 
     1665    else
     1666    {
    16671667      CFList source, dest;
    16681668      A= mapDown (F, info, source, dest);
     
    16721672
    16731673  //bivariate case
    1674   if (A.level() == 2) 
    1675   {
    1676     CFList buf= biFactorize (F, info); 
     1674  if (A.level() == 2)
     1675  {
     1676    CFList buf= biFactorize (F, info);
    16771677    return buf;
    16781678  }
    1679  
     1679
    16801680  Variable x= Variable (1);
    16811681  Variable y= Variable (2);
    1682  
     1682
    16831683  // remove content
    16841684  CFList contentAi;
    16851685  CanonicalForm lcmCont= lcmContent (A, contentAi);
    1686   A /= lcmCont; 
     1686  A /= lcmCont;
    16871687
    16881688  // trivial after content removal
    16891689  CFList contentAFactors;
    1690   if (A.inCoeffDomain()) 
    1691   { 
    1692     for (CFListIterator i= contentAi; i.hasItem(); i++) 
     1690  if (A.inCoeffDomain())
     1691  {
     1692    for (CFListIterator i= contentAi; i.hasItem(); i++)
    16931693    {
    16941694      if (i.getItem().inCoeffDomain())
    16951695        continue;
    1696       else 
     1696      else
    16971697      {
    16981698        lcmCont /= i.getItem();
    1699         contentAFactors= 
    1700         Union (multiFactorize (lcmCont, info), 
     1699        contentAFactors=
     1700        Union (multiFactorize (lcmCont, info),
    17011701               multiFactorize (i.getItem(), info));
    17021702        break;
     
    17091709
    17101710  // factorize content
    1711   contentAFactors= multiFactorize (lcmCont, info); 
     1711  contentAFactors= multiFactorize (lcmCont, info);
    17121712
    17131713  // univariate after content removal
    17141714  CFList factors;
    1715   if (A.isUnivariate ()) 
     1715  if (A.isUnivariate ())
    17161716  {
    17171717    factors= uniFactorizer (A, alpha, GF);
     
    17281728  Variable z;
    17291729  for (int i= 1; i <= A.level(); i++)
    1730   { 
     1730  {
    17311731    z= Variable (i);
    17321732    derivZ= deriv (bufA, z);
     
    17461746      }
    17471747      if (GF)
    1748         gcdDerivZ= GCD_GF (bufA, derivZ); 
     1748        gcdDerivZ= GCD_GF (bufA, derivZ);
    17491749      else if (alpha == Variable (1))
    17501750        gcdDerivZ= GCD_small_p (bufA, derivZ);
    1751       else 
     1751      else
    17521752        gcdDerivZ= GCD_Fp_extension (bufA, derivZ, alpha);
    1753       if (degree (gcdDerivZ) > 0 && !derivZ.isZero()) 
     1753      if (degree (gcdDerivZ) > 0 && !derivZ.isZero())
    17541754      {
    17551755        CanonicalForm g= bufA/gcdDerivZ;
    1756         CFList factorsG= 
     1756        CFList factorsG=
    17571757        Union (multiFactorize (g, info),
    17581758               multiFactorize (gcdDerivZ, info));
     
    17741774  CanonicalForm evalPoly;
    17751775  int lift, bufLift;
    1776   if (factorNums < (int) ceil (log (totaldegree (A)))) 
     1776  if (factorNums < (int) ceil (log (totaldegree (A))))
    17771777    factorNums= (int) ceil (log (totaldegree (A)));
    1778   // several bivariate factorizations 
    1779   for (int i= 0; i < factorNums; i++) 
     1778  // several bivariate factorizations
     1779  for (int i= 0; i < factorNums; i++)
    17801780  {
    17811781    bufA= A;
    17821782    bufAeval= CFList();
    17831783    bufEvaluation= evalPoints (bufA, bufAeval, alpha, list, GF, fail);
    1784     evalPoly= 0; 
    1785 
    1786     if (fail && (i == 0)) 
     1784    evalPoly= 0;
     1785
     1786    if (fail && (i == 0))
    17871787    {
    17881788      if (!swapLevel)
    1789         level= 2;
    1790       else 
    1791         level= swapLevel + 1;
     1789        level= 2;
     1790      else
     1791        level= swapLevel + 1;
    17921792
    17931793      swapLevel2= newMainVariableSearch (A, Aeval, evaluation, alpha, level);
    17941794
    17951795      if (!swapLevel2) // need to pass to an extension
    1796       { 
    1797         factors= extFactorize (A, info);
    1798         appendSwapDecompress (factors, contentAFactors, N, swapLevel, x);
    1799         normalize (factors);
    1800         return factors;
     1796      {
     1797        factors= extFactorize (A, info);
     1798        appendSwapDecompress (factors, contentAFactors, N, swapLevel, x);
     1799        normalize (factors);
     1800        return factors;
    18011801      }
    18021802      else
     
    18051805        bufAeval= Aeval;
    18061806        bufA= A;
    1807         bufEvaluation= evaluation; 
     1807        bufEvaluation= evaluation;
    18081808      }
    18091809    }
     
    18121812
    18131813    bivarEval= bufEvaluation.getLast();
    1814     bufEvaluation.removeLast(); 
     1814    bufEvaluation.removeLast();
    18151815
    18161816    bufLift= degree (A, y) + 1 + degree (LC(A, x), y);
    18171817
    18181818    TIMING_START (fac_bi_factorizer);
    1819     bufBiFactors= biFactorizer (bufAeval.getFirst(), alpha, bivarEval, bufLift); 
    1820     TIMING_END_AND_PRINT (fac_bi_factorizer, 
    1821                           "time for bivariate factorization: ");
    1822 
    1823     if (bufBiFactors.length() == 1) 
    1824     {
    1825       if (extension) 
    1826       {
    1827         CFList source, dest;
    1828         A= mapDown (A, info, source, dest);
     1819    bufBiFactors= biFactorizer (bufAeval.getFirst(), alpha, bivarEval, bufLift);
     1820    TIMING_END_AND_PRINT (fac_bi_factorizer,
     1821                          "time for bivariate factorization: ");
     1822
     1823    if (bufBiFactors.length() == 1)
     1824    {
     1825      if (extension)
     1826      {
     1827        CFList source, dest;
     1828        A= mapDown (A, info, source, dest);
    18291829      }
    18301830      factors.append (A);
    18311831      appendSwapDecompress (factors, contentAFactors, N, swapLevel,
    1832                             swapLevel2, x);
     1832                            swapLevel2, x);
    18331833      normalize (factors);
    18341834      return factors;
     
    18451845    else
    18461846    {
    1847       if (bufBiFactors.length() < biFactors.length() || 
     1847      if (bufBiFactors.length() < biFactors.length() ||
    18481848          ((bufLift < lift) && (bufBiFactors.length() == biFactors.length())))
    18491849      {
     
    18571857    for (CFListIterator j= bufEvaluation; j.hasItem(); j++, k++)
    18581858      evalPoly += j.getItem()*power (x, k);
    1859     list.append (evalPoly); 
     1859    list.append (evalPoly);
    18601860  }
    18611861
     
    18661866  int liftBoundsLength= F.level() - 1;
    18671867  liftBounds= liftingBounds (A, lift);
    1868  
     1868
    18691869  CFList MOD;
    18701870  bool earlySuccess;
    18711871  CFList earlyFactors;
    18721872  TIMING_START (fac_hensel_lift);
    1873   CFList liftedFactors= henselLiftAndEarly 
     1873  CFList liftedFactors= henselLiftAndEarly
    18741874                        (A, MOD, liftBounds, earlySuccess, earlyFactors,
    18751875                         Aeval, biFactors, evaluation, info);
    18761876  TIMING_END_AND_PRINT (fac_hensel_lift, "time for hensel lifting: ");
    18771877
    1878   if (!extension) 
     1878  if (!extension)
    18791879  {
    18801880    TIMING_START (fac_factor_recombination);
    18811881    factors= factorRecombination (A, liftedFactors, MOD);
    1882     TIMING_END_AND_PRINT (fac_factor_recombination, 
     1882    TIMING_END_AND_PRINT (fac_factor_recombination,
    18831883                          "time for factor recombination: ");
    18841884  }
    1885   else 
     1885  else
    18861886  {
    18871887    TIMING_START (fac_factor_recombination);
    18881888    factors= extFactorRecombination (liftedFactors, A, MOD, info, evaluation);
    1889     TIMING_END_AND_PRINT (fac_factor_recombination, 
    1890                           "time for factor recombination: "); 
     1889    TIMING_END_AND_PRINT (fac_factor_recombination,
     1890                          "time for factor recombination: ");
    18911891  }
    18921892
     
    18941894    factors= Union (factors, earlyFactors);
    18951895
    1896   if (!extension) 
     1896  if (!extension)
    18971897  {
    18981898    for (CFListIterator i= factors; i.hasItem(); i++)
     
    19081908  }
    19091909
    1910   swap (factors, swapLevel, swapLevel2, x); 
     1910  swap (factors, swapLevel, swapLevel2, x);
    19111911  append (factors, contentAFactors);
    19121912  decompress (factors, N);
     
    19191919
    19201920/// multivariate factorization over an extension of the initial field
    1921 CFList 
    1922 extFactorize (const CanonicalForm& F, const ExtensionInfo& info) 
     1921CFList
     1922extFactorize (const CanonicalForm& F, const ExtensionInfo& info)
    19231923{
    19241924  CanonicalForm A= F;
     
    19361936  {
    19371937    CFList factors;
    1938     bool extension= true;         
     1938    bool extension= true;
    19391939    int p= getCharacteristic();
    19401940    if (p*p < (1<<16)) // pass to GF if possible
    1941     { 
     1941    {
    19421942      setCharacteristic (getCharacteristic(), 2, 'Z');
    19431943      ExtensionInfo info= ExtensionInfo (extension);
     
    19471947      Variable vBuf= rootOf (gf_mipo);
    19481948      setCharacteristic (getCharacteristic());
    1949       for (CFListIterator j= factors; j.hasItem(); j++) 
    1950         j.getItem()= GF2FalphaRep (j.getItem(), vBuf);
     1949      for (CFListIterator j= factors; j.hasItem(); j++)
     1950        j.getItem()= GF2FalphaRep (j.getItem(), vBuf);
    19511951    }
    19521952    else  // not able to pass to GF, pass to F_p(\alpha)
     
    19591959  }
    19601960  else if (!GF && (alpha != w)) // we are in F_p(\alpha)
    1961   { 
     1961  {
    19621962    if (k == 1) // need factorization over F_p
    19631963    {
    19641964      int extDeg= degree (getMipo (alpha));
    1965       extDeg++; 
     1965      extDeg++;
    19661966      CanonicalForm mipo= randomIrredpoly (extDeg + 1, Variable (1));
    19671967      Variable v= rootOf (mipo);
     
    19691969      factors= biFactorize (A, info);
    19701970    }
    1971     else 
     1971    else
    19721972    {
    19731973      if (beta == Variable (1))
     
    19851985
    19861986        CFList source, dest;
    1987         CanonicalForm bufA= mapUp (A, alpha, v, primElem, imPrimElem, 
     1987        CanonicalForm bufA= mapUp (A, alpha, v, primElem, imPrimElem,
    19881988                                   source, dest);
    19891989        ExtensionInfo info= ExtensionInfo (v, alpha, imPrimElem, primElem);
     
    20142014  }
    20152015  else // we are in GF (p^k)
    2016   { 
     2016  {
    20172017    int p= getCharacteristic();
    20182018    int extensionDeg= getGFDegree();
    20192019    bool extension= true;
    20202020    if (k == 1) // need factorization over F_p
    2021     { 
     2021    {
    20222022      extensionDeg++;
    2023       if (pow ((double) p, (double) extensionDeg) < (1<<16)) 
     2023      if (pow ((double) p, (double) extensionDeg) < (1<<16))
    20242024      // pass to GF(p^k+1)
    2025       { 
     2025      {
    20262026        setCharacteristic (p);
    2027         Variable vBuf= rootOf (gf_mipo);
    2028         A= GF2FalphaRep (A, vBuf);
    2029         setCharacteristic (p, extensionDeg, 'Z');
     2027        Variable vBuf= rootOf (gf_mipo);
     2028        A= GF2FalphaRep (A, vBuf);
     2029        setCharacteristic (p, extensionDeg, 'Z');
    20302030        ExtensionInfo info= ExtensionInfo (extension);
    2031         factors= multiFactorize (A.mapinto(), info);
     2031        factors= multiFactorize (A.mapinto(), info);
    20322032      }
    20332033      else // not able to pass to another GF, pass to F_p(\alpha)
    2034       { 
    2035         setCharacteristic (p);
    2036         Variable vBuf= rootOf (gf_mipo);
    2037         A= GF2FalphaRep (A, vBuf);
    2038         Variable v= chooseExtension (A, beta);
     2034      {
     2035        setCharacteristic (p);
     2036        Variable vBuf= rootOf (gf_mipo);
     2037        A= GF2FalphaRep (A, vBuf);
     2038        Variable v= chooseExtension (A, beta);
    20392039        ExtensionInfo info= ExtensionInfo (v, extension);
    2040         factors= multiFactorize (A, info);
     2040        factors= multiFactorize (A, info);
    20412041      }
    20422042    }
    20432043    else // need factorization over GF (p^k)
    20442044    {
    2045       if (pow ((double) p, (double) 2*extensionDeg) < (1<<16)) 
     2045      if (pow ((double) p, (double) 2*extensionDeg) < (1<<16))
    20462046      // pass to GF(p^2k)
    2047       { 
    2048         setCharacteristic (p, 2*extensionDeg, 'Z');
     2047      {
     2048        setCharacteristic (p, 2*extensionDeg, 'Z');
    20492049        ExtensionInfo info= ExtensionInfo (k, cGFName, extension);
    2050         factors= multiFactorize (GFMapUp (A, extensionDeg), info);
    2051         setCharacteristic (p, extensionDeg, cGFName);
     2050        factors= multiFactorize (GFMapUp (A, extensionDeg), info);
     2051        setCharacteristic (p, extensionDeg, cGFName);
    20522052      }
    20532053      else // not able to pass to GF (p^2k), pass to F_p (\alpha)
    2054       { 
    2055         setCharacteristic (p);
    2056         Variable v1= rootOf (gf_mipo);
    2057         A= GF2FalphaRep (A, v1);
    2058         Variable v2= chooseExtension (A, v1);
     2054      {
     2055        setCharacteristic (p);
     2056        Variable v1= rootOf (gf_mipo);
     2057        A= GF2FalphaRep (A, v1);
     2058        Variable v2= chooseExtension (A, v1);
    20592059        CanonicalForm primElem, imPrimElem;
    20602060        bool primFail= false;
     
    20702070        }
    20712071        CFList source, dest;
    2072         CanonicalForm bufA= mapUp (A, alpha, beta, primElem, imPrimElem, 
     2072        CanonicalForm bufA= mapUp (A, alpha, beta, primElem, imPrimElem,
    20732073                                     source, dest);
    20742074        ExtensionInfo info= ExtensionInfo (v2, v1, imPrimElem, primElem);
    2075         factors= multiFactorize (bufA, info);
    2076         setCharacteristic (p, k, cGFName);
    2077         for (CFListIterator i= factors; i.hasItem(); i++)
    2078           i.getItem()= Falpha2GFRep (i.getItem());
     2075        factors= multiFactorize (bufA, info);
     2076        setCharacteristic (p, k, cGFName);
     2077        for (CFListIterator i= factors; i.hasItem(); i++)
     2078          i.getItem()= Falpha2GFRep (i.getItem());
    20792079      }
    20802080    }
Note: See TracChangeset for help on using the changeset viewer.