Changeset ccd1b0 in git


Ignore:
Timestamp:
Jun 16, 2011, 2:22:22 PM (13 years ago)
Author:
Martin Lee <martinlee84@…>
Branches:
(u'fieker-DuVal', '117eb8c30fc9e991c4decca4832b1d19036c4c65')(u'spielwiese', '38dfc5131670d387a89455159ed1e071997eec94')
Children:
2f128f2c3244812fa0ad92434c4ccb623b9c7b56
Parents:
b2e4bd67738eae99b3545e3cbb442aa7d898ae9c
Message:
added precomputation of leading coefficients for multivariate factorization
deleted obsolete functions for bivariate factorization
instantiated template function prod


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

Legend:

Unmodified
Added
Removed

  • Singular/claptmpl.cc

    rb2e4bd rccd1b0  
    5959  template int tmin ( const int&, const int& );
    6060  template int tabs ( const int& );
     61
     62  template CanonicalForm prod ( const List<CanonicalForm> & );
    6163
    6264// place here your own template stuff, not instantiated by factory

  • factory/facFqFactorize.cc

    rb2e4bd rccd1b0  
    182182
    183183CFList
    184 monicFactorRecombi (const CFList& factors,const CanonicalForm& F, const
    185                     CanonicalForm& M, const DegreePattern& degs)
    186 {
    187   if (degs.getLength() == 1)
    188     return CFList(F);
    189 
    190   CFList T, S;
    191 
    192   T= factors;
    193 
    194   int s= 1;
    195   CFList result;
    196   CanonicalForm buf= F;
    197   CanonicalForm LCBuf= LC (buf, Variable (1));
    198   CanonicalForm g, gg;
    199   int * v= new int [T.length()];
    200   for (int i= 0; i < T.length(); i++)
    201     v[i]= 0;
    202   bool noSubset= false;
    203   CFArray TT;
    204   int subsetDeg;
    205   DegreePattern bufDegs1= degs, bufDegs2;
    206   TT= copy (factors);
    207   while (T.length() >= 2*s)
    208   {
    209     while (noSubset == false)
    210     {
    211       if (T.length() == s)
    212       {
    213         result.append (prodMod (T, M));
    214         delete [] v;
    215         return result;
    216       }
    217       S= subset (v, s, TT, noSubset);
    218       if (noSubset) break;
    219       subsetDeg= subsetDegree (S);
    220       if (!degs.find (subsetDeg))
    221         continue;
    222       else
    223       {
    224         g= prodMod0 (S, M);
    225         gg= mod (g*LCBuf, M); //univariate polys
    226         gg /= content (gg);
    227         if (fdivides (LC (gg), LCBuf))
    228         {
    229           g= prodMod (S, M);
    230           gg= mulMod2 (LCBuf, g, M);
    231           gg /= content (gg, Variable (1));
    232           if (fdivides (gg, buf))
    233           {
    234             result.append (g);
    235             buf /= gg;
    236             LCBuf= LC (buf, Variable(1));
    237             T= Difference (T, S);
    238             // compute new possible degree pattern
    239             bufDegs2= DegreePattern (T);
    240             bufDegs1.intersect (bufDegs2);
    241             bufDegs1.refine ();
    242             if (T.length() < 2*s || T.length() == s ||
    243                 bufDegs1.getLength() == 1)
    244             {
    245               result.append (prodMod (T, M));
    246               delete [] v;
    247               return result;
    248             }
    249             TT= copy (T);
    250             indexUpdate (v, s, T.length(), noSubset);
    251             if (noSubset) break;
    252           }
    253         }
    254       }
    255     }
    256     s++;
    257     if (T.length() < 2*s || T.length() == s)
    258     {
    259       result.append (prodMod (T, M));
    260       delete [] v;
    261       return result;
    262     }
    263     for (int i= 0; i < T.length(); i++)
    264       v[i]= 0;
    265     noSubset= false;
    266   }
    267   if (T.length() < 2*s)
    268     result.append (prodMod (T, M));
    269 
    270   delete [] v;
    271   return result;
    272 }
    273 
    274 CFList
    275 earlyMonicFactorDetect (CanonicalForm& F, CFList& factors,
    276                         int& adaptedLiftBound, DegreePattern& degs,
    277                         bool& success, int deg, const int bound)
    278 {
    279   DegreePattern bufDegs1= degs;
    280   DegreePattern bufDegs2;
    281   CFList result;
    282   CFList T= factors;
    283   CanonicalForm buf= F;
    284   CanonicalForm LCBuf= LC (buf, Variable (1));
    285   CanonicalForm g, gg;
    286   CanonicalForm M= power (F.mvar(), deg);
    287   int d= bound;
    288   int e= 0;
    289   adaptedLiftBound= 0;
    290   for (CFListIterator i= factors; i.hasItem(); i++)
    291   {
    292     if (!bufDegs1.find (degree (i.getItem(), 1)))
    293       continue;
    294     else
    295     {
    296       gg= i.getItem() (0, 1);
    297       gg *= LCBuf;
    298       gg= mod (gg, M);
    299       if (fdivides (LC (gg), LCBuf))
    300       {
    301         g= i.getItem();
    302         gg= mulMod2 (g, LCBuf, M);
    303         gg /= content (gg, Variable (1));
    304         if (fdivides (gg, buf))
    305         {
    306           result.append (g);
    307           CanonicalForm bufbuf= buf;
    308           buf /= gg;
    309           d -= degree (gg) + degree (LC (gg, 1));
    310           e= tmax (e, degree (gg) + degree (LC (gg, 1)));
    311           LCBuf= LC (buf, Variable (1));
    312           T= Difference (T, CFList (i.getItem()));
    313 
    314           // compute new possible degree pattern
    315           bufDegs2= DegreePattern (T);
    316           bufDegs1.intersect (bufDegs2);
    317           bufDegs1.refine ();
    318           if (bufDegs1.getLength() <= 1)
    319           {
    320             result.append (prodMod (T, M));
    321             break;
    322           }
    323         }
    324       }
    325     }
    326   }
    327   adaptedLiftBound= d;
    328 
    329   if (adaptedLiftBound < deg)
    330   {
    331     factors= T;
    332     degs= bufDegs1;
    333     if (adaptedLiftBound < degree (F) + 1)
    334     {
    335       if (d == 1)
    336       {
    337         if (e + 1 > deg)
    338         {
    339           success= false;
    340           adaptedLiftBound= deg;
    341         }
    342         else
    343         {
    344           F= buf;
    345           success= true;
    346           if (e + 1 < degree (F) + 1)
    347             adaptedLiftBound= deg;
    348           else
    349             adaptedLiftBound= e + 1;
    350         }
    351       }
    352       else
    353       {
    354         success= true;
    355         F= buf;
    356         adaptedLiftBound= deg;
    357       }
    358     }
    359     else
    360     {
    361       F= buf;
    362       success= true;
    363     }
    364   }
    365   if (bufDegs1.getLength() <= 1)
    366   {
    367     degs= bufDegs1;
    368     if (!success)
    369       adaptedLiftBound= deg;
    370   }
    371 
    372   return result;
    373 }
    374 
    375 CFList biFactorizer (const CanonicalForm& F, const Variable& alpha,
    376                      CanonicalForm& bivarEval, int& liftBound)
    377 {
    378   CanonicalForm A= F;
    379   bool GF= (CFFactory::gettype() == GaloisFieldDomain);
    380 
    381   if (A.isUnivariate())
    382     return uniFactorizer (F, alpha, GF);
    383 
    384 
    385   CFMap N;
    386   A= compress (A, N);
    387   Variable y= A.mvar();
    388   A /= Lc(A);
    389 
    390   if (y.level() > 2) return CFList (F);
    391   Variable x= Variable (1);
    392 
    393   //remove content and factorize content
    394   CanonicalForm contentAy= content (A, y);
    395   CanonicalForm contentAx= content (A, x);
    396   A= A/(contentAy*contentAx);
    397   CFList contentAyFactors= uniFactorizer (contentAy, alpha, GF);
    398 
    399   //trivial case
    400   CFList factors;
    401   if (A.inCoeffDomain())
    402   {
    403     append (factors, contentAyFactors);
    404     decompress (factors, N);
    405     bivarEval= N (y - bivarEval);
    406     return factors;
    407   }
    408   else if (A.isUnivariate())
    409   {
    410     if (A.mvar() == x)
    411       factors= uniFactorizer (A, alpha, GF);
    412     append (factors, contentAyFactors);
    413     decompress (factors, N);
    414     bivarEval= N (y - bivarEval);
    415     return factors;
    416   }
    417   bool fail;
    418   CanonicalForm Aeval, evaluation, bufAeval, bufEvaluation, buf;
    419   CFList uniFactors, list, bufUniFactors;
    420   DegreePattern degs;
    421   DegreePattern bufDegs;
    422 
    423   int factorNums= 5;
    424   double logarithm= (double) ilog2 (totaldegree (A));
    425   logarithm /= log2exp;
    426   logarithm= ceil (logarithm);
    427   if (factorNums < (int) logarithm)
    428     factorNums= (int) logarithm;
    429   for (int i= 0; i < factorNums; i++)
    430   {
    431     if (i == 0)
    432       Aeval= A (bivarEval, y);
    433     else if (i > 0 && contentAx.inCoeffDomain())
    434     {
    435       Aeval= A;
    436       evaluation= evalPoint (A, Aeval, alpha, list, GF, fail);
    437     }
    438 
    439     if (fail && (i != 0))
    440       break;
    441 
    442     // univariate factorization
    443     uniFactors= uniFactorizer (Aeval, alpha, GF);
    444 
    445     if (uniFactors.length() == 1)
    446     {
    447       append (factors, contentAyFactors);
    448       if (contentAyFactors.isEmpty())
    449         factors.append (F/lc(F));
    450       else
    451       {
    452         A= A (y - bivarEval, y);
    453         A= A/lc (A);
    454         if (!LC(A, 1).isOne())
    455         {
    456           CanonicalForm s,t;
    457           (void) extgcd (LC (A, 1), power (y, liftBound), s, t);
    458           A *= s;
    459           A= mod (A, power (y, liftBound));
    460         }
    461         factors.append (A);
    462       }
    463       decompress (factors, N);
    464       bivarEval= N (bivarEval);
    465       return factors;
    466     }
    467 
    468     // degree analysis
    469     degs= DegreePattern (uniFactors);
    470 
    471     if (i == 0)
    472     {
    473       bufAeval= Aeval;
    474       bufEvaluation= bivarEval;
    475       bufUniFactors= uniFactors;
    476       bufDegs= degs;
    477       if (!contentAx.inCoeffDomain())
    478         break;
    479     }
    480     else
    481     {
    482       bufDegs.intersect (degs);
    483       if (uniFactors.length() < bufUniFactors.length())
    484       {
    485         bufUniFactors= uniFactors;
    486         bufAeval= Aeval;
    487         bufEvaluation= evaluation;
    488       }
    489     }
    490 
    491     if (bufDegs.getLength() == 1)
    492     {
    493       append (factors, contentAyFactors);
    494       if (contentAyFactors.isEmpty())
    495         factors.append (F/lc(F));
    496       else
    497       {
    498         A= A (y - bivarEval, y);
    499         A= A/lc (A);
    500         if (!LC(A, 1).isOne())
    501         {
    502           CanonicalForm s,t;
    503           (void) extgcd (LC (A, 1), power (y, liftBound), s, t);
    504           A *= s;
    505           A= mod (A, power (y, liftBound));
    506         }
    507         factors.append (A);
    508       }
    509       decompress (factors, N);
    510       bivarEval= N (bivarEval);
    511       return factors;
    512     }
    513     list.append (evaluation);
    514   }
    515 
    516   bivarEval= y - bufEvaluation;
    517   A= A (y + bufEvaluation, y);
    518   bufUniFactors.insert (LC (A, x));
    519 
    520   // Hensel lifting
    521   CFList diophant;
    522   CFMatrix M= CFMatrix (liftBound, bufUniFactors.length() - 1);
    523   CFArray Pi;
    524   bool earlySuccess= false;
    525   int newLiftBound= 0;
    526   CFList earlyFactors;
    527   int smallFactorDeg= 11; //tunable parameter
    528   if (smallFactorDeg >= liftBound)
    529     henselLift12 (A, bufUniFactors, liftBound, Pi, diophant, M);
    530   else if (smallFactorDeg >= degree (A, y) + 1)
    531   {
    532     henselLift12 (A, bufUniFactors, degree (A, y) + 1, Pi, diophant, M);
    533     earlyFactors= earlyMonicFactorDetect (A, bufUniFactors, newLiftBound,
    534                                            bufDegs, earlySuccess,
    535                                            degree (A, y) + 1, liftBound);
    536     if (bufDegs.getLength() > 1 && !earlySuccess)
    537     {
    538       if (newLiftBound > degree (A, y) + 1)
    539       {
    540         liftBound= newLiftBound;
    541         bufUniFactors.insert (LC(A, x));
    542         henselLiftResume12 (A, bufUniFactors, degree (A, y) + 1, liftBound,
    543                             Pi, diophant, M);
    544       }
    545     }
    546     else if (earlySuccess)
    547       liftBound= newLiftBound;
    548   }
    549   else if (smallFactorDeg < degree (A, y) + 1)
    550   {
    551     henselLift12 (A, bufUniFactors, smallFactorDeg, Pi, diophant, M);
    552     earlyFactors= earlyMonicFactorDetect (A, bufUniFactors, newLiftBound,
    553                                            bufDegs, earlySuccess,
    554                                            smallFactorDeg, liftBound);
    555     if (bufDegs.getLength() > 1 && !earlySuccess)
    556     {
    557       bufUniFactors.insert (LC (A, x));
    558       henselLiftResume12 (A, bufUniFactors, smallFactorDeg, degree (A, y) +
    559                           1, Pi, diophant, M);
    560       earlyFactors= earlyMonicFactorDetect (A, bufUniFactors, newLiftBound,
    561                                              bufDegs, earlySuccess,
    562                                              degree (A, y) + 1, liftBound);
    563       if (bufDegs.getLength() > 1 && !earlySuccess)
    564       {
    565         if (newLiftBound > degree (A, y) + 1)
    566         {
    567           if (newLiftBound < newLiftBound)
    568             liftBound= newLiftBound;
    569           bufUniFactors.insert (LC(A, x));
    570           henselLiftResume12 (A, bufUniFactors, degree (A, y) + 1, liftBound,
    571                               Pi, diophant, M);
    572         }
    573       }
    574       else if (earlySuccess)
    575         liftBound= newLiftBound;
    576     }
    577     else if (earlySuccess)
    578       liftBound= newLiftBound;
    579   }
    580 
    581   if (newLiftBound > 0)
    582     liftBound= newLiftBound;
    583 
    584   CanonicalForm MODl= power (y, liftBound);
    585 
    586   if (bufDegs.getLength() > 1)
    587     factors= monicFactorRecombi (bufUniFactors, A, MODl, bufDegs);
    588 
    589   if (earlySuccess)
    590     factors= Union (earlyFactors, factors);
    591   else if (!earlySuccess && bufDegs.getLength() == 1)
    592     factors= earlyFactors;
    593 
    594   decompressAppend (factors, contentAyFactors, N);
    595 
    596   bivarEval= N (bivarEval);
    597 
    598   return factors;
    599 }
    600 
    601 CFList
    602184extFactorRecombination (const CFList& factors, const CanonicalForm& F,
    603185                        const CFList& M, const ExtensionInfo& info,
    … …  
    628210  CFList result;
    629211  CanonicalForm buf;
    630   if (beta != Variable (1))
    631     buf= mapDown (F, gamma, delta, alpha, source, dest);
    632   else
    633     buf= F;
     212
     213  buf= F;
    634214
    635215  CanonicalForm g, LCBuf= LC (buf, Variable (1));
    … …  
    738318    appendMapDown (result, buf, info, source, dest);
    739319  }
    740   delete[] v;
    741320
    742321  delete [] v;
    … …  
    1182761    int l= F.level();
    1183762    eval.insert (F);
     763    bool bad= false;
    1184764    for (CFListIterator i= result; i.hasItem(); i++, l--)
     765    {
    1185766      eval.insert (eval.getFirst()(i.getItem(), l));
     767      if (degree (eval.getFirst(), l - 1) != degree (F, l - 1))
     768      {
     769        if (!find (list, random))
     770          list.append (random);
     771        result= CFList();
     772        eval= CFList();
     773        bad= true;
     774        break;
     775      }
     776    }
     777
     778    if (bad)
     779      continue;
    1186780
    1187781    if (degree (eval.getFirst()) != degree (F, 1))
    … …  
    1231825static inline
    1232826int newMainVariableSearch (CanonicalForm& A, CFList& Aeval, CFList&
    1233                            evaluation, const Variable& alpha, const int lev)
     827                           evaluation, const Variable& alpha, const int lev,
     828                           CanonicalForm& g
     829                          )
    1234830{
    1235831  Variable x= Variable (1);
    … …  
    1247843    if (!derivI.isZero())
    1248844    {
     845      g= gcd (buf, derivI);
     846      if (degree (g) > 0)
     847        return -1;
     848
    1249849      buf= swapvar (buf, x, Variable (i));
    1250850      Aeval= CFList();
    … …  
    15641164
    15651165CFList
     1166leadingCoeffReconstruction (const CanonicalForm& F, const CFList& factors,
     1167                            const CFList& M)
     1168{
     1169  CanonicalForm buf= F;
     1170  CanonicalForm LCBuf= LC (buf, 1);
     1171
     1172  CFList result;
     1173
     1174  for (CFListIterator i= factors; i.hasItem(); i++)
     1175  {
     1176    CanonicalForm tmp= i.getItem();
     1177    tmp= mulMod (tmp, LCBuf, M);
     1178    tmp= tmp/content (tmp, 1);
     1179    if (fdivides (tmp, buf))
     1180    {
     1181      buf /= tmp;
     1182      result.append (tmp);
     1183      LCBuf= LC (buf, 1);
     1184    }
     1185    else //no one-to-one correspondence
     1186      return CFList();
     1187  }
     1188
     1189  return result;
     1190}
     1191
     1192void
     1193gcdFreeBasis (CFFList& factors1, CFFList& factors2)
     1194{
     1195  CanonicalForm g;
     1196  int k= factors1.length();
     1197  int l= factors2.length();
     1198  int n= 1;
     1199  int m;
     1200  for (CFFListIterator i= factors1; (i.hasItem() && n < k); i++, n++)
     1201  {
     1202    m= 1;
     1203    for (CFFListIterator j= factors2; (j.hasItem() && m < l); j++, m++)
     1204    {
     1205      CanonicalForm g= gcd (i.getItem().factor(), j.getItem().factor());
     1206      if (degree (g) > 0)
     1207      {
     1208        j.getItem()= CFFactor (j.getItem().factor()/g, j.getItem().exp());
     1209        i.getItem()= CFFactor (i.getItem().factor()/g, i.getItem().exp());
     1210        factors1.append (CFFactor (g, i.getItem().exp()));
     1211        factors2.append (CFFactor (g, j.getItem().exp()));
     1212      }
     1213    }
     1214  }
     1215}
     1216
     1217CFList
     1218distributeContent (const CFList& L, const CFList* differentSecondVarFactors,
     1219                   int length, const CFList& factors
     1220                  )
     1221{
     1222  CFList l= L;
     1223  CanonicalForm content= l.getFirst();
     1224
     1225  if (content.inCoeffDomain())
     1226    return l;
     1227
     1228  if (l.length() == 1)
     1229  {
     1230    CFList result;
     1231    for (int i= 0; i < length; i++)
     1232    {
     1233      if (differentSecondVarFactors[i].isEmpty())
     1234        continue;
     1235      if (result.isEmpty())
     1236      {
     1237        result= differentSecondVarFactors[i];
     1238        for (CFListIterator iter= result; iter.hasItem(); iter++)
     1239          content /= iter.getItem();
     1240      }
     1241      else
     1242      {
     1243        CFListIterator iter1= result;
     1244        for (CFListIterator iter2= differentSecondVarFactors[i]; iter2.hasItem();
     1245             iter2++, iter1++)
     1246        {
     1247          iter1.getItem() *= iter2.getItem();
     1248          content /= iter2.getItem();
     1249        }
     1250      }
     1251    }
     1252    result.insert (content);
     1253    return result;
     1254  }
     1255
     1256  for (int i= 0; i < length; i++)
     1257  {
     1258    if (differentSecondVarFactors[i].isEmpty())
     1259      continue;
     1260    CFListIterator iter1= l;
     1261    iter1++;
     1262
     1263    Variable v= Variable (i + 3);
     1264    for (CFListIterator iter2= differentSecondVarFactors[i]; iter2.hasItem();
     1265         iter2++, iter1++)
     1266    {
     1267      if (degree (iter2.getItem(),v) == degree (iter1.getItem(),v))
     1268        continue;
     1269      CanonicalForm tmp= iter1.getItem();
     1270      for (int j= tmp.level(); j > 1; j--)
     1271      {
     1272        if (j == i + 3)
     1273          continue;
     1274        tmp= tmp (0, j);
     1275      }
     1276      CanonicalForm g= gcd (iter2.getItem(), content);
     1277      if (degree (g) > 0)
     1278      {
     1279        iter2.getItem() /= tmp;
     1280        content /= g;
     1281        iter1.getItem() *= g;
     1282      }
     1283    }
     1284  }
     1285
     1286  l.removeFirst();
     1287  l.insert (content);
     1288  return l;
     1289}
     1290
     1291static inline
     1292CFList evaluateAtZero (const CanonicalForm& F)
     1293{
     1294  CFList result;
     1295  CanonicalForm buf= F;
     1296  result.insert (buf);
     1297  for (int i= F.level(); i > 2; i--)
     1298  {
     1299    buf= buf (0, i);
     1300    result.insert (buf);
     1301  }
     1302  return result;
     1303}
     1304
     1305int
     1306testFactors (const CanonicalForm& G, const CFList& uniFactors,
     1307             const Variable& alpha, CanonicalForm& sqrfPartF, CFList& factors,
     1308             CFFList*& bufSqrfFactors, CFList& evalSqrfPartF)
     1309{
     1310  for (CFListIterator i= uniFactors; i.hasItem(); i++)
     1311  {
     1312    CanonicalForm tmp= i.getItem();
     1313    if (i.hasItem())
     1314      i++;
     1315    else
     1316      break;
     1317    for (CFListIterator j= i; j.hasItem(); j++)
     1318    {
     1319      if (tmp == j.getItem())
     1320        return 0;
     1321    }
     1322  }
     1323
     1324  CanonicalForm F= G;
     1325  CFFList sqrfFactorization= squarefreeFactorization (F, alpha);
     1326
     1327  sqrfPartF= 1;
     1328  for (CFFListIterator i= sqrfFactorization; i.hasItem(); i++)
     1329    sqrfPartF *= i.getItem().factor();
     1330
     1331  evalSqrfPartF= evaluateAtZero (sqrfPartF);
     1332
     1333  CanonicalForm test= evalSqrfPartF.getFirst() (0, 2);
     1334
     1335  if (degree (test) != degree (sqrfPartF, 1))
     1336    return 0;
     1337
     1338  CFFList sqrfFactors;
     1339  CFList tmp2;
     1340  int k= 0;
     1341  factors= uniFactors;
     1342  for (CFListIterator i= factors; i.hasItem(); i++, k++)
     1343  {
     1344    CanonicalForm tmp= 1;
     1345    sqrfFactors= squarefreeFactorization (i.getItem(), alpha);
     1346
     1347    for (CFFListIterator j= sqrfFactors; j.hasItem(); j++)
     1348    {
     1349      tmp2.append (j.getItem().factor());
     1350      tmp *= j.getItem().factor();
     1351    }
     1352    i.getItem()= tmp/Lc(tmp);
     1353    bufSqrfFactors [k]= sqrfFactors;
     1354  }
     1355
     1356  for (int i= 0; i < factors.length() - 1; i++)
     1357  {
     1358    for (int k= i + 1; k < factors.length(); k++)
     1359    {
     1360      gcdFreeBasis (bufSqrfFactors [i], bufSqrfFactors[k]);
     1361    }
     1362  }
     1363
     1364  factors= CFList();
     1365  for (int i= 0; i < uniFactors.length(); i++)
     1366  {
     1367    if (i == 0)
     1368    {
     1369      for (CFFListIterator k= bufSqrfFactors [i]; k.hasItem(); k++)
     1370      {
     1371        k.getItem()= CFFactor (k.getItem().factor()/Lc (k.getItem().factor()),
     1372                               k.getItem().exp());
     1373        factors.append (k.getItem().factor());
     1374      }
     1375    }
     1376    else
     1377    {
     1378      for (CFFListIterator k= bufSqrfFactors [i]; k.hasItem(); k++)
     1379      {
     1380        k.getItem()= CFFactor (k.getItem().factor()/Lc (k.getItem().factor()),
     1381                               k.getItem().exp());
     1382        if (!find (factors, k.getItem().factor()))
     1383          factors.append (k.getItem().factor());
     1384      }
     1385    }
     1386  }
     1387
     1388  test= prod (factors);
     1389  CanonicalForm tmp= evalSqrfPartF.getFirst() (0,2);
     1390  if (test/Lc (test) != tmp/Lc (tmp))
     1391    return 0;
     1392  else
     1393    return 1;
     1394}
     1395
     1396CFList
     1397precomputeLeadingCoeff (const CanonicalForm& LCF, const CFList& LCFFactors,
     1398                        const Variable& alpha, const CFList& evaluation,
     1399                        CFList* & differentSecondVarLCs, int length,
     1400                        Variable& y
     1401                       )
     1402{
     1403  y= Variable (1);
     1404  if (LCF.inCoeffDomain())
     1405  {
     1406    CFList result;
     1407    for (int i= 1; i <= LCFFactors.length() + 1; i++)
     1408      result.append (1);
     1409    return result;
     1410  }
     1411
     1412  CFMap N;
     1413  CanonicalForm F= compress (LCF, N);
     1414  if (LCF.isUnivariate())
     1415  {
     1416    CFList result;
     1417    int LCFLevel= LCF.level();
     1418    bool found= false;
     1419    if (LCFLevel == 2)
     1420    {
     1421    //bivariate leading coefficients are already the true leading coefficients
     1422      result= LCFFactors;
     1423      Variable v= Variable (LCF.mvar());
     1424      CanonicalForm bla= 1;
     1425      for (CFListIterator i= result; i.hasItem(); i++)
     1426      {
     1427        i.getItem()= i.getItem() (v+evaluation.getLast(), v);
     1428        bla *= Lc (i.getItem());
     1429      }
     1430      found= true;
     1431    }
     1432    else
     1433    {
     1434      for (int i= 0; i < length; i++)
     1435      {
     1436        for (CFListIterator j= differentSecondVarLCs[i]; j.hasItem(); j++)
     1437        {
     1438          if (j.getItem().level() == LCFLevel)
     1439          {
     1440            found= true;
     1441            break;
     1442          }
     1443        }
     1444        if (found)
     1445        {
     1446          result= differentSecondVarLCs [i];
     1447          break;
     1448        }
     1449      }
     1450      if (!found)
     1451        result= LCFFactors;
     1452    }
     1453    if (found)
     1454      result.insert (Lc (LCF));
     1455    else
     1456      result.append (LCF);
     1457    return result;
     1458  }
     1459
     1460  CFList factors= LCFFactors;
     1461
     1462  CFMap dummy;
     1463  for (CFListIterator i= factors; i.hasItem(); i++)
     1464  {
     1465    i.getItem()= compress (i.getItem(), dummy);
     1466    i.getItem()= i.getItem() (Variable (1) + evaluation.getLast(), Variable (1));
     1467  }
     1468
     1469  CanonicalForm sqrfPartF;
     1470  CFFList * bufSqrfFactors= new CFFList [factors.length()];
     1471  CFList evalSqrfPartF;
     1472  CanonicalForm bufContent;
     1473  CFList bufFactors;
     1474  int pass= testFactors (F, factors, alpha, sqrfPartF,
     1475                         bufFactors, bufSqrfFactors, evalSqrfPartF);
     1476
     1477  bool foundDifferent= false;
     1478  Variable z;
     1479  Variable x= y;
     1480  int j= 0;
     1481  if (!pass)
     1482  {
     1483    int lev;
     1484    // LCF is non-constant here
     1485    for (int i= 1; i <= LCF.level(); i++)
     1486    {
     1487      if(degree (LCF, i) > 0)
     1488      {
     1489        lev= i - 1;
     1490        break;
     1491      }
     1492    }
     1493    for (int i= 0; i < length; i++)
     1494    {
     1495      if (!differentSecondVarLCs [i].isEmpty())
     1496      {
     1497        bool allConstant= true;
     1498        for (CFListIterator iter= differentSecondVarLCs[i]; iter.hasItem();
     1499             iter++)
     1500        {
     1501          if (!iter.getItem().inCoeffDomain())
     1502          {
     1503            allConstant= false;
     1504            y= Variable (iter.getItem().level());
     1505          }
     1506        }
     1507        if (allConstant)
     1508          continue;
     1509
     1510        bufFactors= differentSecondVarLCs [i];
     1511        for (CFListIterator iter= bufFactors; iter.hasItem(); iter++)
     1512          iter.getItem()= swapvar (iter.getItem(), x, y);
     1513        CanonicalForm bufF= F;
     1514        z= Variable (y.level() - lev);
     1515        bufF= swapvar (bufF, x, z);
     1516        CFList bufBufFactors= bufFactors;
     1517        pass= testFactors (bufF, bufBufFactors, alpha, sqrfPartF, bufFactors,
     1518                           bufSqrfFactors, evalSqrfPartF);
     1519        if (pass)
     1520        {
     1521          foundDifferent= true;
     1522          F= bufF;
     1523          CFList l= factors;
     1524          for (CFListIterator iter= l; iter.hasItem(); iter++)
     1525            iter.getItem()= swapvar (iter.getItem(), x, y);
     1526          differentSecondVarLCs [i]= l;
     1527          j= i;
     1528          break;
     1529        }
     1530        if (!pass && i == length - 1)
     1531        {
     1532          CFList result;
     1533          result.append (LCF);
     1534          for (int k= 1; k <= factors.length(); k++)
     1535            result.append (LCF);
     1536          y= Variable (1);
     1537          return result;
     1538        }
     1539      }
     1540    }
     1541  }
     1542  if (!pass)
     1543  {
     1544    CFList result;
     1545    result.append (LCF);
     1546    for (int k= 1; k <= factors.length(); k++)
     1547      result.append (LCF);
     1548    y= Variable (1);
     1549    return result;
     1550  }
     1551  else
     1552    factors= bufFactors;
     1553
     1554  int liftBound= degree (sqrfPartF,2) + degree (LC (sqrfPartF, 1), 2) + 1;
     1555
     1556  int* liftBounds= liftingBounds (sqrfPartF, liftBound);
     1557
     1558  bufFactors= factors;
     1559  factors.insert (LC (evalSqrfPartF.getFirst(), 1));
     1560  CFMatrix M= CFMatrix (liftBound, factors.length() - 1);
     1561  CFArray Pi;
     1562  CFList diophant;
     1563  henselLift12 (evalSqrfPartF.getFirst(), factors, liftBound, Pi, diophant, M, false);
     1564
     1565  if (sqrfPartF.level() > 2)
     1566    factors= henselLift (evalSqrfPartF, factors, liftBounds,
     1567                         sqrfPartF.level() - 1, false);
     1568
     1569  CFList MOD;
     1570  for (int i= 0; i < sqrfPartF.level() - 1; i++)
     1571    MOD.append (power (Variable (i + 2), liftBounds [i]));
     1572
     1573  CFList interMedResult= leadingCoeffReconstruction (evalSqrfPartF.getLast(),
     1574                                                     factors, MOD);
     1575
     1576  CFList result;
     1577  for (int i= 0; i < LCFFactors.length(); i++)
     1578  {
     1579    CanonicalForm tmp= 1;
     1580    for (CFFListIterator k= bufSqrfFactors[i]; k.hasItem(); k++)
     1581    {
     1582      int pos= findItem (bufFactors, k.getItem().factor());
     1583      if (pos)
     1584        tmp *= power (getItem (interMedResult, pos), k.getItem().exp());
     1585    }
     1586    result.append (tmp);
     1587  }
     1588
     1589  for (CFListIterator i= result; i.hasItem(); i++)
     1590  {
     1591    F /= i.getItem();
     1592    if (foundDifferent)
     1593      i.getItem()= swapvar (i.getItem(), x, z);
     1594    i.getItem()= N (i.getItem());
     1595  }
     1596
     1597  if (foundDifferent)
     1598  {
     1599    CFList l= differentSecondVarLCs [j];
     1600    for (CFListIterator i= l; i.hasItem(); i++)
     1601      i.getItem()= swapvar (i.getItem(), y, z);
     1602    differentSecondVarLCs [j]= l;
     1603    F= swapvar (F, x, z);
     1604  }
     1605
     1606  result.insert (N (F));
     1607
     1608  result= distributeContent (result, differentSecondVarLCs, length, bufFactors);
     1609
     1610  if (!result.getFirst().inCoeffDomain())
     1611  {
     1612    CFListIterator i= result;
     1613    CanonicalForm tmp;
     1614    if (foundDifferent)
     1615      i.getItem()= swapvar (i.getItem(), Variable (2), y);
     1616
     1617    tmp= i.getItem();
     1618
     1619    i++;
     1620    for (; i.hasItem(); i++)
     1621    {
     1622      if (foundDifferent)
     1623        i.getItem()= swapvar (i.getItem(), Variable (2), y)*tmp;
     1624      else
     1625        i.getItem() *= tmp;
     1626    }
     1627  }
     1628  else
     1629    y= Variable (1);
     1630
     1631  return result;
     1632}
     1633
     1634void
     1635evaluationWRTDifferentSecondVars (CFList*& Aeval, const CFList& evaluation,
     1636                                  const CanonicalForm& A)
     1637{
     1638  for (int i= A.level(); i > 2; i--)
     1639  {
     1640    CanonicalForm tmp= A;
     1641    CFList tmp2= CFList();
     1642    CFListIterator iter= evaluation;
     1643    bool preserveDegree= true;
     1644    for (int j= A.level(); j > 1; j--, iter++)
     1645    {
     1646      if (j == i)
     1647        continue;
     1648      else
     1649      {
     1650        tmp= tmp (iter.getItem(), j);
     1651        tmp2.insert (tmp);
     1652        if ((degree (tmp, i) != degree (A, i)) ||
     1653            (degree (tmp, 1) != degree (A, 1)))
     1654        {
     1655          preserveDegree= false;
     1656          break;
     1657        }
     1658        if (!content(tmp).inCoeffDomain() || !content(tmp,1).inCoeffDomain())
     1659        {
     1660          preserveDegree= false;
     1661          break;
     1662        }
     1663      }
     1664    }
     1665    if (preserveDegree)
     1666      Aeval [i - 3]= tmp2;
     1667    else
     1668      Aeval [i - 3]= CFList();
     1669  }
     1670}
     1671
     1672static inline
     1673CanonicalForm prodEval (const CFList& l, const CanonicalForm& evalPoint,
     1674                        const Variable& v)
     1675{
     1676  CanonicalForm result= 1;
     1677  for (CFListIterator i= l; i.hasItem(); i++)
     1678    result *= i.getItem() (evalPoint, v);
     1679  return result;
     1680}
     1681
     1682//recombine bivariate factors in case one bivariate factorization yields less
     1683// factors than the other
     1684CFList
     1685recombination (const CFList& factors1, const CFList& factors2, int s, int thres,
     1686               const CanonicalForm& evalPoint, const Variable& x)
     1687{
     1688  CFList T, S;
     1689
     1690  T= factors1;
     1691  CFList result;
     1692  CanonicalForm buf;
     1693  int * v= new int [T.length()];
     1694  for (int i= 0; i < T.length(); i++)
     1695    v[i]= 0;
     1696  bool nosubset= false;
     1697  CFArray TT;
     1698  TT= copy (factors1);
     1699  while (T.length() >= 2*s && s <= thres)
     1700  {
     1701    while (nosubset == false)
     1702    {
     1703      if (T.length() == s)
     1704      {
     1705        delete [] v;
     1706        result.append (prod (T));
     1707        return result;
     1708      }
     1709      S= subset (v, s, TT, nosubset);
     1710      if (nosubset) break;
     1711      buf= prodEval (S, evalPoint, x);
     1712      buf /= Lc (buf);
     1713      if (find (factors2, buf))
     1714      {
     1715        T= Difference (T, S);
     1716        result.append (prod (S));
     1717        TT= copy (T);
     1718        indexUpdate (v, s, T.length(), nosubset);
     1719        if (nosubset) break;
     1720      }
     1721    }
     1722    s++;
     1723    if (T.length() < 2*s || T.length() == s)
     1724    {
     1725      delete [] v;
     1726      result.append (prod (T));
     1727      return result;
     1728    }
     1729    for (int i= 0; i < T.length(); i++)
     1730      v[i]= 0;
     1731    nosubset= false;
     1732  }
     1733
     1734  delete [] v;
     1735  if (T.length() < 2*s)
     1736  {
     1737    result.append (prod (T));
     1738    return result;
     1739  }
     1740
     1741  return result;
     1742}
     1743
     1744void
     1745factorizationWRTDifferentSecondVars (const CanonicalForm& A, CFList*& Aeval,
     1746                                     const ExtensionInfo& info,
     1747                                     int& minFactorsLength, bool& irred)
     1748{
     1749  Variable x= Variable (1);
     1750  minFactorsLength= 0;
     1751  irred= false;
     1752  for (int j= 0; j < A.level() - 2; j++)
     1753  {
     1754    if (!Aeval[j].isEmpty())
     1755    {
     1756      Variable v= Variable (Aeval[j].getFirst().level());
     1757
     1758      CFList factors;
     1759      if (CFFactory::gettype() == GaloisFieldDomain)
     1760        factors= GFBiSqrfFactorize (Aeval[j].getFirst());
     1761      else if (info.getAlpha().level() == 1)
     1762        factors= FpBiSqrfFactorize (Aeval[j].getFirst());
     1763      else
     1764        factors= FqBiSqrfFactorize (Aeval[j].getFirst(), info.getAlpha());
     1765
     1766      factors.removeFirst();
     1767      if (minFactorsLength == 0)
     1768        minFactorsLength= factors.length();
     1769      else
     1770        minFactorsLength= tmin (minFactorsLength, factors.length());
     1771
     1772      if (factors.length() == 1)
     1773      {
     1774        irred= true;
     1775        return;
     1776      }
     1777      sortList (factors, x);
     1778      Aeval [j]= factors;
     1779    }
     1780  }
     1781}
     1782
     1783void getLeadingCoeffs (const CanonicalForm& A, CFList*& Aeval,
     1784                       const CFList& uniFactors, const CFList& evaluation
     1785                      )
     1786{
     1787  for (int j= 0; j < A.level() - 2; j++)
     1788  {
     1789    if (!Aeval[j].isEmpty())
     1790    {
     1791      int i= A.level();
     1792      CanonicalForm evalPoint;
     1793      for (CFListIterator iter= evaluation; iter.hasItem(); iter++, i--)
     1794      {
     1795        if (i == Aeval[j].getFirst().level())
     1796        {
     1797          evalPoint= iter.getItem();
     1798          break;
     1799        }
     1800      }
     1801
     1802      Variable v= Variable (i);
     1803      if (Aeval[j].length() > uniFactors.length())
     1804        Aeval[j]= recombination (Aeval[j], uniFactors, 1,
     1805                                 Aeval[j].length() - uniFactors.length() + 1,
     1806                                 evalPoint, v);
     1807
     1808      CFList l;
     1809      CanonicalForm buf;
     1810      for (CFListIterator iter1= uniFactors; iter1.hasItem(); iter1++)
     1811      {
     1812        for (CFListIterator iter2= Aeval[j]; iter2.hasItem(); iter2++)
     1813        {
     1814          buf= mod (iter2.getItem(), v - evalPoint);
     1815          buf /= Lc (buf);
     1816          if (iter1.getItem() == buf)
     1817          {
     1818            l.append (iter2.getItem());
     1819            break;
     1820          }
     1821        }
     1822      }
     1823      Aeval [j]= l;
     1824
     1825      CFList LCs;
     1826      for (CFListIterator iter= Aeval[j]; iter.hasItem(); iter++)
     1827        LCs.append (LC (iter.getItem() (v + evalPoint, v), 1));
     1828      normalize (LCs);
     1829      Aeval[j]= LCs;
     1830    }
     1831  }
     1832}
     1833
     1834CFList
     1835buildUniFactors (const CFList& biFactors, const CanonicalForm& evalPoint,
     1836                 const Variable& y)
     1837{
     1838  CFList result;
     1839  CanonicalForm tmp;
     1840  for (CFListIterator i= biFactors; i.hasItem(); i++)
     1841  {
     1842    tmp= mod (i.getItem(), y - evalPoint);
     1843    tmp /= Lc (tmp);
     1844    result.append (tmp);
     1845  }
     1846  return result;
     1847}
     1848
     1849void refineBiFactors (const CanonicalForm& A, CFList& biFactors,
     1850                      CFList* const& Aeval, const CFList& evaluation,
     1851                      int minFactorsLength)
     1852{
     1853  for (int j= 0; j < A.level() - 2; j++)
     1854  {
     1855    if (Aeval[j].length() == minFactorsLength)
     1856    {
     1857      int i= A.level();
     1858      CanonicalForm evalPoint;
     1859      for (CFListIterator iter= evaluation; iter.hasItem(); iter++, i--)
     1860      {
     1861        if (i == Aeval[j].getFirst().level())
     1862        {
     1863          evalPoint= iter.getItem();
     1864          break;
     1865        }
     1866      }
     1867
     1868      Variable v= Variable (i);
     1869      CFList list= buildUniFactors (Aeval[j], evalPoint, v);
     1870
     1871      Variable y= Variable (2);
     1872      biFactors= recombination (biFactors, list, 1,
     1873                                biFactors.length() - list.length() + 1,
     1874                                evaluation.getLast(), y);
     1875      return;
     1876    }
     1877  }
     1878}
     1879
     1880void prepareLeadingCoeffs (CFList*& LCs, int n, const CFList& leadingCoeffs,
     1881                           const CFList& biFactors)
     1882{
     1883  CFList l= leadingCoeffs;
     1884  LCs [n-3]= l;
     1885  for (int i= n - 1; i > 2; i--)
     1886  {
     1887    for (CFListIterator j= l; j.hasItem(); j++)
     1888      j.getItem()= j.getItem() (0, i + 1);
     1889    LCs [i - 3]= l;
     1890  }
     1891  l= LCs [0];
     1892  for (CFListIterator i= l; i.hasItem(); i++)
     1893    i.getItem()= i.getItem() (0, 3);
     1894  CFListIterator ii= biFactors;
     1895  CFList normalizeFactor;
     1896  for (CFListIterator i= l; i.hasItem(); i++, ii++)
     1897    normalizeFactor.append (Lc (LC (ii.getItem(), 1))/Lc (i.getItem()));
     1898  for (int i= 0; i < n-2; i++)
     1899  {
     1900    ii= normalizeFactor;
     1901    for (CFListIterator j= LCs [i]; j.hasItem(); j++, ii++)
     1902      j.getItem() *= ii.getItem();
     1903  }
     1904}
     1905
     1906CFList recoverFactors (const CanonicalForm& F, const CFList& factors)
     1907{
     1908  CFList result;
     1909  CanonicalForm tmp;
     1910  for (CFListIterator i= factors; i.hasItem(); i++)
     1911  {
     1912    tmp= i.getItem() / content (i.getItem(), 1);
     1913    if (fdivides (tmp, F))
     1914      result.append (tmp);
     1915  }
     1916  return result;
     1917}
     1918
     1919CFList
     1920extNonMonicFactorRecombination (const CFList& factors, const CanonicalForm& F,
     1921                                const ExtensionInfo& info,
     1922                                const CFList& evaluation)
     1923{
     1924  Variable alpha= info.getAlpha();
     1925  Variable beta= info.getBeta();
     1926  CanonicalForm gamma= info.getGamma();
     1927  CanonicalForm delta= info.getDelta();
     1928  int k= info.getGFDegree();
     1929  CFList source, dest;
     1930
     1931  int degMipoBeta= 1;
     1932  if (!k && beta != Variable(1))
     1933    degMipoBeta= degree (getMipo (beta));
     1934
     1935  CFList T, S;
     1936  T= factors;
     1937  int s= 1;
     1938  CFList result;
     1939  CanonicalForm buf= F;
     1940
     1941  CanonicalForm g;
     1942  CanonicalForm buf2;
     1943  int * v= new int [T.length()];
     1944  for (int i= 0; i < T.length(); i++)
     1945    v[i]= 0;
     1946  bool noSubset= false;
     1947  CFArray TT;
     1948  TT= copy (factors);
     1949  bool recombination= false;
     1950  bool trueFactor= false;
     1951  while (T.length() >= 2*s)
     1952  {
     1953    while (noSubset == false)
     1954    {
     1955      if (T.length() == s)
     1956      {
     1957        delete [] v;
     1958        if (recombination)
     1959        {
     1960          g= prod (T);
     1961          T.removeFirst();
     1962          result.append (g/myContent (g));
     1963          g= reverseShift (g, evaluation);
     1964          g /= Lc (g);
     1965          appendTestMapDown (result, g, info, source, dest);
     1966          return result;
     1967        }
     1968        else
     1969        {
     1970          buf= reverseShift (buf, evaluation);
     1971          return CFList (buf);
     1972        }
     1973      }
     1974
     1975      S= subset (v, s, TT, noSubset);
     1976      if (noSubset) break;
     1977
     1978      g= prod (S);
     1979      g /= myContent (g);
     1980      if (fdivides (g, buf))
     1981      {
     1982        buf2= reverseShift (g, evaluation);
     1983        buf2 /= Lc (buf2);
     1984        if (!k && beta == Variable (1))
     1985        {
     1986          if (degree (buf2, alpha) < degMipoBeta)
     1987          {
     1988            appendTestMapDown (result, buf2, info, source, dest);
     1989            buf /= g;
     1990            recombination= true;
     1991            trueFactor= true;
     1992          }
     1993        }
     1994        else
     1995        {
     1996          if (!isInExtension (buf2, gamma, k, delta, source, dest))
     1997          {
     1998            appendTestMapDown (result, buf2, info, source, dest);
     1999            buf /= g;
     2000            recombination= true;
     2001            trueFactor= true;
     2002          }
     2003        }
     2004        if (trueFactor)
     2005        {
     2006          T= Difference (T, S);
     2007
     2008          if (T.length() < 2*s || T.length() == s)
     2009          {
     2010            delete [] v;
     2011            buf= reverseShift (buf, evaluation);
     2012            buf /= Lc (buf);
     2013            appendTestMapDown (result, buf, info, source, dest);
     2014            return result;
     2015          }
     2016          trueFactor= false;
     2017          TT= copy (T);
     2018          indexUpdate (v, s, T.length(), noSubset);
     2019          if (noSubset) break;
     2020        }
     2021      }
     2022    }
     2023    s++;
     2024    if (T.length() < 2*s || T.length() == s)
     2025    {
     2026      delete [] v;
     2027      buf= reverseShift (buf, evaluation);
     2028      appendTestMapDown (result, buf, info, source, dest);
     2029      return result;
     2030    }
     2031    for (int i= 0; i < T.length(); i++)
     2032      v[i]= 0;
     2033    noSubset= false;
     2034  }
     2035  if (T.length() < 2*s)
     2036  {
     2037    buf= reverseShift (F, evaluation);
     2038    appendMapDown (result, buf, info, source, dest);
     2039  }
     2040
     2041  delete [] v;
     2042  return result;
     2043}
     2044
     2045CFList
    15662046extFactorize (const CanonicalForm& F, const ExtensionInfo& info);
    15672047
    … …  
    16702150      {
    16712151        swapLevel= i;
    1672         A= swapvar (A, x, z);
     2152        bufA= swapvar (A, x, z);
    16732153      }
    16742154      gcdDerivZ= gcd (bufA, derivZ);
    … …  
    16822162        normalize (factorsG);
    16832163        return factorsG;
     2164      }
     2165      else
     2166      {
     2167        A= bufA;
     2168        break;
    16842169      }
    16852170    }
    … …  
    17012186  if (factorNums < (int) logarithm)
    17022187    factorNums= (int) logarithm;
     2188  CFList* bufAeval2= new CFList [A.level() - 2];
     2189  CFList* Aeval2= new CFList [A.level() - 2];
     2190  int counter;
     2191  int differentSecondVar= 0;
    17032192  // several bivariate factorizations
    17042193  for (int i= 0; i < factorNums; i++)
    17052194  {
     2195    counter= 0;
    17062196    bufA= A;
    17072197    bufAeval= CFList();
    … …  
    17162206        level= swapLevel + 1;
    17172207
    1718       swapLevel2= newMainVariableSearch (A, Aeval, evaluation, alpha, level);
     2208      CanonicalForm g;
     2209      swapLevel2= newMainVariableSearch (A, Aeval, evaluation, alpha, level, g);
    17192210
    17202211      if (!swapLevel2) // need to pass to an extension
    … …  
    17232214        appendSwapDecompress (factors, contentAFactors, N, swapLevel, x);
    17242215        normalize (factors);
     2216        delete [] bufAeval2;
     2217        delete [] Aeval2;
    17252218        return factors;
    17262219      }
    17272220      else
    17282221      {
     2222        if (swapLevel2 == -1)
     2223        {
     2224          CFList factorsG=
     2225          Union (multiFactorize (g, info),
     2226                 multiFactorize (A/g, info));
     2227          appendSwapDecompress (factorsG, contentAFactors, N, swapLevel, x);
     2228          normalize (factorsG);
     2229          delete [] bufAeval2;
     2230          delete [] Aeval2;
     2231          return factorsG;
     2232        }
    17292233        fail= false;
    17302234        bufAeval= Aeval;
    … …  
    17372241
    17382242    bivarEval= bufEvaluation.getLast();
    1739     bufEvaluation.removeLast();
     2243
     2244    evaluationWRTDifferentSecondVars (bufAeval2, bufEvaluation, A);
     2245
     2246    for (int j= 0; j < A.level() - 1; j++)
     2247    {
     2248      if (!bufAeval2[j].isEmpty())
     2249        counter++;
     2250    }
    17402251
    17412252    bufLift= degree (A, y) + 1 + degree (LC(A, x), y);
    17422253
    17432254    TIMING_START (fac_bi_factorizer);
    1744     bufBiFactors= biFactorizer (bufAeval.getFirst(), alpha, bivarEval, bufLift);
     2255    if (!GF && alpha.level() == 1)
     2256      bufBiFactors= FpBiSqrfFactorize (bufAeval.getFirst());
     2257    else if (GF)
     2258      bufBiFactors= GFBiSqrfFactorize (bufAeval.getFirst());
     2259    else
     2260      bufBiFactors= FqBiSqrfFactorize (bufAeval.getFirst(), alpha);
    17452261    TIMING_END_AND_PRINT (fac_bi_factorizer,
    17462262                          "time for bivariate factorization: ");
     2263    bufBiFactors.removeFirst();
    17472264
    17482265    if (bufBiFactors.length() == 1)
    … …  
    17572274                            swapLevel2, x);
    17582275      normalize (factors);
     2276      delete [] bufAeval2;
     2277      delete [] Aeval2;
    17592278      return factors;
    17602279    }
    17612280
    1762     bufEvaluation.append (-bivarEval[0]);
    17632281    if (i == 0)
    17642282    {
    … …  
    17672285      biFactors= bufBiFactors;
    17682286      lift= bufLift;
     2287      for (int j= 0; j < A.level() - 2; j++)
     2288        Aeval2 [j]= bufAeval2 [j];
     2289      differentSecondVar= counter;
    17692290    }
    17702291    else
    17712292    {
    17722293      if (bufBiFactors.length() < biFactors.length() ||
    1773           ((bufLift < lift) && (bufBiFactors.length() == biFactors.length())))
     2294          ((bufLift < lift) && (bufBiFactors.length() == biFactors.length())) ||
     2295          counter > differentSecondVar)
    17742296      {
    17752297        Aeval= bufAeval;
    … …  
    17772299        biFactors= bufBiFactors;
    17782300        lift= bufLift;
     2301        for (int j= 0; j < A.level() - 2; j++)
     2302          Aeval2 [j]= bufAeval2 [j];
     2303        differentSecondVar= counter;
    17792304      }
    17802305    }
    … …  
    17852310  }
    17862311
     2312  delete [] bufAeval2;
     2313
     2314  sortList (biFactors, x);
     2315
     2316  int minFactorsLength;
     2317  bool irred= false;
     2318  factorizationWRTDifferentSecondVars (A, Aeval2, info, minFactorsLength, irred);
     2319
     2320  if (irred)
     2321  {
     2322    if (extension)
     2323    {
     2324      CFList source, dest;
     2325      A= mapDown (A, info, source, dest);
     2326    }
     2327    factors.append (A);
     2328    appendSwapDecompress (factors, contentAFactors, N, swapLevel,
     2329                          swapLevel2, x);
     2330    normalize (factors);
     2331    delete [] Aeval2;
     2332    return factors;
     2333  }
     2334
     2335  if (minFactorsLength == 0)
     2336    minFactorsLength= biFactors.length();
     2337  else if (biFactors.length() > minFactorsLength)
     2338    refineBiFactors (A, biFactors, Aeval2, evaluation, minFactorsLength);
     2339
     2340  CFList uniFactors= buildUniFactors (biFactors, evaluation.getLast(), y);
     2341
     2342  CFList * oldAeval= new CFList [A.level() - 2]; //TODO use bufAeval2 for this
     2343  for (int i= 0; i < A.level() - 2; i++)
     2344    oldAeval[i]= Aeval2[i];
     2345
     2346  getLeadingCoeffs (A, Aeval2, uniFactors, evaluation);
     2347
     2348  CFList biFactorsLCs;
     2349  for (CFListIterator i= biFactors; i.hasItem(); i++)
     2350    biFactorsLCs.append (LC (i.getItem(), 1));
     2351
     2352
    17872353  //shifting to zero
    17882354  A= shift2Zero (A, Aeval, evaluation);
    17892355
    1790   int* liftBounds;
    1791   liftBounds= liftingBounds (A, lift);
    1792 
    1793   CFList MOD;
    1794   bool earlySuccess;
    1795   CFList earlyFactors;
    1796   TIMING_START (fac_hensel_lift);
    1797   CFList liftedFactors= henselLiftAndEarly
    1798                         (A, MOD, liftBounds, earlySuccess, earlyFactors,
    1799                          Aeval, biFactors, evaluation, info);
    1800   TIMING_END_AND_PRINT (fac_hensel_lift, "time for hensel lifting: ");
    1801 
    1802   if (!extension)
    1803   {
    1804     TIMING_START (fac_factor_recombination);
    1805     factors= factorRecombination (A, liftedFactors, MOD);
    1806     TIMING_END_AND_PRINT (fac_factor_recombination,
    1807                           "time for factor recombination: ");
    1808   }
    1809   else
    1810   {
    1811     TIMING_START (fac_factor_recombination);
    1812     factors= extFactorRecombination (liftedFactors, A, MOD, info, evaluation);
    1813     TIMING_END_AND_PRINT (fac_factor_recombination,
    1814                           "time for factor recombination: ");
    1815   }
    1816 
    1817   if (earlySuccess)
    1818     factors= Union (factors, earlyFactors);
     2356  CanonicalForm hh= Lc (Aeval.getFirst());
     2357
     2358  for (CFListIterator i= Aeval; i.hasItem(); i++)
     2359    i.getItem() /= hh;
     2360
     2361  A /= hh;
     2362
     2363  Variable v;
     2364  CFList leadingCoeffs= precomputeLeadingCoeff (LC (A, 1), biFactorsLCs, alpha,
     2365                                          evaluation, Aeval2, A.level() - 2, v);
     2366
     2367  if (v.level() != 1)
     2368  {
     2369    A= swapvar (A, y, v);
     2370    for (int i= 0; i < A.level() - 2; i++)
     2371    {
     2372      if (oldAeval[i].isEmpty())
     2373        continue;
     2374      if (oldAeval[i].getFirst().level() == v.level())
     2375      {
     2376        biFactors= CFList();
     2377        for (CFListIterator iter= oldAeval [i]; iter.hasItem(); iter++)
     2378          biFactors.append (swapvar (iter.getItem(), v, y));
     2379      }
     2380    }
     2381    int i= A.level();
     2382    CanonicalForm evalPoint;
     2383    for (CFListIterator iter= evaluation; iter.hasItem(); iter++, i--)
     2384    {
     2385      if (i == v.level())
     2386      {
     2387        evalPoint= iter.getItem();
     2388        iter.getItem()= evaluation.getLast();
     2389        evaluation.removeLast();
     2390        evaluation.append (evalPoint);
     2391        break;
     2392      }
     2393    }
     2394    Aeval= evaluateAtZero (A);
     2395  }
     2396
     2397  CFListIterator iter= biFactors;
     2398  for (; iter.hasItem(); iter++)
     2399    iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
     2400
     2401  CanonicalForm oldA= A;
     2402  CFList oldBiFactors= biFactors;
     2403  if (!leadingCoeffs.getFirst().inCoeffDomain())
     2404  {
     2405    CanonicalForm tmp= power (leadingCoeffs.getFirst(), biFactors.length() - 1);
     2406    A *= tmp;
     2407    Aeval= evaluateAtZero (A);
     2408    tmp= leadingCoeffs.getFirst();
     2409    for (int i= A.level(); i > 2; i--)
     2410      tmp= tmp (0, i);
     2411    if (!tmp.inCoeffDomain())
     2412    {
     2413      for (CFListIterator i= biFactors; i.hasItem(); i++)
     2414      {
     2415        i.getItem() *= tmp/LC (i.getItem(), 1);
     2416        i.getItem() /= Lc (i.getItem());
     2417      }
     2418    }
     2419    hh= Lc (Aeval.getFirst());
     2420    for (CFListIterator i= Aeval; i.hasItem(); i++)
     2421      i.getItem() /= hh;
     2422
     2423    A /= hh;
     2424  }
     2425
     2426  leadingCoeffs.removeFirst();
     2427
     2428  //prepare leading coefficients
     2429  CFList* leadingCoeffs2= new CFList [A.level() - 2];
     2430  prepareLeadingCoeffs (leadingCoeffs2, A.level(), leadingCoeffs, biFactors);
     2431
     2432  CFArray Pi;
     2433  CFList diophant;
     2434  int* liftBounds= new int [A.level() - 1];
     2435  int liftBoundsLength= A.level() - 1;
     2436  for (int i= 0; i < liftBoundsLength; i++)
     2437    liftBounds [i]= degree (A, i + 2) + 1;
     2438
     2439  Aeval.removeFirst();
     2440  bool noOneToOne= false;
     2441  factors= nonMonicHenselLift (Aeval, biFactors, leadingCoeffs2, diophant,
     2442                               Pi, liftBounds, liftBoundsLength, noOneToOne);
     2443
     2444  if (!noOneToOne)
     2445  {
     2446    int check= factors.length();
     2447    factors= recoverFactors (A, factors);
     2448    if (check != factors.length())
     2449      noOneToOne= true;
     2450
     2451    if (extension && !noOneToOne)
     2452      factors= extNonMonicFactorRecombination (factors, oldA, info, evaluation);
     2453  }
     2454  if (noOneToOne)
     2455  {
     2456    A= oldA;
     2457    Aeval= evaluateAtZero (A);
     2458    biFactors= oldBiFactors;
     2459    CanonicalForm LCA= LC (Aeval.getFirst(), 1);
     2460    CanonicalForm yToLift= power (y, lift);
     2461    CFListIterator i= biFactors;
     2462    lift= degree (i.getItem(), 2) + degree (LC (i.getItem(), 1)) + 1;
     2463    i++;
     2464
     2465    for (; i.hasItem(); i++)
     2466      lift= tmax (lift, degree (i.getItem(), 2) + degree (LC (i.getItem(), 1)) + 1);
     2467
     2468    lift= tmax (degree (Aeval.getFirst() , 2) + 1, lift);
     2469
     2470    i= biFactors;
     2471    yToLift= power (y, lift);
     2472    CanonicalForm dummy;
     2473    for (; i.hasItem(); i++)
     2474    {
     2475      LCA= LC (i.getItem(), 1);
     2476      extgcd (LCA, yToLift, LCA, dummy);
     2477      i.getItem()= mod (i.getItem()*LCA, yToLift);
     2478    }
     2479
     2480    liftBoundsLength= F.level() - 1;
     2481    liftBounds= liftingBounds (A, lift);
     2482
     2483    CFList MOD;
     2484    bool earlySuccess;
     2485    CFList earlyFactors;
     2486    TIMING_START (fac_hensel_lift);
     2487    CFList liftedFactors= henselLiftAndEarly
     2488                          (A, MOD, liftBounds, earlySuccess, earlyFactors,
     2489                           Aeval, biFactors, evaluation, info);
     2490    TIMING_END_AND_PRINT (fac_hensel_lift, "time for hensel lifting: ");
     2491
     2492    if (!extension)
     2493    {
     2494      TIMING_START (fac_factor_recombination);
     2495      factors= factorRecombination (A, liftedFactors, MOD);
     2496      TIMING_END_AND_PRINT (fac_factor_recombination,
     2497                            "time for factor recombination: ");
     2498    }
     2499    else
     2500    {
     2501      TIMING_START (fac_factor_recombination);
     2502      factors= extFactorRecombination (liftedFactors, A, MOD, info, evaluation);
     2503      TIMING_END_AND_PRINT (fac_factor_recombination,
     2504                            "time for factor recombination: ");
     2505    }
     2506
     2507    if (earlySuccess)
     2508      factors= Union (factors, earlyFactors);
     2509  }
    18192510
    18202511  if (!extension)
    … …  
    18302521      }
    18312522    }
     2523  }
     2524
     2525  if (v.level() != 1)
     2526  {
     2527    for (CFListIterator iter= factors; iter.hasItem(); iter++)
     2528      iter.getItem()= swapvar (iter.getItem(), v, y);
    18322529  }
    18332530
    … …  
    18782575      CanonicalForm mipo= randomIrredpoly (2, Variable (1));
    18792576      Variable v= rootOf (mipo);
    1880       ExtensionInfo info= ExtensionInfo (v, extension);
     2577      ExtensionInfo info= ExtensionInfo (v);
    18812578      factors= multiFactorize (A, info);
    18822579    }
    … …  
    19072604          ; //ERROR
    19082605        else
    1909           imPrimElem= mapPrimElem (primElem, alpha, v);
     2606          imPrimElem= mapPrimElem (primElem, vBuf, v);
    19102607
    19112608        CFList source, dest;
Note: See TracChangeset for help on using the changeset viewer.