[493c477] | 1 | /* emacs edit mode for this file is -*- C++ -*- */ |
---|
[76a7114] | 2 | /* $Id: fac_ezgcd.cc,v 1.26 2006-01-30 09:06:18 pohl Exp $ */ |
---|
[c1c3693] | 3 | |
---|
[b973c0] | 4 | #include <config.h> |
---|
| 5 | |
---|
[c1c3693] | 6 | #include "assert.h" |
---|
[0b61044] | 7 | #include "debug.h" |
---|
| 8 | |
---|
[c1c3693] | 9 | #include "cf_defs.h" |
---|
| 10 | #include "canonicalform.h" |
---|
| 11 | #include "fac_util.h" |
---|
[6746a4] | 12 | #include "cf_algorithm.h" |
---|
[c1c3693] | 13 | #include "cf_reval.h" |
---|
| 14 | #include "cf_random.h" |
---|
| 15 | #include "cf_primes.h" |
---|
| 16 | #include "fac_distrib.h" |
---|
[71da5e] | 17 | #include "ftmpl_functions.h" |
---|
[c1c3693] | 18 | |
---|
| 19 | static void findeval( const CanonicalForm & F, const CanonicalForm & G, CanonicalForm & Fb, CanonicalForm & Gb, CanonicalForm & Db, REvaluation & b, int delta, int degF, int degG ); |
---|
| 20 | |
---|
| 21 | static CanonicalForm ezgcd ( const CanonicalForm & FF, const CanonicalForm & GG, REvaluation & b, bool internal ); |
---|
| 22 | |
---|
| 23 | static CanonicalForm ezgcd_specialcase ( const CanonicalForm & F, const CanonicalForm & G, REvaluation & b, const modpk & bound ); |
---|
| 24 | |
---|
| 25 | static modpk findBound ( const CanonicalForm & F, const CanonicalForm & G, const CanonicalForm & lcF, const CanonicalForm & lcG, int degF, int degG ); |
---|
| 26 | |
---|
| 27 | static modpk enlargeBound ( const CanonicalForm & F, const CanonicalForm & Lb, const CanonicalForm & Db, const modpk & pk ); |
---|
| 28 | |
---|
| 29 | CanonicalForm |
---|
| 30 | ezgcd ( const CanonicalForm & FF, const CanonicalForm & GG ) |
---|
| 31 | { |
---|
| 32 | REvaluation b; |
---|
| 33 | return ezgcd( FF, GG, b, false ); |
---|
| 34 | } |
---|
| 35 | |
---|
| 36 | static CanonicalForm |
---|
| 37 | ezgcd ( const CanonicalForm & FF, const CanonicalForm & GG, REvaluation & b, bool internal ) |
---|
| 38 | { |
---|
| 39 | CanonicalForm F, G, f, g, d, Fb, Gb, Db, Fbt, Gbt, Dbt, B0, B, D0, lcF, lcG, lcD; |
---|
| 40 | CFArray DD( 1, 2 ), lcDD( 1, 2 ); |
---|
[e22ea7] | 41 | int degF, degG, delta, t; |
---|
[c1c3693] | 42 | REvaluation bt; |
---|
| 43 | bool gcdfound = false; |
---|
| 44 | Variable x = Variable(1); |
---|
| 45 | modpk bound; |
---|
| 46 | |
---|
| 47 | DEBINCLEVEL( cerr, "ezgcd" ); |
---|
[d81ed62] | 48 | DEBOUTLN( cerr, "FF = " << FF ); |
---|
| 49 | DEBOUTLN( cerr, "GG = " << GG ); |
---|
[c1c3693] | 50 | f = content( FF, x ); g = content( GG, x ); d = gcd( f, g ); |
---|
[d81ed62] | 51 | DEBOUTLN( cerr, "f = " << f ); |
---|
| 52 | DEBOUTLN( cerr, "g = " << g ); |
---|
[c1c3693] | 53 | F = FF / f; G = GG / g; |
---|
| 54 | if ( F.isUnivariate() && G.isUnivariate() ) |
---|
[e22ea7] | 55 | { |
---|
| 56 | DEBDECLEVEL( cerr, "ezgcd" ); |
---|
[661ca5e] | 57 | if(F.mvar()==G.mvar()) |
---|
| 58 | d*=gcd(F,G); |
---|
| 59 | return d; |
---|
[e22ea7] | 60 | } |
---|
[c1c3693] | 61 | else if ( gcd_test_one( F, G, false ) ) |
---|
[e22ea7] | 62 | { |
---|
| 63 | DEBDECLEVEL( cerr, "ezgcd" ); |
---|
[4e6908] | 64 | return d; |
---|
[e22ea7] | 65 | } |
---|
[c1c3693] | 66 | lcF = LC( F, x ); lcG = LC( G, x ); |
---|
| 67 | lcD = gcd( lcF, lcG ); |
---|
| 68 | delta = 0; |
---|
| 69 | degF = degree( F, x ); degG = degree( G, x ); |
---|
| 70 | t = tmax( F.level(), G.level() ); |
---|
| 71 | bound = findBound( F, G, lcF, lcG, degF, degG ); |
---|
| 72 | if ( ! internal ) |
---|
[afd067] | 73 | b = REvaluation( 2, t, IntRandom( 25 ) ); |
---|
[c1c3693] | 74 | while ( ! gcdfound ) { |
---|
[4e6908] | 75 | /// ---> A2 |
---|
| 76 | DEBOUTLN( cerr, "search for evaluation, delta = " << delta ); |
---|
| 77 | DEBOUTLN( cerr, "F = " << F ); |
---|
| 78 | DEBOUTLN( cerr, "G = " << G ); |
---|
| 79 | findeval( F, G, Fb, Gb, Db, b, delta, degF, degG ); |
---|
| 80 | DEBOUTLN( cerr, "found evaluation b = " << b ); |
---|
| 81 | DEBOUTLN( cerr, "F(b) = " << Fb ); |
---|
| 82 | DEBOUTLN( cerr, "G(b) = " << Gb ); |
---|
| 83 | DEBOUTLN( cerr, "D(b) = " << Db ); |
---|
| 84 | delta = degree( Db ); |
---|
| 85 | /// ---> A3 |
---|
| 86 | if ( delta == 0 ) |
---|
[afd067] | 87 | { |
---|
[e22ea7] | 88 | DEBDECLEVEL( cerr, "ezgcd" ); |
---|
| 89 | return d; |
---|
[afd067] | 90 | } |
---|
[4e6908] | 91 | /// ---> A4 |
---|
[e22ea7] | 92 | //deltaold = delta; |
---|
| 93 | while ( 1 ) { |
---|
[4e6908] | 94 | bt = b; |
---|
| 95 | findeval( F, G, Fbt, Gbt, Dbt, bt, delta + 1, degF, degG ); |
---|
[afd067] | 96 | int dd=degree( Dbt ); |
---|
[e22ea7] | 97 | if ( dd /*degree( Dbt )*/ == 0 ) |
---|
[afd067] | 98 | { |
---|
[e22ea7] | 99 | DEBDECLEVEL( cerr, "ezgcd" ); |
---|
[4e6908] | 100 | return d; |
---|
[afd067] | 101 | } |
---|
[e22ea7] | 102 | if ( dd /*degree( Dbt )*/ == delta ) |
---|
| 103 | break; |
---|
| 104 | else if ( dd /*degree( Dbt )*/ < delta ) { |
---|
| 105 | delta = dd /*degree( Dbt )*/; |
---|
[4e6908] | 106 | b = bt; |
---|
| 107 | Db = Dbt; Fb = Fbt; Gb = Gbt; |
---|
| 108 | } |
---|
| 109 | } |
---|
| 110 | DEBOUTLN( cerr, "now after A4, delta = " << delta ); |
---|
| 111 | /// ---> A5 |
---|
| 112 | if ( degF <= degG && delta == degF && divides( F, G ) ) |
---|
[e22ea7] | 113 | { |
---|
| 114 | DEBDECLEVEL( cerr, "ezgcd" ); |
---|
[4e6908] | 115 | return d*F; |
---|
[afd067] | 116 | } |
---|
[4e6908] | 117 | if ( degG < degF && delta == degG && divides( G, F ) ) |
---|
[e22ea7] | 118 | { |
---|
| 119 | DEBDECLEVEL( cerr, "ezgcd" ); |
---|
[4e6908] | 120 | return d*G; |
---|
[afd067] | 121 | } |
---|
[4e6908] | 122 | if ( delta != degF && delta != degG ) { |
---|
[bde566] | 123 | bool B_is_F; |
---|
[4e6908] | 124 | /// ---> A6 |
---|
| 125 | CanonicalForm xxx; |
---|
| 126 | //if ( gcd( (DD[1] = Fb / Db), Db ) == 1 ) { |
---|
[33d8725] | 127 | DD[1] = Fb / Db; |
---|
[afd067] | 128 | xxx= gcd( DD[1], Db ); |
---|
[33d8725] | 129 | DEBOUTLN( cerr, "gcd((Fb/Db),Db) = " << xxx ); |
---|
| 130 | DEBOUTLN( cerr, "Fb/Db = " << DD[1] ); |
---|
| 131 | DEBOUTLN( cerr, "Db = " << Db ); |
---|
[afd067] | 132 | if (xxx.inCoeffDomain()) { |
---|
[4e6908] | 133 | B = F; |
---|
| 134 | DD[2] = Db; |
---|
| 135 | lcDD[1] = lcF; |
---|
| 136 | lcDD[2] = lcF; |
---|
| 137 | B *= lcF; |
---|
[bde566] | 138 | B_is_F=true; |
---|
[4e6908] | 139 | } |
---|
| 140 | //else if ( gcd( (DD[1] = Gb / Db), Db ) == 1 ) { |
---|
[afd067] | 141 | else |
---|
| 142 | { |
---|
[33d8725] | 143 | DD[1] = Gb / Db; |
---|
[afd067] | 144 | xxx=gcd( DD[1], Db ); |
---|
[33d8725] | 145 | DEBOUTLN( cerr, "gcd((Gb/Db),Db) = " << xxx ); |
---|
| 146 | DEBOUTLN( cerr, "Gb/Db = " << DD[1] ); |
---|
| 147 | DEBOUTLN( cerr, "Db = " << Db ); |
---|
[afd067] | 148 | if (xxx.inCoeffDomain()) |
---|
[33d8725] | 149 | { |
---|
[4e6908] | 150 | B = G; |
---|
| 151 | DD[2] = Db; |
---|
| 152 | lcDD[1] = lcG; |
---|
| 153 | lcDD[2] = lcG; |
---|
| 154 | B *= lcG; |
---|
[bde566] | 155 | B_is_F=false; |
---|
[33d8725] | 156 | } |
---|
| 157 | else |
---|
| 158 | { |
---|
[c1c3693] | 159 | #ifdef DEBUGOUTPUT |
---|
[4e6908] | 160 | CanonicalForm dummyres = d * ezgcd_specialcase( F, G, b, bound ); |
---|
| 161 | DEBDECLEVEL( cerr, "ezgcd" ); |
---|
| 162 | return dummyres; |
---|
[c1c3693] | 163 | #else |
---|
[4e6908] | 164 | return d * ezgcd_specialcase( F, G, b, bound ); |
---|
[c1c3693] | 165 | #endif |
---|
[33d8725] | 166 | } |
---|
[afd067] | 167 | } |
---|
[4e6908] | 168 | /// ---> A7 |
---|
| 169 | DD[2] = DD[2] * ( b( lcDD[2] ) / lc( DD[2] ) ); |
---|
| 170 | DD[1] = DD[1] * ( b( lcDD[1] ) / lc( DD[1] ) ); |
---|
| 171 | bound = enlargeBound( B, DD[2], DD[1], bound ); |
---|
| 172 | DEBOUTLN( cerr, "(hensel) B = " << B ); |
---|
| 173 | DEBOUTLN( cerr, "(hensel) lcB = " << LC( B, Variable(1) ) ); |
---|
| 174 | DEBOUTLN( cerr, "(hensel) b(B) = " << b(B) ); |
---|
| 175 | DEBOUTLN( cerr, "(hensel) DD = " << DD ); |
---|
| 176 | DEBOUTLN( cerr, "(hensel) lcDD = " << lcDD ); |
---|
| 177 | gcdfound = Hensel( B, DD, lcDD, b, bound, x ); |
---|
| 178 | DEBOUTLN( cerr, "(hensel finished) DD = " << DD ); |
---|
[afd067] | 179 | |
---|
| 180 | if (gcdfound) |
---|
| 181 | { |
---|
[bde566] | 182 | CanonicalForm xxx=content(DD[2],Variable(1)); |
---|
| 183 | CanonicalForm cand=DD[2] / xxx; //content(DD[2],Variable(1)); |
---|
| 184 | #if 0 |
---|
[4a71670] | 185 | gcdfound= divides(cand,G) && divides(cand,F); |
---|
| 186 | #else |
---|
[bde566] | 187 | if (B_is_F /*B==F*lcF*/) |
---|
[afd067] | 188 | { |
---|
[e22ea7] | 189 | DEBOUTLN( cerr, "(test) G: "<<G<<" % gcd:"<<cand<<" -> " << G%cand ); |
---|
| 190 | gcdfound= divides(cand,G); |
---|
| 191 | } |
---|
[afd067] | 192 | else |
---|
| 193 | { |
---|
[e22ea7] | 194 | DEBOUTLN( cerr, "(test) F: "<<F<<" % gcd:"<<cand<<" -> " << F%cand); |
---|
| 195 | gcdfound= divides(cand,F); |
---|
[afd067] | 196 | } |
---|
[4a71670] | 197 | #endif |
---|
[afd067] | 198 | } |
---|
[4e6908] | 199 | /// ---> A8 (gcdfound) |
---|
| 200 | } |
---|
[33d8725] | 201 | delta++; |
---|
[c1c3693] | 202 | } |
---|
| 203 | /// ---> A9 |
---|
| 204 | DEBDECLEVEL( cerr, "ezgcd" ); |
---|
| 205 | return d * DD[2] / content(DD[2],Variable(1)); |
---|
| 206 | } |
---|
| 207 | |
---|
| 208 | static CanonicalForm |
---|
| 209 | ezgcd_specialcase ( const CanonicalForm & F, const CanonicalForm & G, REvaluation & b, const modpk & bound ) |
---|
| 210 | { |
---|
[d81ed62] | 211 | DEBOUTLN( cerr, "ezgcd: special case" ); |
---|
[c1c3693] | 212 | CanonicalForm Ft, Gt, L, LL, Fb, Gb, Db, Lb, D, Ds, Dt, d; |
---|
| 213 | CFArray DD( 1, 2 ), lcDD( 1, 2 ); |
---|
[4e6908] | 214 | Variable x = Variable( 1 ); |
---|
[c1c3693] | 215 | bool gcdfound; |
---|
| 216 | |
---|
| 217 | Dt = 1; |
---|
| 218 | /// ---> S1 |
---|
[d81ed62] | 219 | DEBOUTLN( cerr, "ezgcdspec: (S1)" ); |
---|
[c1c3693] | 220 | Ft = ezgcd( F, F.deriv( x ) ); |
---|
[6594d4] | 221 | if ( Ft.isOne() ) { |
---|
[4e6908] | 222 | // In this case F is squarefree and we came here by bad chance |
---|
| 223 | // (means: bad evaluation point). Try again with another |
---|
| 224 | // evaluation point. Bug fix (?) by JS. The bad example was |
---|
[6594d4] | 225 | // gcd.debug -ocr /+USE_EZGCD/@12/CB \ |
---|
[4e6908] | 226 | // '(16*B^8-208*B^6*C+927*B^4*C^2-1512*B^2*C^3+432*C^4)' \ |
---|
[6594d4] | 227 | // '(4*B^7*C^2-50*B^5*C^3+208*B^3*C^4-288*B*C^5)' |
---|
[661ca5e] | 228 | b.nextpoint(); |
---|
[afd067] | 229 | return ezgcd( F, G, b, true ); |
---|
[6594d4] | 230 | } |
---|
[41a8db] | 231 | #if 1 |
---|
[33d8725] | 232 | Off(SW_USE_EZGCD); |
---|
[2667bc8] | 233 | //bool ntl0=isOn(SW_USE_NTL_GCD_0); |
---|
| 234 | //Off(SW_USE_NTL_GCD_0); |
---|
| 235 | //bool ntlp=isOn(SW_USE_NTL_GCD_P); |
---|
| 236 | //Off(SW_USE_NTL_GCD_P); |
---|
[33d8725] | 237 | d=gcd( F, G ); |
---|
[2667bc8] | 238 | //if (ntl0) On(SW_USE_NTL_GCD_0); |
---|
| 239 | //if (ntlp) On(SW_USE_NTL_GCD_P); |
---|
[33d8725] | 240 | On(SW_USE_EZGCD); |
---|
| 241 | return d; |
---|
[41a8db] | 242 | #else |
---|
[4e6908] | 243 | |
---|
[d81ed62] | 244 | DEBOUTLN( cerr, "ezgcdspec: (S1) done, Ft = " << Ft ); |
---|
[c1c3693] | 245 | L = F / Ft; |
---|
| 246 | /// ---> S2 |
---|
[d81ed62] | 247 | DEBOUTLN( cerr, "ezgcdspec: (S2)" ); |
---|
[6594d4] | 248 | |
---|
[c1c3693] | 249 | L = ezgcd( L, G, b, true ); |
---|
[d81ed62] | 250 | DEBOUTLN( cerr, "ezgcdspec: (S2) done, Ds = " << Ds ); |
---|
[c1c3693] | 251 | Gt = G / L; |
---|
| 252 | Ds = L; Dt = L; |
---|
| 253 | Lb = b( L ); Gb = b( Gt ); Fb = b( Ft ); |
---|
| 254 | d = gcd( LC( L, x ), gcd( LC( Ft, x ), LC( Gt, x ) ) ); |
---|
| 255 | while ( true ) { |
---|
[4e6908] | 256 | /// ---> S3 |
---|
| 257 | DEBOUTLN( cerr, "ezgcdspec: (S3)" ); |
---|
| 258 | DEBOUTLN( cerr, "ezgcdspec: Fb = " << Fb ); |
---|
| 259 | DEBOUTLN( cerr, "ezgcdspec: Gb = " << Gb ); |
---|
| 260 | DD[1] = gcd( Lb, gcd( Fb, Gb ) ); |
---|
| 261 | /// ---> S4 |
---|
| 262 | DEBOUTLN( cerr, "ezgcdspec: (S4)" ); |
---|
| 263 | if ( degree( DD[1] ) == 0 ) |
---|
| 264 | return Ds; |
---|
| 265 | /// ---> S5 |
---|
| 266 | DEBOUTLN( cerr, "ezgcdspec: (S5)" ); |
---|
| 267 | DEBOUTLN( cerr, "ezgcdspec: Lb = " << Lb ); |
---|
| 268 | DEBOUTLN( cerr, "ezgcdspec: Db = " << DD[1] ); |
---|
| 269 | Db = DD[1]; |
---|
| 270 | if ( ! (DD[2] = Lb/DD[1]).isOne() ) { |
---|
| 271 | DEBOUTLN( cerr, "ezgcdspec: (S55)" ); |
---|
| 272 | lcDD[2] = LC( L, x ); |
---|
| 273 | lcDD[1] = d; |
---|
| 274 | DD[1] = ( DD[1] * b( d ) ) / lc( DD[1] ); |
---|
| 275 | DD[2] = ( DD[2] * b( lcDD[2] ) ) / lc( DD[2] ); |
---|
| 276 | LL = L * d; |
---|
| 277 | modpk newbound = enlargeBound( LL, DD[2], DD[1], bound ); |
---|
| 278 | DEBOUTLN( cerr, "ezgcdspec: begin with lift." ); |
---|
| 279 | DEBOUTLN( cerr, "ezgcdspec: B = " << LL ); |
---|
| 280 | DEBOUTLN( cerr, "ezgcdspec: DD = " << DD ); |
---|
| 281 | DEBOUTLN( cerr, "ezgcdspec: lcDD = " << lcDD ); |
---|
| 282 | DEBOUTLN( cerr, "ezgcdspec: b = " << b ); |
---|
| 283 | DEBOUTLN( cerr, "ezgcdspec: bound = " << bound.getpk() ); |
---|
| 284 | DEBOUTLN( cerr, "ezgcdspec: lc(B) = " << LC( LL, x ) ); |
---|
| 285 | DEBOUTLN( cerr, "ezgcdspec: test = " << b( LL ) - DD[1] * DD[2] ); |
---|
| 286 | gcdfound = Hensel( LL, DD, lcDD, b, newbound, x ); |
---|
| 287 | ASSERT( gcdfound, "fatal error in algorithm" ); |
---|
| 288 | Dt = pp( DD[1] ); |
---|
| 289 | } |
---|
| 290 | DEBOUTLN( cerr, "ezgcdspec: (S7)" ); |
---|
| 291 | Ds = Ds * Dt; |
---|
| 292 | Fb = Fb / Db; |
---|
| 293 | Gb = Gb / Db; |
---|
[c1c3693] | 294 | } |
---|
| 295 | // this point is never reached, but to avoid compiler warnings let's return a value |
---|
| 296 | return 0; |
---|
[41a8db] | 297 | #endif |
---|
[c1c3693] | 298 | } |
---|
| 299 | |
---|
| 300 | static void |
---|
| 301 | findeval( const CanonicalForm & F, const CanonicalForm & G, CanonicalForm & Fb, CanonicalForm & Gb, CanonicalForm & Db, REvaluation & b, int delta, int degF, int degG ) |
---|
| 302 | { |
---|
[e22ea7] | 303 | int i; |
---|
[c1c3693] | 304 | bool ok; |
---|
| 305 | if ( delta != 0 ) |
---|
[661ca5e] | 306 | b.nextpoint(); |
---|
[e22ea7] | 307 | DEBOUTLN( cerr, "ezgcd: (findeval) F = " << F <<", G="<< G); |
---|
| 308 | DEBOUTLN( cerr, "ezgcd: (findeval) degF = " << degF << ", degG="<<degG ); |
---|
[c1c3693] | 309 | do { |
---|
[4e6908] | 310 | DEBOUTLN( cerr, "ezgcd: (findeval) b = " << b ); |
---|
| 311 | Fb = b( F ); |
---|
| 312 | ok = degree( Fb ) == degF; |
---|
| 313 | if ( ok ) { |
---|
| 314 | Gb = b( G ); |
---|
| 315 | ok = degree( Gb ) == degG; |
---|
| 316 | } |
---|
[afd067] | 317 | |
---|
[c92316] | 318 | if ( ok ) |
---|
[afd067] | 319 | { |
---|
[c92316] | 320 | Db = gcd( Fb, Gb ); |
---|
| 321 | if ( delta > 0 ) |
---|
| 322 | ok = degree( Db ) < delta; |
---|
[4e6908] | 323 | } |
---|
| 324 | if ( ! ok ) |
---|
[afd067] | 325 | { |
---|
[661ca5e] | 326 | b.nextpoint(); |
---|
[afd067] | 327 | } |
---|
[c1c3693] | 328 | } while ( ! ok ); |
---|
| 329 | } |
---|
| 330 | |
---|
| 331 | static modpk |
---|
| 332 | enlargeBound ( const CanonicalForm & F, const CanonicalForm & Lb, const CanonicalForm & Db, const modpk & pk ) |
---|
| 333 | { |
---|
[d81ed62] | 334 | DEBOUTLN( cerr, "ezgcd: (enlarge bound) F = " << F ); |
---|
| 335 | DEBOUTLN( cerr, "ezgcd: (enlarge bound) Lb = " << Lb ); |
---|
| 336 | DEBOUTLN( cerr, "ezgcd: (enlarge bound) Db = " << Db ); |
---|
| 337 | DEBOUTLN( cerr, "ezgcd: (enlarge bound) Lb % p = " << mod( Lb, pk.getp() ) ); |
---|
| 338 | DEBOUTLN( cerr, "ezgcd: (enlarge bound) Db % p = " << mod( Db, pk.getp() ) ); |
---|
[c1c3693] | 339 | |
---|
| 340 | CanonicalForm limit = power( CanonicalForm(2), degree( Db ) ) * |
---|
[4e6908] | 341 | tmax( maxNorm( Lb ), tmax( maxNorm( Db ), maxNorm( F ) ) ); |
---|
[c1c3693] | 342 | int p = pk.getp(); |
---|
| 343 | int k = pk.getk(); |
---|
| 344 | CanonicalForm bound = pk.getpk(); |
---|
| 345 | while ( bound < limit ) { |
---|
[4e6908] | 346 | k++; |
---|
| 347 | bound *= p; |
---|
[c1c3693] | 348 | } |
---|
| 349 | k *= 2; |
---|
[d81ed62] | 350 | DEBOUTLN( cerr, "ezgcd: (enlarge bound) newbound = " << power( CanonicalForm( p ), k ) ); |
---|
[c1c3693] | 351 | return modpk( p, k ); |
---|
| 352 | } |
---|
| 353 | |
---|
| 354 | static modpk |
---|
| 355 | findBound ( const CanonicalForm & F, const CanonicalForm & G, const CanonicalForm & lcF, const CanonicalForm & lcG, int degF, int degG ) |
---|
| 356 | { |
---|
| 357 | CanonicalForm limit = power( CanonicalForm(2), tmin( degF, degG ) ) * |
---|
[4e6908] | 358 | gcd( icontent( lcF ), icontent( lcG ) ) * tmin( maxNorm( F ), maxNorm( G ) ); |
---|
[c1c3693] | 359 | int p, i = 0; |
---|
| 360 | do { |
---|
[4e6908] | 361 | p = cf_getBigPrime( i ); |
---|
| 362 | i++; |
---|
[c1c3693] | 363 | } while ( mod( lcF, p ).isZero() && mod( lcG, p ).isZero() ); |
---|
| 364 | CanonicalForm bound = p; |
---|
| 365 | i = 1; |
---|
| 366 | while ( bound < limit ) { |
---|
[4e6908] | 367 | i++; |
---|
| 368 | bound *= p; |
---|
[c1c3693] | 369 | } |
---|
| 370 | return modpk( p, i ); |
---|
| 371 | } |
---|