Changeset 7bf145 in git


Ignore:
Timestamp:
Jun 17, 2010, 2:29:28 PM (13 years ago)
Author:
Martin Lee <martinlee84@…>
Branches:
(u'jengelh-datetime', 'ceac47cbc86fe4a15902392bdbb9bd2ae0ea02c6')(u'spielwiese', 'f875bbaccd0831e36aaed09ff6adeb3eb45aeb94')
Children:
547f6439fcbe82be0ab53e3707bf2e0d4fbc7872
Parents:
9015fc56fb11f10a66eb0275771d88644708bac3
Message:
new factorization over finite fields


git-svn-id: file:///usr/local/Singular/svn/trunk@12873 2c84dea3-7e68-4137-9b89-c4e89433aadc
Location:
factory
Files:
12 added
1 edited

Legend:

Unmodified
Added
Removed

  • factory/cf_factor.cc

    r9015fc r7bf145  
    2727#include "fac_sqrfree.h"
    2828#include "cf_algorithm.h"
     29#include "facFqFactorize.h"
    2930#include "cf_map.h"
     31#include "algext.h"
    3032
    3133#include "int_int.h"
    … …  
    427429  if ( getCharacteristic() > 0 )
    428430  {
    429     ASSERT( f.isUnivariate(), "multivariate factorization not implemented" );
    430     #ifdef HAVE_NTL
    431     if (isOn(SW_USE_NTL) && (isPurePoly(f)))
    432     {
    433       // USE NTL
    434       if (getCharacteristic()!=2)
    435       {
    436         if (fac_NTL_char!=getCharacteristic())
    437         {
    438           fac_NTL_char=getCharacteristic();
    439           #ifndef NTL_ZZ
    440           if (fac_NTL_char >NTL_SP_BOUND)
    441           {
    442             ZZ r;
    443             r=getCharacteristic();
    444             ZZ_pContext ccc(r);
    445             ccc.restore();
    446             ZZ_p::init(r);
    447           }
    448           else
    449           #endif
    450           {
    451             #ifdef NTL_ZZ
    452             ZZ r;
    453             r=getCharacteristic();
    454             ZZ_pContext ccc(r);
    455             #else
    456             zz_pContext ccc(getCharacteristic());
    457             #endif
    458             ccc.restore();
    459             #ifdef NTL_ZZ
    460             ZZ_p::init(r);
    461             #else
    462             zz_p::init(getCharacteristic());
    463             #endif
    464           }
    465         }
    466        #ifndef NTL_ZZ
    467        if (fac_NTL_char >NTL_SP_BOUND)
    468        {
    469           // convert to NTL
    470           ZZ_pX f1=convertFacCF2NTLZZpX(f);
    471           ZZ_p leadcoeff = LeadCoeff(f1);
    472           //make monic
    473           f1=f1 / LeadCoeff(f1);
    474           // factorize
    475           vec_pair_ZZ_pX_long factors;
    476           CanZass(factors,f1);
    477           // convert back to factory
    478           F=convertNTLvec_pair_ZZpX_long2FacCFFList(factors,leadcoeff,f.mvar());
    479         }
     431    if (f.isUnivariate())
     432    {
     433      #ifdef HAVE_NTL
     434      if (isOn(SW_USE_NTL) && (isPurePoly(f)))
     435      {
     436        // USE NTL
     437        if (getCharacteristic()!=2)
     438        {
     439          if (fac_NTL_char!=getCharacteristic())
     440          {
     441            fac_NTL_char=getCharacteristic();
     442            #ifndef NTL_ZZ
     443            if (fac_NTL_char >NTL_SP_BOUND)
     444            {
     445              ZZ r;
     446              r=getCharacteristic();
     447              ZZ_pContext ccc(r);
     448              ccc.restore();
     449              ZZ_p::init(r);
     450            }
     451            else
     452            #endif
     453            {
     454              #ifdef NTL_ZZ
     455              ZZ r;
     456              r=getCharacteristic();
     457              ZZ_pContext ccc(r);
     458              #else
     459              zz_pContext ccc(getCharacteristic());
     460              #endif
     461              ccc.restore();
     462              #ifdef NTL_ZZ
     463              ZZ_p::init(r);
     464              #else
     465              zz_p::init(getCharacteristic());
     466              #endif
     467            }
     468          }
     469        #ifndef NTL_ZZ
     470        if (fac_NTL_char >NTL_SP_BOUND)
     471        {
     472            // convert to NTL
     473            ZZ_pX f1=convertFacCF2NTLZZpX(f);
     474            ZZ_p leadcoeff = LeadCoeff(f1);
     475            //make monic
     476            f1=f1 / LeadCoeff(f1);
     477            // factorize
     478            vec_pair_ZZ_pX_long factors;
     479            CanZass(factors,f1);
     480            // convert back to factory
     481            F=convertNTLvec_pair_ZZpX_long2FacCFFList(factors,leadcoeff,f.mvar());
     482          }
     483          else
     484          #endif
     485          {
     486            // convert to NTL
     487            #ifdef NTL_ZZ
     488            ZZ_pX f1=convertFacCF2NTLZZpX(f);
     489            ZZ_p leadcoeff = LeadCoeff(f1);
     490            #else
     491            zz_pX f1=convertFacCF2NTLzzpX(f);
     492            zz_p leadcoeff = LeadCoeff(f1);
     493            #endif
     494            //make monic
     495            f1=f1 / LeadCoeff(f1);
     496            // factorize
     497            #ifdef NTL_ZZ
     498            vec_pair_ZZ_pX_long factors;
     499            #else
     500            vec_pair_zz_pX_long factors;
     501            #endif
     502            CanZass(factors,f1);
     503            // convert back to factory
     504            #ifdef NTL_ZZ
     505            F=convertNTLvec_pair_ZZpX_long2FacCFFList(factors,leadcoeff,f.mvar());
     506            #else
     507            F=convertNTLvec_pair_zzpX_long2FacCFFList(factors,leadcoeff,f.mvar());
     508            #endif
     509          }
     510          //test_cff(F,f);
     511        }
     512        else
     513        {
     514          // Specialcase characteristic==2
     515          if (fac_NTL_char!=2)
     516          {
     517            fac_NTL_char=2;
     518            zz_p::init(2);
     519          }
     520          // convert to NTL using the faster conversion routine for characteristic 2
     521          GF2X f1=convertFacCF2NTLGF2X(f);
     522          // no make monic necessary in GF2
     523          //factorize
     524          vec_pair_GF2X_long factors;
     525          CanZass(factors,f1);
     526
     527          // convert back to factory again using the faster conversion routine for vectors over GF2X
     528          F=convertNTLvec_pair_GF2X_long2FacCFFList(factors,LeadCoeff(f1),f.mvar());
     529        }
     530      }
     531      else
     532      #endif
     533      {  // Use Factory without NTL
     534        if ( isOn( SW_BERLEKAMP ) )
     535          F=FpFactorizeUnivariateB( f, issqrfree );
     536        else
     537          F=FpFactorizeUnivariateCZ( f, issqrfree, 0, Variable(), Variable() );
     538      }
     539    }
     540    else
     541    {
     542      #ifdef HAVE_NTL
     543      if (issqrfree)
     544      {
     545        CFList factors;
     546        Variable alpha;
     547        if (CFFactory::gettype() == GaloisFieldDomain)
     548          factors= GFSqrfFactorize (f);
     549        else if (hasFirstAlgVar (f, alpha))
     550          factors= FqSqrfFactorize (f, alpha);
    480551        else
    481         #endif
    482         {
    483           // convert to NTL
    484           #ifdef NTL_ZZ
    485           ZZ_pX f1=convertFacCF2NTLZZpX(f);
    486           ZZ_p leadcoeff = LeadCoeff(f1);
    487           #else
    488           zz_pX f1=convertFacCF2NTLzzpX(f);
    489           zz_p leadcoeff = LeadCoeff(f1);
    490           #endif
    491           //make monic
    492           f1=f1 / LeadCoeff(f1);
    493           // factorize
    494           #ifdef NTL_ZZ
    495           vec_pair_ZZ_pX_long factors;
    496           #else
    497           vec_pair_zz_pX_long factors;
    498           #endif
    499           CanZass(factors,f1);
    500           // convert back to factory
    501           #ifdef NTL_ZZ
    502           F=convertNTLvec_pair_ZZpX_long2FacCFFList(factors,leadcoeff,f.mvar());
    503           #else
    504           F=convertNTLvec_pair_zzpX_long2FacCFFList(factors,leadcoeff,f.mvar());
    505           #endif
    506         }
    507         //test_cff(F,f);
     552          factors= FpSqrfFactorize (f);
     553        for (CFListIterator i= factors; i.hasItem(); i++)
     554          F.append (CFFactor (i.getItem(), 1));
    508555      }
    509556      else
    510557      {
    511         // Specialcase characteristic==2
    512         if (fac_NTL_char!=2)
    513         {
    514           fac_NTL_char=2;
    515           zz_p::init(2);
    516         }
    517         // convert to NTL using the faster conversion routine for characteristic 2
    518         GF2X f1=convertFacCF2NTLGF2X(f);
    519         // no make monic necessary in GF2
    520         //factorize
    521         vec_pair_GF2X_long factors;
    522         CanZass(factors,f1);
    523 
    524         // convert back to factory again using the faster conversion routine for vectors over GF2X
    525         F=convertNTLvec_pair_GF2X_long2FacCFFList(factors,LeadCoeff(f1),f.mvar());
    526       }
    527     }
    528     else
    529     #endif
    530     {  // Use Factory without NTL
    531       if ( isOn( SW_BERLEKAMP ) )
    532          F=FpFactorizeUnivariateB( f, issqrfree );
    533       else
    534         F=FpFactorizeUnivariateCZ( f, issqrfree, 0, Variable(), Variable() );
     558        Variable alpha;
     559        if (CFFactory::gettype() == GaloisFieldDomain)
     560          F= GFFactorize (f);
     561        else if (hasFirstAlgVar (f, alpha))
     562          F= FqFactorize (f, alpha);
     563        else
     564          F= FpFactorize (f);
     565      }
     566      #else
     567      ASSERT( f.isUnivariate(), "multivariate factorization not implemented" );
     568      #endif
    535569    }
    536570  }
    … …  
    641675  CFFList F;
    642676  ASSERT( alpha.level() < 0, "not an algebraic extension" );
    643   ASSERT( f.isUnivariate(), "multivariate factorization not implemented" );
    644677  ASSERT( getCharacteristic() > 0, "char 0 factorization not implemented" );
    645   #ifdef HAVE_NTL
    646   if  (isOn(SW_USE_NTL))
    647   {
    648     //USE NTL
    649     if (getCharacteristic()!=2)
    650     {
    651       // First all cases with characteristic !=2
    652       // set remainder
    653       if (fac_NTL_char!=getCharacteristic())
    654       {
    655         fac_NTL_char=getCharacteristic();
    656         #ifdef NTL_ZZ
    657         ZZ r;
    658         r=getCharacteristic();
    659         ZZ_pContext ccc(r);
    660         #else
    661         zz_pContext ccc(getCharacteristic());
    662         #endif
    663         ccc.restore();
    664         #ifdef NTL_ZZ
    665         ZZ_p::init(r);
    666         #else
    667         zz_p::init(getCharacteristic());
    668         #endif
    669       }
    670 
    671       // set minimal polynomial in NTL
    672       #ifdef NTL_ZZ
    673       ZZ_pX minPo=convertFacCF2NTLZZpX(getMipo(alpha));
    674       ZZ_pEContext c(minPo);
    675       #else
    676       zz_pX minPo=convertFacCF2NTLzzpX(getMipo(alpha));
    677       zz_pEContext c(minPo);
    678       #endif
    679 
    680       c.restore();
    681 
    682       // convert to NTL
    683       #ifdef NTL_ZZ
    684       ZZ_pEX f1=convertFacCF2NTLZZ_pEX(f,minPo);
    685       ZZ_pE leadcoeff= LeadCoeff(f1);
    686       #else
    687       zz_pEX f1=convertFacCF2NTLzz_pEX(f,minPo);
    688       zz_pE leadcoeff= LeadCoeff(f1);
    689       #endif
    690 
    691       //make monic
    692       f1=f1 / leadcoeff;
    693 
    694       // factorize using NTL
    695       #ifdef NTL_ZZ
    696       vec_pair_ZZ_pEX_long factors;
    697       #else
    698       vec_pair_zz_pEX_long factors;
    699       #endif
    700       CanZass(factors,f1);
    701 
    702       // return converted result
    703       F=convertNTLvec_pair_zzpEX_long2FacCFFList(factors,leadcoeff,f.mvar(),alpha);
    704     }
    705     else
    706     {
    707       // special case : GF2
    708 
    709       // remainder is two ==> nothing to do
    710       // set remainder
    711       ZZ r;
    712       r=getCharacteristic();
    713       ZZ_pContext ccc(r);
    714       ccc.restore();
    715 
    716       // set minimal polynomial in NTL using the optimized conversion routines for characteristic 2
    717       GF2X minPo=convertFacCF2NTLGF2X(getMipo(alpha,f.mvar()));
    718       GF2EContext c(minPo);
    719       c.restore();
    720 
    721       // convert to NTL again using the faster conversion routines
    722       GF2EX f1;
    723       if (isPurePoly(f))
    724       {
    725         GF2X f_tmp=convertFacCF2NTLGF2X(f);
    726         f1=to_GF2EX(f_tmp);
     678  if (f.isUnivariate())
     679  {
     680    #ifdef HAVE_NTL
     681    if  (isOn(SW_USE_NTL))
     682    {
     683      //USE NTL
     684      if (getCharacteristic()!=2)
     685      {
     686        // First all cases with characteristic !=2
     687        // set remainder
     688        if (fac_NTL_char!=getCharacteristic())
     689        {
     690          fac_NTL_char=getCharacteristic();
     691          #ifdef NTL_ZZ
     692          ZZ r;
     693          r=getCharacteristic();
     694          ZZ_pContext ccc(r);
     695          #else
     696          zz_pContext ccc(getCharacteristic());
     697          #endif
     698          ccc.restore();
     699          #ifdef NTL_ZZ
     700          ZZ_p::init(r);
     701          #else
     702          zz_p::init(getCharacteristic());
     703          #endif
     704        }
     705
     706        // set minimal polynomial in NTL
     707        #ifdef NTL_ZZ
     708        ZZ_pX minPo=convertFacCF2NTLZZpX(getMipo(alpha));
     709        ZZ_pEContext c(minPo);
     710        #else
     711        zz_pX minPo=convertFacCF2NTLzzpX(getMipo(alpha));
     712        zz_pEContext c(minPo);
     713        #endif
     714
     715        c.restore();
     716
     717        // convert to NTL
     718        #ifdef NTL_ZZ
     719        ZZ_pEX f1=convertFacCF2NTLZZ_pEX(f,minPo);
     720        ZZ_pE leadcoeff= LeadCoeff(f1);
     721        #else
     722        zz_pEX f1=convertFacCF2NTLzz_pEX(f,minPo);
     723        zz_pE leadcoeff= LeadCoeff(f1);
     724        #endif
     725
     726        //make monic
     727        f1=f1 / leadcoeff;
     728
     729        // factorize using NTL
     730        #ifdef NTL_ZZ
     731        vec_pair_ZZ_pEX_long factors;
     732        #else
     733        vec_pair_zz_pEX_long factors;
     734        #endif
     735        CanZass(factors,f1);
     736
     737        // return converted result
     738        F=convertNTLvec_pair_zzpEX_long2FacCFFList(factors,leadcoeff,f.mvar(),alpha);
    727739      }
    728740      else
    729741      {
    730         f1=convertFacCF2NTLGF2EX(f,minPo);
    731       }
    732 
    733       // make monic (in Z/2(a))
    734       GF2E f1_coef=LeadCoeff(f1);
    735       MakeMonic(f1);
    736 
    737       // factorize using NTL
    738       vec_pair_GF2EX_long factors;
    739       CanZass(factors,f1);
    740 
    741       // return converted result
    742       F=convertNTLvec_pair_GF2EX_long2FacCFFList(factors,f1_coef,f.mvar(),alpha);
    743     }
    744 
     742        // special case : GF2
     743
     744        // remainder is two ==> nothing to do
     745        // set remainder
     746        ZZ r;
     747        r=getCharacteristic();
     748        ZZ_pContext ccc(r);
     749        ccc.restore();
     750
     751        // set minimal polynomial in NTL using the optimized conversion routines for characteristic 2
     752        GF2X minPo=convertFacCF2NTLGF2X(getMipo(alpha,f.mvar()));
     753        GF2EContext c(minPo);
     754        c.restore();
     755
     756        // convert to NTL again using the faster conversion routines
     757        GF2EX f1;
     758        if (isPurePoly(f))
     759        {
     760          GF2X f_tmp=convertFacCF2NTLGF2X(f);
     761          f1=to_GF2EX(f_tmp);
     762        }
     763        else
     764        {
     765          f1=convertFacCF2NTLGF2EX(f,minPo);
     766        }
     767
     768        // make monic (in Z/2(a))
     769        GF2E f1_coef=LeadCoeff(f1);
     770        MakeMonic(f1);
     771
     772        // factorize using NTL
     773        vec_pair_GF2EX_long factors;
     774        CanZass(factors,f1);
     775
     776        // return converted result
     777        F=convertNTLvec_pair_GF2EX_long2FacCFFList(factors,f1_coef,f.mvar(),alpha);
     778      }
     779
     780    }
     781    else
     782    #endif
     783    {
     784      F=FpFactorizeUnivariateCZ( f, false, 1, alpha, Variable() );
     785    }
    745786  }
    746787  else
    747   #endif
    748   {
    749     F=FpFactorizeUnivariateCZ( f, false, 1, alpha, Variable() );
     788  {
     789    #ifdef HAVE_NTL
     790    F= FqFactorize (f, alpha);
     791    #else
     792    ASSERT( f.isUnivariate(), "multivariate factorization not implemented" );
     793    #endif
     794   
    750795  }
    751796  return F;
Note: See TracChangeset for help on using the changeset viewer.