Changeset cd86ac in git for factory/fac_cantzass.cc
 Timestamp:
 Feb 14, 2003, 4:53:27 PM (20 years ago)
 Branches:
 (u'spielwiese', '0d6b7fcd9813a1ca1ed4220cfa2b104b97a0a003')
 Children:
 335eeed94f74c9b1536e445cd619be96c31754b8
 Parents:
 1048e0ca855f8b8edf41222fdf2dc2413b72cfcc
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

factory/fac_cantzass.cc
r1048e0c rcd86ac 1 1 /* emacs edit mode for this file is * C++ * */ 2 /* $Id: fac_cantzass.cc,v 1. 5 19980511 09:37:40 schmidtExp $ */2 /* $Id: fac_cantzass.cc,v 1.6 20030214 15:53:27 Singular Exp $ */ 3 3 4 4 #include <config.h> … … 53 53 54 54 if ( galoisfield ) 55 55 q = ipower( getCharacteristic(), getGFDegree() ); 56 56 else 57 57 q = getCharacteristic(); 58 58 if ( numext > 0 ) { 59 60 61 62 63 64 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 ); 65 65 } 66 66 if ( LC( f ).isOne() ) 67 68 69 70 67 if ( issqrfree ) 68 F.append( CFFactor( f, 1 ) ); 69 else 70 F = sqrFreeFp( f ); 71 71 else { 72 73 74 75 76 72 if ( issqrfree ) 73 F.append( CFFactor( f / LC( f ), 1 ) ); 74 else 75 F = sqrFreeFp( f / LC( f ) ); 76 H.append( LC( f ) ); 77 77 } 78 78 for ( i = F; i.hasItem(); ++i ) { 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 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 } 100 100 } 101 101 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 103 107 return H; 104 108 } … … 112 116 i = 1; 113 117 while ( g.degree(x) > 0 && i <= g.degree(x) ) { 114 115 116 117 118 119 120 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++; 121 125 } 122 126 ASSERT( g.degree(x) == 0, "fatal fatal" ); … … 132 136 i = 1; 133 137 while ( g.degree(x) > 0 && i <= g.degree(x) ) { 134 135 136 137 138 139 140 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++; 141 145 } 142 146 ASSERT( g.degree(x) == 0, "fatal fatal" ); … … 152 156 153 157 if ( (d=f.degree(x)) == s ) 154 158 return CFFactor( f, 1 ); 155 159 else while ( 1 ) { 156 157 158 159 160 161 162 163 164 165 166 167 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 } 170 174 } 171 175 } … … 179 183 180 184 if ( (d=f.degree(x)) == s ) 181 185 return CFFactor( f, 1 ); 182 186 else while ( 1 ) { 183 184 185 186 187 188 189 190 191 192 193 194 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 } 197 201 } 198 202 } … … 202 206 CanonicalForm result = 0; 203 207 for ( int i = 0; i < d; i++ ) 204 208 result += power( x, i ) * g.generate(); 205 209 result += power( x, d ); 206 210 return result; … … 213 217 214 218 while ( m != 0 ) { 215 216 217 218 219 219 if ( m % 2 != 0 ) 220 prod = (prod * b) % d; 221 m /= 2; 222 if ( m != 0 ) 223 b = (b * b) % d; 220 224 } 221 225 return prod; … … 233 237 mpz_mypow_ui( &m, p, s ); 234 238 while ( mpz_cmp_si( &m, 0 ) != 0 ) { 235 236 237 238 239 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; 240 244 } 241 245 mpz_clear( &m ); … … 256 260 mpz_div_ui( &m, &m, 2 ); 257 261 while ( mpz_cmp_si( &m, 0 ) != 0 ) { 258 259 260 261 262 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; 263 267 } 264 268 mpz_clear( &m ); … … 279 283 mpz_div_ui( &m, &m, 2 ); 280 284 while ( mpz_cmp_si( &m, 0 ) != 0 ) { 281 282 283 284 285 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; 286 290 } 287 291 mpz_clear( &m );
Note: See TracChangeset
for help on using the changeset viewer.