Changeset cd86ac in git


Ignore:
Timestamp:
Feb 14, 2003, 4:53:27 PM (21 years ago)
Author:
Hans Schönemann <hannes@…>
Branches:
(u'spielwiese', '8e0ad00ce244dfd0756200662572aef8402f13d5')
Children:
335eeed94f74c9b1536e445cd619be96c31754b8
Parents:
1048e0ca855f8b8edf41222fdf2dc2413b72cfcc
Message:
* hannes: bugfix
          could not factorize x2+xy+y2 in Fp(a)[x,y], a2+a+1=0
	  added tests in factorize(f,a) (isPurePoly(f,a))
	  added sort option to FpFactorizeUnivariateCZ
	  (NTLconvert.cc cf_factor.cc fac_cantzass.cc)


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

Legend:

Unmodified
Added
Removed

  • factory/NTLconvert.cc

    r1048e0c rcd86ac  
    1 /* $Id: NTLconvert.cc,v 1.6 2003-02-11 16:28:48 Singular Exp $ */
     1/* $Id: NTLconvert.cc,v 1.7 2003-02-14 15:53:26 Singular Exp $ */
    22#include <config.h>
    33
    … …  
    292292}
    293293
    294 static int
    295 NTLcmpCF( const CFFactor & f, const CFFactor & g )
     294int NTLcmpCF( const CFFactor & f, const CFFactor & g )
    296295{
    297296  if (f.exp() > g.exp()) return 1;

  • factory/cf_factor.cc

    r1048e0c rcd86ac  
    11/* emacs edit mode for this file is -*- C++ -*- */
    2 /* $Id: cf_factor.cc,v 1.18 2002-10-24 12:20:04 Singular Exp $ */
     2/* $Id: cf_factor.cc,v 1.19 2003-02-14 15:53:27 Singular Exp $ */
    33
    44//{{{ docu
    … …  
    2929
    3030#include "int_int.h"
    31 #ifdef HAVE_NTL 
     31#ifdef HAVE_NTL
    3232#include "NTLconvert.h"
    3333#endif
    … …  
    9494      {
    9595        printf("+");
    96         if (e==0) printf("1");
    97         else
    98         {
    99           printf("v(%d)",l);
    100           if (e!=1) printf("^%d",e);
     96        if (e==0) printf("1");
     97        else
     98        {
     99          printf("v(%d)",l);
     100          if (e!=1) printf("^%d",e);
    101101        }
    102       } 
     102      }
    103103      else
    104104      {
    105105        out_cf("+(",i.coeff(),")");
    106106        if (e!=0)
    107         {
    108           printf("*v(%d)",l);
    109           if (e!=1) printf("^%d",e);
    110         } 
    111       } 
     107        {
     108          printf("*v(%d)",l);
     109          if (e!=1) printf("^%d",e);
     110        }
     111      }
    112112    }
    113113  }
    … …  
    166166  {
    167167    if (!(i.coeff().inBaseDomain())) return false;
     168  }
     169  return true;
     170}
     171
     172static bool isPurePoly(const CanonicalForm & f, const Variable alpha)
     173{
     174  if (f.level()<=0) return (f.mvar() == alpha);
     175  for (CFIterator i=f;i.hasTerms();i++)
     176  {
     177    if (!(i.coeff().inBaseDomain()))
     178    {
     179      if (f.mvar() != alpha) return false;
     180    }
    168181  }
    169182  return true;
    … …  
    286299            F.insert( CFFactor( ic ) );
    287300        }
    288         else
    289         {
     301        else
     302        {
    290303          if ( !F.getFirst().factor().inCoeffDomain() )
    291304          {
    … …  
    293306            F.insert( new_first );
    294307          }
    295         }
     308        }
    296309        //if ( F.getFirst().factor().isOne() )
    297310        //{
    298311        //  F.removeFirst();
    299312        //}
    300         //printf("NTL:\n");out_cff(F);
    301         //F=ZFactorizeUnivariate( fz, issqrfree );
    302         //printf("fac.:\n");out_cff(F);
     313        //printf("NTL:\n");out_cff(F);
     314        //F=ZFactorizeUnivariate( fz, issqrfree );
     315        //printf("fac.:\n");out_cff(F);
    303316      }
    304317      else
    … …  
    347360  ZZX f1=convertFacCF2NTLZZX(f);
    348361  return convertZZ2CF(coeff(f1,j));
    349 } 
     362}
    350363#endif
    351364
    352365CFFList factorize ( const CanonicalForm & f, const Variable & alpha )
    353366{
    354     CFFList F;
    355     ASSERT( alpha.level() < 0, "not an algebraic extension" );
    356     ASSERT( f.isUnivariate(), "multivariate factorization not implemented" );
    357     ASSERT( getCharacteristic() > 0, "char 0 factorization not implemented" );
    358     #ifdef HAVE_NTL
    359     if  (isOn(SW_USE_NTL))
    360     {
    361       //USE NTL
    362       if (1 ) //getCharacteristic()!=2)
    363       {
    364         // First all cases with characteristic !=2
    365         // set remainder
    366         ZZ r;
    367         r=getCharacteristic();
    368         ZZ_pContext ccc(r);
    369         ccc.restore();
    370 
    371         // set minimal polynomial in NTL
    372         ZZ_pX minPo=convertFacCF2NTLZZpX(getMipo(alpha));
    373         ZZ_pEContext c(minPo);
    374 
    375         c.restore();
    376 
    377         // convert to NTL
    378         ZZ_pEX f1=convertFacCF2NTLZZ_pEX(f,minPo);
    379 
    380         //make monic
    381         ZZ_pE leadcoeff= LeadCoeff(f1);
    382         f1=f1 / leadcoeff;
    383 
    384         // factorize using NTL
    385         vec_pair_ZZ_pEX_long factors;
    386         CanZass(factors,f1);
    387 
    388         // return converted result
    389         F=convertNTLvec_pair_ZZpEX_long2FacCFFList(factors,leadcoeff,f.mvar(),alpha);
    390       }
    391       else
    392       {
    393         // special case : GF2
    394 
    395         // remainder is two ==> nothing to do
    396 
    397         // set minimal polynomial in NTL using the optimized conversion routines for characteristic 2
    398         GF2X minPo=convertFacCF2NTLGF2X(getMipo(alpha,f.mvar()));
    399         GF2EContext c(minPo);
    400         c.restore();
    401 
    402         // convert to NTL again using the faster conversion routines
    403         GF2X f_tmp=convertFacCF2NTLGF2X(f);
    404         GF2EX f1=to_GF2EX(f_tmp);
    405 
    406         // no make monic necessary in GF2
    407 
    408         // factorize using NTL
    409         vec_pair_GF2EX_long factors;
    410         CanZass(factors,f1);
    411 
    412         // return converted result
    413         F=convertNTLvec_pair_GF2EX_long2FacCFFList(factors,LeadCoeff(f1),f.mvar(),alpha);
    414       }
    415 
    416     }
    417     else
    418     #endif
    419     {
    420       F=FpFactorizeUnivariateCZ( f, false, 1, alpha, Variable() );
    421     }
    422     return F;
     367  //out_cf("factorize:",f,"==================================\n");
     368  //out_cf("mipo:",getMipo(alpha),"\n");
     369  CFFList F;
     370  ASSERT( alpha.level() < 0, "not an algebraic extension" );
     371  ASSERT( f.isUnivariate(), "multivariate factorization not implemented" );
     372  ASSERT( getCharacteristic() > 0, "char 0 factorization not implemented" );
     373  #ifdef HAVE_NTL
     374  //if  (isOn(SW_USE_NTL))
     375  if (isOn(SW_USE_NTL) && (isPurePoly(f,alpha)))
     376  {
     377    //USE NTL
     378    if (getCharacteristic()!=2)
     379    {
     380      // First all cases with characteristic !=2
     381      // set remainder
     382      ZZ r;
     383      r=getCharacteristic();
     384      ZZ_pContext ccc(r);
     385      ccc.restore();
     386
     387      // set minimal polynomial in NTL
     388      ZZ_pX minPo=convertFacCF2NTLZZpX(getMipo(alpha));
     389      ZZ_pEContext c(minPo);
     390
     391      c.restore();
     392
     393      // convert to NTL
     394      ZZ_pEX f1=convertFacCF2NTLZZ_pEX(f,minPo);
     395
     396      //make monic
     397      ZZ_pE leadcoeff= LeadCoeff(f1);
     398      f1=f1 / leadcoeff;
     399
     400      // factorize using NTL
     401      vec_pair_ZZ_pEX_long factors;
     402      CanZass(factors,f1);
     403
     404      // return converted result
     405      F=convertNTLvec_pair_ZZpEX_long2FacCFFList(factors,leadcoeff,f.mvar(),alpha);
     406    }
     407    else
     408    {
     409      // special case : GF2
     410
     411      // remainder is two ==> nothing to do
     412
     413      // set minimal polynomial in NTL using the optimized conversion routines for characteristic 2
     414      GF2X minPo=convertFacCF2NTLGF2X(getMipo(alpha,f.mvar()));
     415      GF2EContext c(minPo);
     416      c.restore();
     417
     418      // convert to NTL again using the faster conversion routines
     419      GF2X f_tmp=convertFacCF2NTLGF2X(f);
     420      GF2EX f1=to_GF2EX(f_tmp);
     421
     422      // no make monic necessary in GF2
     423
     424      // factorize using NTL
     425      vec_pair_GF2EX_long factors;
     426      CanZass(factors,f1);
     427
     428      // return converted result
     429      F=convertNTLvec_pair_GF2EX_long2FacCFFList(factors,LeadCoeff(f1),f.mvar(),alpha);
     430    }
     431
     432  }
     433  else
     434  #endif
     435  {
     436    F=FpFactorizeUnivariateCZ( f, false, 1, alpha, Variable() );
     437  }
     438  return F;
    423439}
    424440

  • factory/fac_cantzass.cc

    r1048e0c rcd86ac  
    11/* emacs edit mode for this file is -*- C++ -*- */
    2 /* $Id: fac_cantzass.cc,v 1.5 1998-05-11 09:37:40 schmidt Exp $ */
     2/* $Id: fac_cantzass.cc,v 1.6 2003-02-14 15:53:27 Singular Exp $ */
    33
    44#include <config.h>
    … …  
    5353
    5454    if ( galoisfield )
    55         q = ipower( getCharacteristic(), getGFDegree() );
     55        q = ipower( getCharacteristic(), getGFDegree() );
    5656    else
    57         q = getCharacteristic();
     57        q = getCharacteristic();
    5858    if ( numext > 0 ) {
    59         if ( numext == 1 )
    60             n = getMipo( alpha ).degree();
    61         else
    62             n = getMipo( alpha ).degree() * getMipo( beta ).degree();
    63         mpz_init( &qq );
    64         mpz_mypow_ui( &qq, q, n );
     59        if ( numext == 1 )
     60            n = getMipo( alpha ).degree();
     61        else
     62            n = getMipo( alpha ).degree() * getMipo( beta ).degree();
     63        mpz_init( &qq );
     64        mpz_mypow_ui( &qq, q, n );
    6565    }
    6666    if ( LC( f ).isOne() )
    67         if ( issqrfree )
    68             F.append( CFFactor( f, 1 ) );
    69         else
    70             F = sqrFreeFp( f );
     67        if ( issqrfree )
     68            F.append( CFFactor( f, 1 ) );
     69        else
     70            F = sqrFreeFp( f );
    7171    else {
    72         if ( issqrfree )
    73             F.append( CFFactor( f / LC( f ), 1 ) );
    74         else
    75             F = sqrFreeFp( f / LC( f ) );
    76         H.append( LC( f ) );
     72        if ( issqrfree )
     73            F.append( CFFactor( f / LC( f ), 1 ) );
     74        else
     75            F = sqrFreeFp( f / LC( f ) );
     76        H.append( LC( f ) );
    7777    }
    7878    for ( i = F; i.hasItem(); ++i ) {
    79         d = i.getItem().exp();
    80         if ( numext > 0 )
    81             G = distinctDegreeFactorExt( i.getItem().factor(), q, n );
    82         else
    83             G = distinctDegreeFactorFFGF( i.getItem().factor(), q );
    84         for ( j = G; j.hasItem(); ++j ) {
    85             if ( numext > 0 ) {
    86                 if ( numext == 1 )
    87                     HH = CantorZassenhausFactorExt( j.getItem().factor(), j.getItem().exp(), &qq, AlgExtRandomF( alpha ) );
    88                 else
    89                     HH = CantorZassenhausFactorExt( j.getItem().factor(), j.getItem().exp(), &qq, AlgExtRandomF( alpha, beta ) );
    90             }
    91             else  if ( galoisfield )
    92                 HH = CantorZassenhausFactorFFGF( j.getItem().factor(), j.getItem().exp(), q, GFRandom() );
    93             else
    94                 HH = CantorZassenhausFactorFFGF( j.getItem().factor(), j.getItem().exp(), q, FFRandom() );
    95             for ( k = HH; k.hasItem(); ++k ) {
    96                 fac = k.getItem().factor();
    97                 H.append( CFFactor( fac / LC( fac ), d ) );
    98             }
    99         }
     79        d = i.getItem().exp();
     80        if ( numext > 0 )
     81            G = distinctDegreeFactorExt( i.getItem().factor(), q, n );
     82        else
     83            G = distinctDegreeFactorFFGF( i.getItem().factor(), q );
     84        for ( j = G; j.hasItem(); ++j ) {
     85            if ( numext > 0 ) {
     86                if ( numext == 1 )
     87                    HH = CantorZassenhausFactorExt( j.getItem().factor(), j.getItem().exp(), &qq, AlgExtRandomF( alpha ) );
     88                else
     89                    HH = CantorZassenhausFactorExt( j.getItem().factor(), j.getItem().exp(), &qq, AlgExtRandomF( alpha, beta ) );
     90            }
     91            else  if ( galoisfield )
     92                HH = CantorZassenhausFactorFFGF( j.getItem().factor(), j.getItem().exp(), q, GFRandom() );
     93            else
     94                HH = CantorZassenhausFactorFFGF( j.getItem().factor(), j.getItem().exp(), q, FFRandom() );
     95            for ( k = HH; k.hasItem(); ++k ) {
     96                fac = k.getItem().factor();
     97                H.append( CFFactor( fac / LC( fac ), d ) );
     98            }
     99        }
    100100    }
    101101    if ( numext > 0 )
    102         mpz_clear( &qq );
     102        mpz_clear( &qq );
     103#ifdef HAVE_NTL
     104    extern  int NTLcmpCF( const CFFactor & f, const CFFactor & g );
     105    if(isOn(SW_USE_NTL_SORT)) H.sort(NTLcmpCF);
     106#endif   
    103107    return H;
    104108}
    … …  
    112116    i = 1;
    113117    while ( g.degree(x) > 0 && i <= g.degree(x) ) {
    114         r = powerMod( r, q, g );
    115         h = gcd( g, r - x );
    116         if ( h.degree(x) > 0 ) {
    117             F.append( CFFactor( h, i ) );
    118             g /= h;
    119         }
    120         i++;
     118        r = powerMod( r, q, g );
     119        h = gcd( g, r - x );
     120        if ( h.degree(x) > 0 ) {
     121            F.append( CFFactor( h, i ) );
     122            g /= h;
     123        }
     124        i++;
    121125    }
    122126    ASSERT( g.degree(x) == 0, "fatal fatal" );
    … …  
    132136    i = 1;
    133137    while ( g.degree(x) > 0 && i <= g.degree(x) ) {
    134         r = powerMod( r, p, n, g );
    135         h = gcd( g, r - x );
    136         if ( h.degree(x) > 0 ) {
    137             F.append( CFFactor( h, i ) );
    138             g /= h;
    139         }
    140         i++;
     138        r = powerMod( r, p, n, g );
     139        h = gcd( g, r - x );
     140        if ( h.degree(x) > 0 ) {
     141            F.append( CFFactor( h, i ) );
     142            g /= h;
     143        }
     144        i++;
    141145    }
    142146    ASSERT( g.degree(x) == 0, "fatal fatal" );
    … …  
    152156
    153157    if ( (d=f.degree(x)) == s )
    154         return CFFactor( f, 1 );
     158        return CFFactor( f, 1 );
    155159    else while ( 1 ) {
    156         b = randomPoly( d, x, gen );
    157         f1 = gcd( b, f );
    158         if ( (d1 = f1.degree(x)) > 0 && d1 < d ) {
    159             CFFList firstFactor = CantorZassenhausFactorFFGF( f1, s, q, gen );
    160             CFFList secondFactor = CantorZassenhausFactorFFGF( f/f1, s, q, gen );
    161             return Union( firstFactor, secondFactor );
    162         } else {
    163             f1 = gcd( f, powerMod2( b, q, s, f ) - 1 );
    164             if ( (d1 = f1.degree(x)) > 0 && d1 < d ) {
    165                 CFFList firstFactor = CantorZassenhausFactorFFGF( f1, s, q, gen );
    166                 CFFList secondFactor = CantorZassenhausFactorFFGF( f/f1, s, q, gen );
    167                 return Union( firstFactor, secondFactor );
    168             }
    169         }
     160        b = randomPoly( d, x, gen );
     161        f1 = gcd( b, f );
     162        if ( (d1 = f1.degree(x)) > 0 && d1 < d ) {
     163            CFFList firstFactor = CantorZassenhausFactorFFGF( f1, s, q, gen );
     164            CFFList secondFactor = CantorZassenhausFactorFFGF( f/f1, s, q, gen );
     165            return Union( firstFactor, secondFactor );
     166        } else {
     167            f1 = gcd( f, powerMod2( b, q, s, f ) - 1 );
     168            if ( (d1 = f1.degree(x)) > 0 && d1 < d ) {
     169                CFFList firstFactor = CantorZassenhausFactorFFGF( f1, s, q, gen );
     170                CFFList secondFactor = CantorZassenhausFactorFFGF( f/f1, s, q, gen );
     171                return Union( firstFactor, secondFactor );
     172            }
     173        }
    170174    }
    171175}
    … …  
    179183
    180184    if ( (d=f.degree(x)) == s )
    181         return CFFactor( f, 1 );
     185        return CFFactor( f, 1 );
    182186    else while ( 1 ) {
    183         b = randomPoly( d, x, gen );
    184         f1 = gcd( b, f );
    185         if ( (d1 = f1.degree(x)) > 0 && d1 < d ) {
    186             CFFList firstFactor = CantorZassenhausFactorExt( f1, s, q, gen );
    187             CFFList secondFactor = CantorZassenhausFactorExt( f/f1, s, q, gen );
    188             return Union( firstFactor, secondFactor );
    189         } else {
    190             f1 = gcd( f, powerMod2( b, q, s, f ) - 1 );
    191             if ( (d1 = f1.degree(x)) > 0 && d1 < d ) {
    192                 CFFList firstFactor = CantorZassenhausFactorExt( f1, s, q, gen );
    193                 CFFList secondFactor = CantorZassenhausFactorExt( f/f1, s, q, gen );
    194                 return Union( firstFactor, secondFactor );
    195             }
    196         }
     187        b = randomPoly( d, x, gen );
     188        f1 = gcd( b, f );
     189        if ( (d1 = f1.degree(x)) > 0 && d1 < d ) {
     190            CFFList firstFactor = CantorZassenhausFactorExt( f1, s, q, gen );
     191            CFFList secondFactor = CantorZassenhausFactorExt( f/f1, s, q, gen );
     192            return Union( firstFactor, secondFactor );
     193        } else {
     194            f1 = gcd( f, powerMod2( b, q, s, f ) - 1 );
     195            if ( (d1 = f1.degree(x)) > 0 && d1 < d ) {
     196                CFFList firstFactor = CantorZassenhausFactorExt( f1, s, q, gen );
     197                CFFList secondFactor = CantorZassenhausFactorExt( f/f1, s, q, gen );
     198                return Union( firstFactor, secondFactor );
     199            }
     200        }
    197201    }
    198202}
    … …  
    202206    CanonicalForm result = 0;
    203207    for ( int i = 0; i < d; i++ )
    204         result += power( x, i ) * g.generate();
     208        result += power( x, i ) * g.generate();
    205209    result += power( x, d );
    206210    return result;
    … …  
    213217
    214218    while ( m != 0 ) {
    215         if ( m % 2 != 0 )
    216             prod = (prod * b) % d;
    217         m /= 2;
    218         if ( m != 0 )
    219             b = (b * b) % d;
     219        if ( m % 2 != 0 )
     220            prod = (prod * b) % d;
     221        m /= 2;
     222        if ( m != 0 )
     223            b = (b * b) % d;
    220224    }
    221225    return prod;
    … …  
    233237    mpz_mypow_ui( &m, p, s );
    234238    while ( mpz_cmp_si( &m, 0 ) != 0 ) {
    235         odd = mpz_mdivmod_ui( &m, 0, &m, 2 );
    236         if ( odd != 0 )
    237             prod = (prod * b) % d;
    238         if ( mpz_cmp_si( &m, 0 ) != 0 )
    239             b = (b*b) % d;
     239        odd = mpz_mdivmod_ui( &m, 0, &m, 2 );
     240        if ( odd != 0 )
     241            prod = (prod * b) % d;
     242        if ( mpz_cmp_si( &m, 0 ) != 0 )
     243            b = (b*b) % d;
    240244    }
    241245    mpz_clear( &m );
    … …  
    256260    mpz_div_ui( &m, &m, 2 );
    257261    while ( mpz_cmp_si( &m, 0 ) != 0 ) {
    258         odd = mpz_mdivmod_ui( &m, 0, &m, 2 );
    259         if ( odd != 0 )
    260             prod = (prod * b) % d;
    261         if ( mpz_cmp_si( &m, 0 ) != 0 )
    262             b = (b*b) % d;
     262        odd = mpz_mdivmod_ui( &m, 0, &m, 2 );
     263        if ( odd != 0 )
     264            prod = (prod * b) % d;
     265        if ( mpz_cmp_si( &m, 0 ) != 0 )
     266            b = (b*b) % d;
    263267    }
    264268    mpz_clear( &m );
    … …  
    279283    mpz_div_ui( &m, &m, 2 );
    280284    while ( mpz_cmp_si( &m, 0 ) != 0 ) {
    281         odd = mpz_mdivmod_ui( &m, 0, &m, 2 );
    282         if ( odd != 0 )
    283             prod = (prod * b) % d;
    284         if ( mpz_cmp_si( &m, 0 ) != 0 )
    285             b = (b*b) % d;
     285        odd = mpz_mdivmod_ui( &m, 0, &m, 2 );
     286        if ( odd != 0 )
     287            prod = (prod * b) % d;
     288        if ( mpz_cmp_si( &m, 0 ) != 0 )
     289            b = (b*b) % d;
    286290    }
    287291    mpz_clear( &m );
Note: See TracChangeset for help on using the changeset viewer.