Changeset b1d287 in git for factory/facFqBivar.cc


Ignore:
Timestamp:
Aug 1, 2012, 2:25:24 AM (12 years ago)
Author:
Oleksandr Motsak <motsak@…>
Branches:
(u'spielwiese', 'fe61d9c35bf7c61f2b6cbf1b56e25e2f08d536cc')
Children:
0df59c8a8e59eded04e4aca4e57cfed188a00cf1
Parents:
09afeb85ea17e564813761786f76281c8162dad0362fc6799a207ad61d3be8abe0206e52b5782e50
Message:
Merge pull request #157 from mmklee/factory_catch_up_sw

Factory catch up sw
File:
1 edited

Legend:

Unmodified
Added
Removed

  • factory/facFqBivar.cc

    r09afeb rb1d287  
    1313 *
    1414 * @author Martin Lee
    15  *
    16  * @internal @version \$Id$
    1715 *
    1816 **/
    … …  
    13331331  Variable x= Variable (1);
    13341332  CanonicalForm yToL= power (y, liftBound);
     1333  if (factors.length() == 2)
     1334  {
     1335    CanonicalForm tmp1, tmp2, tmp3;
     1336    tmp1= factors.getFirst();
     1337    tmp2= factors.getLast();
     1338    tmp1 *= LC (F, x);
     1339    tmp1= mod (tmp1, yToL);
     1340    tmp1 /= content (tmp1, x);
     1341    tmp2 *= LC (F, x);
     1342    tmp2= mod (tmp2, yToL);
     1343    tmp2 /= content (tmp2, x);
     1344    tmp3 = tmp1*tmp2;
     1345    if (tmp3/Lc (tmp3) == F/Lc (F))
     1346    {
     1347      factorsFound++;
     1348      F= 1;
     1349      reconstructedFactors.append (tmp1);
     1350      reconstructedFactors.append (tmp2);
     1351      return;
     1352    }
     1353  }
    13351354  CanonicalForm quot, buf;
    13361355  CFListIterator iter;
    … …  
    13881407  Variable y= Variable (2);
    13891408  Variable x= Variable (1);
     1409  CanonicalForm yToL= power (y, liftBound);
     1410  if (factors.length() == 2)
     1411  {
     1412    CanonicalForm tmp1, tmp2, tmp3;
     1413    tmp1= factors.getFirst();
     1414    tmp2= factors.getLast();
     1415    tmp1 *= LC (F, x);
     1416    tmp1= mod (tmp1, yToL);
     1417    tmp1 /= content (tmp1, x);
     1418    tmp2 *= LC (F, x);
     1419    tmp2= mod (tmp2, yToL);
     1420    tmp2 /= content (tmp2, x);
     1421    tmp3 = tmp1*tmp2;
     1422    if (tmp3/Lc (tmp3) == F/Lc (F))
     1423    {
     1424      factorsFound++;
     1425      F= 1;
     1426      reconstructedFactors.append (tmp1);
     1427      reconstructedFactors.append (tmp2);
     1428      return;
     1429    }
     1430  }
    13901431  CanonicalForm quot, buf;
    1391   CanonicalForm yToL= power (y, liftBound);
    13921432  CFListIterator iter;
    13931433  for (long i= 1; i <= N.NumCols(); i++)
    … …  
    16821722  CanonicalForm delta= info.getDelta();
    16831723  CanonicalForm yToL= power (y, liftBound);
     1724  CFList source, dest;
     1725  if (factors.length() == 2)
     1726  {
     1727    CanonicalForm tmp1, tmp2, tmp3;
     1728    tmp1= factors.getFirst();
     1729    tmp2= factors.getLast();
     1730    tmp1 *= LC (F, x);
     1731    tmp1= mod (tmp1, yToL);
     1732    tmp1 /= content (tmp1, x);
     1733    tmp2 *= LC (F, x);
     1734    tmp2= mod (tmp2, yToL);
     1735    tmp2 /= content (tmp2, x);
     1736    tmp3 = tmp1*tmp2;
     1737    if (tmp3/Lc (tmp3) == F/Lc (F))
     1738    {
     1739      tmp1= tmp1 (y - evaluation, y);
     1740      tmp2= tmp2 (y - evaluation, y);
     1741      if (!k && beta == x && degree (tmp2, alpha) < 1 &&
     1742          degree (tmp1, alpha) < 1)
     1743      {
     1744        factorsFound++;
     1745        F= 1;
     1746        tmp1= mapDown (tmp1, info, source, dest);
     1747        tmp2= mapDown (tmp2, info, source, dest);
     1748        reconstructedFactors.append (tmp1);
     1749        reconstructedFactors.append (tmp2);
     1750        return;
     1751      }
     1752      else if (!isInExtension (tmp2, gamma, k, delta, source, dest) &&
     1753               !isInExtension (tmp1, gamma, k, delta, source, dest))
     1754      {
     1755        factorsFound++;
     1756        F= 1;
     1757        tmp1= mapDown (tmp1, info, source, dest);
     1758        tmp2= mapDown (tmp2, info, source, dest);
     1759        reconstructedFactors.append (tmp1);
     1760        reconstructedFactors.append (tmp2);
     1761        return;
     1762      }
     1763    }
     1764  }
    16841765  CanonicalForm quot, buf, buf2;
    1685   CFList source, dest;
    16861766  CFListIterator iter;
    16871767  for (long i= 1; i <= N.NumCols(); i++)
    … …  
    41794259                               CanonicalForm& bufF, CFList& factors, int& l,
    41804260                               int& factorsFound, bool beenInThres, CFMatrix& M,
    4181                                CFArray& Pi, CFList& diophant
     4261                               CFArray& Pi, CFList& diophant, bool symmetric,
     4262                               const CanonicalForm& evaluation
    41824263                              )
    41834264{
    … …  
    42494330    while ((degree (F,y)/4)*i + 4 <= smallFactorDeg)
    42504331      i++;
    4251     while (i < 4)
    4252     {
    4253       dummy= tmin (degree (F,y)+1, (degree (F,y)/4)*(i+1)+4);
     4332    while (i < 5)
     4333    {
     4334      dummy= tmin (degree (F,y)+1, (degree (F,y)/4)*i+4);
    42544335      if (l < dummy)
    42554336      {
    … …  
    42574338        henselLiftResume12 (F, factors, l, dummy, Pi, diophant, M);
    42584339        l= dummy;
     4340        if (i == 1 && degree (F)%4==0 && symmetric && factors.length() == 2 &&
     4341            LC (F,1).inCoeffDomain() &&
     4342           (degree (factors.getFirst(), 1) == degree (factors.getLast(),1)))
     4343        {
     4344          Variable x= Variable (1);
     4345          CanonicalForm g, h, gg, hh, multiplier1, multiplier2, check1, check2;
     4346          int m= degree (F)/4+1;
     4347          g= factors.getFirst();
     4348          h= factors.getLast();
     4349          g= mod (g, power (y,m));
     4350          h= mod (h, power (y,m));
     4351          g= g (y-evaluation, y);
     4352          h= h (y-evaluation, y);
     4353          gg= mod (swapvar (g,x,y),power (x,m));
     4354          gg= gg (y + evaluation, y);
     4355          multiplier1= factors.getLast()[m-1][0]/gg[m-1][0];
     4356          gg= div (gg, power (y,m));
     4357          gg= gg*power (y,m);
     4358          hh= mod (swapvar (h,x,y),power (x,m));
     4359          hh= hh (y + evaluation, y);
     4360          multiplier2= factors.getFirst()[m-1][0]/hh[m-1][0];
     4361          hh= div (hh, power (y,m));
     4362          hh= hh*power (y,m);
     4363          gg= multiplier1*gg+mod (factors.getLast(), power (y,m));
     4364          hh= multiplier2*hh+mod (factors.getFirst(), power (y,m));
     4365          check1= gg (y-evaluation,y);
     4366          check2= hh (y-evaluation,y);
     4367          check1= swapvar (check1, x, y);
     4368          if (check1/Lc (check1) == check2/Lc (check2))
     4369          {
     4370            result.append (gg);
     4371            result.append (hh);
     4372            delete [] liftPre;
     4373            delete [] factorsFoundIndex;
     4374            return result;
     4375          }
     4376        }
    42594377      }
    42604378      else
    42614379      {
    42624380        i++;
    4263         if (i < 4)
     4381        if (i < 5)
    42644382          continue;
    42654383      }
    … …  
    42864404                               CanonicalForm& bufF, CFList& factors, int& l,
    42874405                               int& factorsFound, bool beenInThres, CFMatrix& M,
    4288                                CFArray& Pi, CFList& diophant
     4406                               CFArray& Pi, CFList& diophant, bool symmetric,
     4407                               const CanonicalForm& evaluation
    42894408                              )
    42904409{
    … …  
    43554474    while ((degree (F,y)/4)*i + 4 <= smallFactorDeg)
    43564475      i++;
    4357     while (i < 4)
    4358     {
    4359       dummy= tmin (degree (F,y)+1, (degree (F,y)/4)*(i+1)+4);
     4476    while (i < 5)
     4477    {
     4478      dummy= tmin (degree (F,y)+1, (degree (F,y)/4)*i+4);
    43604479      if (l < dummy)
    43614480      {
    … …  
    43634482        henselLiftResume12 (F, factors, l, dummy, Pi, diophant, M);
    43644483        l= dummy;
     4484        if (i == 1 && degree (F)%4==0 && symmetric && factors.length() == 2 &&
     4485            LC (F,1).inCoeffDomain() &&
     4486           (degree (factors.getFirst(), 1) == degree (factors.getLast(),1)))
     4487        {
     4488          Variable x= Variable (1);
     4489          CanonicalForm g, h, gg, hh, multiplier1, multiplier2, check1, check2;
     4490          int m= degree (F)/4+1;
     4491          g= factors.getFirst();
     4492          h= factors.getLast();
     4493          g= mod (g, power (y,m));
     4494          h= mod (h, power (y,m));
     4495          g= g (y-evaluation, y);
     4496          h= h (y-evaluation, y);
     4497          gg= mod (swapvar (g,x,y),power (x,m));
     4498          gg= gg (y + evaluation, y);
     4499          multiplier1= factors.getLast()[m-1][0]/gg[m-1][0];
     4500          gg= div (gg, power (y,m));
     4501          gg= gg*power (y,m);
     4502          hh= mod (swapvar (h,x,y),power (x,m));
     4503          hh= hh (y + evaluation, y);
     4504          multiplier2= factors.getFirst()[m-1][0]/hh[m-1][0];
     4505          hh= div (hh, power (y,m));
     4506          hh= hh*power (y,m);
     4507          gg= multiplier1*gg+mod (factors.getLast(), power (y,m));
     4508          hh= multiplier2*hh+mod (factors.getFirst(), power (y,m));
     4509          check1= gg (y-evaluation,y);
     4510          check2= hh (y-evaluation,y);
     4511          check1= swapvar (check1, x, y);
     4512          if (check1/Lc (check1) == check2/Lc (check2))
     4513          {
     4514            result.append (gg);
     4515            result.append (hh);
     4516            delete [] liftPre;
     4517            delete [] factorsFoundIndex;
     4518            return result;
     4519          }
     4520        }
    43654521      }
    43664522      else
    43674523      {
    43684524        i++;
    4369         if (i < 4)
     4525        if (i < 5)
    43704526          continue;
    43714527      }
    … …  
    44664622    while ((degree (F,y)/4)*i + 4 <= smallFactorDeg)
    44674623      i++;
    4468     while (i < 4)
    4469     {
    4470       dummy= tmin (degree (F,y)+1, (degree (F,y)/4)*(i+1)+4);
     4624    while (i < 5)
     4625    {
     4626      dummy= tmin (degree (F,y)+1, (degree (F,y)/4)*i+4);
    44714627      if (l < dummy)
    44724628      {
    … …  
    44784634      {
    44794635        i++;
    4480         if (i < 4)
     4636        if (i < 5)
    44814637          continue;
    44824638      }
    … …  
    45794735  }
    45804736  Variable y= F.mvar();
    4581   CanonicalForm shiftedF= G (y - evaluation, y);
    4582   int sizeOldF= size (shiftedF);
     4737  int sizeOldF= size (G);
    45834738  if (size (F) < sizeOldF)
    45844739  {
    4585     H= F (y + evaluation, y); //shift back to zero
     4740    H= F;
    45864741    success= true;
    45874742    return earlyFactors;
    … …  
    45964751CFList
    45974752henselLiftAndLatticeRecombi (const CanonicalForm& G, const CFList& uniFactors,
    4598                              const Variable& alpha, const DegreePattern& degPat
     4753                             const Variable& alpha, const DegreePattern& degPat,
     4754                             bool symmetric, const CanonicalForm& evaluation
    45994755                            )
    46004756{
    … …  
    46274783  CFList smallFactors;
    46284784  CanonicalForm H;
    4629   bool success;
     4785  bool success= false;
    46304786  smallFactors= sieveSmallFactors (F, bufUniFactors, degs, H, diophant, Pi, M,
    46314787                                   success, minBound + 1
    … …  
    49265082    result= earlyReconstructionAndLifting (F, NTLN, bufF, bufUniFactors, l,
    49275083                                           factorsFound, beenInThres, M, Pi,
    4928                                            diophant
     5084                                           diophant, symmetric, evaluation
    49295085                                          );
    49305086
    … …  
    49395095    result= earlyReconstructionAndLifting (F, NTLNe, bufF, bufUniFactors, l,
    49405096                                           factorsFound, beenInThres, M, Pi,
    4941                                            diophant
     5097                                           diophant, symmetric, evaluation
    49425098                                          );
    49435099
    … …  
    50645220    }
    50655221    return Union (result, henselLiftAndLatticeRecombi (bufF, bufUniFactors,
    5066                                                        alpha, degs
     5222                                                       alpha, degs, symmetric,
     5223                                                       evaluation
    50675224                                                      )
    50685225                 );
    … …  
    51945351    delete [] bounds;
    51955352    return Union (result, henselLiftAndLatticeRecombi (F, bufUniFactors, alpha,
    5196                                                        degs
     5353                                                       degs,symmetric, evaluation
    51975354                                                      )
    51985355                 );
    … …  
    52815438  {
    52825439    delete [] bounds;
    5283     return CFList (F);
     5440    CFList source, dest;
     5441    CanonicalForm tmp= G (y - evaluation, y);
     5442    tmp= mapDown (tmp, info, source, dest);
     5443    return CFList (tmp);
    52845444  }
    52855445  int minBound= bounds[0];
    … …  
    52995459  CFList smallFactors;
    53005460  CanonicalForm H;
    5301   bool success;
     5461  bool success= false;
    53025462  smallFactors= extSieveSmallFactors (F, bufUniFactors, degs, H, diophant, Pi,
    53035463                                      M, success, minBound + 1, evaluation, info
    … …  
    58516011
    58526012  bool fail= false;
    5853   CanonicalForm Aeval, evaluation, bufAeval, bufEvaluation, buf;
     6013  CanonicalForm Aeval, evaluation, bufAeval, bufEvaluation, buf, tmp;
    58546014  CFList uniFactors, list, bufUniFactors;
    58556015  DegreePattern degs;
    … …  
    58696029  int subCheck1= substituteCheck (A, x);
    58706030  int subCheck2= substituteCheck (A, y);
     6031  bool symmetric= false;
    58716032  for (int i= 0; i < factorNums; i++)
    58726033  {
    58736034    bufAeval= A;
    58746035    bufEvaluation= evalPoint (A, bufAeval, alpha, list, GF, fail);
    5875     if (!derivXZero && !fail2)
    5876     {
    5877       buf= swapvar (A, x, y);
     6036    if (!derivXZero && !fail2 && !symmetric)
     6037    {
     6038      if (i == 0)
     6039      {
     6040        buf= swapvar (A, x, y);
     6041        symmetric= (A/Lc (A) == buf/Lc (buf));
     6042      }
    58786043      bufAeval2= buf;
    58796044      bufEvaluation2= evalPoint (buf, bufAeval2, alpha, list2, GF, fail2);
    … …  
    58826047    if (fail && (i == 0))
    58836048    {
    5884       if (!derivXZero && !fail2)
     6049      if (!derivXZero && !fail2 && !symmetric)
    58856050      {
    58866051        bufEvaluation= bufEvaluation2;
    … …  
    58886053        subCheck2= subCheck1;
    58896054        subCheck1= dummy;
     6055        tmp= A;
    58906056        A= buf;
     6057        buf= tmp;
    58916058        bufAeval= bufAeval2;
    58926059        swap2= true;
    … …  
    59206087              (prod (bufUniFactors)*Lc (bufAeval) == bufAeval));
    59216088
    5922     if (!derivXZero && !fail2)
     6089    if (!derivXZero && !fail2 && !symmetric)
    59236090    {
    59246091      TIMING_START (fac_fq_uni_factorizer);
    … …  
    59316098
    59326099    if (bufUniFactors.length() == 1 ||
    5933         (!fail2 && !derivXZero && (bufUniFactors2.length() == 1)))
     6100        (!fail2 && !derivXZero && !symmetric && (bufUniFactors2.length() == 1)))
    59346101    {
    59356102      if (extension)
    … …  
    59696136      }
    59706137
    5971       if (!derivXZero && !fail2 && subCheck2 > 0)
     6138      if (!derivXZero && !fail2 && !symmetric && subCheck2 > 0)
    59726139      {
    59736140        int subCheck= substituteCheck (bufUniFactors2);
    … …  
    59896156    // degree analysis
    59906157    bufDegs = DegreePattern (bufUniFactors);
    5991     if (!derivXZero && !fail2)
     6158    if (!derivXZero && !fail2 && !symmetric)
    59926159      bufDegs2= DegreePattern (bufUniFactors2);
    59936160
    … …  
    59986165      uniFactors= bufUniFactors;
    59996166      degs= bufDegs;
    6000       if (!derivXZero && !fail2)
     6167      if (!derivXZero && !fail2 && !symmetric)
    60016168      {
    60026169        Aeval2= bufAeval2;
    … …  
    60096176    {
    60106177      degs.intersect (bufDegs);
    6011       if (!derivXZero && !fail2)
     6178      if (!derivXZero && !fail2 && !symmetric)
    60126179      {
    60136180        degs2.intersect (bufDegs2);
    … …  
    60276194    }
    60286195    list.append (bufEvaluation);
    6029     if (!derivXZero && !fail2)
     6196    if (!derivXZero && !fail2 && !symmetric)
    60306197      list2.append (bufEvaluation2);
    60316198  }
    60326199
    6033   if (!derivXZero && !fail2)
     6200  if (!derivXZero && !fail2 && !symmetric)
    60346201  {
    60356202    if (uniFactors.length() > uniFactors2.length() ||
    … …  
    61186285    else if (alpha.level() == 1 && !GF)
    61196286    {
    6120       CFList lll= henselLiftAndLatticeRecombi (A, uniFactors, alpha, degs);
     6287      CFList lll= henselLiftAndLatticeRecombi (A, uniFactors, alpha, degs,
     6288                                               symmetric, evaluation);
    61216289      factors= Union (lll, factors);
    61226290    }
    61236291    else if (!extension && (alpha != x || GF))
    61246292    {
    6125       CFList lll= henselLiftAndLatticeRecombi (A, uniFactors, alpha, degs);
     6293      CFList lll= henselLiftAndLatticeRecombi (A, uniFactors, alpha, degs,
     6294                                               symmetric, evaluation);
    61266295      factors= Union (lll, factors);
    61276296    }
Note: See TracChangeset for help on using the changeset viewer.