Changeset e90dfd6 in git for coeffs/rmodulo2m.cc
- Timestamp:
- Sep 6, 2010, 12:08:33 PM (14 years ago)
- Branches:
- (u'spielwiese', '4a9821a93ffdc22a6696668bd4f6b8c9de3e6c5f')
- Children:
- e903733fa2ff9e4f7582f1faabf6cc2a6baea275
- Parents:
- 5d594a96114bdb26100c2b8e2ae329a7529f0e45
- git-author:
- Frank Seelisch <seelisch@mathematik.uni-kl.de>2010-09-06 12:08:33+02:00
- git-committer:
- Mohamed Barakat <mohamed.barakat@rwth-aachen.de>2011-11-09 11:55:29+01:00
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
coeffs/rmodulo2m.cc
-
Property
mode
changed from
100644
to100755
r5d594a9 re90dfd6 24 24 #include <string.h> 25 25 26 int nr2mExp;27 28 26 extern omBin gmp_nrz_bin; /* init in rintegers*/ 29 27 … … 34 32 nr2mInitExp((int)(long)(p), r); 35 33 36 r->cfInit = nr2mInit;37 r->cfCopy = ndCopy;38 r->cfInt = nr2mInt;34 r->cfInit = nr2mInit; 35 r->cfCopy = ndCopy; 36 r->cfInt = nr2mInt; 39 37 r->cfAdd = nr2mAdd; 40 38 r->cfSub = nr2mSub; … … 54 52 r->cfIsMOne = nr2mIsMOne; 55 53 r->cfGreaterZero = nr2mGreaterZero; 56 r->cfWrite = nr2mWrite;54 r->cfWrite = nr2mWrite; 57 55 r->cfRead = nr2mRead; 58 56 r->cfPower = nr2mPower; 59 r->cfSetMap = nr2mSetMap;57 r->cfSetMap = nr2mSetMap; 60 58 r->cfNormalize = ndNormalize; 61 59 r->cfLcm = nr2mLcm; … … 75 73 * Multiply two numbers 76 74 */ 77 number nr2mMult 75 number nr2mMult(number a, number b, const coeffs r) 78 76 { 79 77 if (((NATNUMBER)a == 0) || ((NATNUMBER)b == 0)) 80 78 return (number)0; 81 79 else 82 return nr2mMultM(a, b,r);83 } 84 85 /* 86 * Give the smallest non unitk, such that a * x = k = b * y has a solution80 return nr2mMultM(a, b, r); 81 } 82 83 /* 84 * Give the smallest k, such that a * x = k = b * y has a solution 87 85 */ 88 number nr2mLcm 86 number nr2mLcm(number a, number b, const coeffs r) 89 87 { 90 88 NATNUMBER res = 0; 91 if ((NATNUMBER) 92 if ((NATNUMBER) 93 while ((NATNUMBER) 94 { 95 a = (number) ((NATNUMBER)a / 2);96 if ((NATNUMBER) b % 2 == 0) b = (number) ((NATNUMBER)b / 2);89 if ((NATNUMBER)a == 0) a = (number) 1; 90 if ((NATNUMBER)b == 0) b = (number) 1; 91 while ((NATNUMBER)a % 2 == 0) 92 { 93 a = (number)((NATNUMBER)a / 2); 94 if ((NATNUMBER)b % 2 == 0) b = (number)((NATNUMBER)b / 2); 97 95 res++; 98 96 } 99 while ((NATNUMBER) 100 { 101 b = (number) ((NATNUMBER)b / 2);97 while ((NATNUMBER)b % 2 == 0) 98 { 99 b = (number)((NATNUMBER)b / 2); 102 100 res++; 103 101 } 104 return (number) 105 } 106 107 /* 108 * Give the largest non unitk, such that a = x * k, b = y * k has102 return (number)(1L << res); // (2**res) 103 } 104 105 /* 106 * Give the largest k, such that a = x * k, b = y * k has 109 107 * a solution. 110 108 */ 111 number nr2mGcd 109 number nr2mGcd(number a, number b, const coeffs r) 112 110 { 113 111 NATNUMBER res = 0; 114 if ((NATNUMBER) a == 0 && (NATNUMBER) b == 0) return (number)1;115 while ((NATNUMBER) a % 2 == 0 && (NATNUMBER)b % 2 == 0)116 { 117 a = (number) ((NATNUMBER)a / 2);118 b = (number) ((NATNUMBER)b / 2);112 if ((NATNUMBER)a == 0 && (NATNUMBER)b == 0) return (number)1; 113 while ((NATNUMBER)a % 2 == 0 && (NATNUMBER)b % 2 == 0) 114 { 115 a = (number)((NATNUMBER)a / 2); 116 b = (number)((NATNUMBER)b / 2); 119 117 res++; 120 118 } 121 // if ((NATNUMBER) 119 // if ((NATNUMBER)b % 2 == 0) 122 120 // { 123 // return (number) ((1L << res));// * (NATNUMBER) a); // (2**res)*a a ist Einheit121 // return (number)((1L << res)); // * (NATNUMBER) a); // (2**res)*a a is a unit 124 122 // } 125 123 // else 126 124 // { 127 return (number) ((1L << res));// * (NATNUMBER) b); // (2**res)*b b ist Einheit125 return (number)((1L << res)); // * (NATNUMBER) b); // (2**res)*b b is a unit 128 126 // } 129 127 } 130 128 131 129 /* 132 * Give the largest non unitk, such that a = x * k, b = y * k has130 * Give the largest k, such that a = x * k, b = y * k has 133 131 * a solution. 134 132 */ 135 number nr2mExtGcd 133 number nr2mExtGcd(number a, number b, number *s, number *t, const coeffs r) 136 134 { 137 135 NATNUMBER res = 0; 138 if ((NATNUMBER) a == 0 && (NATNUMBER) b == 0) return (number)1;139 while ((NATNUMBER) a % 2 == 0 && (NATNUMBER)b % 2 == 0)140 { 141 a = (number) ((NATNUMBER)a / 2);142 b = (number) ((NATNUMBER)b / 2);136 if ((NATNUMBER)a == 0 && (NATNUMBER)b == 0) return (number)1; 137 while ((NATNUMBER)a % 2 == 0 && (NATNUMBER)b % 2 == 0) 138 { 139 a = (number)((NATNUMBER)a / 2); 140 b = (number)((NATNUMBER)b / 2); 143 141 res++; 144 142 } 145 if ((NATNUMBER) 143 if ((NATNUMBER)b % 2 == 0) 146 144 { 147 145 *t = NULL; 148 146 *s = nr2mInvers(a,r); 149 return (number) ((1L << res));// * (NATNUMBER) a); // (2**res)*a a ist Einheit147 return (number)((1L << res)); // * (NATNUMBER) a); // (2**res)*a a is a unit 150 148 } 151 149 else … … 153 151 *s = NULL; 154 152 *t = nr2mInvers(b,r); 155 return (number) ((1L << res));// * (NATNUMBER) b); // (2**res)*b b ist Einheit156 } 157 } 158 159 void nr2mPower 160 { 161 if (i ==0)153 return (number)((1L << res)); // * (NATNUMBER) b); // (2**res)*b b is a unit 154 } 155 } 156 157 void nr2mPower(number a, int i, number * result, const coeffs r) 158 { 159 if (i == 0) 162 160 { 163 161 *(NATNUMBER *)result = 1; 164 162 } 165 else if (i ==1)163 else if (i == 1) 166 164 { 167 165 *result = a; … … 169 167 else 170 168 { 171 nr2mPower(a, i-1,result,r);172 *result = nr2mMultM(a, *result,r);169 nr2mPower(a, i-1, result, r); 170 *result = nr2mMultM(a, *result, r); 173 171 } 174 172 } … … 177 175 * create a number from int 178 176 */ 179 number nr2mInit 177 number nr2mInit(int i, const coeffs r) 180 178 { 181 179 if (i == 0) return (number)(NATNUMBER)i; … … 183 181 long ii = i; 184 182 NATNUMBER j = (NATNUMBER)1; 185 if (ii < 0) { j = r-> nr2mModul; ii = -ii; }183 if (ii < 0) { j = r->mod2mMask; ii = -ii; } 186 184 NATNUMBER k = (NATNUMBER)ii; 187 k = k & r-> nr2mModul;188 /* now we have: from= j * k mod 2^m */189 return (number)nr2mMult((number)j, (number)k, r);185 k = k & r->mod2mMask; 186 /* now we have: i = j * k mod 2^m */ 187 return (number)nr2mMult((number)j, (number)k, r); 190 188 } 191 189 … … 198 196 int nr2mInt(number &n, const coeffs r) 199 197 { 200 NATNUMBER nn = (unsigned long)(NATNUMBER)n & r-> nr2mModul;201 unsigned long l = r-> nr2mModul>> 1; l++; /* now: l = 2^(m-1) */198 NATNUMBER nn = (unsigned long)(NATNUMBER)n & r->mod2mMask; 199 unsigned long l = r->mod2mMask >> 1; l++; /* now: l = 2^(m-1) */ 202 200 if ((NATNUMBER)nn > l) 203 return (int)((NATNUMBER)nn - r-> nr2mModul- 1);201 return (int)((NATNUMBER)nn - r->mod2mMask - 1); 204 202 else 205 203 return (int)((NATNUMBER)nn); 206 204 } 207 205 208 number nr2mAdd (number a, number b, const coeffs r) 209 { 210 return nr2mAddM(a,b,r); 211 } 212 213 number nr2mSub (number a, number b, const coeffs r) 214 { 215 return nr2mSubM(a,b,r); 216 } 217 218 BOOLEAN nr2mIsUnit (number a, const coeffs r) 219 { 220 return ((NATNUMBER) a % 2 == 1); 221 } 222 223 number nr2mGetUnit (number k, const coeffs r) 224 { 225 if (k == NULL) 226 return (number) 1; 227 NATNUMBER tmp = (NATNUMBER) k; 228 while (tmp % 2 == 0) 229 tmp = tmp / 2; 230 return (number) tmp; 231 } 232 233 BOOLEAN nr2mIsZero (number a, const coeffs r) 206 number nr2mAdd(number a, number b, const coeffs r) 207 { 208 return nr2mAddM(a, b, r); 209 } 210 211 number nr2mSub(number a, number b, const coeffs r) 212 { 213 return nr2mSubM(a, b, r); 214 } 215 216 BOOLEAN nr2mIsUnit(number a, const coeffs r) 217 { 218 return ((NATNUMBER)a % 2 == 1); 219 } 220 221 number nr2mGetUnit(number k, const coeffs r) 222 { 223 if (k == NULL) return (number)1; 224 NATNUMBER erg = (NATNUMBER)k; 225 while (erg % 2 == 0) erg = erg / 2; 226 return (number)erg; 227 } 228 229 BOOLEAN nr2mIsZero(number a, const coeffs r) 234 230 { 235 231 return 0 == (NATNUMBER)a; 236 232 } 237 233 238 BOOLEAN nr2mIsOne 234 BOOLEAN nr2mIsOne(number a, const coeffs r) 239 235 { 240 236 return 1 == (NATNUMBER)a; 241 237 } 242 238 243 BOOLEAN nr2mIsMOne (number a, const coeffs r) 244 { 245 return (r->nr2mModul == (NATNUMBER)a) 246 && (r->nr2mModul != 2); 247 } 248 249 BOOLEAN nr2mEqual (number a, number b, const coeffs r) 250 { 251 return a==b; 252 } 253 254 BOOLEAN nr2mGreater (number a, number b, const coeffs r) 239 BOOLEAN nr2mIsMOne(number a, const coeffs r) 240 { 241 return (r->mod2mMask == (NATNUMBER)a); 242 } 243 244 BOOLEAN nr2mEqual(number a, number b, const coeffs r) 245 { 246 return a == b; 247 } 248 249 BOOLEAN nr2mGreater(number a, number b, const coeffs r) 255 250 { 256 251 return nr2mDivBy(a, b,r); … … 265 260 if (a == NULL) 266 261 { 267 NATNUMBER c = r-> nr2mModul+ 1;262 NATNUMBER c = r->mod2mMask + 1; 268 263 if (c != 0) /* i.e., if no overflow */ 269 264 return (c % (NATNUMBER)b) == 0; … … 291 286 int nr2mDivComp(number as, number bs, const coeffs r) 292 287 { 293 NATNUMBER a = (NATNUMBER) 294 NATNUMBER b = (NATNUMBER) 288 NATNUMBER a = (NATNUMBER)as; 289 NATNUMBER b = (NATNUMBER)bs; 295 290 assume(a != 0 && b != 0); 296 291 while (a % 2 == 0 && b % 2 == 0) … … 317 312 318 313 /* TRUE iff 0 < k <= 2^m / 2 */ 319 BOOLEAN nr2mGreaterZero 314 BOOLEAN nr2mGreaterZero(number k, const coeffs r) 320 315 { 321 316 if ((NATNUMBER)k == 0) return FALSE; 322 if ((NATNUMBER)k > ((r-> nr2mModul>> 1) + 1)) return FALSE;317 if ((NATNUMBER)k > ((r->mod2mMask >> 1) + 1)) return FALSE; 323 318 return TRUE; 324 319 } … … 328 323 and 't' such that a * s + 2^m * t = gcd(a, 2^m) = 1; 329 324 this code will always find a positive 's' */ 330 void specialXGCD(unsigned long& s, unsigned long a, const coeffs R)325 void specialXGCD(unsigned long& s, unsigned long a, const coeffs r) 331 326 { 332 327 int_number u = (int_number)omAlloc(sizeof(mpz_t)); … … 339 334 mpz_init(u2); 340 335 int_number v = (int_number)omAlloc(sizeof(mpz_t)); 341 mpz_init_set_ui(v, R->nr2mModul);336 mpz_init_set_ui(v, r->mod2mMask); 342 337 mpz_add_ui(v, v, 1); /* now: v = 2^m */ 343 338 int_number v0 = (int_number)omAlloc(sizeof(mpz_t)); … … 349 344 int_number q = (int_number)omAlloc(sizeof(mpz_t)); 350 345 mpz_init(q); 351 int_number r = (int_number)omAlloc(sizeof(mpz_t));352 mpz_init(r );346 int_number rr = (int_number)omAlloc(sizeof(mpz_t)); 347 mpz_init(rr); 353 348 354 349 while (mpz_cmp_ui(v, 0) != 0) /* i.e., while v != 0 */ 355 350 { 356 351 mpz_div(q, u, v); 357 mpz_mod(r , u, v);352 mpz_mod(rr, u, v); 358 353 mpz_set(u, v); 359 mpz_set(v, r );354 mpz_set(v, rr); 360 355 mpz_set(u0, u2); 361 356 mpz_set(v0, v2); … … 369 364 { 370 365 /* we add 2^m = (2^m - 1) + 1 to u1: */ 371 mpz_add_ui(u1, u1, R->nr2mModul);366 mpz_add_ui(u1, u1, r->mod2mMask); 372 367 mpz_add_ui(u1, u1, 1); 373 368 } … … 383 378 mpz_clear(v2); omFree((ADDRESS)v2); 384 379 mpz_clear(q); omFree((ADDRESS)q); 385 mpz_clear(r ); omFree((ADDRESS)r);380 mpz_clear(rr); omFree((ADDRESS)rr); 386 381 } 387 382 … … 395 390 //#endif 396 391 397 inline number nr2mInversM 392 inline number nr2mInversM(number c, const coeffs r) 398 393 { 399 394 assume((NATNUMBER)c % 2 != 0); … … 401 396 NATNUMBER inv; 402 397 inv = InvMod((NATNUMBER)c,r); 403 return (number) inv; 404 } 405 406 number nr2mDiv (number a, number b, const coeffs r) 407 { 408 if ((NATNUMBER)a==0) 409 return (number)0; 410 else if ((NATNUMBER)b%2==0) 398 return (number)inv; 399 } 400 401 number nr2mDiv(number a, number b, const coeffs r) 402 { 403 if ((NATNUMBER)a == 0) return (number)0; 404 else if ((NATNUMBER)b % 2 == 0) 411 405 { 412 406 if ((NATNUMBER)b != 0) 413 407 { 414 while (( NATNUMBER) b%2 == 0 && (NATNUMBER) a%2 == 0)408 while (((NATNUMBER)b % 2 == 0) && ((NATNUMBER)a % 2 == 0)) 415 409 { 416 a = (number) ((NATNUMBER)a / 2);417 b = (number) ((NATNUMBER)b / 2);410 a = (number)((NATNUMBER)a / 2); 411 b = (number)((NATNUMBER)b / 2); 418 412 } 419 413 } 420 if ((NATNUMBER) b%2 == 0)414 if ((NATNUMBER)b % 2 == 0) 421 415 { 422 416 WerrorS("Division not possible, even by cancelling zero divisors."); … … 425 419 } 426 420 } 427 return (number) 428 } 429 430 number nr2mMod (number a, number b, const coeffs R)421 return (number)nr2mMult(a, nr2mInversM(b,r),r); 422 } 423 424 number nr2mMod(number a, number b, const coeffs r) 431 425 { 432 426 /* 433 We need to return the number r which is uniquely determined by the427 We need to return the number rr which is uniquely determined by the 434 428 following two properties: 435 (1) 0 <= r < |b| (with respect to '<' and '<=' performed in Z x Z)436 (2) There exists some k in the integers Z such that a = k * b + r .429 (1) 0 <= rr < |b| (with respect to '<' and '<=' performed in Z x Z) 430 (2) There exists some k in the integers Z such that a = k * b + rr. 437 431 Consider g := gcd(2^m, |b|). Note that then |b|/g is a unit in Z/2^m. 438 432 Now, there are three cases: 439 433 (a) g = 1 440 434 Then |b| is a unit in Z/2^m, i.e. |b| (and also b) divides a. 441 Thus r = 0.435 Thus rr = 0. 442 436 (b) g <> 1 and g divides a 443 Then a = (a/g) * (|b|/g)^(-1) * b (up to sign), i.e. again r = 0.437 Then a = (a/g) * (|b|/g)^(-1) * b (up to sign), i.e. again rr = 0. 444 438 (c) g <> 1 and g does not divide a 445 439 Let's denote the division with remainder of a by g as follows: 446 440 a = s * g + t. Then t = a - s * g = a - s * (|b|/g)^(-1) * |b| 447 fulfills (1) and (2), i.e. r := t is the correct result. Hence448 in this third case, r is the remainder of division of a by g in Z.441 fulfills (1) and (2), i.e. rr := t is the correct result. Hence 442 in this third case, rr is the remainder of division of a by g in Z. 449 443 This algorithm is the same as for the case Z/n, except that we may 450 444 compute the gcd of |b| and 2^m "by hand": We just extract the highest … … 455 449 NATNUMBER b_div = (NATNUMBER)b; 456 450 if (b_div < 0) b_div = -b_div; // b_div now represents |b| 457 NATNUMBER r = 0;458 while ((g < R->nr2mModul) && (b_div > 0) && (b_div % 2 == 0))451 NATNUMBER rr = 0; 452 while ((g < r->mod2mMask ) && (b_div > 0) && (b_div % 2 == 0)) 459 453 { 460 454 b_div = b_div >> 1; … … 462 456 } // g is now the gcd of 2^m and |b| 463 457 464 if (g != 1) r = (NATNUMBER)a % g;465 return (number)r ;466 } 467 468 number nr2mIntDiv 458 if (g != 1) rr = (NATNUMBER)a % g; 459 return (number)rr; 460 } 461 462 number nr2mIntDiv(number a, number b, const coeffs r) 469 463 { 470 464 if ((NATNUMBER)a == 0) … … 474 468 if ((NATNUMBER)b == 1) 475 469 return (number)0; 476 NATNUMBER c = r-> nr2mModul+ 1;470 NATNUMBER c = r->mod2mMask + 1; 477 471 if (c != 0) /* i.e., if no overflow */ 478 472 return (number)(c / (NATNUMBER)b); … … 481 475 /* overflow: c = 2^32 resp. 2^64, depending on platform */ 482 476 int_number cc = (int_number)omAlloc(sizeof(mpz_t)); 483 mpz_init_set_ui(cc, r-> nr2mModul); mpz_add_ui(cc, cc, 1);477 mpz_init_set_ui(cc, r->mod2mMask); mpz_add_ui(cc, cc, 1); 484 478 mpz_div_ui(cc, cc, (unsigned long)(NATNUMBER)b); 485 479 unsigned long s = mpz_get_ui(cc); … … 496 490 } 497 491 498 number nr2mInvers(number c, const coeffs r)499 { 500 if ((NATNUMBER)c %2==0)492 number nr2mInvers(number c, const coeffs r) 493 { 494 if ((NATNUMBER)c % 2 == 0) 501 495 { 502 496 WerrorS("division by zero divisor"); 503 497 return (number)0; 504 498 } 505 return nr2mInversM(c, r);506 } 507 508 number nr2mNeg 509 { 510 if ((NATNUMBER)c ==0) return c;511 return nr2mNegM(c, r);499 return nr2mInversM(c, r); 500 } 501 502 number nr2mNeg(number c, const coeffs r) 503 { 504 if ((NATNUMBER)c == 0) return c; 505 return nr2mNegM(c, r); 512 506 } 513 507 514 508 number nr2mMapMachineInt(number from, const coeffs src, const coeffs dst) 515 509 { 516 NATNUMBER i = ((NATNUMBER) from) % dst->nr2mModul;517 return (number) 510 NATNUMBER i = ((NATNUMBER)from) % dst->mod2mMask ; 511 return (number)i; 518 512 } 519 513 … … 521 515 { 522 516 NATNUMBER j = (NATNUMBER)1; 523 long ii = (long) 524 if (ii < 0) { j = dst-> nr2mModul; ii = -ii; }517 long ii = (long)from; 518 if (ii < 0) { j = dst->mod2mMask; ii = -ii; } 525 519 NATNUMBER i = (NATNUMBER)ii; 526 i = i & dst-> nr2mModul;520 i = i & dst->mod2mMask; 527 521 /* now we have: from = j * i mod 2^m */ 528 522 return (number)nr2mMult((number)i, (number)j, dst); … … 531 525 number nr2mMapQ(number from, const coeffs src, const coeffs dst) 532 526 { 533 int_number erg = (int_number) 527 int_number erg = (int_number)omAllocBin(gmp_nrz_bin); 534 528 mpz_init(erg); 535 int_number k = (int_number) 536 mpz_init_set_ui(k, dst-> nr2mModul);529 int_number k = (int_number)omAlloc(sizeof(mpz_t)); 530 mpz_init_set_ui(k, dst->mod2mMask); 537 531 538 532 nlGMP(from, (number)erg, dst); … … 543 537 mpz_clear(k); omFree((ADDRESS)k); 544 538 545 return (number) 539 return (number)res; 546 540 } 547 541 548 542 number nr2mMapGMP(number from, const coeffs src, const coeffs dst) 549 543 { 550 int_number erg = (int_number) 544 int_number erg = (int_number)omAllocBin(gmp_nrz_bin); 551 545 mpz_init(erg); 552 int_number k = (int_number) 553 mpz_init_set_ui(k, dst-> nr2mModul);546 int_number k = (int_number)omAlloc(sizeof(mpz_t)); 547 mpz_init_set_ui(k, dst->mod2mMask); 554 548 555 549 mpz_and(erg, (int_number)from, k); … … 559 553 mpz_clear(k); omFree((ADDRESS)k); 560 554 561 return (number) 555 return (number)res; 562 556 } 563 557 … … 565 559 { 566 560 if (nCoeff_is_Ring_2toM(src) 567 && (src-> ringflagb == dst->ringflagb))561 && (src->mod2mMask == dst->mod2mMask)) 568 562 { 569 563 return ndCopyMap; … … 587 581 return nr2mMapQ; 588 582 } 589 if (nCoeff_is_Zp(src) 590 && (src->ch == 2) 591 && (dst->ringflagb == 1)) 583 if (nCoeff_is_Zp(src) && (src->ch == 2)) 592 584 { 593 585 return nr2mMapZp; … … 596 588 { 597 589 // Computing the n of Z/n 598 int_number modul = (int_number) omAllocBin(gmp_nrz_bin); 599 mpz_init(modul); 600 mpz_set(modul, src->ringflaga); 601 mpz_pow_ui(modul, modul, src->ringflagb); 602 if (mpz_divisible_2exp_p(modul, dst->ringflagb)) 603 { 604 mpz_clear(modul); 605 omFree((void *) modul); 590 int_number modul = (int_number)omAllocBin(gmp_nrz_bin); 591 mpz_init_set(modul, src->modNumber); 592 int_number twoToTheK = (int_number)omAllocBin(gmp_nrz_bin); 593 mpz_init_set_ui(twoToTheK, src->mod2mMask); 594 mpz_add_ui(twoToTheK, twoToTheK, 1); 595 if (mpz_divisible_p(modul, twoToTheK)) 596 { 597 mpz_clear(modul); omFree((void *)modul); 598 mpz_clear(twoToTheK); omFree((void *)twoToTheK); 606 599 return nr2mMapGMP; 607 600 } 608 mpz_clear(modul); 609 omFree((void *) modul);601 mpz_clear(modul); omFree((void *) modul); 602 mpz_clear(twoToTheK); omFree((void *)twoToTheK); 610 603 } 611 604 return NULL; // default … … 613 606 614 607 /* 615 * set the exponent (allocate and init tables) (TODO)608 * set the exponent 616 609 */ 617 610 … … 620 613 if (m > 1) 621 614 { 622 nr2mExp = m; 623 /* we want nr2mModul to be the bit pattern '11..1' consisting 624 of m one's: */ 625 r->nr2mModul = 1; 626 for (int i = 1; i < m; i++) r->nr2mModul = (r->nr2mModul * 2) + 1; 627 } 628 else 629 { 630 nr2mExp = 2; 631 r->nr2mModul = 3; /* i.e., '11' in binary representation */ 615 /* we want mod2mMask to be the bit pattern 616 '111..1' consisting of m one's: */ 617 r->mod2mMask = 1; 618 for (int i = 1; i < m; i++) r->mod2mMask = (r->mod2mMask << 1) + 1; 619 } 620 else 621 { 622 /* code unexpectedly called with m = 1; we go on with m = 2: */ 623 r->mod2mMask = 3; /* i.e., '11' in binary representation */ 632 624 } 633 625 } … … 636 628 { 637 629 nr2mSetExp(m, r); 638 if (m < 2) WarnS("nr2mInitExp failed: we go on with Z/2^2"); 630 if (m < 2) 631 WarnS("nr2mInitExp unexpectedly called with m = 1 (we go on with Z/2^2"); 639 632 } 640 633 … … 643 636 { 644 637 if ((NATNUMBER)a < 0) return FALSE; 645 if (((NATNUMBER)a & r-> nr2mModul) != (NATNUMBER)a) return FALSE;638 if (((NATNUMBER)a & r->mod2mMask) != (NATNUMBER)a) return FALSE; 646 639 return TRUE; 647 640 } … … 664 657 (*i) *= 10; 665 658 (*i) += *s++ - '0'; 666 if ((*i) >= (MAX_INT_VAL / 10)) (*i) = (*i) & r-> nr2mModul;659 if ((*i) >= (MAX_INT_VAL / 10)) (*i) = (*i) & r->mod2mMask; 667 660 } 668 661 while (((*s) >= '0') && ((*s) <= '9')); 669 (*i) = (*i) & r-> nr2mModul;662 (*i) = (*i) & r->mod2mMask; 670 663 } 671 664 else (*i) = 1; -
Property
mode
changed from
Note: See TracChangeset
for help on using the changeset viewer.