Changeset cd86ac in git
 Timestamp:
 Feb 14, 2003, 4:53:27 PM (21 years ago)
 Branches:
 (u'spielwiese', '8e0ad00ce244dfd0756200662572aef8402f13d5')
 Children:
 335eeed94f74c9b1536e445cd619be96c31754b8
 Parents:
 1048e0ca855f8b8edf41222fdf2dc2413b72cfcc
 Location:
 factory
 Files:

 3 edited
Legend:
 Unmodified
 Added
 Removed

factory/NTLconvert.cc
r1048e0c rcd86ac 1 /* $Id: NTLconvert.cc,v 1. 6 20030211 16:28:48Singular Exp $ */1 /* $Id: NTLconvert.cc,v 1.7 20030214 15:53:26 Singular Exp $ */ 2 2 #include <config.h> 3 3 … … 292 292 } 293 293 294 static int 295 NTLcmpCF( const CFFactor & f, const CFFactor & g ) 294 int NTLcmpCF( const CFFactor & f, const CFFactor & g ) 296 295 { 297 296 if (f.exp() > g.exp()) return 1; 
factory/cf_factor.cc
r1048e0c rcd86ac 1 1 /* emacs edit mode for this file is * C++ * */ 2 /* $Id: cf_factor.cc,v 1.1 8 20021024 12:20:04Singular Exp $ */2 /* $Id: cf_factor.cc,v 1.19 20030214 15:53:27 Singular Exp $ */ 3 3 4 4 //{{{ docu … … 29 29 30 30 #include "int_int.h" 31 #ifdef HAVE_NTL 31 #ifdef HAVE_NTL 32 32 #include "NTLconvert.h" 33 33 #endif … … 94 94 { 95 95 printf("+"); 96 97 else 98 99 100 96 if (e==0) printf("1"); 97 else 98 { 99 printf("v(%d)",l); 100 if (e!=1) printf("^%d",e); 101 101 } 102 } 102 } 103 103 else 104 104 { 105 105 out_cf("+(",i.coeff(),")"); 106 106 if (e!=0) 107 108 109 110 } 111 } 107 { 108 printf("*v(%d)",l); 109 if (e!=1) printf("^%d",e); 110 } 111 } 112 112 } 113 113 } … … 166 166 { 167 167 if (!(i.coeff().inBaseDomain())) return false; 168 } 169 return true; 170 } 171 172 static 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 } 168 181 } 169 182 return true; … … 286 299 F.insert( CFFactor( ic ) ); 287 300 } 288 289 301 else 302 { 290 303 if ( !F.getFirst().factor().inCoeffDomain() ) 291 304 { … … 293 306 F.insert( new_first ); 294 307 } 295 308 } 296 309 //if ( F.getFirst().factor().isOne() ) 297 310 //{ 298 311 // F.removeFirst(); 299 312 //} 300 301 302 313 //printf("NTL:\n");out_cff(F); 314 //F=ZFactorizeUnivariate( fz, issqrfree ); 315 //printf("fac.:\n");out_cff(F); 303 316 } 304 317 else … … 347 360 ZZX f1=convertFacCF2NTLZZX(f); 348 361 return convertZZ2CF(coeff(f1,j)); 349 } 362 } 350 363 #endif 351 364 352 365 CFFList factorize ( const CanonicalForm & f, const Variable & alpha ) 353 366 { 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; 423 439 } 424 440 
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.