Changeset cd86ac in git for factory/fac_cantzass.cc


Ignore:
Timestamp:
Feb 14, 2003, 4:53:27 PM (20 years ago)
Author:
Hans Schönemann <hannes@…>
Branches:
(u'spielwiese', '0d6b7fcd9813a1ca1ed4220cfa2b104b97a0a003')
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
File:
1 edited

Legend:

Unmodified
Added
Removed

  • 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.