1 package org.bouncycastle.math.raw; 2 3 import java.math.BigInteger; 4 5 import org.bouncycastle.util.Pack; 6 7 public abstract class Nat256 8 { 9 private static final long M = 0xFFFFFFFFL; 10 11 public static int add(int[] x, int[] y, int[] z) 12 { 13 long c = 0; 14 c += (x[0] & M) + (y[0] & M); 15 z[0] = (int)c; 16 c >>>= 32; 17 c += (x[1] & M) + (y[1] & M); 18 z[1] = (int)c; 19 c >>>= 32; 20 c += (x[2] & M) + (y[2] & M); 21 z[2] = (int)c; 22 c >>>= 32; 23 c += (x[3] & M) + (y[3] & M); 24 z[3] = (int)c; 25 c >>>= 32; 26 c += (x[4] & M) + (y[4] & M); 27 z[4] = (int)c; 28 c >>>= 32; 29 c += (x[5] & M) + (y[5] & M); 30 z[5] = (int)c; 31 c >>>= 32; 32 c += (x[6] & M) + (y[6] & M); 33 z[6] = (int)c; 34 c >>>= 32; 35 c += (x[7] & M) + (y[7] & M); 36 z[7] = (int)c; 37 c >>>= 32; 38 return (int)c; 39 } 40 41 public static int add(int[] x, int xOff, int[] y, int yOff, int[] z, int zOff) 42 { 43 long c = 0; 44 c += (x[xOff + 0] & M) + (y[yOff + 0] & M); 45 z[zOff + 0] = (int)c; 46 c >>>= 32; 47 c += (x[xOff + 1] & M) + (y[yOff + 1] & M); 48 z[zOff + 1] = (int)c; 49 c >>>= 32; 50 c += (x[xOff + 2] & M) + (y[yOff + 2] & M); 51 z[zOff + 2] = (int)c; 52 c >>>= 32; 53 c += (x[xOff + 3] & M) + (y[yOff + 3] & M); 54 z[zOff + 3] = (int)c; 55 c >>>= 32; 56 c += (x[xOff + 4] & M) + (y[yOff + 4] & M); 57 z[zOff + 4] = (int)c; 58 c >>>= 32; 59 c += (x[xOff + 5] & M) + (y[yOff + 5] & M); 60 z[zOff + 5] = (int)c; 61 c >>>= 32; 62 c += (x[xOff + 6] & M) + (y[yOff + 6] & M); 63 z[zOff + 6] = (int)c; 64 c >>>= 32; 65 c += (x[xOff + 7] & M) + (y[yOff + 7] & M); 66 z[zOff + 7] = (int)c; 67 c >>>= 32; 68 return (int)c; 69 } 70 71 public static int addBothTo(int[] x, int[] y, int[] z) 72 { 73 long c = 0; 74 c += (x[0] & M) + (y[0] & M) + (z[0] & M); 75 z[0] = (int)c; 76 c >>>= 32; 77 c += (x[1] & M) + (y[1] & M) + (z[1] & M); 78 z[1] = (int)c; 79 c >>>= 32; 80 c += (x[2] & M) + (y[2] & M) + (z[2] & M); 81 z[2] = (int)c; 82 c >>>= 32; 83 c += (x[3] & M) + (y[3] & M) + (z[3] & M); 84 z[3] = (int)c; 85 c >>>= 32; 86 c += (x[4] & M) + (y[4] & M) + (z[4] & M); 87 z[4] = (int)c; 88 c >>>= 32; 89 c += (x[5] & M) + (y[5] & M) + (z[5] & M); 90 z[5] = (int)c; 91 c >>>= 32; 92 c += (x[6] & M) + (y[6] & M) + (z[6] & M); 93 z[6] = (int)c; 94 c >>>= 32; 95 c += (x[7] & M) + (y[7] & M) + (z[7] & M); 96 z[7] = (int)c; 97 c >>>= 32; 98 return (int)c; 99 } 100 101 public static int addBothTo(int[] x, int xOff, int[] y, int yOff, int[] z, int zOff) 102 { 103 long c = 0; 104 c += (x[xOff + 0] & M) + (y[yOff + 0] & M) + (z[zOff + 0] & M); 105 z[zOff + 0] = (int)c; 106 c >>>= 32; 107 c += (x[xOff + 1] & M) + (y[yOff + 1] & M) + (z[zOff + 1] & M); 108 z[zOff + 1] = (int)c; 109 c >>>= 32; 110 c += (x[xOff + 2] & M) + (y[yOff + 2] & M) + (z[zOff + 2] & M); 111 z[zOff + 2] = (int)c; 112 c >>>= 32; 113 c += (x[xOff + 3] & M) + (y[yOff + 3] & M) + (z[zOff + 3] & M); 114 z[zOff + 3] = (int)c; 115 c >>>= 32; 116 c += (x[xOff + 4] & M) + (y[yOff + 4] & M) + (z[zOff + 4] & M); 117 z[zOff + 4] = (int)c; 118 c >>>= 32; 119 c += (x[xOff + 5] & M) + (y[yOff + 5] & M) + (z[zOff + 5] & M); 120 z[zOff + 5] = (int)c; 121 c >>>= 32; 122 c += (x[xOff + 6] & M) + (y[yOff + 6] & M) + (z[zOff + 6] & M); 123 z[zOff + 6] = (int)c; 124 c >>>= 32; 125 c += (x[xOff + 7] & M) + (y[yOff + 7] & M) + (z[zOff + 7] & M); 126 z[zOff + 7] = (int)c; 127 c >>>= 32; 128 return (int)c; 129 } 130 131 public static int addTo(int[] x, int[] z) 132 { 133 long c = 0; 134 c += (x[0] & M) + (z[0] & M); 135 z[0] = (int)c; 136 c >>>= 32; 137 c += (x[1] & M) + (z[1] & M); 138 z[1] = (int)c; 139 c >>>= 32; 140 c += (x[2] & M) + (z[2] & M); 141 z[2] = (int)c; 142 c >>>= 32; 143 c += (x[3] & M) + (z[3] & M); 144 z[3] = (int)c; 145 c >>>= 32; 146 c += (x[4] & M) + (z[4] & M); 147 z[4] = (int)c; 148 c >>>= 32; 149 c += (x[5] & M) + (z[5] & M); 150 z[5] = (int)c; 151 c >>>= 32; 152 c += (x[6] & M) + (z[6] & M); 153 z[6] = (int)c; 154 c >>>= 32; 155 c += (x[7] & M) + (z[7] & M); 156 z[7] = (int)c; 157 c >>>= 32; 158 return (int)c; 159 } 160 161 public static int addTo(int[] x, int xOff, int[] z, int zOff, int cIn) 162 { 163 long c = cIn & M; 164 c += (x[xOff + 0] & M) + (z[zOff + 0] & M); 165 z[zOff + 0] = (int)c; 166 c >>>= 32; 167 c += (x[xOff + 1] & M) + (z[zOff + 1] & M); 168 z[zOff + 1] = (int)c; 169 c >>>= 32; 170 c += (x[xOff + 2] & M) + (z[zOff + 2] & M); 171 z[zOff + 2] = (int)c; 172 c >>>= 32; 173 c += (x[xOff + 3] & M) + (z[zOff + 3] & M); 174 z[zOff + 3] = (int)c; 175 c >>>= 32; 176 c += (x[xOff + 4] & M) + (z[zOff + 4] & M); 177 z[zOff + 4] = (int)c; 178 c >>>= 32; 179 c += (x[xOff + 5] & M) + (z[zOff + 5] & M); 180 z[zOff + 5] = (int)c; 181 c >>>= 32; 182 c += (x[xOff + 6] & M) + (z[zOff + 6] & M); 183 z[zOff + 6] = (int)c; 184 c >>>= 32; 185 c += (x[xOff + 7] & M) + (z[zOff + 7] & M); 186 z[zOff + 7] = (int)c; 187 c >>>= 32; 188 return (int)c; 189 } 190 191 public static int addToEachOther(int[] u, int uOff, int[] v, int vOff) 192 { 193 long c = 0; 194 c += (u[uOff + 0] & M) + (v[vOff + 0] & M); 195 u[uOff + 0] = (int)c; 196 v[vOff + 0] = (int)c; 197 c >>>= 32; 198 c += (u[uOff + 1] & M) + (v[vOff + 1] & M); 199 u[uOff + 1] = (int)c; 200 v[vOff + 1] = (int)c; 201 c >>>= 32; 202 c += (u[uOff + 2] & M) + (v[vOff + 2] & M); 203 u[uOff + 2] = (int)c; 204 v[vOff + 2] = (int)c; 205 c >>>= 32; 206 c += (u[uOff + 3] & M) + (v[vOff + 3] & M); 207 u[uOff + 3] = (int)c; 208 v[vOff + 3] = (int)c; 209 c >>>= 32; 210 c += (u[uOff + 4] & M) + (v[vOff + 4] & M); 211 u[uOff + 4] = (int)c; 212 v[vOff + 4] = (int)c; 213 c >>>= 32; 214 c += (u[uOff + 5] & M) + (v[vOff + 5] & M); 215 u[uOff + 5] = (int)c; 216 v[vOff + 5] = (int)c; 217 c >>>= 32; 218 c += (u[uOff + 6] & M) + (v[vOff + 6] & M); 219 u[uOff + 6] = (int)c; 220 v[vOff + 6] = (int)c; 221 c >>>= 32; 222 c += (u[uOff + 7] & M) + (v[vOff + 7] & M); 223 u[uOff + 7] = (int)c; 224 v[vOff + 7] = (int)c; 225 c >>>= 32; 226 return (int)c; 227 } 228 229 public static void copy(int[] x, int[] z) 230 { 231 z[0] = x[0]; 232 z[1] = x[1]; 233 z[2] = x[2]; 234 z[3] = x[3]; 235 z[4] = x[4]; 236 z[5] = x[5]; 237 z[6] = x[6]; 238 z[7] = x[7]; 239 } 240 241 public static int[] create() 242 { 243 return new int[8]; 244 } 245 246 public static int[] createExt() 247 { 248 return new int[16]; 249 } 250 251 public static boolean diff(int[] x, int xOff, int[] y, int yOff, int[] z, int zOff) 252 { 253 boolean pos = gte(x, xOff, y, yOff); 254 if (pos) 255 { 256 sub(x, xOff, y, yOff, z, zOff); 257 } 258 else 259 { 260 sub(y, yOff, x, xOff, z, zOff); 261 } 262 return pos; 263 } 264 265 public static boolean eq(int[] x, int[] y) 266 { 267 for (int i = 7; i >= 0; --i) 268 { 269 if (x[i] != y[i]) 270 { 271 return false; 272 } 273 } 274 return true; 275 } 276 277 public static int[] fromBigInteger(BigInteger x) 278 { 279 if (x.signum() < 0 || x.bitLength() > 256) 280 { 281 throw new IllegalArgumentException(); 282 } 283 284 int[] z = create(); 285 int i = 0; 286 while (x.signum() != 0) 287 { 288 z[i++] = x.intValue(); 289 x = x.shiftRight(32); 290 } 291 return z; 292 } 293 294 public static int getBit(int[] x, int bit) 295 { 296 if (bit == 0) 297 { 298 return x[0] & 1; 299 } 300 if ((bit & 255) != bit) 301 { 302 return 0; 303 } 304 int w = bit >>> 5; 305 int b = bit & 31; 306 return (x[w] >>> b) & 1; 307 } 308 309 public static boolean gte(int[] x, int[] y) 310 { 311 for (int i = 7; i >= 0; --i) 312 { 313 int x_i = x[i] ^ Integer.MIN_VALUE; 314 int y_i = y[i] ^ Integer.MIN_VALUE; 315 if (x_i < y_i) 316 return false; 317 if (x_i > y_i) 318 return true; 319 } 320 return true; 321 } 322 323 public static boolean gte(int[] x, int xOff, int[] y, int yOff) 324 { 325 for (int i = 7; i >= 0; --i) 326 { 327 int x_i = x[xOff + i] ^ Integer.MIN_VALUE; 328 int y_i = y[yOff + i] ^ Integer.MIN_VALUE; 329 if (x_i < y_i) 330 return false; 331 if (x_i > y_i) 332 return true; 333 } 334 return true; 335 } 336 337 public static boolean isOne(int[] x) 338 { 339 if (x[0] != 1) 340 { 341 return false; 342 } 343 for (int i = 1; i < 8; ++i) 344 { 345 if (x[i] != 0) 346 { 347 return false; 348 } 349 } 350 return true; 351 } 352 353 public static boolean isZero(int[] x) 354 { 355 for (int i = 0; i < 8; ++i) 356 { 357 if (x[i] != 0) 358 { 359 return false; 360 } 361 } 362 return true; 363 } 364 365 public static void mul(int[] x, int[] y, int[] zz) 366 { 367 long y_0 = y[0] & M; 368 long y_1 = y[1] & M; 369 long y_2 = y[2] & M; 370 long y_3 = y[3] & M; 371 long y_4 = y[4] & M; 372 long y_5 = y[5] & M; 373 long y_6 = y[6] & M; 374 long y_7 = y[7] & M; 375 376 { 377 long c = 0, x_0 = x[0] & M; 378 c += x_0 * y_0; 379 zz[0] = (int)c; 380 c >>>= 32; 381 c += x_0 * y_1; 382 zz[1] = (int)c; 383 c >>>= 32; 384 c += x_0 * y_2; 385 zz[2] = (int)c; 386 c >>>= 32; 387 c += x_0 * y_3; 388 zz[3] = (int)c; 389 c >>>= 32; 390 c += x_0 * y_4; 391 zz[4] = (int)c; 392 c >>>= 32; 393 c += x_0 * y_5; 394 zz[5] = (int)c; 395 c >>>= 32; 396 c += x_0 * y_6; 397 zz[6] = (int)c; 398 c >>>= 32; 399 c += x_0 * y_7; 400 zz[7] = (int)c; 401 c >>>= 32; 402 zz[8] = (int)c; 403 } 404 405 for (int i = 1; i < 8; ++i) 406 { 407 long c = 0, x_i = x[i] & M; 408 c += x_i * y_0 + (zz[i + 0] & M); 409 zz[i + 0] = (int)c; 410 c >>>= 32; 411 c += x_i * y_1 + (zz[i + 1] & M); 412 zz[i + 1] = (int)c; 413 c >>>= 32; 414 c += x_i * y_2 + (zz[i + 2] & M); 415 zz[i + 2] = (int)c; 416 c >>>= 32; 417 c += x_i * y_3 + (zz[i + 3] & M); 418 zz[i + 3] = (int)c; 419 c >>>= 32; 420 c += x_i * y_4 + (zz[i + 4] & M); 421 zz[i + 4] = (int)c; 422 c >>>= 32; 423 c += x_i * y_5 + (zz[i + 5] & M); 424 zz[i + 5] = (int)c; 425 c >>>= 32; 426 c += x_i * y_6 + (zz[i + 6] & M); 427 zz[i + 6] = (int)c; 428 c >>>= 32; 429 c += x_i * y_7 + (zz[i + 7] & M); 430 zz[i + 7] = (int)c; 431 c >>>= 32; 432 zz[i + 8] = (int)c; 433 } 434 } 435 436 public static void mul(int[] x, int xOff, int[] y, int yOff, int[] zz, int zzOff) 437 { 438 long y_0 = y[yOff + 0] & M; 439 long y_1 = y[yOff + 1] & M; 440 long y_2 = y[yOff + 2] & M; 441 long y_3 = y[yOff + 3] & M; 442 long y_4 = y[yOff + 4] & M; 443 long y_5 = y[yOff + 5] & M; 444 long y_6 = y[yOff + 6] & M; 445 long y_7 = y[yOff + 7] & M; 446 447 { 448 long c = 0, x_0 = x[xOff + 0] & M; 449 c += x_0 * y_0; 450 zz[zzOff + 0] = (int)c; 451 c >>>= 32; 452 c += x_0 * y_1; 453 zz[zzOff + 1] = (int)c; 454 c >>>= 32; 455 c += x_0 * y_2; 456 zz[zzOff + 2] = (int)c; 457 c >>>= 32; 458 c += x_0 * y_3; 459 zz[zzOff + 3] = (int)c; 460 c >>>= 32; 461 c += x_0 * y_4; 462 zz[zzOff + 4] = (int)c; 463 c >>>= 32; 464 c += x_0 * y_5; 465 zz[zzOff + 5] = (int)c; 466 c >>>= 32; 467 c += x_0 * y_6; 468 zz[zzOff + 6] = (int)c; 469 c >>>= 32; 470 c += x_0 * y_7; 471 zz[zzOff + 7] = (int)c; 472 c >>>= 32; 473 zz[zzOff + 8] = (int)c; 474 } 475 476 for (int i = 1; i < 8; ++i) 477 { 478 ++zzOff; 479 long c = 0, x_i = x[xOff + i] & M; 480 c += x_i * y_0 + (zz[zzOff + 0] & M); 481 zz[zzOff + 0] = (int)c; 482 c >>>= 32; 483 c += x_i * y_1 + (zz[zzOff + 1] & M); 484 zz[zzOff + 1] = (int)c; 485 c >>>= 32; 486 c += x_i * y_2 + (zz[zzOff + 2] & M); 487 zz[zzOff + 2] = (int)c; 488 c >>>= 32; 489 c += x_i * y_3 + (zz[zzOff + 3] & M); 490 zz[zzOff + 3] = (int)c; 491 c >>>= 32; 492 c += x_i * y_4 + (zz[zzOff + 4] & M); 493 zz[zzOff + 4] = (int)c; 494 c >>>= 32; 495 c += x_i * y_5 + (zz[zzOff + 5] & M); 496 zz[zzOff + 5] = (int)c; 497 c >>>= 32; 498 c += x_i * y_6 + (zz[zzOff + 6] & M); 499 zz[zzOff + 6] = (int)c; 500 c >>>= 32; 501 c += x_i * y_7 + (zz[zzOff + 7] & M); 502 zz[zzOff + 7] = (int)c; 503 c >>>= 32; 504 zz[zzOff + 8] = (int)c; 505 } 506 } 507 508 public static int mulAddTo(int[] x, int[] y, int[] zz) 509 { 510 long y_0 = y[0] & M; 511 long y_1 = y[1] & M; 512 long y_2 = y[2] & M; 513 long y_3 = y[3] & M; 514 long y_4 = y[4] & M; 515 long y_5 = y[5] & M; 516 long y_6 = y[6] & M; 517 long y_7 = y[7] & M; 518 519 long zc = 0; 520 for (int i = 0; i < 8; ++i) 521 { 522 long c = 0, x_i = x[i] & M; 523 c += x_i * y_0 + (zz[i + 0] & M); 524 zz[i + 0] = (int)c; 525 c >>>= 32; 526 c += x_i * y_1 + (zz[i + 1] & M); 527 zz[i + 1] = (int)c; 528 c >>>= 32; 529 c += x_i * y_2 + (zz[i + 2] & M); 530 zz[i + 2] = (int)c; 531 c >>>= 32; 532 c += x_i * y_3 + (zz[i + 3] & M); 533 zz[i + 3] = (int)c; 534 c >>>= 32; 535 c += x_i * y_4 + (zz[i + 4] & M); 536 zz[i + 4] = (int)c; 537 c >>>= 32; 538 c += x_i * y_5 + (zz[i + 5] & M); 539 zz[i + 5] = (int)c; 540 c >>>= 32; 541 c += x_i * y_6 + (zz[i + 6] & M); 542 zz[i + 6] = (int)c; 543 c >>>= 32; 544 c += x_i * y_7 + (zz[i + 7] & M); 545 zz[i + 7] = (int)c; 546 c >>>= 32; 547 c += zc + (zz[i + 8] & M); 548 zz[i + 8] = (int)c; 549 zc = c >>> 32; 550 } 551 return (int)zc; 552 } 553 554 public static int mulAddTo(int[] x, int xOff, int[] y, int yOff, int[] zz, int zzOff) 555 { 556 long y_0 = y[yOff + 0] & M; 557 long y_1 = y[yOff + 1] & M; 558 long y_2 = y[yOff + 2] & M; 559 long y_3 = y[yOff + 3] & M; 560 long y_4 = y[yOff + 4] & M; 561 long y_5 = y[yOff + 5] & M; 562 long y_6 = y[yOff + 6] & M; 563 long y_7 = y[yOff + 7] & M; 564 565 long zc = 0; 566 for (int i = 0; i < 8; ++i) 567 { 568 long c = 0, x_i = x[xOff + i] & M; 569 c += x_i * y_0 + (zz[zzOff + 0] & M); 570 zz[zzOff + 0] = (int)c; 571 c >>>= 32; 572 c += x_i * y_1 + (zz[zzOff + 1] & M); 573 zz[zzOff + 1] = (int)c; 574 c >>>= 32; 575 c += x_i * y_2 + (zz[zzOff + 2] & M); 576 zz[zzOff + 2] = (int)c; 577 c >>>= 32; 578 c += x_i * y_3 + (zz[zzOff + 3] & M); 579 zz[zzOff + 3] = (int)c; 580 c >>>= 32; 581 c += x_i * y_4 + (zz[zzOff + 4] & M); 582 zz[zzOff + 4] = (int)c; 583 c >>>= 32; 584 c += x_i * y_5 + (zz[zzOff + 5] & M); 585 zz[zzOff + 5] = (int)c; 586 c >>>= 32; 587 c += x_i * y_6 + (zz[zzOff + 6] & M); 588 zz[zzOff + 6] = (int)c; 589 c >>>= 32; 590 c += x_i * y_7 + (zz[zzOff + 7] & M); 591 zz[zzOff + 7] = (int)c; 592 c >>>= 32; 593 c += zc + (zz[zzOff + 8] & M); 594 zz[zzOff + 8] = (int)c; 595 zc = c >>> 32; 596 ++zzOff; 597 } 598 return (int)zc; 599 } 600 601 public static long mul33Add(int w, int[] x, int xOff, int[] y, int yOff, int[] z, int zOff) 602 { 603 // assert w >>> 31 == 0; 604 605 long c = 0, wVal = w & M; 606 long x0 = x[xOff + 0] & M; 607 c += wVal * x0 + (y[yOff + 0] & M); 608 z[zOff + 0] = (int)c; 609 c >>>= 32; 610 long x1 = x[xOff + 1] & M; 611 c += wVal * x1 + x0 + (y[yOff + 1] & M); 612 z[zOff + 1] = (int)c; 613 c >>>= 32; 614 long x2 = x[xOff + 2] & M; 615 c += wVal * x2 + x1 + (y[yOff + 2] & M); 616 z[zOff + 2] = (int)c; 617 c >>>= 32; 618 long x3 = x[xOff + 3] & M; 619 c += wVal * x3 + x2 + (y[yOff + 3] & M); 620 z[zOff + 3] = (int)c; 621 c >>>= 32; 622 long x4 = x[xOff + 4] & M; 623 c += wVal * x4 + x3 + (y[yOff + 4] & M); 624 z[zOff + 4] = (int)c; 625 c >>>= 32; 626 long x5 = x[xOff + 5] & M; 627 c += wVal * x5 + x4 + (y[yOff + 5] & M); 628 z[zOff + 5] = (int)c; 629 c >>>= 32; 630 long x6 = x[xOff + 6] & M; 631 c += wVal * x6 + x5 + (y[yOff + 6] & M); 632 z[zOff + 6] = (int)c; 633 c >>>= 32; 634 long x7 = x[xOff + 7] & M; 635 c += wVal * x7 + x6 + (y[yOff + 7] & M); 636 z[zOff + 7] = (int)c; 637 c >>>= 32; 638 c += x7; 639 return c; 640 } 641 642 public static int mulByWord(int x, int[] z) 643 { 644 long c = 0, xVal = x & M; 645 c += xVal * (z[0] & M); 646 z[0] = (int)c; 647 c >>>= 32; 648 c += xVal * (z[1] & M); 649 z[1] = (int)c; 650 c >>>= 32; 651 c += xVal * (z[2] & M); 652 z[2] = (int)c; 653 c >>>= 32; 654 c += xVal * (z[3] & M); 655 z[3] = (int)c; 656 c >>>= 32; 657 c += xVal * (z[4] & M); 658 z[4] = (int)c; 659 c >>>= 32; 660 c += xVal * (z[5] & M); 661 z[5] = (int)c; 662 c >>>= 32; 663 c += xVal * (z[6] & M); 664 z[6] = (int)c; 665 c >>>= 32; 666 c += xVal * (z[7] & M); 667 z[7] = (int)c; 668 c >>>= 32; 669 return (int)c; 670 } 671 672 public static int mulByWordAddTo(int x, int[] y, int[] z) 673 { 674 long c = 0, xVal = x & M; 675 c += xVal * (z[0] & M) + (y[0] & M); 676 z[0] = (int)c; 677 c >>>= 32; 678 c += xVal * (z[1] & M) + (y[1] & M); 679 z[1] = (int)c; 680 c >>>= 32; 681 c += xVal * (z[2] & M) + (y[2] & M); 682 z[2] = (int)c; 683 c >>>= 32; 684 c += xVal * (z[3] & M) + (y[3] & M); 685 z[3] = (int)c; 686 c >>>= 32; 687 c += xVal * (z[4] & M) + (y[4] & M); 688 z[4] = (int)c; 689 c >>>= 32; 690 c += xVal * (z[5] & M) + (y[5] & M); 691 z[5] = (int)c; 692 c >>>= 32; 693 c += xVal * (z[6] & M) + (y[6] & M); 694 z[6] = (int)c; 695 c >>>= 32; 696 c += xVal * (z[7] & M) + (y[7] & M); 697 z[7] = (int)c; 698 c >>>= 32; 699 return (int)c; 700 } 701 702 public static int mulWordAddTo(int x, int[] y, int yOff, int[] z, int zOff) 703 { 704 long c = 0, xVal = x & M; 705 c += xVal * (y[yOff + 0] & M) + (z[zOff + 0] & M); 706 z[zOff + 0] = (int)c; 707 c >>>= 32; 708 c += xVal * (y[yOff + 1] & M) + (z[zOff + 1] & M); 709 z[zOff + 1] = (int)c; 710 c >>>= 32; 711 c += xVal * (y[yOff + 2] & M) + (z[zOff + 2] & M); 712 z[zOff + 2] = (int)c; 713 c >>>= 32; 714 c += xVal * (y[yOff + 3] & M) + (z[zOff + 3] & M); 715 z[zOff + 3] = (int)c; 716 c >>>= 32; 717 c += xVal * (y[yOff + 4] & M) + (z[zOff + 4] & M); 718 z[zOff + 4] = (int)c; 719 c >>>= 32; 720 c += xVal * (y[yOff + 5] & M) + (z[zOff + 5] & M); 721 z[zOff + 5] = (int)c; 722 c >>>= 32; 723 c += xVal * (y[yOff + 6] & M) + (z[zOff + 6] & M); 724 z[zOff + 6] = (int)c; 725 c >>>= 32; 726 c += xVal * (y[yOff + 7] & M) + (z[zOff + 7] & M); 727 z[zOff + 7] = (int)c; 728 c >>>= 32; 729 return (int)c; 730 } 731 732 public static int mul33DWordAdd(int x, long y, int[] z, int zOff) 733 { 734 // assert x >>> 31 == 0; 735 // assert zOff <= 4; 736 737 long c = 0, xVal = x & M; 738 long y00 = y & M; 739 c += xVal * y00 + (z[zOff + 0] & M); 740 z[zOff + 0] = (int)c; 741 c >>>= 32; 742 long y01 = y >>> 32; 743 c += xVal * y01 + y00 + (z[zOff + 1] & M); 744 z[zOff + 1] = (int)c; 745 c >>>= 32; 746 c += y01 + (z[zOff + 2] & M); 747 z[zOff + 2] = (int)c; 748 c >>>= 32; 749 c += (z[zOff + 3] & M); 750 z[zOff + 3] = (int)c; 751 c >>>= 32; 752 return c == 0 ? 0 : Nat.incAt(8, z, zOff, 4); 753 } 754 755 public static int mul33WordAdd(int x, int y, int[] z, int zOff) 756 { 757 // assert x >>> 31 == 0; 758 // assert zOff <= 5; 759 760 long c = 0, xVal = x & M, yVal = y & M; 761 c += yVal * xVal + (z[zOff + 0] & M); 762 z[zOff + 0] = (int)c; 763 c >>>= 32; 764 c += yVal + (z[zOff + 1] & M); 765 z[zOff + 1] = (int)c; 766 c >>>= 32; 767 c += (z[zOff + 2] & M); 768 z[zOff + 2] = (int)c; 769 c >>>= 32; 770 return c == 0 ? 0 : Nat.incAt(8, z, zOff, 3); 771 } 772 773 public static int mulWordDwordAdd(int x, long y, int[] z, int zOff) 774 { 775 // assert zOff <= 5; 776 long c = 0, xVal = x & M; 777 c += xVal * (y & M) + (z[zOff + 0] & M); 778 z[zOff + 0] = (int)c; 779 c >>>= 32; 780 c += xVal * (y >>> 32) + (z[zOff + 1] & M); 781 z[zOff + 1] = (int)c; 782 c >>>= 32; 783 c += (z[zOff + 2] & M); 784 z[zOff + 2] = (int)c; 785 c >>>= 32; 786 return c == 0 ? 0 : Nat.incAt(8, z, zOff, 3); 787 } 788 789 public static int mulWord(int x, int[] y, int[] z, int zOff) 790 { 791 long c = 0, xVal = x & M; 792 int i = 0; 793 do 794 { 795 c += xVal * (y[i] & M); 796 z[zOff + i] = (int)c; 797 c >>>= 32; 798 } 799 while (++i < 8); 800 return (int)c; 801 } 802 803 public static void square(int[] x, int[] zz) 804 { 805 long x_0 = x[0] & M; 806 long zz_1; 807 808 int c = 0, w; 809 { 810 int i = 7, j = 16; 811 do 812 { 813 long xVal = (x[i--] & M); 814 long p = xVal * xVal; 815 zz[--j] = (c << 31) | (int)(p >>> 33); 816 zz[--j] = (int)(p >>> 1); 817 c = (int)p; 818 } 819 while (i > 0); 820 821 { 822 long p = x_0 * x_0; 823 zz_1 = ((c << 31) & M) | (p >>> 33); 824 zz[0] = (int)p; 825 c = (int)(p >>> 32) & 1; 826 } 827 } 828 829 long x_1 = x[1] & M; 830 long zz_2 = zz[2] & M; 831 832 { 833 zz_1 += x_1 * x_0; 834 w = (int)zz_1; 835 zz[1] = (w << 1) | c; 836 c = w >>> 31; 837 zz_2 += zz_1 >>> 32; 838 } 839 840 long x_2 = x[2] & M; 841 long zz_3 = zz[3] & M; 842 long zz_4 = zz[4] & M; 843 { 844 zz_2 += x_2 * x_0; 845 w = (int)zz_2; 846 zz[2] = (w << 1) | c; 847 c = w >>> 31; 848 zz_3 += (zz_2 >>> 32) + x_2 * x_1; 849 zz_4 += zz_3 >>> 32; 850 zz_3 &= M; 851 } 852 853 long x_3 = x[3] & M; 854 long zz_5 = zz[5] & M; 855 long zz_6 = zz[6] & M; 856 { 857 zz_3 += x_3 * x_0; 858 w = (int)zz_3; 859 zz[3] = (w << 1) | c; 860 c = w >>> 31; 861 zz_4 += (zz_3 >>> 32) + x_3 * x_1; 862 zz_5 += (zz_4 >>> 32) + x_3 * x_2; 863 zz_4 &= M; 864 zz_6 += zz_5 >>> 32; 865 zz_5 &= M; 866 } 867 868 long x_4 = x[4] & M; 869 long zz_7 = zz[7] & M; 870 long zz_8 = zz[8] & M; 871 { 872 zz_4 += x_4 * x_0; 873 w = (int)zz_4; 874 zz[4] = (w << 1) | c; 875 c = w >>> 31; 876 zz_5 += (zz_4 >>> 32) + x_4 * x_1; 877 zz_6 += (zz_5 >>> 32) + x_4 * x_2; 878 zz_5 &= M; 879 zz_7 += (zz_6 >>> 32) + x_4 * x_3; 880 zz_6 &= M; 881 zz_8 += zz_7 >>> 32; 882 zz_7 &= M; 883 } 884 885 long x_5 = x[5] & M; 886 long zz_9 = zz[9] & M; 887 long zz_10 = zz[10] & M; 888 { 889 zz_5 += x_5 * x_0; 890 w = (int)zz_5; 891 zz[5] = (w << 1) | c; 892 c = w >>> 31; 893 zz_6 += (zz_5 >>> 32) + x_5 * x_1; 894 zz_7 += (zz_6 >>> 32) + x_5 * x_2; 895 zz_6 &= M; 896 zz_8 += (zz_7 >>> 32) + x_5 * x_3; 897 zz_7 &= M; 898 zz_9 += (zz_8 >>> 32) + x_5 * x_4; 899 zz_8 &= M; 900 zz_10 += zz_9 >>> 32; 901 zz_9 &= M; 902 } 903 904 long x_6 = x[6] & M; 905 long zz_11 = zz[11] & M; 906 long zz_12 = zz[12] & M; 907 { 908 zz_6 += x_6 * x_0; 909 w = (int)zz_6; 910 zz[6] = (w << 1) | c; 911 c = w >>> 31; 912 zz_7 += (zz_6 >>> 32) + x_6 * x_1; 913 zz_8 += (zz_7 >>> 32) + x_6 * x_2; 914 zz_7 &= M; 915 zz_9 += (zz_8 >>> 32) + x_6 * x_3; 916 zz_8 &= M; 917 zz_10 += (zz_9 >>> 32) + x_6 * x_4; 918 zz_9 &= M; 919 zz_11 += (zz_10 >>> 32) + x_6 * x_5; 920 zz_10 &= M; 921 zz_12 += zz_11 >>> 32; 922 zz_11 &= M; 923 } 924 925 long x_7 = x[7] & M; 926 long zz_13 = zz[13] & M; 927 long zz_14 = zz[14] & M; 928 { 929 zz_7 += x_7 * x_0; 930 w = (int)zz_7; 931 zz[7] = (w << 1) | c; 932 c = w >>> 31; 933 zz_8 += (zz_7 >>> 32) + x_7 * x_1; 934 zz_9 += (zz_8 >>> 32) + x_7 * x_2; 935 zz_10 += (zz_9 >>> 32) + x_7 * x_3; 936 zz_11 += (zz_10 >>> 32) + x_7 * x_4; 937 zz_12 += (zz_11 >>> 32) + x_7 * x_5; 938 zz_13 += (zz_12 >>> 32) + x_7 * x_6; 939 zz_14 += zz_13 >>> 32; 940 } 941 942 w = (int)zz_8; 943 zz[8] = (w << 1) | c; 944 c = w >>> 31; 945 w = (int)zz_9; 946 zz[9] = (w << 1) | c; 947 c = w >>> 31; 948 w = (int)zz_10; 949 zz[10] = (w << 1) | c; 950 c = w >>> 31; 951 w = (int)zz_11; 952 zz[11] = (w << 1) | c; 953 c = w >>> 31; 954 w = (int)zz_12; 955 zz[12] = (w << 1) | c; 956 c = w >>> 31; 957 w = (int)zz_13; 958 zz[13] = (w << 1) | c; 959 c = w >>> 31; 960 w = (int)zz_14; 961 zz[14] = (w << 1) | c; 962 c = w >>> 31; 963 w = zz[15] + (int)(zz_14 >> 32); 964 zz[15] = (w << 1) | c; 965 } 966 967 public static void square(int[] x, int xOff, int[] zz, int zzOff) 968 { 969 long x_0 = x[xOff + 0] & M; 970 long zz_1; 971 972 int c = 0, w; 973 { 974 int i = 7, j = 16; 975 do 976 { 977 long xVal = (x[xOff + i--] & M); 978 long p = xVal * xVal; 979 zz[zzOff + --j] = (c << 31) | (int)(p >>> 33); 980 zz[zzOff + --j] = (int)(p >>> 1); 981 c = (int)p; 982 } 983 while (i > 0); 984 985 { 986 long p = x_0 * x_0; 987 zz_1 = ((c << 31) & M) | (p >>> 33); 988 zz[zzOff + 0] = (int)p; 989 c = (int)(p >>> 32) & 1; 990 } 991 } 992 993 long x_1 = x[xOff + 1] & M; 994 long zz_2 = zz[zzOff + 2] & M; 995 996 { 997 zz_1 += x_1 * x_0; 998 w = (int)zz_1; 999 zz[zzOff + 1] = (w << 1) | c; 1000 c = w >>> 31; 1001 zz_2 += zz_1 >>> 32; 1002 } 1003 1004 long x_2 = x[xOff + 2] & M; 1005 long zz_3 = zz[zzOff + 3] & M; 1006 long zz_4 = zz[zzOff + 4] & M; 1007 { 1008 zz_2 += x_2 * x_0; 1009 w = (int)zz_2; 1010 zz[zzOff + 2] = (w << 1) | c; 1011 c = w >>> 31; 1012 zz_3 += (zz_2 >>> 32) + x_2 * x_1; 1013 zz_4 += zz_3 >>> 32; 1014 zz_3 &= M; 1015 } 1016 1017 long x_3 = x[xOff + 3] & M; 1018 long zz_5 = zz[zzOff + 5] & M; 1019 long zz_6 = zz[zzOff + 6] & M; 1020 { 1021 zz_3 += x_3 * x_0; 1022 w = (int)zz_3; 1023 zz[zzOff + 3] = (w << 1) | c; 1024 c = w >>> 31; 1025 zz_4 += (zz_3 >>> 32) + x_3 * x_1; 1026 zz_5 += (zz_4 >>> 32) + x_3 * x_2; 1027 zz_4 &= M; 1028 zz_6 += zz_5 >>> 32; 1029 zz_5 &= M; 1030 } 1031 1032 long x_4 = x[xOff + 4] & M; 1033 long zz_7 = zz[zzOff + 7] & M; 1034 long zz_8 = zz[zzOff + 8] & M; 1035 { 1036 zz_4 += x_4 * x_0; 1037 w = (int)zz_4; 1038 zz[zzOff + 4] = (w << 1) | c; 1039 c = w >>> 31; 1040 zz_5 += (zz_4 >>> 32) + x_4 * x_1; 1041 zz_6 += (zz_5 >>> 32) + x_4 * x_2; 1042 zz_5 &= M; 1043 zz_7 += (zz_6 >>> 32) + x_4 * x_3; 1044 zz_6 &= M; 1045 zz_8 += zz_7 >>> 32; 1046 zz_7 &= M; 1047 } 1048 1049 long x_5 = x[xOff + 5] & M; 1050 long zz_9 = zz[zzOff + 9] & M; 1051 long zz_10 = zz[zzOff + 10] & M; 1052 { 1053 zz_5 += x_5 * x_0; 1054 w = (int)zz_5; 1055 zz[zzOff + 5] = (w << 1) | c; 1056 c = w >>> 31; 1057 zz_6 += (zz_5 >>> 32) + x_5 * x_1; 1058 zz_7 += (zz_6 >>> 32) + x_5 * x_2; 1059 zz_6 &= M; 1060 zz_8 += (zz_7 >>> 32) + x_5 * x_3; 1061 zz_7 &= M; 1062 zz_9 += (zz_8 >>> 32) + x_5 * x_4; 1063 zz_8 &= M; 1064 zz_10 += zz_9 >>> 32; 1065 zz_9 &= M; 1066 } 1067 1068 long x_6 = x[xOff + 6] & M; 1069 long zz_11 = zz[zzOff + 11] & M; 1070 long zz_12 = zz[zzOff + 12] & M; 1071 { 1072 zz_6 += x_6 * x_0; 1073 w = (int)zz_6; 1074 zz[zzOff + 6] = (w << 1) | c; 1075 c = w >>> 31; 1076 zz_7 += (zz_6 >>> 32) + x_6 * x_1; 1077 zz_8 += (zz_7 >>> 32) + x_6 * x_2; 1078 zz_7 &= M; 1079 zz_9 += (zz_8 >>> 32) + x_6 * x_3; 1080 zz_8 &= M; 1081 zz_10 += (zz_9 >>> 32) + x_6 * x_4; 1082 zz_9 &= M; 1083 zz_11 += (zz_10 >>> 32) + x_6 * x_5; 1084 zz_10 &= M; 1085 zz_12 += zz_11 >>> 32; 1086 zz_11 &= M; 1087 } 1088 1089 long x_7 = x[xOff + 7] & M; 1090 long zz_13 = zz[zzOff + 13] & M; 1091 long zz_14 = zz[zzOff + 14] & M; 1092 { 1093 zz_7 += x_7 * x_0; 1094 w = (int)zz_7; 1095 zz[zzOff + 7] = (w << 1) | c; 1096 c = w >>> 31; 1097 zz_8 += (zz_7 >>> 32) + x_7 * x_1; 1098 zz_9 += (zz_8 >>> 32) + x_7 * x_2; 1099 zz_10 += (zz_9 >>> 32) + x_7 * x_3; 1100 zz_11 += (zz_10 >>> 32) + x_7 * x_4; 1101 zz_12 += (zz_11 >>> 32) + x_7 * x_5; 1102 zz_13 += (zz_12 >>> 32) + x_7 * x_6; 1103 zz_14 += zz_13 >>> 32; 1104 } 1105 1106 w = (int)zz_8; 1107 zz[zzOff + 8] = (w << 1) | c; 1108 c = w >>> 31; 1109 w = (int)zz_9; 1110 zz[zzOff + 9] = (w << 1) | c; 1111 c = w >>> 31; 1112 w = (int)zz_10; 1113 zz[zzOff + 10] = (w << 1) | c; 1114 c = w >>> 31; 1115 w = (int)zz_11; 1116 zz[zzOff + 11] = (w << 1) | c; 1117 c = w >>> 31; 1118 w = (int)zz_12; 1119 zz[zzOff + 12] = (w << 1) | c; 1120 c = w >>> 31; 1121 w = (int)zz_13; 1122 zz[zzOff + 13] = (w << 1) | c; 1123 c = w >>> 31; 1124 w = (int)zz_14; 1125 zz[zzOff + 14] = (w << 1) | c; 1126 c = w >>> 31; 1127 w = zz[zzOff + 15] + (int)(zz_14 >> 32); 1128 zz[zzOff + 15] = (w << 1) | c; 1129 } 1130 1131 public static int sub(int[] x, int[] y, int[] z) 1132 { 1133 long c = 0; 1134 c += (x[0] & M) - (y[0] & M); 1135 z[0] = (int)c; 1136 c >>= 32; 1137 c += (x[1] & M) - (y[1] & M); 1138 z[1] = (int)c; 1139 c >>= 32; 1140 c += (x[2] & M) - (y[2] & M); 1141 z[2] = (int)c; 1142 c >>= 32; 1143 c += (x[3] & M) - (y[3] & M); 1144 z[3] = (int)c; 1145 c >>= 32; 1146 c += (x[4] & M) - (y[4] & M); 1147 z[4] = (int)c; 1148 c >>= 32; 1149 c += (x[5] & M) - (y[5] & M); 1150 z[5] = (int)c; 1151 c >>= 32; 1152 c += (x[6] & M) - (y[6] & M); 1153 z[6] = (int)c; 1154 c >>= 32; 1155 c += (x[7] & M) - (y[7] & M); 1156 z[7] = (int)c; 1157 c >>= 32; 1158 return (int)c; 1159 } 1160 1161 public static int sub(int[] x, int xOff, int[] y, int yOff, int[] z, int zOff) 1162 { 1163 long c = 0; 1164 c += (x[xOff + 0] & M) - (y[yOff + 0] & M); 1165 z[zOff + 0] = (int)c; 1166 c >>= 32; 1167 c += (x[xOff + 1] & M) - (y[yOff + 1] & M); 1168 z[zOff + 1] = (int)c; 1169 c >>= 32; 1170 c += (x[xOff + 2] & M) - (y[yOff + 2] & M); 1171 z[zOff + 2] = (int)c; 1172 c >>= 32; 1173 c += (x[xOff + 3] & M) - (y[yOff + 3] & M); 1174 z[zOff + 3] = (int)c; 1175 c >>= 32; 1176 c += (x[xOff + 4] & M) - (y[yOff + 4] & M); 1177 z[zOff + 4] = (int)c; 1178 c >>= 32; 1179 c += (x[xOff + 5] & M) - (y[yOff + 5] & M); 1180 z[zOff + 5] = (int)c; 1181 c >>= 32; 1182 c += (x[xOff + 6] & M) - (y[yOff + 6] & M); 1183 z[zOff + 6] = (int)c; 1184 c >>= 32; 1185 c += (x[xOff + 7] & M) - (y[yOff + 7] & M); 1186 z[zOff + 7] = (int)c; 1187 c >>= 32; 1188 return (int)c; 1189 } 1190 1191 public static int subBothFrom(int[] x, int[] y, int[] z) 1192 { 1193 long c = 0; 1194 c += (z[0] & M) - (x[0] & M) - (y[0] & M); 1195 z[0] = (int)c; 1196 c >>= 32; 1197 c += (z[1] & M) - (x[1] & M) - (y[1] & M); 1198 z[1] = (int)c; 1199 c >>= 32; 1200 c += (z[2] & M) - (x[2] & M) - (y[2] & M); 1201 z[2] = (int)c; 1202 c >>= 32; 1203 c += (z[3] & M) - (x[3] & M) - (y[3] & M); 1204 z[3] = (int)c; 1205 c >>= 32; 1206 c += (z[4] & M) - (x[4] & M) - (y[4] & M); 1207 z[4] = (int)c; 1208 c >>= 32; 1209 c += (z[5] & M) - (x[5] & M) - (y[5] & M); 1210 z[5] = (int)c; 1211 c >>= 32; 1212 c += (z[6] & M) - (x[6] & M) - (y[6] & M); 1213 z[6] = (int)c; 1214 c >>= 32; 1215 c += (z[7] & M) - (x[7] & M) - (y[7] & M); 1216 z[7] = (int)c; 1217 c >>= 32; 1218 return (int)c; 1219 } 1220 1221 public static int subFrom(int[] x, int[] z) 1222 { 1223 long c = 0; 1224 c += (z[0] & M) - (x[0] & M); 1225 z[0] = (int)c; 1226 c >>= 32; 1227 c += (z[1] & M) - (x[1] & M); 1228 z[1] = (int)c; 1229 c >>= 32; 1230 c += (z[2] & M) - (x[2] & M); 1231 z[2] = (int)c; 1232 c >>= 32; 1233 c += (z[3] & M) - (x[3] & M); 1234 z[3] = (int)c; 1235 c >>= 32; 1236 c += (z[4] & M) - (x[4] & M); 1237 z[4] = (int)c; 1238 c >>= 32; 1239 c += (z[5] & M) - (x[5] & M); 1240 z[5] = (int)c; 1241 c >>= 32; 1242 c += (z[6] & M) - (x[6] & M); 1243 z[6] = (int)c; 1244 c >>= 32; 1245 c += (z[7] & M) - (x[7] & M); 1246 z[7] = (int)c; 1247 c >>= 32; 1248 return (int)c; 1249 } 1250 1251 public static int subFrom(int[] x, int xOff, int[] z, int zOff) 1252 { 1253 long c = 0; 1254 c += (z[zOff + 0] & M) - (x[xOff + 0] & M); 1255 z[zOff + 0] = (int)c; 1256 c >>= 32; 1257 c += (z[zOff + 1] & M) - (x[xOff + 1] & M); 1258 z[zOff + 1] = (int)c; 1259 c >>= 32; 1260 c += (z[zOff + 2] & M) - (x[xOff + 2] & M); 1261 z[zOff + 2] = (int)c; 1262 c >>= 32; 1263 c += (z[zOff + 3] & M) - (x[xOff + 3] & M); 1264 z[zOff + 3] = (int)c; 1265 c >>= 32; 1266 c += (z[zOff + 4] & M) - (x[xOff + 4] & M); 1267 z[zOff + 4] = (int)c; 1268 c >>= 32; 1269 c += (z[zOff + 5] & M) - (x[xOff + 5] & M); 1270 z[zOff + 5] = (int)c; 1271 c >>= 32; 1272 c += (z[zOff + 6] & M) - (x[xOff + 6] & M); 1273 z[zOff + 6] = (int)c; 1274 c >>= 32; 1275 c += (z[zOff + 7] & M) - (x[xOff + 7] & M); 1276 z[zOff + 7] = (int)c; 1277 c >>= 32; 1278 return (int)c; 1279 } 1280 1281 public static BigInteger toBigInteger(int[] x) 1282 { 1283 byte[] bs = new byte[32]; 1284 for (int i = 0; i < 8; ++i) 1285 { 1286 int x_i = x[i]; 1287 if (x_i != 0) 1288 { 1289 Pack.intToBigEndian(x_i, bs, (7 - i) << 2); 1290 } 1291 } 1292 return new BigInteger(1, bs); 1293 } 1294 1295 public static void zero(int[] z) 1296 { 1297 z[0] = 0; 1298 z[1] = 0; 1299 z[2] = 0; 1300 z[3] = 0; 1301 z[4] = 0; 1302 z[5] = 0; 1303 z[6] = 0; 1304 z[7] = 0; 1305 } 1306 } 1307
