Changeset 6e2ef0e in git
 Timestamp:
 Jun 7, 2011, 11:27:14 AM (12 years ago)
 Branches:
 (u'spielwiese', '91fdef05f09f54b8d58d92a472e9c4a43aa4656f')
 Children:
 c1b99270645a77c4bc459b6e4de16489e0a1a56e
 Parents:
 aacb5ac3506ca9207c0dc541708e70838974185c
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

factory/cf_gcd.cc
raacb5a r6e2ef0e 20 20 #include "fieldGCD.h" 21 21 #include "cf_gcd_smallp.h" 22 #include "cf_map_ext.h" 23 #include "cf_util.h" 22 24 23 25 #ifdef HAVE_NTL … … 43 45 int count = 0; 44 46 // assume polys have same level; 45 CFRandom * sample = CFRandomFactory::generate(); 47 48 Variable v= Variable (1); 49 bool algExtension= (hasFirstAlgVar (f, v)  hasFirstAlgVar (g, v)); 50 CanonicalForm lcf, lcg; 51 if ( swap ) 52 { 53 lcf = swapvar( LC( f ), Variable(1), f.mvar() ); 54 lcg = swapvar( LC( g ), Variable(1), f.mvar() ); 55 } 56 else 57 { 58 lcf = LC( f, Variable(1) ); 59 lcg = LC( g, Variable(1) ); 60 } 61 62 CanonicalForm F, G; 63 if ( swap ) 64 { 65 F=swapvar( f, Variable(1), f.mvar() ); 66 G=swapvar( g, Variable(1), g.mvar() ); 67 } 68 else 69 { 70 F = f; 71 G = g; 72 } 73 74 #define TEST_ONE_MAX 50 75 int p= getCharacteristic(); 76 bool passToGF= false; 77 int k= 1; 78 if (p > 0 && p < TEST_ONE_MAX && CFFactory::gettype() != GaloisFieldDomain && !algExtension) 79 { 80 if (p == 2) 81 setCharacteristic (2, 6, 'Z'); 82 else if (p == 3) 83 setCharacteristic (3, 4, 'Z'); 84 else if (p == 5  p == 7) 85 setCharacteristic (p, 3, 'Z'); 86 else 87 setCharacteristic (p, 2, 'Z'); 88 passToGF= true; 89 } 90 else if (p > 0 && CFFactory::gettype() == GaloisFieldDomain && ipower (p , getGFDegree()) < TEST_ONE_MAX) 91 { 92 k= getGFDegree(); 93 if (ipower (p, 2*k) > TEST_ONE_MAX) 94 setCharacteristic (p, 2*k, gf_name); 95 else 96 setCharacteristic (p, 3*k, gf_name); 97 F= GFMapUp (F, k); 98 G= GFMapUp (G, k); 99 lcf= GFMapUp (lcf, k); 100 lcg= GFMapUp (lcg, k); 101 } 102 else if (p > 0 && p < TEST_ONE_MAX && algExtension) 103 { 104 bool extOfExt= false; 105 int d= degree (getMipo (v)); 106 CFList source, dest; 107 Variable v2; 108 CanonicalForm primElem, imPrimElem; 109 if (p == 2 && d < 6) 110 { 111 zz_p::init (p); 112 bool primFail= false; 113 Variable vBuf; 114 primElem= primitiveElement (v, vBuf, primFail); 115 ASSERT (!primFail, "failure in integer factorizer"); 116 if (d < 3) 117 { 118 zz_pX NTLIrredpoly; 119 BuildIrred (NTLIrredpoly, d*3); 120 CanonicalForm newMipo= convertNTLzzpX2CF (NTLIrredpoly, Variable (1)); 121 v2= rootOf (newMipo); 122 } 123 else 124 { 125 zz_pX NTLIrredpoly; 126 BuildIrred (NTLIrredpoly, d*2); 127 CanonicalForm newMipo= convertNTLzzpX2CF (NTLIrredpoly, Variable (1)); 128 v2= rootOf (newMipo); 129 } 130 imPrimElem= mapPrimElem (primElem, v, v2); 131 extOfExt= true; 132 } 133 else if ((p == 3 && d < 4)  ((p == 5  p == 7) && d < 3)) 134 { 135 zz_p::init (p); 136 bool primFail= false; 137 Variable vBuf; 138 primElem= primitiveElement (v, vBuf, primFail); 139 ASSERT (!primFail, "failure in integer factorizer"); 140 zz_pX NTLIrredpoly; 141 BuildIrred (NTLIrredpoly, d*2); 142 CanonicalForm newMipo= convertNTLzzpX2CF (NTLIrredpoly, Variable (1)); 143 v2= rootOf (newMipo); 144 imPrimElem= mapPrimElem (primElem, v, v2); 145 extOfExt= true; 146 } 147 if (extOfExt) 148 { 149 F= mapUp (F, v, v2, primElem, imPrimElem, source, dest); 150 G= mapUp (G, v, v2, primElem, imPrimElem, source, dest); 151 lcf= mapUp (lcf, v, v2, primElem, imPrimElem, source, dest); 152 lcg= mapUp (lcg, v, v2, primElem, imPrimElem, source, dest); 153 v= v2; 154 } 155 } 156 157 CFRandom * sample; 158 if ((!algExtension && p > 0)  p == 0) 159 sample = CFRandomFactory::generate(); 160 else 161 sample = AlgExtRandomF (v).clone(); 162 46 163 REvaluation e( 2, tmax( f.level(), g.level() ), *sample ); 47 164 delete sample; 48 CanonicalForm lcf, lcg; 49 if ( swap ) 50 { 51 lcf = swapvar( LC( f ), Variable(1), f.mvar() ); 52 lcg = swapvar( LC( g ), Variable(1), f.mvar() ); 53 } 54 else 55 { 56 lcf = LC( f, Variable(1) ); 57 lcg = LC( g, Variable(1) ); 58 } 59 #define TEST_ONE_MAX 50 60 while ( ( e( lcf ).isZero()  e( lcg ).isZero() ) && count < TEST_ONE_MAX ) 165 166 if (passToGF) 167 { 168 lcf= lcf.mapinto(); 169 lcg= lcg.mapinto(); 170 } 171 172 CanonicalForm eval1, eval2; 173 if (passToGF) 174 { 175 eval1= e (lcf); 176 eval2= e (lcg); 177 } 178 else 179 { 180 eval1= e (lcf); 181 eval2= e (lcg); 182 } 183 184 while ( ( eval1.isZero()  eval2.isZero() ) && count < TEST_ONE_MAX ) 61 185 { 62 186 e.nextpoint(); 63 187 count++; 64 } 65 if ( count == TEST_ONE_MAX ) 188 eval1= e (lcf); 189 eval2= e (lcg); 190 } 191 if ( count >= TEST_ONE_MAX ) 192 { 193 if (passToGF) 194 setCharacteristic (p); 195 if (k > 1) 196 setCharacteristic (p, k, gf_name); 66 197 return false; 67 CanonicalForm F, G; 68 if ( swap ) 69 { 70 F=swapvar( f, Variable(1), f.mvar() ); 71 G=swapvar( g, Variable(1), g.mvar() ); 72 } 73 else 74 { 75 F = f; 76 G = g; 77 } 78 if ( e(F).taildegree() > 0 && e(G).taildegree() > 0 ) 198 } 199 200 201 if (passToGF) 202 { 203 F= F.mapinto(); 204 G= G.mapinto(); 205 eval1= e (F); 206 eval2= e (G); 207 } 208 else 209 { 210 eval1= e (F); 211 eval2= e (G); 212 } 213 214 if ( eval1.taildegree() > 0 && eval2.taildegree() > 0 ) 215 { 216 if (passToGF) 217 setCharacteristic (p); 218 if (k > 1) 219 setCharacteristic (p, k, gf_name); 79 220 return false; 80 return gcd( e( F ), e( G ) ).degree() < 1; 221 } 222 223 CanonicalForm c= gcd (eval1, eval2); 224 bool result= c.degree() < 1; 225 226 if (passToGF) 227 setCharacteristic (p); 228 if (k > 1) 229 setCharacteristic (p, k, gf_name); 230 return result; 81 231 } 82 232 … … 413 563 else 414 564 bi = 1; 565 int maxNumVars= tmax (getNumVars (pi), getNumVars (pi1)); 566 CanonicalForm oldPi= pi, oldPi1= pi1; 415 567 while ( degree( pi1, v ) > 0 ) 416 568 { 569 if (!(pi.isUnivariate() && pi1.isUnivariate())) 570 { 571 if (size (pi)/maxNumVars > 500  size (pi1)/maxNumVars > 500) 572 { 573 On (SW_USE_FF_MOD_GCD); 574 C *= gcd (oldPi, oldPi1); 575 Off (SW_USE_FF_MOD_GCD); 576 return C; 577 } 578 } 417 579 pi2 = psr( pi, pi1, v ); 418 580 pi2 = pi2 / bi; 419 581 pi = pi1; pi1 = pi2; 582 maxNumVars= tmax (getNumVars (pi), getNumVars (pi1)); 420 583 if ( degree( pi1, v ) > 0 ) 421 584 {
Note: See TracChangeset
for help on using the changeset viewer.