Changeset 14e634 in git


Ignore:
Timestamp:
Dec 10, 2012, 3:38:49 PM (11 years ago)
Author:
Martin Lee <martinlee84@…>
Branches:
(u'spielwiese', '17f1d200f27c5bd38f5dfc6e8a0879242279d1d8')
Children:
b15cf8578937df382dad415dbfdd2229103409bf
Parents:
3e7db4d961b4509d248e12d8e96e2bed08d9cfe8
git-author:
Martin Lee <martinlee84@web.de>2012-12-10 15:38:49+01:00
git-committer:
Martin Lee <martinlee84@web.de>2012-12-12 15:24:58+01:00
Message:
fix: bug in factorization over Q(a)
Location:
factory
Files:
3 edited

Legend:

Unmodified
Added
Removed

  • factory/facBivar.cc

    r3e7db4 r14e634  
    499499  modpk b= modpk();
    500500  bool mipoHasDen= false;
     501  CanonicalForm den= 1;
    501502  if (!extension)
    502503  {
    … …  
    519520  {
    520521    A /= Lc (Aeval);
     522    mipoHasDen= !bCommonDen(mipo).isOne();
     523    mipo *= bCommonDen (mipo);
     524    ZZX NTLmipo= convertFacCF2NTLZZX (mipo);
     525    ZZX NTLLcf= convertFacCF2NTLZZX (Lc (A*bCommonDen (A)));
     526    ZZ NTLf= resultant (NTLmipo, NTLLcf);
     527    ZZ NTLD= discriminant (NTLmipo);
     528    den= abs (convertZZ2CF (NTLD*NTLf));
     529
    521530    // make factors elements of Z(a)[x] disable for modularDiophant
    522531    CanonicalForm multiplier= 1;
    … …  
    529538    A *= bCommonDen (A);
    530539
    531     mipoHasDen= !bCommonDen(mipo).isOne();
    532     mipo *= bCommonDen (mipo);
    533540    Off (SW_RATIONAL);
    534541    int i= 0;
    535     ZZX NTLmipo= convertFacCF2NTLZZX (mipo);
    536     CanonicalForm discMipo= convertZZ2CF (discriminant (NTLmipo));
     542    CanonicalForm discMipo= convertZZ2CF (NTLD);
    537543    findGoodPrime (F*discMipo,i);
    538544    findGoodPrime (Aeval*discMipo,i);
    … …  
    555561  uniFactors= henselLiftAndEarly
    556562              (A, earlySuccess, earlyFactors, degs, liftBound,
    557                uniFactors, dummy, evaluation, b);
     563               uniFactors, dummy, evaluation, b, den);
    558564  TIMING_END_AND_PRINT (fac_bi_hensel_lift,
    559565                        "time for bivariate hensel lifting over Q: ");
    … …  
    578584  TIMING_START (fac_bi_factor_recombination);
    579585  factors= factorRecombination (uniFactors, A, MODl, degs, 1,
    580                                 uniFactors.length()/2, b);
     586                                uniFactors.length()/2, b, den);
    581587  TIMING_END_AND_PRINT (fac_bi_factor_recombination,
    582588                        "time for bivariate factor recombination over Q: ");

  • factory/facFqBivar.cc

    r3e7db4 r14e634  
    482482factorRecombination (CFList& factors, CanonicalForm& F,
    483483                     const CanonicalForm& N, DegreePattern& degs, int s,
    484                      int thres, const modpk& b
     484                     int thres, const modpk& b, const CanonicalForm& den
    485485                    )
    486486{
    … …  
    515515  Variable y= Variable (2);
    516516  Variable x= Variable (1);
    517   CanonicalForm LCBuf= LC (F, x);
     517  CanonicalForm denom= den, denQuot;
     518  CanonicalForm LCBuf= LC (F, x)*denom;
    518519  CanonicalForm g, quot, buf= F;
    519520  int * v= new int [T.length()];
    … …  
    598599          {
    599600            On (SW_RATIONAL);
     601            if (!Lc (g).inBaseDomain())
     602              g /= Lc (g);
    600603            g *= bCommonDen (g);
    601604            Off (SW_RATIONAL);
    … …  
    605608          if (fdivides (g, buf, quot))
    606609          {
     610            denom *= abs (lc (g));
    607611            recombination= true;
    608612            result.append (g);
    609613            if (b.getp() != 0)
    610               buf= quot*bCommonDen (quot);
     614            {
     615              denQuot= bCommonDen (quot);
     616              buf= quot*denQuot;
     617              Off (SW_RATIONAL);
     618              denom /= gcd (denom, denQuot);
     619              On (SW_RATIONAL);
     620            }
    611621            else
    612622              buf= quot;
    613             LCBuf= LC (buf, x);
     623            LCBuf= LC (buf, x)*denom;
    614624            T= Difference (T, S);
    615625            l -= degree (g);
    … …  
    726736                      factors, int& adaptedLiftBound, int*& factorsFoundIndex,
    727737                      DegreePattern& degs, bool& success, int deg,
    728                       const modpk& b)
     738                      const modpk& b, CanonicalForm& den)
    729739{
    730740  DegreePattern bufDegs1= degs;
    … …  
    742752  if (b.getp() != 0)
    743753    buf *= bCommonDen (buf);
    744   CanonicalForm LCBuf= LC (buf, x);
     754  CanonicalForm LCBuf= LC (buf, x)*den;
    745755  CanonicalForm buf0= mulNTL (buf (0,x), LCBuf);
    746756  CanonicalForm buf1= mulNTL (buf (1,x), LCBuf);
    … …  
    748758    Off (SW_RATIONAL);
    749759  CanonicalForm test0, test1;
     760  CanonicalForm denQuot;
    750761
    751762  for (CFListIterator i= factors; i.hasItem(); i++, l++)
    … …  
    777788          {
    778789            On (SW_RATIONAL);
     790            if (!Lc (g).inBaseDomain())
     791              g /= Lc (g);
    779792            g *= bCommonDen (g);
    780793            Off (SW_RATIONAL);
    … …  
    784797          if (fdivides (g, buf, quot))
    785798          {
     799            den *= abs (lc (g));
    786800            reconstructedFactors.append (g);
    787801            factorsFoundIndex[l]= 1;
    788802            if (b.getp() != 0)
    789               buf= quot*bCommonDen(quot);
     803            {
     804              denQuot= bCommonDen (quot);
     805              buf= quot*denQuot;
     806              Off (SW_RATIONAL);
     807              den /= gcd (den, denQuot);
     808              On (SW_RATIONAL);
     809            }
    790810            else
    791811              buf= quot;
    792812            d -= degree (g);
    793             LCBuf= LC (buf, x);
     813            LCBuf= LC (buf, x)*den;
    794814            buf0= mulNTL (buf (0,x), LCBuf);
    795815            buf1= mulNTL (buf (1,x), LCBuf);
    … …  
    827847  if (bufDegs1.getLength() <= 1)
    828848    degs= bufDegs1;
     849}
     850
     851void
     852earlyFactorDetection (CFList& reconstructedFactors, CanonicalForm& F, CFList&
     853                      factors, int& adaptedLiftBound, int*& factorsFoundIndex,
     854                      DegreePattern& degs, bool& success, int deg,
     855                      const modpk& b)
     856{
     857  CanonicalForm den= 1;
     858  earlyFactorDetection (reconstructedFactors, F, factors, adaptedLiftBound, factorsFoundIndex, degs, success, deg,b, den);
    829859}
    830860
    … …  
    10021032                    earlyFactors, DegreePattern& degs, int& liftBound,
    10031033                    const CFList& uniFactors, const ExtensionInfo& info,
    1004                     const CanonicalForm& eval, modpk& b)
     1034                    const CanonicalForm& eval,modpk& b, CanonicalForm& den)
    10051035{
    10061036  Variable alpha= info.getAlpha();
    … …  
    10181048  CFList diophant;
    10191049  CFList bufUniFactors= uniFactors;
     1050  On (SW_RATIONAL);
    10201051  CanonicalForm bufA= A;
     1052  if (!Lc (A).inBaseDomain())
     1053  {
     1054    bufA /= Lc (A);
     1055    CanonicalForm denBufA= bCommonDen (bufA);
     1056    bufA *= denBufA;
     1057    Off (SW_RATIONAL);
     1058    den /= gcd (den, denBufA);
     1059  }
     1060  else
     1061  {
     1062    bufA= A;
     1063    Off (SW_RATIONAL);
     1064    den /= gcd (den, Lc (A));
     1065  }
    10211066  CanonicalForm lcA0= 0;
    10221067  bool mipoHasDen= false;
    … …  
    10821127        earlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
    10831128                              factorsFoundIndex, degs, earlySuccess,
    1084                               smallFactorDeg, b);
     1129                              smallFactorDeg, b, den);
    10851130      else
    10861131        earlyFactorDetection(earlyFactors, bufA, bufBufUniFactors, newLiftBound,
    10871132                             factorsFoundIndex, degs, earlySuccess,
    1088                              smallFactorDeg, b);
     1133                             smallFactorDeg, b, den);
    10891134    }
    10901135    else
    … …  
    11111156          earlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
    11121157                                factorsFoundIndex, degs, earlySuccess,
    1113                                 liftPre[sizeOfLiftPre-1] + 1, b);
     1158                                liftPre[sizeOfLiftPre-1] + 1, b, den);
    11141159          else
    11151160          earlyFactorDetection (earlyFactors,bufA,bufBufUniFactors,newLiftBound,
    11161161                                factorsFoundIndex, degs, earlySuccess,
    1117                                 liftPre[sizeOfLiftPre-1] + 1, b);
     1162                                liftPre[sizeOfLiftPre-1] + 1, b, den);
    11181163        }
    11191164        else
    … …  
    11451190          earlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
    11461191                                factorsFoundIndex, degs, earlySuccess,
    1147                                 liftPre[i-1] + 1, b);
     1192                                liftPre[i-1] + 1, b, den);
    11481193          else
    11491194          earlyFactorDetection (earlyFactors,bufA,bufBufUniFactors,newLiftBound,
    11501195                                factorsFoundIndex, degs, earlySuccess,
    1151                                 liftPre[i-1] + 1, b);
     1196                                liftPre[i-1] + 1, b, den);
    11521197        }
    11531198        else
    … …  
    11881233      earlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
    11891234                            factorsFoundIndex, degs, earlySuccess,
    1190                             smallFactorDeg, b);
     1235                            smallFactorDeg, b, den);
    11911236      else
    11921237      earlyFactorDetection (earlyFactors, bufA, bufBufUniFactors, newLiftBound,
    11931238                            factorsFoundIndex, degs, earlySuccess,
    1194                             smallFactorDeg, b);
     1239                            smallFactorDeg, b, den);
    11951240    }
    11961241    else
    … …  
    12171262        if (v==alpha)
    12181263        earlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
    1219                               factorsFoundIndex, degs, earlySuccess, dummy, b);
     1264                              factorsFoundIndex, degs, earlySuccess, dummy, b,
     1265                              den);
    12201266        else
    12211267        earlyFactorDetection (earlyFactors, bufA,bufBufUniFactors, newLiftBound,
    1222                               factorsFoundIndex, degs, earlySuccess, dummy, b);
     1268                              factorsFoundIndex, degs, earlySuccess, dummy, b,
     1269                              den);
    12231270      }
    12241271      else
    … …  
    12451292          if (v==alpha)
    12461293          earlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
    1247                                 factorsFoundIndex, degs, earlySuccess, dummy,b);
     1294                                factorsFoundIndex, degs, earlySuccess, dummy,b,
     1295                                den);
    12481296          else
    12491297          earlyFactorDetection (earlyFactors,bufA,bufBufUniFactors,newLiftBound,
    1250                                 factorsFoundIndex, degs, earlySuccess, dummy,b);
     1298                                factorsFoundIndex, degs, earlySuccess, dummy,b,
     1299                                den);
    12511300        }
    12521301        else
    … …  
    12871336{
    12881337  modpk dummy= modpk();
     1338  CanonicalForm den= 1;
    12891339  return henselLiftAndEarly (A, earlySuccess, earlyFactors, degs, liftBound,
    1290                              uniFactors, info, eval, dummy);
     1340                             uniFactors, info, eval, dummy, den);
    12911341}
    12921342

  • factory/facFqBivar.h

    r3e7db4 r14e634  
    585585CFList
    586586factorRecombination (
    587                 CFList& factors,       ///< [in,out] list of lifted factors
    588                                        ///< that are monic wrt Variable (1)
    589                 CanonicalForm& F,      ///< [in,out] poly to be factored
    590                 const CanonicalForm& M,///< [in] Variable (2)^liftBound
    591                 DegreePattern& degs,   ///< [in] degree pattern
    592                 int s,                 ///< [in] algorithm starts checking
    593                                        ///< subsets of size s
    594                 int thres,             ///< [in] threshold for the size of
    595                                        ///< subsets which are checked, for a
    596                                        ///< full factor recombination choose
    597                                        ///< thres= factors.length()/2
    598                 const modpk& b=modpk() ///< [in] coeff bound
     587            CFList& factors,            ///< [in,out] list of lifted factors
     588                                        ///< that are monic wrt Variable (1)
     589            CanonicalForm& F,           ///< [in,out] poly to be factored
     590            const CanonicalForm& M,     ///< [in] Variable (2)^liftBound
     591            DegreePattern& degs,        ///< [in] degree pattern
     592            int s,                      ///< [in] algorithm starts checking
     593                                        ///< subsets of size s
     594            int thres,                  ///< [in] threshold for the size of
     595                                        ///< subsets which are checked, for a
     596                                        ///< full factor recombination choose
     597                                        ///< thres= factors.length()/2
     598            const modpk& b=modpk(),     ///< [in] coeff bound
     599            const CanonicalForm& den= 1 ///< [in] bound on the den if over Q (a)
    599600                    );
    600601
    … …  
    690691        const ExtensionInfo& info, ///< [in] information about extension
    691692        const CanonicalForm& eval, ///< [in] evaluation point
    692         modpk& b                   ///< [in] coeff bound
     693        modpk& b,                  ///< [in] coeff bound
     694        CanonicalForm& den         ///< [in] bound on the den if over Q(a)
    693695                  );
    694696
Note: See TracChangeset for help on using the changeset viewer.