1 /* 2 * Copyright (c) 1996, 2011, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. Oracle designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Oracle in the LICENSE file that accompanied this code. 10 * 11 * This code is distributed in the hope that it will be useful, but WITHOUT 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 * version 2 for more details (a copy is included in the LICENSE file that 15 * accompanied this code). 16 * 17 * You should have received a copy of the GNU General Public License version 18 * 2 along with this work; if not, write to the Free Software Foundation, 19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 20 * 21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22 * or visit www.oracle.com if you need additional information or have any 23 * questions. 24 */ 25 26 /* 27 * Portions Copyright (c) 1995 Colin Plumb. All rights reserved. 28 */ 29 30 package java.math; 31 32 import java.util.Random; 33 import java.io.*; 34 35 /** 36 * Immutable arbitrary-precision integers. All operations behave as if 37 * BigIntegers were represented in two's-complement notation (like Java's 38 * primitive integer types). BigInteger provides analogues to all of Java's 39 * primitive integer operators, and all relevant methods from java.lang.Math. 40 * Additionally, BigInteger provides operations for modular arithmetic, GCD 41 * calculation, primality testing, prime generation, bit manipulation, 42 * and a few other miscellaneous operations. 43 * 44 * <p>Semantics of arithmetic operations exactly mimic those of Java's integer 45 * arithmetic operators, as defined in <i>The Java Language Specification</i>. 46 * For example, division by zero throws an {@code ArithmeticException}, and 47 * division of a negative by a positive yields a negative (or zero) remainder. 48 * All of the details in the Spec concerning overflow are ignored, as 49 * BigIntegers are made as large as necessary to accommodate the results of an 50 * operation. 51 * 52 * <p>Semantics of shift operations extend those of Java's shift operators 53 * to allow for negative shift distances. A right-shift with a negative 54 * shift distance results in a left shift, and vice-versa. The unsigned 55 * right shift operator ({@code >>>}) is omitted, as this operation makes 56 * little sense in combination with the "infinite word size" abstraction 57 * provided by this class. 58 * 59 * <p>Semantics of bitwise logical operations exactly mimic those of Java's 60 * bitwise integer operators. The binary operators ({@code and}, 61 * {@code or}, {@code xor}) implicitly perform sign extension on the shorter 62 * of the two operands prior to performing the operation. 63 * 64 * <p>Comparison operations perform signed integer comparisons, analogous to 65 * those performed by Java's relational and equality operators. 66 * 67 * <p>Modular arithmetic operations are provided to compute residues, perform 68 * exponentiation, and compute multiplicative inverses. These methods always 69 * return a non-negative result, between {@code 0} and {@code (modulus - 1)}, 70 * inclusive. 71 * 72 * <p>Bit operations operate on a single bit of the two's-complement 73 * representation of their operand. If necessary, the operand is sign- 74 * extended so that it contains the designated bit. None of the single-bit 75 * operations can produce a BigInteger with a different sign from the 76 * BigInteger being operated on, as they affect only a single bit, and the 77 * "infinite word size" abstraction provided by this class ensures that there 78 * are infinitely many "virtual sign bits" preceding each BigInteger. 79 * 80 * <p>For the sake of brevity and clarity, pseudo-code is used throughout the 81 * descriptions of BigInteger methods. The pseudo-code expression 82 * {@code (i + j)} is shorthand for "a BigInteger whose value is 83 * that of the BigInteger {@code i} plus that of the BigInteger {@code j}." 84 * The pseudo-code expression {@code (i == j)} is shorthand for 85 * "{@code true} if and only if the BigInteger {@code i} represents the same 86 * value as the BigInteger {@code j}." Other pseudo-code expressions are 87 * interpreted similarly. 88 * 89 * <p>All methods and constructors in this class throw 90 * {@code NullPointerException} when passed 91 * a null object reference for any input parameter. 92 * 93 * @see BigDecimal 94 * @author Josh Bloch 95 * @author Michael McCloskey 96 * @since JDK1.1 97 */ 98 99 public class BigInteger extends Number implements Comparable<BigInteger> { 100 /** 101 * The signum of this BigInteger: -1 for negative, 0 for zero, or 102 * 1 for positive. Note that the BigInteger zero <i>must</i> have 103 * a signum of 0. This is necessary to ensures that there is exactly one 104 * representation for each BigInteger value. 105 * 106 * @serial 107 */ 108 final int signum; 109 110 /** 111 * The magnitude of this BigInteger, in <i>big-endian</i> order: the 112 * zeroth element of this array is the most-significant int of the 113 * magnitude. The magnitude must be "minimal" in that the most-significant 114 * int ({@code mag[0]}) must be non-zero. This is necessary to 115 * ensure that there is exactly one representation for each BigInteger 116 * value. Note that this implies that the BigInteger zero has a 117 * zero-length mag array. 118 */ 119 final int[] mag; 120 121 // These "redundant fields" are initialized with recognizable nonsense 122 // values, and cached the first time they are needed (or never, if they 123 // aren't needed). 124 125 /** 126 * One plus the bitCount of this BigInteger. Zeros means unitialized. 127 * 128 * @serial 129 * @see #bitCount 130 * @deprecated Deprecated since logical value is offset from stored 131 * value and correction factor is applied in accessor method. 132 */ 133 @Deprecated 134 private int bitCount; 135 136 /** 137 * One plus the bitLength of this BigInteger. Zeros means unitialized. 138 * (either value is acceptable). 139 * 140 * @serial 141 * @see #bitLength() 142 * @deprecated Deprecated since logical value is offset from stored 143 * value and correction factor is applied in accessor method. 144 */ 145 @Deprecated 146 private int bitLength; 147 148 /** 149 * Two plus the lowest set bit of this BigInteger, as returned by 150 * getLowestSetBit(). 151 * 152 * @serial 153 * @see #getLowestSetBit 154 * @deprecated Deprecated since logical value is offset from stored 155 * value and correction factor is applied in accessor method. 156 */ 157 @Deprecated 158 private int lowestSetBit; 159 160 /** 161 * Two plus the index of the lowest-order int in the magnitude of this 162 * BigInteger that contains a nonzero int, or -2 (either value is acceptable). 163 * The least significant int has int-number 0, the next int in order of 164 * increasing significance has int-number 1, and so forth. 165 * @deprecated Deprecated since logical value is offset from stored 166 * value and correction factor is applied in accessor method. 167 */ 168 @Deprecated 169 private int firstNonzeroIntNum; 170 171 /** 172 * This mask is used to obtain the value of an int as if it were unsigned. 173 */ 174 final static long LONG_MASK = 0xffffffffL; 175 176 //Constructors 177 178 /** 179 * Translates a byte array containing the two's-complement binary 180 * representation of a BigInteger into a BigInteger. The input array is 181 * assumed to be in <i>big-endian</i> byte-order: the most significant 182 * byte is in the zeroth element. 183 * 184 * @param val big-endian two's-complement binary representation of 185 * BigInteger. 186 * @throws NumberFormatException {@code val} is zero bytes long. 187 */ 188 public BigInteger(byte[] val) { 189 if (val.length == 0) 190 throw new NumberFormatException("Zero length BigInteger"); 191 192 if (val[0] < 0) { 193 mag = makePositive(val); 194 signum = -1; 195 } else { 196 mag = stripLeadingZeroBytes(val); 197 signum = (mag.length == 0 ? 0 : 1); 198 } 199 } 200 201 /** 202 * This private constructor translates an int array containing the 203 * two's-complement binary representation of a BigInteger into a 204 * BigInteger. The input array is assumed to be in <i>big-endian</i> 205 * int-order: the most significant int is in the zeroth element. 206 */ 207 private BigInteger(int[] val) { 208 if (val.length == 0) 209 throw new NumberFormatException("Zero length BigInteger"); 210 211 if (val[0] < 0) { 212 mag = makePositive(val); 213 signum = -1; 214 } else { 215 mag = trustedStripLeadingZeroInts(val); 216 signum = (mag.length == 0 ? 0 : 1); 217 } 218 } 219 220 /** 221 * Translates the sign-magnitude representation of a BigInteger into a 222 * BigInteger. The sign is represented as an integer signum value: -1 for 223 * negative, 0 for zero, or 1 for positive. The magnitude is a byte array 224 * in <i>big-endian</i> byte-order: the most significant byte is in the 225 * zeroth element. A zero-length magnitude array is permissible, and will 226 * result in a BigInteger value of 0, whether signum is -1, 0 or 1. 227 * 228 * @param signum signum of the number (-1 for negative, 0 for zero, 1 229 * for positive). 230 * @param magnitude big-endian binary representation of the magnitude of 231 * the number. 232 * @throws NumberFormatException {@code signum} is not one of the three 233 * legal values (-1, 0, and 1), or {@code signum} is 0 and 234 * {@code magnitude} contains one or more non-zero bytes. 235 */ 236 public BigInteger(int signum, byte[] magnitude) { 237 this.mag = stripLeadingZeroBytes(magnitude); 238 239 if (signum < -1 || signum > 1) 240 throw(new NumberFormatException("Invalid signum value")); 241 242 if (this.mag.length==0) { 243 this.signum = 0; 244 } else { 245 if (signum == 0) 246 throw(new NumberFormatException("signum-magnitude mismatch")); 247 this.signum = signum; 248 } 249 } 250 251 /** 252 * A constructor for internal use that translates the sign-magnitude 253 * representation of a BigInteger into a BigInteger. It checks the 254 * arguments and copies the magnitude so this constructor would be 255 * safe for external use. 256 */ 257 private BigInteger(int signum, int[] magnitude) { 258 this.mag = stripLeadingZeroInts(magnitude); 259 260 if (signum < -1 || signum > 1) 261 throw(new NumberFormatException("Invalid signum value")); 262 263 if (this.mag.length==0) { 264 this.signum = 0; 265 } else { 266 if (signum == 0) 267 throw(new NumberFormatException("signum-magnitude mismatch")); 268 this.signum = signum; 269 } 270 } 271 272 /** 273 * Translates the String representation of a BigInteger in the 274 * specified radix into a BigInteger. The String representation 275 * consists of an optional minus or plus sign followed by a 276 * sequence of one or more digits in the specified radix. The 277 * character-to-digit mapping is provided by {@code 278 * Character.digit}. The String may not contain any extraneous 279 * characters (whitespace, for example). 280 * 281 * @param val String representation of BigInteger. 282 * @param radix radix to be used in interpreting {@code val}. 283 * @throws NumberFormatException {@code val} is not a valid representation 284 * of a BigInteger in the specified radix, or {@code radix} is 285 * outside the range from {@link Character#MIN_RADIX} to 286 * {@link Character#MAX_RADIX}, inclusive. 287 * @see Character#digit 288 */ 289 public BigInteger(String val, int radix) { 290 int cursor = 0, numDigits; 291 final int len = val.length(); 292 293 if (radix < Character.MIN_RADIX || radix > Character.MAX_RADIX) 294 throw new NumberFormatException("Radix out of range"); 295 if (len == 0) 296 throw new NumberFormatException("Zero length BigInteger"); 297 298 // Check for at most one leading sign 299 int sign = 1; 300 int index1 = val.lastIndexOf('-'); 301 int index2 = val.lastIndexOf('+'); 302 if ((index1 + index2) <= -1) { 303 // No leading sign character or at most one leading sign character 304 if (index1 == 0 || index2 == 0) { 305 cursor = 1; 306 if (len == 1) 307 throw new NumberFormatException("Zero length BigInteger"); 308 } 309 if (index1 == 0) 310 sign = -1; 311 } else 312 throw new NumberFormatException("Illegal embedded sign character"); 313 314 // Skip leading zeros and compute number of digits in magnitude 315 while (cursor < len && 316 Character.digit(val.charAt(cursor), radix) == 0) 317 cursor++; 318 if (cursor == len) { 319 signum = 0; 320 mag = ZERO.mag; 321 return; 322 } 323 324 numDigits = len - cursor; 325 signum = sign; 326 327 // Pre-allocate array of expected size. May be too large but can 328 // never be too small. Typically exact. 329 int numBits = (int)(((numDigits * bitsPerDigit[radix]) >>> 10) + 1); 330 int numWords = (numBits + 31) >>> 5; 331 int[] magnitude = new int[numWords]; 332 333 // Process first (potentially short) digit group 334 int firstGroupLen = numDigits % digitsPerInt[radix]; 335 if (firstGroupLen == 0) 336 firstGroupLen = digitsPerInt[radix]; 337 String group = val.substring(cursor, cursor += firstGroupLen); 338 magnitude[numWords - 1] = Integer.parseInt(group, radix); 339 if (magnitude[numWords - 1] < 0) 340 throw new NumberFormatException("Illegal digit"); 341 342 // Process remaining digit groups 343 int superRadix = intRadix[radix]; 344 int groupVal = 0; 345 while (cursor < len) { 346 group = val.substring(cursor, cursor += digitsPerInt[radix]); 347 groupVal = Integer.parseInt(group, radix); 348 if (groupVal < 0) 349 throw new NumberFormatException("Illegal digit"); 350 destructiveMulAdd(magnitude, superRadix, groupVal); 351 } 352 // Required for cases where the array was overallocated. 353 mag = trustedStripLeadingZeroInts(magnitude); 354 } 355 356 /* 357 * Constructs a new BigInteger using a char array with radix=10. 358 * Sign is precalculated outside and not allowed in the val. 359 */ 360 BigInteger(char[] val, int sign, int len) { 361 int cursor = 0, numDigits; 362 363 // Skip leading zeros and compute number of digits in magnitude 364 while (cursor < len && Character.digit(val[cursor], 10) == 0) { 365 cursor++; 366 } 367 if (cursor == len) { 368 signum = 0; 369 mag = ZERO.mag; 370 return; 371 } 372 373 numDigits = len - cursor; 374 signum = sign; 375 // Pre-allocate array of expected size 376 int numWords; 377 if (len < 10) { 378 numWords = 1; 379 } else { 380 int numBits = (int)(((numDigits * bitsPerDigit[10]) >>> 10) + 1); 381 numWords = (numBits + 31) >>> 5; 382 } 383 int[] magnitude = new int[numWords]; 384 385 // Process first (potentially short) digit group 386 int firstGroupLen = numDigits % digitsPerInt[10]; 387 if (firstGroupLen == 0) 388 firstGroupLen = digitsPerInt[10]; 389 magnitude[numWords - 1] = parseInt(val, cursor, cursor += firstGroupLen); 390 391 // Process remaining digit groups 392 while (cursor < len) { 393 int groupVal = parseInt(val, cursor, cursor += digitsPerInt[10]); 394 destructiveMulAdd(magnitude, intRadix[10], groupVal); 395 } 396 mag = trustedStripLeadingZeroInts(magnitude); 397 } 398 399 // Create an integer with the digits between the two indexes 400 // Assumes start < end. The result may be negative, but it 401 // is to be treated as an unsigned value. 402 private int parseInt(char[] source, int start, int end) { 403 int result = Character.digit(source[start++], 10); 404 if (result == -1) 405 throw new NumberFormatException(new String(source)); 406 407 for (int index = start; index<end; index++) { 408 int nextVal = Character.digit(source[index], 10); 409 if (nextVal == -1) 410 throw new NumberFormatException(new String(source)); 411 result = 10*result + nextVal; 412 } 413 414 return result; 415 } 416 417 // bitsPerDigit in the given radix times 1024 418 // Rounded up to avoid underallocation. 419 private static long bitsPerDigit[] = { 0, 0, 420 1024, 1624, 2048, 2378, 2648, 2875, 3072, 3247, 3402, 3543, 3672, 421 3790, 3899, 4001, 4096, 4186, 4271, 4350, 4426, 4498, 4567, 4633, 422 4696, 4756, 4814, 4870, 4923, 4975, 5025, 5074, 5120, 5166, 5210, 423 5253, 5295}; 424 425 // Multiply x array times word y in place, and add word z 426 private static void destructiveMulAdd(int[] x, int y, int z) { 427 // Perform the multiplication word by word 428 long ylong = y & LONG_MASK; 429 long zlong = z & LONG_MASK; 430 int len = x.length; 431 432 long product = 0; 433 long carry = 0; 434 for (int i = len-1; i >= 0; i--) { 435 product = ylong * (x[i] & LONG_MASK) + carry; 436 x[i] = (int)product; 437 carry = product >>> 32; 438 } 439 440 // Perform the addition 441 long sum = (x[len-1] & LONG_MASK) + zlong; 442 x[len-1] = (int)sum; 443 carry = sum >>> 32; 444 for (int i = len-2; i >= 0; i--) { 445 sum = (x[i] & LONG_MASK) + carry; 446 x[i] = (int)sum; 447 carry = sum >>> 32; 448 } 449 } 450 451 /** 452 * Translates the decimal String representation of a BigInteger into a 453 * BigInteger. The String representation consists of an optional minus 454 * sign followed by a sequence of one or more decimal digits. The 455 * character-to-digit mapping is provided by {@code Character.digit}. 456 * The String may not contain any extraneous characters (whitespace, for 457 * example). 458 * 459 * @param val decimal String representation of BigInteger. 460 * @throws NumberFormatException {@code val} is not a valid representation 461 * of a BigInteger. 462 * @see Character#digit 463 */ 464 public BigInteger(String val) { 465 this(val, 10); 466 } 467 468 /** 469 * Constructs a randomly generated BigInteger, uniformly distributed over 470 * the range 0 to (2<sup>{@code numBits}</sup> - 1), inclusive. 471 * The uniformity of the distribution assumes that a fair source of random 472 * bits is provided in {@code rnd}. Note that this constructor always 473 * constructs a non-negative BigInteger. 474 * 475 * @param numBits maximum bitLength of the new BigInteger. 476 * @param rnd source of randomness to be used in computing the new 477 * BigInteger. 478 * @throws IllegalArgumentException {@code numBits} is negative. 479 * @see #bitLength() 480 */ 481 public BigInteger(int numBits, Random rnd) { 482 this(1, randomBits(numBits, rnd)); 483 } 484 485 private static byte[] randomBits(int numBits, Random rnd) { 486 if (numBits < 0) 487 throw new IllegalArgumentException("numBits must be non-negative"); 488 int numBytes = (int)(((long)numBits+7)/8); // avoid overflow 489 byte[] randomBits = new byte[numBytes]; 490 491 // Generate random bytes and mask out any excess bits 492 if (numBytes > 0) { 493 rnd.nextBytes(randomBits); 494 int excessBits = 8*numBytes - numBits; 495 randomBits[0] &= (1 << (8-excessBits)) - 1; 496 } 497 return randomBits; 498 } 499 500 /** 501 * Constructs a randomly generated positive BigInteger that is probably 502 * prime, with the specified bitLength. 503 * 504 * <p>It is recommended that the {@link #probablePrime probablePrime} 505 * method be used in preference to this constructor unless there 506 * is a compelling need to specify a certainty. 507 * 508 * @param bitLength bitLength of the returned BigInteger. 509 * @param certainty a measure of the uncertainty that the caller is 510 * willing to tolerate. The probability that the new BigInteger 511 * represents a prime number will exceed 512 * (1 - 1/2<sup>{@code certainty}</sup>). The execution time of 513 * this constructor is proportional to the value of this parameter. 514 * @param rnd source of random bits used to select candidates to be 515 * tested for primality. 516 * @throws ArithmeticException {@code bitLength < 2}. 517 * @see #bitLength() 518 */ 519 public BigInteger(int bitLength, int certainty, Random rnd) { 520 BigInteger prime; 521 522 if (bitLength < 2) 523 throw new ArithmeticException("bitLength < 2"); 524 // The cutoff of 95 was chosen empirically for best performance 525 prime = (bitLength < 95 ? smallPrime(bitLength, certainty, rnd) 526 : largePrime(bitLength, certainty, rnd)); 527 signum = 1; 528 mag = prime.mag; 529 } 530 531 // Minimum size in bits that the requested prime number has 532 // before we use the large prime number generating algorithms 533 private static final int SMALL_PRIME_THRESHOLD = 95; 534 535 // Certainty required to meet the spec of probablePrime 536 private static final int DEFAULT_PRIME_CERTAINTY = 100; 537 538 /** 539 * Returns a positive BigInteger that is probably prime, with the 540 * specified bitLength. The probability that a BigInteger returned 541 * by this method is composite does not exceed 2<sup>-100</sup>. 542 * 543 * @param bitLength bitLength of the returned BigInteger. 544 * @param rnd source of random bits used to select candidates to be 545 * tested for primality. 546 * @return a BigInteger of {@code bitLength} bits that is probably prime 547 * @throws ArithmeticException {@code bitLength < 2}. 548 * @see #bitLength() 549 * @since 1.4 550 */ 551 public static BigInteger probablePrime(int bitLength, Random rnd) { 552 if (bitLength < 2) 553 throw new ArithmeticException("bitLength < 2"); 554 555 // The cutoff of 95 was chosen empirically for best performance 556 return (bitLength < SMALL_PRIME_THRESHOLD ? 557 smallPrime(bitLength, DEFAULT_PRIME_CERTAINTY, rnd) : 558 largePrime(bitLength, DEFAULT_PRIME_CERTAINTY, rnd)); 559 } 560 561 /** 562 * Find a random number of the specified bitLength that is probably prime. 563 * This method is used for smaller primes, its performance degrades on 564 * larger bitlengths. 565 * 566 * This method assumes bitLength > 1. 567 */ 568 private static BigInteger smallPrime(int bitLength, int certainty, Random rnd) { 569 int magLen = (bitLength + 31) >>> 5; 570 int temp[] = new int[magLen]; 571 int highBit = 1 << ((bitLength+31) & 0x1f); // High bit of high int 572 int highMask = (highBit << 1) - 1; // Bits to keep in high int 573 574 while(true) { 575 // Construct a candidate 576 for (int i=0; i<magLen; i++) 577 temp[i] = rnd.nextInt(); 578 temp[0] = (temp[0] & highMask) | highBit; // Ensure exact length 579 if (bitLength > 2) 580 temp[magLen-1] |= 1; // Make odd if bitlen > 2 581 582 BigInteger p = new BigInteger(temp, 1); 583 584 // Do cheap "pre-test" if applicable 585 if (bitLength > 6) { 586 long r = p.remainder(SMALL_PRIME_PRODUCT).longValue(); 587 if ((r%3==0) || (r%5==0) || (r%7==0) || (r%11==0) || 588 (r%13==0) || (r%17==0) || (r%19==0) || (r%23==0) || 589 (r%29==0) || (r%31==0) || (r%37==0) || (r%41==0)) 590 continue; // Candidate is composite; try another 591 } 592 593 // All candidates of bitLength 2 and 3 are prime by this point 594 if (bitLength < 4) 595 return p; 596 597 // Do expensive test if we survive pre-test (or it's inapplicable) 598 if (p.primeToCertainty(certainty, rnd)) 599 return p; 600 } 601 } 602 603 private static final BigInteger SMALL_PRIME_PRODUCT 604 = valueOf(3L*5*7*11*13*17*19*23*29*31*37*41); 605 606 /** 607 * Find a random number of the specified bitLength that is probably prime. 608 * This method is more appropriate for larger bitlengths since it uses 609 * a sieve to eliminate most composites before using a more expensive 610 * test. 611 */ 612 private static BigInteger largePrime(int bitLength, int certainty, Random rnd) { 613 BigInteger p; 614 p = new BigInteger(bitLength, rnd).setBit(bitLength-1); 615 p.mag[p.mag.length-1] &= 0xfffffffe; 616 617 // Use a sieve length likely to contain the next prime number 618 int searchLen = (bitLength / 20) * 64; 619 BitSieve searchSieve = new BitSieve(p, searchLen); 620 BigInteger candidate = searchSieve.retrieve(p, certainty, rnd); 621 622 while ((candidate == null) || (candidate.bitLength() != bitLength)) { 623 p = p.add(BigInteger.valueOf(2*searchLen)); 624 if (p.bitLength() != bitLength) 625 p = new BigInteger(bitLength, rnd).setBit(bitLength-1); 626 p.mag[p.mag.length-1] &= 0xfffffffe; 627 searchSieve = new BitSieve(p, searchLen); 628 candidate = searchSieve.retrieve(p, certainty, rnd); 629 } 630 return candidate; 631 } 632 633 /** 634 * Returns the first integer greater than this {@code BigInteger} that 635 * is probably prime. The probability that the number returned by this 636 * method is composite does not exceed 2<sup>-100</sup>. This method will 637 * never skip over a prime when searching: if it returns {@code p}, there 638 * is no prime {@code q} such that {@code this < q < p}. 639 * 640 * @return the first integer greater than this {@code BigInteger} that 641 * is probably prime. 642 * @throws ArithmeticException {@code this < 0}. 643 * @since 1.5 644 */ 645 public BigInteger nextProbablePrime() { 646 if (this.signum < 0) 647 throw new ArithmeticException("start < 0: " + this); 648 649 // Handle trivial cases 650 if ((this.signum == 0) || this.equals(ONE)) 651 return TWO; 652 653 BigInteger result = this.add(ONE); 654 655 // Fastpath for small numbers 656 if (result.bitLength() < SMALL_PRIME_THRESHOLD) { 657 658 // Ensure an odd number 659 if (!result.testBit(0)) 660 result = result.add(ONE); 661 662 while(true) { 663 // Do cheap "pre-test" if applicable 664 if (result.bitLength() > 6) { 665 long r = result.remainder(SMALL_PRIME_PRODUCT).longValue(); 666 if ((r%3==0) || (r%5==0) || (r%7==0) || (r%11==0) || 667 (r%13==0) || (r%17==0) || (r%19==0) || (r%23==0) || 668 (r%29==0) || (r%31==0) || (r%37==0) || (r%41==0)) { 669 result = result.add(TWO); 670 continue; // Candidate is composite; try another 671 } 672 } 673 674 // All candidates of bitLength 2 and 3 are prime by this point 675 if (result.bitLength() < 4) 676 return result; 677 678 // The expensive test 679 if (result.primeToCertainty(DEFAULT_PRIME_CERTAINTY, null)) 680 return result; 681 682 result = result.add(TWO); 683 } 684 } 685 686 // Start at previous even number 687 if (result.testBit(0)) 688 result = result.subtract(ONE); 689 690 // Looking for the next large prime 691 int searchLen = (result.bitLength() / 20) * 64; 692 693 while(true) { 694 BitSieve searchSieve = new BitSieve(result, searchLen); 695 BigInteger candidate = searchSieve.retrieve(result, 696 DEFAULT_PRIME_CERTAINTY, null); 697 if (candidate != null) 698 return candidate; 699 result = result.add(BigInteger.valueOf(2 * searchLen)); 700 } 701 } 702 703 /** 704 * Returns {@code true} if this BigInteger is probably prime, 705 * {@code false} if it's definitely composite. 706 * 707 * This method assumes bitLength > 2. 708 * 709 * @param certainty a measure of the uncertainty that the caller is 710 * willing to tolerate: if the call returns {@code true} 711 * the probability that this BigInteger is prime exceeds 712 * {@code (1 - 1/2<sup>certainty</sup>)}. The execution time of 713 * this method is proportional to the value of this parameter. 714 * @return {@code true} if this BigInteger is probably prime, 715 * {@code false} if it's definitely composite. 716 */ 717 boolean primeToCertainty(int certainty, Random random) { 718 int rounds = 0; 719 int n = (Math.min(certainty, Integer.MAX_VALUE-1)+1)/2; 720 721 // The relationship between the certainty and the number of rounds 722 // we perform is given in the draft standard ANSI X9.80, "PRIME 723 // NUMBER GENERATION, PRIMALITY TESTING, AND PRIMALITY CERTIFICATES". 724 int sizeInBits = this.bitLength(); 725 if (sizeInBits < 100) { 726 rounds = 50; 727 rounds = n < rounds ? n : rounds; 728 return passesMillerRabin(rounds, random); 729 } 730 731 if (sizeInBits < 256) { 732 rounds = 27; 733 } else if (sizeInBits < 512) { 734 rounds = 15; 735 } else if (sizeInBits < 768) { 736 rounds = 8; 737 } else if (sizeInBits < 1024) { 738 rounds = 4; 739 } else { 740 rounds = 2; 741 } 742 rounds = n < rounds ? n : rounds; 743 744 return passesMillerRabin(rounds, random) && passesLucasLehmer(); 745 } 746 747 /** 748 * Returns true iff this BigInteger is a Lucas-Lehmer probable prime. 749 * 750 * The following assumptions are made: 751 * This BigInteger is a positive, odd number. 752 */ 753 private boolean passesLucasLehmer() { 754 BigInteger thisPlusOne = this.add(ONE); 755 756 // Step 1 757 int d = 5; 758 while (jacobiSymbol(d, this) != -1) { 759 // 5, -7, 9, -11, ... 760 d = (d<0) ? Math.abs(d)+2 : -(d+2); 761 } 762 763 // Step 2 764 BigInteger u = lucasLehmerSequence(d, thisPlusOne, this); 765 766 // Step 3 767 return u.mod(this).equals(ZERO); 768 } 769 770 /** 771 * Computes Jacobi(p,n). 772 * Assumes n positive, odd, n>=3. 773 */ 774 private static int jacobiSymbol(int p, BigInteger n) { 775 if (p == 0) 776 return 0; 777 778 // Algorithm and comments adapted from Colin Plumb's C library. 779 int j = 1; 780 int u = n.mag[n.mag.length-1]; 781 782 // Make p positive 783 if (p < 0) { 784 p = -p; 785 int n8 = u & 7; 786 if ((n8 == 3) || (n8 == 7)) 787 j = -j; // 3 (011) or 7 (111) mod 8 788 } 789 790 // Get rid of factors of 2 in p 791 while ((p & 3) == 0) 792 p >>= 2; 793 if ((p & 1) == 0) { 794 p >>= 1; 795 if (((u ^ (u>>1)) & 2) != 0) 796 j = -j; // 3 (011) or 5 (101) mod 8 797 } 798 if (p == 1) 799 return j; 800 // Then, apply quadratic reciprocity 801 if ((p & u & 2) != 0) // p = u = 3 (mod 4)? 802 j = -j; 803 // And reduce u mod p 804 u = n.mod(BigInteger.valueOf(p)).intValue(); 805 806 // Now compute Jacobi(u,p), u < p 807 while (u != 0) { 808 while ((u & 3) == 0) 809 u >>= 2; 810 if ((u & 1) == 0) { 811 u >>= 1; 812 if (((p ^ (p>>1)) & 2) != 0) 813 j = -j; // 3 (011) or 5 (101) mod 8 814 } 815 if (u == 1) 816 return j; 817 // Now both u and p are odd, so use quadratic reciprocity 818 assert (u < p); 819 int t = u; u = p; p = t; 820 if ((u & p & 2) != 0) // u = p = 3 (mod 4)? 821 j = -j; 822 // Now u >= p, so it can be reduced 823 u %= p; 824 } 825 return 0; 826 } 827 828 private static BigInteger lucasLehmerSequence(int z, BigInteger k, BigInteger n) { 829 BigInteger d = BigInteger.valueOf(z); 830 BigInteger u = ONE; BigInteger u2; 831 BigInteger v = ONE; BigInteger v2; 832 833 for (int i=k.bitLength()-2; i>=0; i--) { 834 u2 = u.multiply(v).mod(n); 835 836 v2 = v.square().add(d.multiply(u.square())).mod(n); 837 if (v2.testBit(0)) 838 v2 = v2.subtract(n); 839 840 v2 = v2.shiftRight(1); 841 842 u = u2; v = v2; 843 if (k.testBit(i)) { 844 u2 = u.add(v).mod(n); 845 if (u2.testBit(0)) 846 u2 = u2.subtract(n); 847 848 u2 = u2.shiftRight(1); 849 v2 = v.add(d.multiply(u)).mod(n); 850 if (v2.testBit(0)) 851 v2 = v2.subtract(n); 852 v2 = v2.shiftRight(1); 853 854 u = u2; v = v2; 855 } 856 } 857 return u; 858 } 859 860 private static volatile Random staticRandom; 861 862 private static Random getSecureRandom() { 863 if (staticRandom == null) { 864 staticRandom = new java.security.SecureRandom(); 865 } 866 return staticRandom; 867 } 868 869 /** 870 * Returns true iff this BigInteger passes the specified number of 871 * Miller-Rabin tests. This test is taken from the DSA spec (NIST FIPS 872 * 186-2). 873 * 874 * The following assumptions are made: 875 * This BigInteger is a positive, odd number greater than 2. 876 * iterations<=50. 877 */ 878 private boolean passesMillerRabin(int iterations, Random rnd) { 879 // Find a and m such that m is odd and this == 1 + 2**a * m 880 BigInteger thisMinusOne = this.subtract(ONE); 881 BigInteger m = thisMinusOne; 882 int a = m.getLowestSetBit(); 883 m = m.shiftRight(a); 884 885 // Do the tests 886 if (rnd == null) { 887 rnd = getSecureRandom(); 888 } 889 for (int i=0; i<iterations; i++) { 890 // Generate a uniform random on (1, this) 891 BigInteger b; 892 do { 893 b = new BigInteger(this.bitLength(), rnd); 894 } while (b.compareTo(ONE) <= 0 || b.compareTo(this) >= 0); 895 896 int j = 0; 897 BigInteger z = b.modPow(m, this); 898 while(!((j==0 && z.equals(ONE)) || z.equals(thisMinusOne))) { 899 if (j>0 && z.equals(ONE) || ++j==a) 900 return false; 901 z = z.modPow(TWO, this); 902 } 903 } 904 return true; 905 } 906 907 /** 908 * This internal constructor differs from its public cousin 909 * with the arguments reversed in two ways: it assumes that its 910 * arguments are correct, and it doesn't copy the magnitude array. 911 */ 912 BigInteger(int[] magnitude, int signum) { 913 this.signum = (magnitude.length==0 ? 0 : signum); 914 this.mag = magnitude; 915 } 916 917 /** 918 * This private constructor is for internal use and assumes that its 919 * arguments are correct. 920 */ 921 private BigInteger(byte[] magnitude, int signum) { 922 this.signum = (magnitude.length==0 ? 0 : signum); 923 this.mag = stripLeadingZeroBytes(magnitude); 924 } 925 926 //Static Factory Methods 927 928 /** 929 * Returns a BigInteger whose value is equal to that of the 930 * specified {@code long}. This "static factory method" is 931 * provided in preference to a ({@code long}) constructor 932 * because it allows for reuse of frequently used BigIntegers. 933 * 934 * @param val value of the BigInteger to return. 935 * @return a BigInteger with the specified value. 936 */ 937 public static BigInteger valueOf(long val) { 938 // If -MAX_CONSTANT < val < MAX_CONSTANT, return stashed constant 939 if (val == 0) 940 return ZERO; 941 if (val > 0 && val <= MAX_CONSTANT) 942 return posConst[(int) val]; 943 else if (val < 0 && val >= -MAX_CONSTANT) 944 return negConst[(int) -val]; 945 946 return new BigInteger(val); 947 } 948 949 /** 950 * Constructs a BigInteger with the specified value, which may not be zero. 951 */ 952 private BigInteger(long val) { 953 if (val < 0) { 954 val = -val; 955 signum = -1; 956 } else { 957 signum = 1; 958 } 959 960 int highWord = (int)(val >>> 32); 961 if (highWord==0) { 962 mag = new int[1]; 963 mag[0] = (int)val; 964 } else { 965 mag = new int[2]; 966 mag[0] = highWord; 967 mag[1] = (int)val; 968 } 969 } 970 971 /** 972 * Returns a BigInteger with the given two's complement representation. 973 * Assumes that the input array will not be modified (the returned 974 * BigInteger will reference the input array if feasible). 975 */ 976 private static BigInteger valueOf(int val[]) { 977 return (val[0]>0 ? new BigInteger(val, 1) : new BigInteger(val)); 978 } 979 980 // Constants 981 982 /** 983 * Initialize static constant array when class is loaded. 984 */ 985 private final static int MAX_CONSTANT = 16; 986 private static BigInteger posConst[] = new BigInteger[MAX_CONSTANT+1]; 987 private static BigInteger negConst[] = new BigInteger[MAX_CONSTANT+1]; 988 static { 989 for (int i = 1; i <= MAX_CONSTANT; i++) { 990 int[] magnitude = new int[1]; 991 magnitude[0] = i; 992 posConst[i] = new BigInteger(magnitude, 1); 993 negConst[i] = new BigInteger(magnitude, -1); 994 } 995 } 996 997 /** 998 * The BigInteger constant zero. 999 * 1000 * @since 1.2 1001 */ 1002 public static final BigInteger ZERO = new BigInteger(new int[0], 0); 1003 1004 /** 1005 * The BigInteger constant one. 1006 * 1007 * @since 1.2 1008 */ 1009 public static final BigInteger ONE = valueOf(1); 1010 1011 /** 1012 * The BigInteger constant two. (Not exported.) 1013 */ 1014 private static final BigInteger TWO = valueOf(2); 1015 1016 /** 1017 * The BigInteger constant ten. 1018 * 1019 * @since 1.5 1020 */ 1021 public static final BigInteger TEN = valueOf(10); 1022 1023 // Arithmetic Operations 1024 1025 /** 1026 * Returns a BigInteger whose value is {@code (this + val)}. 1027 * 1028 * @param val value to be added to this BigInteger. 1029 * @return {@code this + val} 1030 */ 1031 public BigInteger add(BigInteger val) { 1032 if (val.signum == 0) 1033 return this; 1034 if (signum == 0) 1035 return val; 1036 if (val.signum == signum) 1037 return new BigInteger(add(mag, val.mag), signum); 1038 1039 int cmp = compareMagnitude(val); 1040 if (cmp == 0) 1041 return ZERO; 1042 int[] resultMag = (cmp > 0 ? subtract(mag, val.mag) 1043 : subtract(val.mag, mag)); 1044 resultMag = trustedStripLeadingZeroInts(resultMag); 1045 1046 return new BigInteger(resultMag, cmp == signum ? 1 : -1); 1047 } 1048 1049 /** 1050 * Package private methods used by BigDecimal code to add a BigInteger 1051 * with a long. Assumes val is not equal to INFLATED. 1052 */ 1053 BigInteger add(long val) { 1054 if (val == 0) 1055 return this; 1056 if (signum == 0) 1057 return valueOf(val); 1058 if (Long.signum(val) == signum) 1059 return new BigInteger(add(mag, Math.abs(val)), signum); 1060 int cmp = compareMagnitude(val); 1061 if (cmp == 0) 1062 return ZERO; 1063 int[] resultMag = (cmp > 0 ? subtract(mag, Math.abs(val)) : subtract(Math.abs(val), mag)); 1064 resultMag = trustedStripLeadingZeroInts(resultMag); 1065 return new BigInteger(resultMag, cmp == signum ? 1 : -1); 1066 } 1067 1068 /** 1069 * Adds the contents of the int array x and long value val. This 1070 * method allocates a new int array to hold the answer and returns 1071 * a reference to that array. Assumes x.length > 0 and val is 1072 * non-negative 1073 */ 1074 private static int[] add(int[] x, long val) { 1075 int[] y; 1076 long sum = 0; 1077 int xIndex = x.length; 1078 int[] result; 1079 int highWord = (int)(val >>> 32); 1080 if (highWord==0) { 1081 result = new int[xIndex]; 1082 sum = (x[--xIndex] & LONG_MASK) + val; 1083 result[xIndex] = (int)sum; 1084 } else { 1085 if (xIndex == 1) { 1086 result = new int[2]; 1087 sum = val + (x[0] & LONG_MASK); 1088 result[1] = (int)sum; 1089 result[0] = (int)(sum >>> 32); 1090 return result; 1091 } else { 1092 result = new int[xIndex]; 1093 sum = (x[--xIndex] & LONG_MASK) + (val & LONG_MASK); 1094 result[xIndex] = (int)sum; 1095 sum = (x[--xIndex] & LONG_MASK) + (highWord & LONG_MASK) + (sum >>> 32); 1096 result[xIndex] = (int)sum; 1097 } 1098 } 1099 // Copy remainder of longer number while carry propagation is required 1100 boolean carry = (sum >>> 32 != 0); 1101 while (xIndex > 0 && carry) 1102 carry = ((result[--xIndex] = x[xIndex] + 1) == 0); 1103 // Copy remainder of longer number 1104 while (xIndex > 0) 1105 result[--xIndex] = x[xIndex]; 1106 // Grow result if necessary 1107 if (carry) { 1108 int bigger[] = new int[result.length + 1]; 1109 System.arraycopy(result, 0, bigger, 1, result.length); 1110 bigger[0] = 0x01; 1111 return bigger; 1112 } 1113 return result; 1114 } 1115 1116 /** 1117 * Adds the contents of the int arrays x and y. This method allocates 1118 * a new int array to hold the answer and returns a reference to that 1119 * array. 1120 */ 1121 private static int[] add(int[] x, int[] y) { 1122 // If x is shorter, swap the two arrays 1123 if (x.length < y.length) { 1124 int[] tmp = x; 1125 x = y; 1126 y = tmp; 1127 } 1128 1129 int xIndex = x.length; 1130 int yIndex = y.length; 1131 int result[] = new int[xIndex]; 1132 long sum = 0; 1133 if(yIndex==1) { 1134 sum = (x[--xIndex] & LONG_MASK) + (y[0] & LONG_MASK) ; 1135 result[xIndex] = (int)sum; 1136 } else { 1137 // Add common parts of both numbers 1138 while(yIndex > 0) { 1139 sum = (x[--xIndex] & LONG_MASK) + 1140 (y[--yIndex] & LONG_MASK) + (sum >>> 32); 1141 result[xIndex] = (int)sum; 1142 } 1143 } 1144 // Copy remainder of longer number while carry propagation is required 1145 boolean carry = (sum >>> 32 != 0); 1146 while (xIndex > 0 && carry) 1147 carry = ((result[--xIndex] = x[xIndex] + 1) == 0); 1148 1149 // Copy remainder of longer number 1150 while (xIndex > 0) 1151 result[--xIndex] = x[xIndex]; 1152 1153 // Grow result if necessary 1154 if (carry) { 1155 int bigger[] = new int[result.length + 1]; 1156 System.arraycopy(result, 0, bigger, 1, result.length); 1157 bigger[0] = 0x01; 1158 return bigger; 1159 } 1160 return result; 1161 } 1162 1163 private static int[] subtract(long val, int[] little) { 1164 int highWord = (int)(val >>> 32); 1165 if (highWord==0) { 1166 int result[] = new int[1]; 1167 result[0] = (int)(val - (little[0] & LONG_MASK)); 1168 return result; 1169 } else { 1170 int result[] = new int[2]; 1171 if(little.length==1) { 1172 long difference = ((int)val & LONG_MASK) - (little[0] & LONG_MASK); 1173 result[1] = (int)difference; 1174 // Subtract remainder of longer number while borrow propagates 1175 boolean borrow = (difference >> 32 != 0); 1176 if(borrow) { 1177 result[0] = highWord - 1; 1178 } else { // Copy remainder of longer number 1179 result[0] = highWord; 1180 } 1181 return result; 1182 } else { // little.length==2 1183 long difference = ((int)val & LONG_MASK) - (little[1] & LONG_MASK); 1184 result[1] = (int)difference; 1185 difference = (highWord & LONG_MASK) - (little[0] & LONG_MASK) + (difference >> 32); 1186 result[0] = (int)difference; 1187 return result; 1188 } 1189 } 1190 } 1191 1192 /** 1193 * Subtracts the contents of the second argument (val) from the 1194 * first (big). The first int array (big) must represent a larger number 1195 * than the second. This method allocates the space necessary to hold the 1196 * answer. 1197 * assumes val >= 0 1198 */ 1199 private static int[] subtract(int[] big, long val) { 1200 int highWord = (int)(val >>> 32); 1201 int bigIndex = big.length; 1202 int result[] = new int[bigIndex]; 1203 long difference = 0; 1204 1205 if (highWord==0) { 1206 difference = (big[--bigIndex] & LONG_MASK) - val; 1207 result[bigIndex] = (int)difference; 1208 } else { 1209 difference = (big[--bigIndex] & LONG_MASK) - (val & LONG_MASK); 1210 result[bigIndex] = (int)difference; 1211 difference = (big[--bigIndex] & LONG_MASK) - (highWord & LONG_MASK) + (difference >> 32); 1212 result[bigIndex] = (int)difference; 1213 } 1214 1215 1216 // Subtract remainder of longer number while borrow propagates 1217 boolean borrow = (difference >> 32 != 0); 1218 while (bigIndex > 0 && borrow) 1219 borrow = ((result[--bigIndex] = big[bigIndex] - 1) == -1); 1220 1221 // Copy remainder of longer number 1222 while (bigIndex > 0) 1223 result[--bigIndex] = big[bigIndex]; 1224 1225 return result; 1226 } 1227 1228 /** 1229 * Returns a BigInteger whose value is {@code (this - val)}. 1230 * 1231 * @param val value to be subtracted from this BigInteger. 1232 * @return {@code this - val} 1233 */ 1234 public BigInteger subtract(BigInteger val) { 1235 if (val.signum == 0) 1236 return this; 1237 if (signum == 0) 1238 return val.negate(); 1239 if (val.signum != signum) 1240 return new BigInteger(add(mag, val.mag), signum); 1241 1242 int cmp = compareMagnitude(val); 1243 if (cmp == 0) 1244 return ZERO; 1245 int[] resultMag = (cmp > 0 ? subtract(mag, val.mag) 1246 : subtract(val.mag, mag)); 1247 resultMag = trustedStripLeadingZeroInts(resultMag); 1248 return new BigInteger(resultMag, cmp == signum ? 1 : -1); 1249 } 1250 1251 /** 1252 * Subtracts the contents of the second int arrays (little) from the 1253 * first (big). The first int array (big) must represent a larger number 1254 * than the second. This method allocates the space necessary to hold the 1255 * answer. 1256 */ 1257 private static int[] subtract(int[] big, int[] little) { 1258 int bigIndex = big.length; 1259 int result[] = new int[bigIndex]; 1260 int littleIndex = little.length; 1261 long difference = 0; 1262 1263 // Subtract common parts of both numbers 1264 while(littleIndex > 0) { 1265 difference = (big[--bigIndex] & LONG_MASK) - 1266 (little[--littleIndex] & LONG_MASK) + 1267 (difference >> 32); 1268 result[bigIndex] = (int)difference; 1269 } 1270 1271 // Subtract remainder of longer number while borrow propagates 1272 boolean borrow = (difference >> 32 != 0); 1273 while (bigIndex > 0 && borrow) 1274 borrow = ((result[--bigIndex] = big[bigIndex] - 1) == -1); 1275 1276 // Copy remainder of longer number 1277 while (bigIndex > 0) 1278 result[--bigIndex] = big[bigIndex]; 1279 1280 return result; 1281 } 1282 1283 /** 1284 * Returns a BigInteger whose value is {@code (this * val)}. 1285 * 1286 * @param val value to be multiplied by this BigInteger. 1287 * @return {@code this * val} 1288 */ 1289 public BigInteger multiply(BigInteger val) { 1290 if (val.signum == 0 || signum == 0) 1291 return ZERO; 1292 int resultSign = signum == val.signum ? 1 : -1; 1293 if (val.mag.length == 1) { 1294 return multiplyByInt(mag,val.mag[0], resultSign); 1295 } 1296 if(mag.length == 1) { 1297 return multiplyByInt(val.mag,mag[0], resultSign); 1298 } 1299 int[] result = multiplyToLen(mag, mag.length, 1300 val.mag, val.mag.length, null); 1301 result = trustedStripLeadingZeroInts(result); 1302 return new BigInteger(result, resultSign); 1303 } 1304 1305 private static BigInteger multiplyByInt(int[] x, int y, int sign) { 1306 if(Integer.bitCount(y)==1) { 1307 return new BigInteger(shiftLeft(x,Integer.numberOfTrailingZeros(y)), sign); 1308 } 1309 int xlen = x.length; 1310 int[] rmag = new int[xlen + 1]; 1311 long carry = 0; 1312 long yl = y & LONG_MASK; 1313 int rstart = rmag.length - 1; 1314 for (int i = xlen - 1; i >= 0; i--) { 1315 long product = (x[i] & LONG_MASK) * yl + carry; 1316 rmag[rstart--] = (int)product; 1317 carry = product >>> 32; 1318 } 1319 if (carry == 0L) { 1320 rmag = java.util.Arrays.copyOfRange(rmag, 1, rmag.length); 1321 } else { 1322 rmag[rstart] = (int)carry; 1323 } 1324 return new BigInteger(rmag, sign); 1325 } 1326 1327 /** 1328 * Package private methods used by BigDecimal code to multiply a BigInteger 1329 * with a long. Assumes v is not equal to INFLATED. 1330 */ 1331 BigInteger multiply(long v) { 1332 if (v == 0 || signum == 0) 1333 return ZERO; 1334 if (v == BigDecimal.INFLATED) 1335 return multiply(BigInteger.valueOf(v)); 1336 int rsign = (v > 0 ? signum : -signum); 1337 if (v < 0) 1338 v = -v; 1339 long dh = v >>> 32; // higher order bits 1340 long dl = v & LONG_MASK; // lower order bits 1341 1342 int xlen = mag.length; 1343 int[] value = mag; 1344 int[] rmag = (dh == 0L) ? (new int[xlen + 1]) : (new int[xlen + 2]); 1345 long carry = 0; 1346 int rstart = rmag.length - 1; 1347 for (int i = xlen - 1; i >= 0; i--) { 1348 long product = (value[i] & LONG_MASK) * dl + carry; 1349 rmag[rstart--] = (int)product; 1350 carry = product >>> 32; 1351 } 1352 rmag[rstart] = (int)carry; 1353 if (dh != 0L) { 1354 carry = 0; 1355 rstart = rmag.length - 2; 1356 for (int i = xlen - 1; i >= 0; i--) { 1357 long product = (value[i] & LONG_MASK) * dh + 1358 (rmag[rstart] & LONG_MASK) + carry; 1359 rmag[rstart--] = (int)product; 1360 carry = product >>> 32; 1361 } 1362 rmag[0] = (int)carry; 1363 } 1364 if (carry == 0L) 1365 rmag = java.util.Arrays.copyOfRange(rmag, 1, rmag.length); 1366 return new BigInteger(rmag, rsign); 1367 } 1368 1369 /** 1370 * Multiplies int arrays x and y to the specified lengths and places 1371 * the result into z. There will be no leading zeros in the resultant array. 1372 */ 1373 private int[] multiplyToLen(int[] x, int xlen, int[] y, int ylen, int[] z) { 1374 int xstart = xlen - 1; 1375 int ystart = ylen - 1; 1376 1377 if (z == null || z.length < (xlen+ ylen)) 1378 z = new int[xlen+ylen]; 1379 1380 long carry = 0; 1381 for (int j=ystart, k=ystart+1+xstart; j>=0; j--, k--) { 1382 long product = (y[j] & LONG_MASK) * 1383 (x[xstart] & LONG_MASK) + carry; 1384 z[k] = (int)product; 1385 carry = product >>> 32; 1386 } 1387 z[xstart] = (int)carry; 1388 1389 for (int i = xstart-1; i >= 0; i--) { 1390 carry = 0; 1391 for (int j=ystart, k=ystart+1+i; j>=0; j--, k--) { 1392 long product = (y[j] & LONG_MASK) * 1393 (x[i] & LONG_MASK) + 1394 (z[k] & LONG_MASK) + carry; 1395 z[k] = (int)product; 1396 carry = product >>> 32; 1397 } 1398 z[i] = (int)carry; 1399 } 1400 return z; 1401 } 1402 1403 /** 1404 * Returns a BigInteger whose value is {@code (this<sup>2</sup>)}. 1405 * 1406 * @return {@code this<sup>2</sup>} 1407 */ 1408 private BigInteger square() { 1409 if (signum == 0) 1410 return ZERO; 1411 int[] z = squareToLen(mag, mag.length, null); 1412 return new BigInteger(trustedStripLeadingZeroInts(z), 1); 1413 } 1414 1415 /** 1416 * Squares the contents of the int array x. The result is placed into the 1417 * int array z. The contents of x are not changed. 1418 */ 1419 private static final int[] squareToLen(int[] x, int len, int[] z) { 1420 /* 1421 * The algorithm used here is adapted from Colin Plumb's C library. 1422 * Technique: Consider the partial products in the multiplication 1423 * of "abcde" by itself: 1424 * 1425 * a b c d e 1426 * * a b c d e 1427 * ================== 1428 * ae be ce de ee 1429 * ad bd cd dd de 1430 * ac bc cc cd ce 1431 * ab bb bc bd be 1432 * aa ab ac ad ae 1433 * 1434 * Note that everything above the main diagonal: 1435 * ae be ce de = (abcd) * e 1436 * ad bd cd = (abc) * d 1437 * ac bc = (ab) * c 1438 * ab = (a) * b 1439 * 1440 * is a copy of everything below the main diagonal: 1441 * de 1442 * cd ce 1443 * bc bd be 1444 * ab ac ad ae 1445 * 1446 * Thus, the sum is 2 * (off the diagonal) + diagonal. 1447 * 1448 * This is accumulated beginning with the diagonal (which 1449 * consist of the squares of the digits of the input), which is then 1450 * divided by two, the off-diagonal added, and multiplied by two 1451 * again. The low bit is simply a copy of the low bit of the 1452 * input, so it doesn't need special care. 1453 */ 1454 int zlen = len << 1; 1455 if (z == null || z.length < zlen) 1456 z = new int[zlen]; 1457 1458 // Store the squares, right shifted one bit (i.e., divided by 2) 1459 int lastProductLowWord = 0; 1460 for (int j=0, i=0; j<len; j++) { 1461 long piece = (x[j] & LONG_MASK); 1462 long product = piece * piece; 1463 z[i++] = (lastProductLowWord << 31) | (int)(product >>> 33); 1464 z[i++] = (int)(product >>> 1); 1465 lastProductLowWord = (int)product; 1466 } 1467 1468 // Add in off-diagonal sums 1469 for (int i=len, offset=1; i>0; i--, offset+=2) { 1470 int t = x[i-1]; 1471 t = mulAdd(z, x, offset, i-1, t); 1472 addOne(z, offset-1, i, t); 1473 } 1474 1475 // Shift back up and set low bit 1476 primitiveLeftShift(z, zlen, 1); 1477 z[zlen-1] |= x[len-1] & 1; 1478 1479 return z; 1480 } 1481 1482 /** 1483 * Returns a BigInteger whose value is {@code (this / val)}. 1484 * 1485 * @param val value by which this BigInteger is to be divided. 1486 * @return {@code this / val} 1487 * @throws ArithmeticException if {@code val} is zero. 1488 */ 1489 public BigInteger divide(BigInteger val) { 1490 MutableBigInteger q = new MutableBigInteger(), 1491 a = new MutableBigInteger(this.mag), 1492 b = new MutableBigInteger(val.mag); 1493 1494 a.divide(b, q, false); 1495 return q.toBigInteger(this.signum * val.signum); 1496 } 1497 1498 /** 1499 * Returns an array of two BigIntegers containing {@code (this / val)} 1500 * followed by {@code (this % val)}. 1501 * 1502 * @param val value by which this BigInteger is to be divided, and the 1503 * remainder computed. 1504 * @return an array of two BigIntegers: the quotient {@code (this / val)} 1505 * is the initial element, and the remainder {@code (this % val)} 1506 * is the final element. 1507 * @throws ArithmeticException if {@code val} is zero. 1508 */ 1509 public BigInteger[] divideAndRemainder(BigInteger val) { 1510 BigInteger[] result = new BigInteger[2]; 1511 MutableBigInteger q = new MutableBigInteger(), 1512 a = new MutableBigInteger(this.mag), 1513 b = new MutableBigInteger(val.mag); 1514 MutableBigInteger r = a.divide(b, q); 1515 result[0] = q.toBigInteger(this.signum == val.signum ? 1 : -1); 1516 result[1] = r.toBigInteger(this.signum); 1517 return result; 1518 } 1519 1520 /** 1521 * Returns a BigInteger whose value is {@code (this % val)}. 1522 * 1523 * @param val value by which this BigInteger is to be divided, and the 1524 * remainder computed. 1525 * @return {@code this % val} 1526 * @throws ArithmeticException if {@code val} is zero. 1527 */ 1528 public BigInteger remainder(BigInteger val) { 1529 MutableBigInteger q = new MutableBigInteger(), 1530 a = new MutableBigInteger(this.mag), 1531 b = new MutableBigInteger(val.mag); 1532 1533 return a.divide(b, q).toBigInteger(this.signum); 1534 } 1535 1536 /** 1537 * Returns a BigInteger whose value is <tt>(this<sup>exponent</sup>)</tt>. 1538 * Note that {@code exponent} is an integer rather than a BigInteger. 1539 * 1540 * @param exponent exponent to which this BigInteger is to be raised. 1541 * @return <tt>this<sup>exponent</sup></tt> 1542 * @throws ArithmeticException {@code exponent} is negative. (This would 1543 * cause the operation to yield a non-integer value.) 1544 */ 1545 public BigInteger pow(int exponent) { 1546 if (exponent < 0) 1547 throw new ArithmeticException("Negative exponent"); 1548 if (signum==0) 1549 return (exponent==0 ? ONE : this); 1550 1551 // Perform exponentiation using repeated squaring trick 1552 int newSign = (signum<0 && (exponent&1)==1 ? -1 : 1); 1553 int[] baseToPow2 = this.mag; 1554 int[] result = {1}; 1555 1556 while (exponent != 0) { 1557 if ((exponent & 1)==1) { 1558 result = multiplyToLen(result, result.length, 1559 baseToPow2, baseToPow2.length, null); 1560 result = trustedStripLeadingZeroInts(result); 1561 } 1562 if ((exponent >>>= 1) != 0) { 1563 baseToPow2 = squareToLen(baseToPow2, baseToPow2.length, null); 1564 baseToPow2 = trustedStripLeadingZeroInts(baseToPow2); 1565 } 1566 } 1567 return new BigInteger(result, newSign); 1568 } 1569 1570 /** 1571 * Returns a BigInteger whose value is the greatest common divisor of 1572 * {@code abs(this)} and {@code abs(val)}. Returns 0 if 1573 * {@code this==0 && val==0}. 1574 * 1575 * @param val value with which the GCD is to be computed. 1576 * @return {@code GCD(abs(this), abs(val))} 1577 */ 1578 public BigInteger gcd(BigInteger val) { 1579 if (val.signum == 0) 1580 return this.abs(); 1581 else if (this.signum == 0) 1582 return val.abs(); 1583 1584 MutableBigInteger a = new MutableBigInteger(this); 1585 MutableBigInteger b = new MutableBigInteger(val); 1586 1587 MutableBigInteger result = a.hybridGCD(b); 1588 1589 return result.toBigInteger(1); 1590 } 1591 1592 /** 1593 * Package private method to return bit length for an integer. 1594 */ 1595 static int bitLengthForInt(int n) { 1596 return 32 - Integer.numberOfLeadingZeros(n); 1597 } 1598 1599 /** 1600 * Left shift int array a up to len by n bits. Returns the array that 1601 * results from the shift since space may have to be reallocated. 1602 */ 1603 private static int[] leftShift(int[] a, int len, int n) { 1604 int nInts = n >>> 5; 1605 int nBits = n&0x1F; 1606 int bitsInHighWord = bitLengthForInt(a[0]); 1607 1608 // If shift can be done without recopy, do so 1609 if (n <= (32-bitsInHighWord)) { 1610 primitiveLeftShift(a, len, nBits); 1611 return a; 1612 } else { // Array must be resized 1613 if (nBits <= (32-bitsInHighWord)) { 1614 int result[] = new int[nInts+len]; 1615 for (int i=0; i<len; i++) 1616 result[i] = a[i]; 1617 primitiveLeftShift(result, result.length, nBits); 1618 return result; 1619 } else { 1620 int result[] = new int[nInts+len+1]; 1621 for (int i=0; i<len; i++) 1622 result[i] = a[i]; 1623 primitiveRightShift(result, result.length, 32 - nBits); 1624 return result; 1625 } 1626 } 1627 } 1628 1629 // shifts a up to len right n bits assumes no leading zeros, 0<n<32 1630 static void primitiveRightShift(int[] a, int len, int n) { 1631 int n2 = 32 - n; 1632 for (int i=len-1, c=a[i]; i>0; i--) { 1633 int b = c; 1634 c = a[i-1]; 1635 a[i] = (c << n2) | (b >>> n); 1636 } 1637 a[0] >>>= n; 1638 } 1639 1640 // shifts a up to len left n bits assumes no leading zeros, 0<=n<32 1641 static void primitiveLeftShift(int[] a, int len, int n) { 1642 if (len == 0 || n == 0) 1643 return; 1644 1645 int n2 = 32 - n; 1646 for (int i=0, c=a[i], m=i+len-1; i<m; i++) { 1647 int b = c; 1648 c = a[i+1]; 1649 a[i] = (b << n) | (c >>> n2); 1650 } 1651 a[len-1] <<= n; 1652 } 1653 1654 /** 1655 * Calculate bitlength of contents of the first len elements an int array, 1656 * assuming there are no leading zero ints. 1657 */ 1658 private static int bitLength(int[] val, int len) { 1659 if (len == 0) 1660 return 0; 1661 return ((len - 1) << 5) + bitLengthForInt(val[0]); 1662 } 1663 1664 /** 1665 * Returns a BigInteger whose value is the absolute value of this 1666 * BigInteger. 1667 * 1668 * @return {@code abs(this)} 1669 */ 1670 public BigInteger abs() { 1671 return (signum >= 0 ? this : this.negate()); 1672 } 1673 1674 /** 1675 * Returns a BigInteger whose value is {@code (-this)}. 1676 * 1677 * @return {@code -this} 1678 */ 1679 public BigInteger negate() { 1680 return new BigInteger(this.mag, -this.signum); 1681 } 1682 1683 /** 1684 * Returns the signum function of this BigInteger. 1685 * 1686 * @return -1, 0 or 1 as the value of this BigInteger is negative, zero or 1687 * positive. 1688 */ 1689 public int signum() { 1690 return this.signum; 1691 } 1692 1693 // Modular Arithmetic Operations 1694 1695 /** 1696 * Returns a BigInteger whose value is {@code (this mod m}). This method 1697 * differs from {@code remainder} in that it always returns a 1698 * <i>non-negative</i> BigInteger. 1699 * 1700 * @param m the modulus. 1701 * @return {@code this mod m} 1702 * @throws ArithmeticException {@code m} ≤ 0 1703 * @see #remainder 1704 */ 1705 public BigInteger mod(BigInteger m) { 1706 if (m.signum <= 0) 1707 throw new ArithmeticException("BigInteger: modulus not positive"); 1708 1709 BigInteger result = this.remainder(m); 1710 return (result.signum >= 0 ? result : result.add(m)); 1711 } 1712 1713 /** 1714 * Returns a BigInteger whose value is 1715 * <tt>(this<sup>exponent</sup> mod m)</tt>. (Unlike {@code pow}, this 1716 * method permits negative exponents.) 1717 * 1718 * @param exponent the exponent. 1719 * @param m the modulus. 1720 * @return <tt>this<sup>exponent</sup> mod m</tt> 1721 * @throws ArithmeticException {@code m} ≤ 0 or the exponent is 1722 * negative and this BigInteger is not <i>relatively 1723 * prime</i> to {@code m}. 1724 * @see #modInverse 1725 */ 1726 public BigInteger modPow(BigInteger exponent, BigInteger m) { 1727 if (m.signum <= 0) 1728 throw new ArithmeticException("BigInteger: modulus not positive"); 1729 1730 // Trivial cases 1731 if (exponent.signum == 0) 1732 return (m.equals(ONE) ? ZERO : ONE); 1733 1734 if (this.equals(ONE)) 1735 return (m.equals(ONE) ? ZERO : ONE); 1736 1737 if (this.equals(ZERO) && exponent.signum >= 0) 1738 return ZERO; 1739 1740 if (this.equals(negConst[1]) && (!exponent.testBit(0))) 1741 return (m.equals(ONE) ? ZERO : ONE); 1742 1743 boolean invertResult; 1744 if ((invertResult = (exponent.signum < 0))) 1745 exponent = exponent.negate(); 1746 1747 BigInteger base = (this.signum < 0 || this.compareTo(m) >= 0 1748 ? this.mod(m) : this); 1749 BigInteger result; 1750 if (m.testBit(0)) { // odd modulus 1751 result = base.oddModPow(exponent, m); 1752 } else { 1753 /* 1754 * Even modulus. Tear it into an "odd part" (m1) and power of two 1755 * (m2), exponentiate mod m1, manually exponentiate mod m2, and 1756 * use Chinese Remainder Theorem to combine results. 1757 */ 1758 1759 // Tear m apart into odd part (m1) and power of 2 (m2) 1760 int p = m.getLowestSetBit(); // Max pow of 2 that divides m 1761 1762 BigInteger m1 = m.shiftRight(p); // m/2**p 1763 BigInteger m2 = ONE.shiftLeft(p); // 2**p 1764 1765 // Calculate new base from m1 1766 BigInteger base2 = (this.signum < 0 || this.compareTo(m1) >= 0 1767 ? this.mod(m1) : this); 1768 1769 // Caculate (base ** exponent) mod m1. 1770 BigInteger a1 = (m1.equals(ONE) ? ZERO : 1771 base2.oddModPow(exponent, m1)); 1772 1773 // Calculate (this ** exponent) mod m2 1774 BigInteger a2 = base.modPow2(exponent, p); 1775 1776 // Combine results using Chinese Remainder Theorem 1777 BigInteger y1 = m2.modInverse(m1); 1778 BigInteger y2 = m1.modInverse(m2); 1779 1780 result = a1.multiply(m2).multiply(y1).add 1781 (a2.multiply(m1).multiply(y2)).mod(m); 1782 } 1783 1784 return (invertResult ? result.modInverse(m) : result); 1785 } 1786 1787 static int[] bnExpModThreshTable = {7, 25, 81, 241, 673, 1793, 1788 Integer.MAX_VALUE}; // Sentinel 1789 1790 /** 1791 * Returns a BigInteger whose value is x to the power of y mod z. 1792 * Assumes: z is odd && x < z. 1793 */ 1794 private BigInteger oddModPow(BigInteger y, BigInteger z) { 1795 /* 1796 * The algorithm is adapted from Colin Plumb's C library. 1797 * 1798 * The window algorithm: 1799 * The idea is to keep a running product of b1 = n^(high-order bits of exp) 1800 * and then keep appending exponent bits to it. The following patterns 1801 * apply to a 3-bit window (k = 3): 1802 * To append 0: square 1803 * To append 1: square, multiply by n^1 1804 * To append 10: square, multiply by n^1, square 1805 * To append 11: square, square, multiply by n^3 1806 * To append 100: square, multiply by n^1, square, square 1807 * To append 101: square, square, square, multiply by n^5 1808 * To append 110: square, square, multiply by n^3, square 1809 * To append 111: square, square, square, multiply by n^7 1810 * 1811 * Since each pattern involves only one multiply, the longer the pattern 1812 * the better, except that a 0 (no multiplies) can be appended directly. 1813 * We precompute a table of odd powers of n, up to 2^k, and can then 1814 * multiply k bits of exponent at a time. Actually, assuming random 1815 * exponents, there is on average one zero bit between needs to 1816 * multiply (1/2 of the time there's none, 1/4 of the time there's 1, 1817 * 1/8 of the time, there's 2, 1/32 of the time, there's 3, etc.), so 1818 * you have to do one multiply per k+1 bits of exponent. 1819 * 1820 * The loop walks down the exponent, squaring the result buffer as 1821 * it goes. There is a wbits+1 bit lookahead buffer, buf, that is 1822 * filled with the upcoming exponent bits. (What is read after the 1823 * end of the exponent is unimportant, but it is filled with zero here.) 1824 * When the most-significant bit of this buffer becomes set, i.e. 1825 * (buf & tblmask) != 0, we have to decide what pattern to multiply 1826 * by, and when to do it. We decide, remember to do it in future 1827 * after a suitable number of squarings have passed (e.g. a pattern 1828 * of "100" in the buffer requires that we multiply by n^1 immediately; 1829 * a pattern of "110" calls for multiplying by n^3 after one more 1830 * squaring), clear the buffer, and continue. 1831 * 1832 * When we start, there is one more optimization: the result buffer 1833 * is implcitly one, so squaring it or multiplying by it can be 1834 * optimized away. Further, if we start with a pattern like "100" 1835 * in the lookahead window, rather than placing n into the buffer 1836 * and then starting to square it, we have already computed n^2 1837 * to compute the odd-powers table, so we can place that into 1838 * the buffer and save a squaring. 1839 * 1840 * This means that if you have a k-bit window, to compute n^z, 1841 * where z is the high k bits of the exponent, 1/2 of the time 1842 * it requires no squarings. 1/4 of the time, it requires 1 1843 * squaring, ... 1/2^(k-1) of the time, it reqires k-2 squarings. 1844 * And the remaining 1/2^(k-1) of the time, the top k bits are a 1845 * 1 followed by k-1 0 bits, so it again only requires k-2 1846 * squarings, not k-1. The average of these is 1. Add that 1847 * to the one squaring we have to do to compute the table, 1848 * and you'll see that a k-bit window saves k-2 squarings 1849 * as well as reducing the multiplies. (It actually doesn't 1850 * hurt in the case k = 1, either.) 1851 */ 1852 // Special case for exponent of one 1853 if (y.equals(ONE)) 1854 return this; 1855 1856 // Special case for base of zero 1857 if (signum==0) 1858 return ZERO; 1859 1860 int[] base = mag.clone(); 1861 int[] exp = y.mag; 1862 int[] mod = z.mag; 1863 int modLen = mod.length; 1864 1865 // Select an appropriate window size 1866 int wbits = 0; 1867 int ebits = bitLength(exp, exp.length); 1868 // if exponent is 65537 (0x10001), use minimum window size 1869 if ((ebits != 17) || (exp[0] != 65537)) { 1870 while (ebits > bnExpModThreshTable[wbits]) { 1871 wbits++; 1872 } 1873 } 1874 1875 // Calculate appropriate table size 1876 int tblmask = 1 << wbits; 1877 1878 // Allocate table for precomputed odd powers of base in Montgomery form 1879 int[][] table = new int[tblmask][]; 1880 for (int i=0; i<tblmask; i++) 1881 table[i] = new int[modLen]; 1882 1883 // Compute the modular inverse 1884 int inv = -MutableBigInteger.inverseMod32(mod[modLen-1]); 1885 1886 // Convert base to Montgomery form 1887 int[] a = leftShift(base, base.length, modLen << 5); 1888 1889 MutableBigInteger q = new MutableBigInteger(), 1890 a2 = new MutableBigInteger(a), 1891 b2 = new MutableBigInteger(mod); 1892 1893 MutableBigInteger r= a2.divide(b2, q); 1894 table[0] = r.toIntArray(); 1895 1896 // Pad table[0] with leading zeros so its length is at least modLen 1897 if (table[0].length < modLen) { 1898 int offset = modLen - table[0].length; 1899 int[] t2 = new int[modLen]; 1900 for (int i=0; i<table[0].length; i++) 1901 t2[i+offset] = table[0][i]; 1902 table[0] = t2; 1903 } 1904 1905 // Set b to the square of the base 1906 int[] b = squareToLen(table[0], modLen, null); 1907 b = montReduce(b, mod, modLen, inv); 1908 1909 // Set t to high half of b 1910 int[] t = new int[modLen]; 1911 for(int i=0; i<modLen; i++) 1912 t[i] = b[i]; 1913 1914 // Fill in the table with odd powers of the base 1915 for (int i=1; i<tblmask; i++) { 1916 int[] prod = multiplyToLen(t, modLen, table[i-1], modLen, null); 1917 table[i] = montReduce(prod, mod, modLen, inv); 1918 } 1919 1920 // Pre load the window that slides over the exponent 1921 int bitpos = 1 << ((ebits-1) & (32-1)); 1922 1923 int buf = 0; 1924 int elen = exp.length; 1925 int eIndex = 0; 1926 for (int i = 0; i <= wbits; i++) { 1927 buf = (buf << 1) | (((exp[eIndex] & bitpos) != 0)?1:0); 1928 bitpos >>>= 1; 1929 if (bitpos == 0) { 1930 eIndex++; 1931 bitpos = 1 << (32-1); 1932 elen--; 1933 } 1934 } 1935 1936 int multpos = ebits; 1937 1938 // The first iteration, which is hoisted out of the main loop 1939 ebits--; 1940 boolean isone = true; 1941 1942 multpos = ebits - wbits; 1943 while ((buf & 1) == 0) { 1944 buf >>>= 1; 1945 multpos++; 1946 } 1947 1948 int[] mult = table[buf >>> 1]; 1949 1950 buf = 0; 1951 if (multpos == ebits) 1952 isone = false; 1953 1954 // The main loop 1955 while(true) { 1956 ebits--; 1957 // Advance the window 1958 buf <<= 1; 1959 1960 if (elen != 0) { 1961 buf |= ((exp[eIndex] & bitpos) != 0) ? 1 : 0; 1962 bitpos >>>= 1; 1963 if (bitpos == 0) { 1964 eIndex++; 1965 bitpos = 1 << (32-1); 1966 elen--; 1967 } 1968 } 1969 1970 // Examine the window for pending multiplies 1971 if ((buf & tblmask) != 0) { 1972 multpos = ebits - wbits; 1973 while ((buf & 1) == 0) { 1974 buf >>>= 1; 1975 multpos++; 1976 } 1977 mult = table[buf >>> 1]; 1978 buf = 0; 1979 } 1980 1981 // Perform multiply 1982 if (ebits == multpos) { 1983 if (isone) { 1984 b = mult.clone(); 1985 isone = false; 1986 } else { 1987 t = b; 1988 a = multiplyToLen(t, modLen, mult, modLen, a); 1989 a = montReduce(a, mod, modLen, inv); 1990 t = a; a = b; b = t; 1991 } 1992 } 1993 1994 // Check if done 1995 if (ebits == 0) 1996 break; 1997 1998 // Square the input 1999 if (!isone) { 2000 t = b; 2001 a = squareToLen(t, modLen, a); 2002 a = montReduce(a, mod, modLen, inv); 2003 t = a; a = b; b = t; 2004 } 2005 } 2006 2007 // Convert result out of Montgomery form and return 2008 int[] t2 = new int[2*modLen]; 2009 for(int i=0; i<modLen; i++) 2010 t2[i+modLen] = b[i]; 2011 2012 b = montReduce(t2, mod, modLen, inv); 2013 2014 t2 = new int[modLen]; 2015 for(int i=0; i<modLen; i++) 2016 t2[i] = b[i]; 2017 2018 return new BigInteger(1, t2); 2019 } 2020 2021 /** 2022 * Montgomery reduce n, modulo mod. This reduces modulo mod and divides 2023 * by 2^(32*mlen). Adapted from Colin Plumb's C library. 2024 */ 2025 private static int[] montReduce(int[] n, int[] mod, int mlen, int inv) { 2026 int c=0; 2027 int len = mlen; 2028 int offset=0; 2029 2030 do { 2031 int nEnd = n[n.length-1-offset]; 2032 int carry = mulAdd(n, mod, offset, mlen, inv * nEnd); 2033 c += addOne(n, offset, mlen, carry); 2034 offset++; 2035 } while(--len > 0); 2036 2037 while(c>0) 2038 c += subN(n, mod, mlen); 2039 2040 while (intArrayCmpToLen(n, mod, mlen) >= 0) 2041 subN(n, mod, mlen); 2042 2043 return n; 2044 } 2045 2046 2047 /* 2048 * Returns -1, 0 or +1 as big-endian unsigned int array arg1 is less than, 2049 * equal to, or greater than arg2 up to length len. 2050 */ 2051 private static int intArrayCmpToLen(int[] arg1, int[] arg2, int len) { 2052 for (int i=0; i<len; i++) { 2053 long b1 = arg1[i] & LONG_MASK; 2054 long b2 = arg2[i] & LONG_MASK; 2055 if (b1 < b2) 2056 return -1; 2057 if (b1 > b2) 2058 return 1; 2059 } 2060 return 0; 2061 } 2062 2063 /** 2064 * Subtracts two numbers of same length, returning borrow. 2065 */ 2066 private static int subN(int[] a, int[] b, int len) { 2067 long sum = 0; 2068 2069 while(--len >= 0) { 2070 sum = (a[len] & LONG_MASK) - 2071 (b[len] & LONG_MASK) + (sum >> 32); 2072 a[len] = (int)sum; 2073 } 2074 2075 return (int)(sum >> 32); 2076 } 2077 2078 /** 2079 * Multiply an array by one word k and add to result, return the carry 2080 */ 2081 static int mulAdd(int[] out, int[] in, int offset, int len, int k) { 2082 long kLong = k & LONG_MASK; 2083 long carry = 0; 2084 2085 offset = out.length-offset - 1; 2086 for (int j=len-1; j >= 0; j--) { 2087 long product = (in[j] & LONG_MASK) * kLong + 2088 (out[offset] & LONG_MASK) + carry; 2089 out[offset--] = (int)product; 2090 carry = product >>> 32; 2091 } 2092 return (int)carry; 2093 } 2094 2095 /** 2096 * Add one word to the number a mlen words into a. Return the resulting 2097 * carry. 2098 */ 2099 static int addOne(int[] a, int offset, int mlen, int carry) { 2100 offset = a.length-1-mlen-offset; 2101 long t = (a[offset] & LONG_MASK) + (carry & LONG_MASK); 2102 2103 a[offset] = (int)t; 2104 if ((t >>> 32) == 0) 2105 return 0; 2106 while (--mlen >= 0) { 2107 if (--offset < 0) { // Carry out of number 2108 return 1; 2109 } else { 2110 a[offset]++; 2111 if (a[offset] != 0) 2112 return 0; 2113 } 2114 } 2115 return 1; 2116 } 2117 2118 /** 2119 * Returns a BigInteger whose value is (this ** exponent) mod (2**p) 2120 */ 2121 private BigInteger modPow2(BigInteger exponent, int p) { 2122 /* 2123 * Perform exponentiation using repeated squaring trick, chopping off 2124 * high order bits as indicated by modulus. 2125 */ 2126 BigInteger result = valueOf(1); 2127 BigInteger baseToPow2 = this.mod2(p); 2128 int expOffset = 0; 2129 2130 int limit = exponent.bitLength(); 2131 2132 if (this.testBit(0)) 2133 limit = (p-1) < limit ? (p-1) : limit; 2134 2135 while (expOffset < limit) { 2136 if (exponent.testBit(expOffset)) 2137 result = result.multiply(baseToPow2).mod2(p); 2138 expOffset++; 2139 if (expOffset < limit) 2140 baseToPow2 = baseToPow2.square().mod2(p); 2141 } 2142 2143 return result; 2144 } 2145 2146 /** 2147 * Returns a BigInteger whose value is this mod(2**p). 2148 * Assumes that this {@code BigInteger >= 0} and {@code p > 0}. 2149 */ 2150 private BigInteger mod2(int p) { 2151 if (bitLength() <= p) 2152 return this; 2153 2154 // Copy remaining ints of mag 2155 int numInts = (p + 31) >>> 5; 2156 int[] mag = new int[numInts]; 2157 for (int i=0; i<numInts; i++) 2158 mag[i] = this.mag[i + (this.mag.length - numInts)]; 2159 2160 // Mask out any excess bits 2161 int excessBits = (numInts << 5) - p; 2162 mag[0] &= (1L << (32-excessBits)) - 1; 2163 2164 return (mag[0]==0 ? new BigInteger(1, mag) : new BigInteger(mag, 1)); 2165 } 2166 2167 /** 2168 * Returns a BigInteger whose value is {@code (this}<sup>-1</sup> {@code mod m)}. 2169 * 2170 * @param m the modulus. 2171 * @return {@code this}<sup>-1</sup> {@code mod m}. 2172 * @throws ArithmeticException {@code m} ≤ 0, or this BigInteger 2173 * has no multiplicative inverse mod m (that is, this BigInteger 2174 * is not <i>relatively prime</i> to m). 2175 */ 2176 public BigInteger modInverse(BigInteger m) { 2177 if (m.signum != 1) 2178 throw new ArithmeticException("BigInteger: modulus not positive"); 2179 2180 if (m.equals(ONE)) 2181 return ZERO; 2182 2183 // Calculate (this mod m) 2184 BigInteger modVal = this; 2185 if (signum < 0 || (this.compareMagnitude(m) >= 0)) 2186 modVal = this.mod(m); 2187 2188 if (modVal.equals(ONE)) 2189 return ONE; 2190 2191 MutableBigInteger a = new MutableBigInteger(modVal); 2192 MutableBigInteger b = new MutableBigInteger(m); 2193 2194 MutableBigInteger result = a.mutableModInverse(b); 2195 return result.toBigInteger(1); 2196 } 2197 2198 // Shift Operations 2199 2200 /** 2201 * Returns a BigInteger whose value is {@code (this << n)}. 2202 * The shift distance, {@code n}, may be negative, in which case 2203 * this method performs a right shift. 2204 * (Computes <tt>floor(this * 2<sup>n</sup>)</tt>.) 2205 * 2206 * @param n shift distance, in bits. 2207 * @return {@code this << n} 2208 * @throws ArithmeticException if the shift distance is {@code 2209 * Integer.MIN_VALUE}. 2210 * @see #shiftRight 2211 */ 2212 public BigInteger shiftLeft(int n) { 2213 if (signum == 0) 2214 return ZERO; 2215 if (n==0) 2216 return this; 2217 if (n<0) { 2218 if (n == Integer.MIN_VALUE) { 2219 throw new ArithmeticException("Shift distance of Integer.MIN_VALUE not supported."); 2220 } else { 2221 return shiftRight(-n); 2222 } 2223 } 2224 int[] newMag = shiftLeft(mag,n); 2225 2226 return new BigInteger(newMag, signum); 2227 } 2228 2229 private static int[] shiftLeft(int[] mag, int n) { 2230 int nInts = n >>> 5; 2231 int nBits = n & 0x1f; 2232 int magLen = mag.length; 2233 int newMag[] = null; 2234 2235 if (nBits == 0) { 2236 newMag = new int[magLen + nInts]; 2237 for (int i=0; i<magLen; i++) 2238 newMag[i] = mag[i]; 2239 } else { 2240 int i = 0; 2241 int nBits2 = 32 - nBits; 2242 int highBits = mag[0] >>> nBits2; 2243 if (highBits != 0) { 2244 newMag = new int[magLen + nInts + 1]; 2245 newMag[i++] = highBits; 2246 } else { 2247 newMag = new int[magLen + nInts]; 2248 } 2249 int j=0; 2250 while (j < magLen-1) 2251 newMag[i++] = mag[j++] << nBits | mag[j] >>> nBits2; 2252 newMag[i] = mag[j] << nBits; 2253 } 2254 return newMag; 2255 } 2256 2257 /** 2258 * Returns a BigInteger whose value is {@code (this >> n)}. Sign 2259 * extension is performed. The shift distance, {@code n}, may be 2260 * negative, in which case this method performs a left shift. 2261 * (Computes <tt>floor(this / 2<sup>n</sup>)</tt>.) 2262 * 2263 * @param n shift distance, in bits. 2264 * @return {@code this >> n} 2265 * @throws ArithmeticException if the shift distance is {@code 2266 * Integer.MIN_VALUE}. 2267 * @see #shiftLeft 2268 */ 2269 public BigInteger shiftRight(int n) { 2270 if (n==0) 2271 return this; 2272 if (n<0) { 2273 if (n == Integer.MIN_VALUE) { 2274 throw new ArithmeticException("Shift distance of Integer.MIN_VALUE not supported."); 2275 } else { 2276 return shiftLeft(-n); 2277 } 2278 } 2279 2280 int nInts = n >>> 5; 2281 int nBits = n & 0x1f; 2282 int magLen = mag.length; 2283 int newMag[] = null; 2284 2285 // Special case: entire contents shifted off the end 2286 if (nInts >= magLen) 2287 return (signum >= 0 ? ZERO : negConst[1]); 2288 2289 if (nBits == 0) { 2290 int newMagLen = magLen - nInts; 2291 newMag = new int[newMagLen]; 2292 for (int i=0; i<newMagLen; i++) 2293 newMag[i] = mag[i]; 2294 } else { 2295 int i = 0; 2296 int highBits = mag[0] >>> nBits; 2297 if (highBits != 0) { 2298 newMag = new int[magLen - nInts]; 2299 newMag[i++] = highBits; 2300 } else { 2301 newMag = new int[magLen - nInts -1]; 2302 } 2303 2304 int nBits2 = 32 - nBits; 2305 int j=0; 2306 while (j < magLen - nInts - 1) 2307 newMag[i++] = (mag[j++] << nBits2) | (mag[j] >>> nBits); 2308 } 2309 2310 if (signum < 0) { 2311 // Find out whether any one-bits were shifted off the end. 2312 boolean onesLost = false; 2313 for (int i=magLen-1, j=magLen-nInts; i>=j && !onesLost; i--) 2314 onesLost = (mag[i] != 0); 2315 if (!onesLost && nBits != 0) 2316 onesLost = (mag[magLen - nInts - 1] << (32 - nBits) != 0); 2317 2318 if (onesLost) 2319 newMag = javaIncrement(newMag); 2320 } 2321 2322 return new BigInteger(newMag, signum); 2323 } 2324 2325 int[] javaIncrement(int[] val) { 2326 int lastSum = 0; 2327 for (int i=val.length-1; i >= 0 && lastSum == 0; i--) 2328 lastSum = (val[i] += 1); 2329 if (lastSum == 0) { 2330 val = new int[val.length+1]; 2331 val[0] = 1; 2332 } 2333 return val; 2334 } 2335 2336 // Bitwise Operations 2337 2338 /** 2339 * Returns a BigInteger whose value is {@code (this & val)}. (This 2340 * method returns a negative BigInteger if and only if this and val are 2341 * both negative.) 2342 * 2343 * @param val value to be AND'ed with this BigInteger. 2344 * @return {@code this & val} 2345 */ 2346 public BigInteger and(BigInteger val) { 2347 int[] result = new int[Math.max(intLength(), val.intLength())]; 2348 for (int i=0; i<result.length; i++) 2349 result[i] = (getInt(result.length-i-1) 2350 & val.getInt(result.length-i-1)); 2351 2352 return valueOf(result); 2353 } 2354 2355 /** 2356 * Returns a BigInteger whose value is {@code (this | val)}. (This method 2357 * returns a negative BigInteger if and only if either this or val is 2358 * negative.) 2359 * 2360 * @param val value to be OR'ed with this BigInteger. 2361 * @return {@code this | val} 2362 */ 2363 public BigInteger or(BigInteger val) { 2364 int[] result = new int[Math.max(intLength(), val.intLength())]; 2365 for (int i=0; i<result.length; i++) 2366 result[i] = (getInt(result.length-i-1) 2367 | val.getInt(result.length-i-1)); 2368 2369 return valueOf(result); 2370 } 2371 2372 /** 2373 * Returns a BigInteger whose value is {@code (this ^ val)}. (This method 2374 * returns a negative BigInteger if and only if exactly one of this and 2375 * val are negative.) 2376 * 2377 * @param val value to be XOR'ed with this BigInteger. 2378 * @return {@code this ^ val} 2379 */ 2380 public BigInteger xor(BigInteger val) { 2381 int[] result = new int[Math.max(intLength(), val.intLength())]; 2382 for (int i=0; i<result.length; i++) 2383 result[i] = (getInt(result.length-i-1) 2384 ^ val.getInt(result.length-i-1)); 2385 2386 return valueOf(result); 2387 } 2388 2389 /** 2390 * Returns a BigInteger whose value is {@code (~this)}. (This method 2391 * returns a negative value if and only if this BigInteger is 2392 * non-negative.) 2393 * 2394 * @return {@code ~this} 2395 */ 2396 public BigInteger not() { 2397 int[] result = new int[intLength()]; 2398 for (int i=0; i<result.length; i++) 2399 result[i] = ~getInt(result.length-i-1); 2400 2401 return valueOf(result); 2402 } 2403 2404 /** 2405 * Returns a BigInteger whose value is {@code (this & ~val)}. This 2406 * method, which is equivalent to {@code and(val.not())}, is provided as 2407 * a convenience for masking operations. (This method returns a negative 2408 * BigInteger if and only if {@code this} is negative and {@code val} is 2409 * positive.) 2410 * 2411 * @param val value to be complemented and AND'ed with this BigInteger. 2412 * @return {@code this & ~val} 2413 */ 2414 public BigInteger andNot(BigInteger val) { 2415 int[] result = new int[Math.max(intLength(), val.intLength())]; 2416 for (int i=0; i<result.length; i++) 2417 result[i] = (getInt(result.length-i-1) 2418 & ~val.getInt(result.length-i-1)); 2419 2420 return valueOf(result); 2421 } 2422 2423 2424 // Single Bit Operations 2425 2426 /** 2427 * Returns {@code true} if and only if the designated bit is set. 2428 * (Computes {@code ((this & (1<<n)) != 0)}.) 2429 * 2430 * @param n index of bit to test. 2431 * @return {@code true} if and only if the designated bit is set. 2432 * @throws ArithmeticException {@code n} is negative. 2433 */ 2434 public boolean testBit(int n) { 2435 if (n<0) 2436 throw new ArithmeticException("Negative bit address"); 2437 2438 return (getInt(n >>> 5) & (1 << (n & 31))) != 0; 2439 } 2440 2441 /** 2442 * Returns a BigInteger whose value is equivalent to this BigInteger 2443 * with the designated bit set. (Computes {@code (this | (1<<n))}.) 2444 * 2445 * @param n index of bit to set. 2446 * @return {@code this | (1<<n)} 2447 * @throws ArithmeticException {@code n} is negative. 2448 */ 2449 public BigInteger setBit(int n) { 2450 if (n<0) 2451 throw new ArithmeticException("Negative bit address"); 2452 2453 int intNum = n >>> 5; 2454 int[] result = new int[Math.max(intLength(), intNum+2)]; 2455 2456 for (int i=0; i<result.length; i++) 2457 result[result.length-i-1] = getInt(i); 2458 2459 result[result.length-intNum-1] |= (1 << (n & 31)); 2460 2461 return valueOf(result); 2462 } 2463 2464 /** 2465 * Returns a BigInteger whose value is equivalent to this BigInteger 2466 * with the designated bit cleared. 2467 * (Computes {@code (this & ~(1<<n))}.) 2468 * 2469 * @param n index of bit to clear. 2470 * @return {@code this & ~(1<<n)} 2471 * @throws ArithmeticException {@code n} is negative. 2472 */ 2473 public BigInteger clearBit(int n) { 2474 if (n<0) 2475 throw new ArithmeticException("Negative bit address"); 2476 2477 int intNum = n >>> 5; 2478 int[] result = new int[Math.max(intLength(), ((n + 1) >>> 5) + 1)]; 2479 2480 for (int i=0; i<result.length; i++) 2481 result[result.length-i-1] = getInt(i); 2482 2483 result[result.length-intNum-1] &= ~(1 << (n & 31)); 2484 2485 return valueOf(result); 2486 } 2487 2488 /** 2489 * Returns a BigInteger whose value is equivalent to this BigInteger 2490 * with the designated bit flipped. 2491 * (Computes {@code (this ^ (1<<n))}.) 2492 * 2493 * @param n index of bit to flip. 2494 * @return {@code this ^ (1<<n)} 2495 * @throws ArithmeticException {@code n} is negative. 2496 */ 2497 public BigInteger flipBit(int n) { 2498 if (n<0) 2499 throw new ArithmeticException("Negative bit address"); 2500 2501 int intNum = n >>> 5; 2502 int[] result = new int[Math.max(intLength(), intNum+2)]; 2503 2504 for (int i=0; i<result.length; i++) 2505 result[result.length-i-1] = getInt(i); 2506 2507 result[result.length-intNum-1] ^= (1 << (n & 31)); 2508 2509 return valueOf(result); 2510 } 2511 2512 /** 2513 * Returns the index of the rightmost (lowest-order) one bit in this 2514 * BigInteger (the number of zero bits to the right of the rightmost 2515 * one bit). Returns -1 if this BigInteger contains no one bits. 2516 * (Computes {@code (this==0? -1 : log2(this & -this))}.) 2517 * 2518 * @return index of the rightmost one bit in this BigInteger. 2519 */ 2520 public int getLowestSetBit() { 2521 @SuppressWarnings("deprecation") int lsb = lowestSetBit - 2; 2522 if (lsb == -2) { // lowestSetBit not initialized yet 2523 lsb = 0; 2524 if (signum == 0) { 2525 lsb -= 1; 2526 } else { 2527 // Search for lowest order nonzero int 2528 int i,b; 2529 for (i=0; (b = getInt(i))==0; i++) 2530 ; 2531 lsb += (i << 5) + Integer.numberOfTrailingZeros(b); 2532 } 2533 lowestSetBit = lsb + 2; 2534 } 2535 return lsb; 2536 } 2537 2538 2539 // Miscellaneous Bit Operations 2540 2541 /** 2542 * Returns the number of bits in the minimal two's-complement 2543 * representation of this BigInteger, <i>excluding</i> a sign bit. 2544 * For positive BigIntegers, this is equivalent to the number of bits in 2545 * the ordinary binary representation. (Computes 2546 * {@code (ceil(log2(this < 0 ? -this : this+1)))}.) 2547 * 2548 * @return number of bits in the minimal two's-complement 2549 * representation of this BigInteger, <i>excluding</i> a sign bit. 2550 */ 2551 public int bitLength() { 2552 @SuppressWarnings("deprecation") int n = bitLength - 1; 2553 if (n == -1) { // bitLength not initialized yet 2554 int[] m = mag; 2555 int len = m.length; 2556 if (len == 0) { 2557 n = 0; // offset by one to initialize 2558 } else { 2559 // Calculate the bit length of the magnitude 2560 int magBitLength = ((len - 1) << 5) + bitLengthForInt(mag[0]); 2561 if (signum < 0) { 2562 // Check if magnitude is a power of two 2563 boolean pow2 = (Integer.bitCount(mag[0]) == 1); 2564 for(int i=1; i< len && pow2; i++) 2565 pow2 = (mag[i] == 0); 2566 2567 n = (pow2 ? magBitLength -1 : magBitLength); 2568 } else { 2569 n = magBitLength; 2570 } 2571 } 2572 bitLength = n + 1; 2573 } 2574 return n; 2575 } 2576 2577 /** 2578 * Returns the number of bits in the two's complement representation 2579 * of this BigInteger that differ from its sign bit. This method is 2580 * useful when implementing bit-vector style sets atop BigIntegers. 2581 * 2582 * @return number of bits in the two's complement representation 2583 * of this BigInteger that differ from its sign bit. 2584 */ 2585 public int bitCount() { 2586 @SuppressWarnings("deprecation") int bc = bitCount - 1; 2587 if (bc == -1) { // bitCount not initialized yet 2588 bc = 0; // offset by one to initialize 2589 // Count the bits in the magnitude 2590 for (int i=0; i<mag.length; i++) 2591 bc += Integer.bitCount(mag[i]); 2592 if (signum < 0) { 2593 // Count the trailing zeros in the magnitude 2594 int magTrailingZeroCount = 0, j; 2595 for (j=mag.length-1; mag[j]==0; j--) 2596 magTrailingZeroCount += 32; 2597 magTrailingZeroCount += Integer.numberOfTrailingZeros(mag[j]); 2598 bc += magTrailingZeroCount - 1; 2599 } 2600 bitCount = bc + 1; 2601 } 2602 return bc; 2603 } 2604 2605 // Primality Testing 2606 2607 /** 2608 * Returns {@code true} if this BigInteger is probably prime, 2609 * {@code false} if it's definitely composite. If 2610 * {@code certainty} is ≤ 0, {@code true} is 2611 * returned. 2612 * 2613 * @param certainty a measure of the uncertainty that the caller is 2614 * willing to tolerate: if the call returns {@code true} 2615 * the probability that this BigInteger is prime exceeds 2616 * (1 - 1/2<sup>{@code certainty}</sup>). The execution time of 2617 * this method is proportional to the value of this parameter. 2618 * @return {@code true} if this BigInteger is probably prime, 2619 * {@code false} if it's definitely composite. 2620 */ 2621 public boolean isProbablePrime(int certainty) { 2622 if (certainty <= 0) 2623 return true; 2624 BigInteger w = this.abs(); 2625 if (w.equals(TWO)) 2626 return true; 2627 if (!w.testBit(0) || w.equals(ONE)) 2628 return false; 2629 2630 return w.primeToCertainty(certainty, null); 2631 } 2632 2633 // Comparison Operations 2634 2635 /** 2636 * Compares this BigInteger with the specified BigInteger. This 2637 * method is provided in preference to individual methods for each 2638 * of the six boolean comparison operators ({@literal <}, ==, 2639 * {@literal >}, {@literal >=}, !=, {@literal <=}). The suggested 2640 * idiom for performing these comparisons is: {@code 2641 * (x.compareTo(y)} <<i>op</i>> {@code 0)}, where 2642 * <<i>op</i>> is one of the six comparison operators. 2643 * 2644 * @param val BigInteger to which this BigInteger is to be compared. 2645 * @return -1, 0 or 1 as this BigInteger is numerically less than, equal 2646 * to, or greater than {@code val}. 2647 */ 2648 public int compareTo(BigInteger val) { 2649 if (signum == val.signum) { 2650 switch (signum) { 2651 case 1: 2652 return compareMagnitude(val); 2653 case -1: 2654 return val.compareMagnitude(this); 2655 default: 2656 return 0; 2657 } 2658 } 2659 return signum > val.signum ? 1 : -1; 2660 } 2661 2662 /** 2663 * Compares the magnitude array of this BigInteger with the specified 2664 * BigInteger's. This is the version of compareTo ignoring sign. 2665 * 2666 * @param val BigInteger whose magnitude array to be compared. 2667 * @return -1, 0 or 1 as this magnitude array is less than, equal to or 2668 * greater than the magnitude aray for the specified BigInteger's. 2669 */ 2670 final int compareMagnitude(BigInteger val) { 2671 int[] m1 = mag; 2672 int len1 = m1.length; 2673 int[] m2 = val.mag; 2674 int len2 = m2.length; 2675 if (len1 < len2) 2676 return -1; 2677 if (len1 > len2) 2678 return 1; 2679 for (int i = 0; i < len1; i++) { 2680 int a = m1[i]; 2681 int b = m2[i]; 2682 if (a != b) 2683 return ((a & LONG_MASK) < (b & LONG_MASK)) ? -1 : 1; 2684 } 2685 return 0; 2686 } 2687 2688 /** 2689 * Version of compareMagnitude that compares magnitude with long value. 2690 * val can't be Long.MIN_VALUE. 2691 */ 2692 final int compareMagnitude(long val) { 2693 assert val != Long.MIN_VALUE; 2694 int[] m1 = mag; 2695 int len = m1.length; 2696 if(len > 2) { 2697 return 1; 2698 } 2699 if (val < 0) { 2700 val = -val; 2701 } 2702 int highWord = (int)(val >>> 32); 2703 if (highWord==0) { 2704 if (len < 1) 2705 return -1; 2706 if (len > 1) 2707 return 1; 2708 int a = m1[0]; 2709 int b = (int)val; 2710 if (a != b) { 2711 return ((a & LONG_MASK) < (b & LONG_MASK))? -1 : 1; 2712 } 2713 return 0; 2714 } else { 2715 if (len < 2) 2716 return -1; 2717 int a = m1[0]; 2718 int b = highWord; 2719 if (a != b) { 2720 return ((a & LONG_MASK) < (b & LONG_MASK))? -1 : 1; 2721 } 2722 a = m1[1]; 2723 b = (int)val; 2724 if (a != b) { 2725 return ((a & LONG_MASK) < (b & LONG_MASK))? -1 : 1; 2726 } 2727 return 0; 2728 } 2729 } 2730 2731 /** 2732 * Compares this BigInteger with the specified Object for equality. 2733 * 2734 * @param x Object to which this BigInteger is to be compared. 2735 * @return {@code true} if and only if the specified Object is a 2736 * BigInteger whose value is numerically equal to this BigInteger. 2737 */ 2738 public boolean equals(Object x) { 2739 // This test is just an optimization, which may or may not help 2740 if (x == this) 2741 return true; 2742 2743 if (!(x instanceof BigInteger)) 2744 return false; 2745 2746 BigInteger xInt = (BigInteger) x; 2747 if (xInt.signum != signum) 2748 return false; 2749 2750 int[] m = mag; 2751 int len = m.length; 2752 int[] xm = xInt.mag; 2753 if (len != xm.length) 2754 return false; 2755 2756 for (int i = 0; i < len; i++) 2757 if (xm[i] != m[i]) 2758 return false; 2759 2760 return true; 2761 } 2762 2763 /** 2764 * Returns the minimum of this BigInteger and {@code val}. 2765 * 2766 * @param val value with which the minimum is to be computed. 2767 * @return the BigInteger whose value is the lesser of this BigInteger and 2768 * {@code val}. If they are equal, either may be returned. 2769 */ 2770 public BigInteger min(BigInteger val) { 2771 return (compareTo(val)<0 ? this : val); 2772 } 2773 2774 /** 2775 * Returns the maximum of this BigInteger and {@code val}. 2776 * 2777 * @param val value with which the maximum is to be computed. 2778 * @return the BigInteger whose value is the greater of this and 2779 * {@code val}. If they are equal, either may be returned. 2780 */ 2781 public BigInteger max(BigInteger val) { 2782 return (compareTo(val)>0 ? this : val); 2783 } 2784 2785 2786 // Hash Function 2787 2788 /** 2789 * Returns the hash code for this BigInteger. 2790 * 2791 * @return hash code for this BigInteger. 2792 */ 2793 public int hashCode() { 2794 int hashCode = 0; 2795 2796 for (int i=0; i<mag.length; i++) 2797 hashCode = (int)(31*hashCode + (mag[i] & LONG_MASK)); 2798 2799 return hashCode * signum; 2800 } 2801 2802 /** 2803 * Returns the String representation of this BigInteger in the 2804 * given radix. If the radix is outside the range from {@link 2805 * Character#MIN_RADIX} to {@link Character#MAX_RADIX} inclusive, 2806 * it will default to 10 (as is the case for 2807 * {@code Integer.toString}). The digit-to-character mapping 2808 * provided by {@code Character.forDigit} is used, and a minus 2809 * sign is prepended if appropriate. (This representation is 2810 * compatible with the {@link #BigInteger(String, int) (String, 2811 * int)} constructor.) 2812 * 2813 * @param radix radix of the String representation. 2814 * @return String representation of this BigInteger in the given radix. 2815 * @see Integer#toString 2816 * @see Character#forDigit 2817 * @see #BigInteger(java.lang.String, int) 2818 */ 2819 public String toString(int radix) { 2820 if (signum == 0) 2821 return "0"; 2822 if (radix < Character.MIN_RADIX || radix > Character.MAX_RADIX) 2823 radix = 10; 2824 2825 // Compute upper bound on number of digit groups and allocate space 2826 int maxNumDigitGroups = (4*mag.length + 6)/7; 2827 String digitGroup[] = new String[maxNumDigitGroups]; 2828 2829 // Translate number to string, a digit group at a time 2830 BigInteger tmp = this.abs(); 2831 int numGroups = 0; 2832 while (tmp.signum != 0) { 2833 BigInteger d = longRadix[radix]; 2834 2835 MutableBigInteger q = new MutableBigInteger(), 2836 a = new MutableBigInteger(tmp.mag), 2837 b = new MutableBigInteger(d.mag); 2838 MutableBigInteger r = a.divide(b, q); 2839 BigInteger q2 = q.toBigInteger(tmp.signum * d.signum); 2840 BigInteger r2 = r.toBigInteger(tmp.signum * d.signum); 2841 2842 digitGroup[numGroups++] = Long.toString(r2.longValue(), radix); 2843 tmp = q2; 2844 } 2845 2846 // Put sign (if any) and first digit group into result buffer 2847 StringBuilder buf = new StringBuilder(numGroups*digitsPerLong[radix]+1); 2848 if (signum<0) 2849 buf.append('-'); 2850 buf.append(digitGroup[numGroups-1]); 2851 2852 // Append remaining digit groups padded with leading zeros 2853 for (int i=numGroups-2; i>=0; i--) { 2854 // Prepend (any) leading zeros for this digit group 2855 int numLeadingZeros = digitsPerLong[radix]-digitGroup[i].length(); 2856 if (numLeadingZeros != 0) 2857 buf.append(zeros[numLeadingZeros]); 2858 buf.append(digitGroup[i]); 2859 } 2860 return buf.toString(); 2861 } 2862 2863 /* zero[i] is a string of i consecutive zeros. */ 2864 private static String zeros[] = new String[64]; 2865 static { 2866 zeros[63] = 2867 "000000000000000000000000000000000000000000000000000000000000000"; 2868 for (int i=0; i<63; i++) 2869 zeros[i] = zeros[63].substring(0, i); 2870 } 2871 2872 /** 2873 * Returns the decimal String representation of this BigInteger. 2874 * The digit-to-character mapping provided by 2875 * {@code Character.forDigit} is used, and a minus sign is 2876 * prepended if appropriate. (This representation is compatible 2877 * with the {@link #BigInteger(String) (String)} constructor, and 2878 * allows for String concatenation with Java's + operator.) 2879 * 2880 * @return decimal String representation of this BigInteger. 2881 * @see Character#forDigit 2882 * @see #BigInteger(java.lang.String) 2883 */ 2884 public String toString() { 2885 return toString(10); 2886 } 2887 2888 /** 2889 * Returns a byte array containing the two's-complement 2890 * representation of this BigInteger. The byte array will be in 2891 * <i>big-endian</i> byte-order: the most significant byte is in 2892 * the zeroth element. The array will contain the minimum number 2893 * of bytes required to represent this BigInteger, including at 2894 * least one sign bit, which is {@code (ceil((this.bitLength() + 2895 * 1)/8))}. (This representation is compatible with the 2896 * {@link #BigInteger(byte[]) (byte[])} constructor.) 2897 * 2898 * @return a byte array containing the two's-complement representation of 2899 * this BigInteger. 2900 * @see #BigInteger(byte[]) 2901 */ 2902 public byte[] toByteArray() { 2903 int byteLen = bitLength()/8 + 1; 2904 byte[] byteArray = new byte[byteLen]; 2905 2906 for (int i=byteLen-1, bytesCopied=4, nextInt=0, intIndex=0; i>=0; i--) { 2907 if (bytesCopied == 4) { 2908 nextInt = getInt(intIndex++); 2909 bytesCopied = 1; 2910 } else { 2911 nextInt >>>= 8; 2912 bytesCopied++; 2913 } 2914 byteArray[i] = (byte)nextInt; 2915 } 2916 return byteArray; 2917 } 2918 2919 /** 2920 * Converts this BigInteger to an {@code int}. This 2921 * conversion is analogous to a 2922 * <i>narrowing primitive conversion</i> from {@code long} to 2923 * {@code int} as defined in section 5.1.3 of 2924 * <cite>The Java™ Language Specification</cite>: 2925 * if this BigInteger is too big to fit in an 2926 * {@code int}, only the low-order 32 bits are returned. 2927 * Note that this conversion can lose information about the 2928 * overall magnitude of the BigInteger value as well as return a 2929 * result with the opposite sign. 2930 * 2931 * @return this BigInteger converted to an {@code int}. 2932 */ 2933 public int intValue() { 2934 int result = 0; 2935 result = getInt(0); 2936 return result; 2937 } 2938 2939 /** 2940 * Converts this BigInteger to a {@code long}. This 2941 * conversion is analogous to a 2942 * <i>narrowing primitive conversion</i> from {@code long} to 2943 * {@code int} as defined in section 5.1.3 of 2944 * <cite>The Java™ Language Specification</cite>: 2945 * if this BigInteger is too big to fit in a 2946 * {@code long}, only the low-order 64 bits are returned. 2947 * Note that this conversion can lose information about the 2948 * overall magnitude of the BigInteger value as well as return a 2949 * result with the opposite sign. 2950 * 2951 * @return this BigInteger converted to a {@code long}. 2952 */ 2953 public long longValue() { 2954 long result = 0; 2955 2956 for (int i=1; i>=0; i--) 2957 result = (result << 32) + (getInt(i) & LONG_MASK); 2958 return result; 2959 } 2960 2961 /** 2962 * Converts this BigInteger to a {@code float}. This 2963 * conversion is similar to the 2964 * <i>narrowing primitive conversion</i> from {@code double} to 2965 * {@code float} as defined in section 5.1.3 of 2966 * <cite>The Java™ Language Specification</cite>: 2967 * if this BigInteger has too great a magnitude 2968 * to represent as a {@code float}, it will be converted to 2969 * {@link Float#NEGATIVE_INFINITY} or {@link 2970 * Float#POSITIVE_INFINITY} as appropriate. Note that even when 2971 * the return value is finite, this conversion can lose 2972 * information about the precision of the BigInteger value. 2973 * 2974 * @return this BigInteger converted to a {@code float}. 2975 */ 2976 public float floatValue() { 2977 // Somewhat inefficient, but guaranteed to work. 2978 return Float.parseFloat(this.toString()); 2979 } 2980 2981 /** 2982 * Converts this BigInteger to a {@code double}. This 2983 * conversion is similar to the 2984 * <i>narrowing primitive conversion</i> from {@code double} to 2985 * {@code float} as defined in section 5.1.3 of 2986 * <cite>The Java™ Language Specification</cite>: 2987 * if this BigInteger has too great a magnitude 2988 * to represent as a {@code double}, it will be converted to 2989 * {@link Double#NEGATIVE_INFINITY} or {@link 2990 * Double#POSITIVE_INFINITY} as appropriate. Note that even when 2991 * the return value is finite, this conversion can lose 2992 * information about the precision of the BigInteger value. 2993 * 2994 * @return this BigInteger converted to a {@code double}. 2995 */ 2996 public double doubleValue() { 2997 // Somewhat inefficient, but guaranteed to work. 2998 return Double.parseDouble(this.toString()); 2999 } 3000 3001 /** 3002 * Returns a copy of the input array stripped of any leading zero bytes. 3003 */ 3004 private static int[] stripLeadingZeroInts(int val[]) { 3005 int vlen = val.length; 3006 int keep; 3007 3008 // Find first nonzero byte 3009 for (keep = 0; keep < vlen && val[keep] == 0; keep++) 3010 ; 3011 return java.util.Arrays.copyOfRange(val, keep, vlen); 3012 } 3013 3014 /** 3015 * Returns the input array stripped of any leading zero bytes. 3016 * Since the source is trusted the copying may be skipped. 3017 */ 3018 private static int[] trustedStripLeadingZeroInts(int val[]) { 3019 int vlen = val.length; 3020 int keep; 3021 3022 // Find first nonzero byte 3023 for (keep = 0; keep < vlen && val[keep] == 0; keep++) 3024 ; 3025 return keep == 0 ? val : java.util.Arrays.copyOfRange(val, keep, vlen); 3026 } 3027 3028 /** 3029 * Returns a copy of the input array stripped of any leading zero bytes. 3030 */ 3031 private static int[] stripLeadingZeroBytes(byte a[]) { 3032 int byteLength = a.length; 3033 int keep; 3034 3035 // Find first nonzero byte 3036 for (keep = 0; keep < byteLength && a[keep]==0; keep++) 3037 ; 3038 3039 // Allocate new array and copy relevant part of input array 3040 int intLength = ((byteLength - keep) + 3) >>> 2; 3041 int[] result = new int[intLength]; 3042 int b = byteLength - 1; 3043 for (int i = intLength-1; i >= 0; i--) { 3044 result[i] = a[b--] & 0xff; 3045 int bytesRemaining = b - keep + 1; 3046 int bytesToTransfer = Math.min(3, bytesRemaining); 3047 for (int j=8; j <= (bytesToTransfer << 3); j += 8) 3048 result[i] |= ((a[b--] & 0xff) << j); 3049 } 3050 return result; 3051 } 3052 3053 /** 3054 * Takes an array a representing a negative 2's-complement number and 3055 * returns the minimal (no leading zero bytes) unsigned whose value is -a. 3056 */ 3057 private static int[] makePositive(byte a[]) { 3058 int keep, k; 3059 int byteLength = a.length; 3060 3061 // Find first non-sign (0xff) byte of input 3062 for (keep=0; keep<byteLength && a[keep]==-1; keep++) 3063 ; 3064 3065 3066 /* Allocate output array. If all non-sign bytes are 0x00, we must 3067 * allocate space for one extra output byte. */ 3068 for (k=keep; k<byteLength && a[k]==0; k++) 3069 ; 3070 3071 int extraByte = (k==byteLength) ? 1 : 0; 3072 int intLength = ((byteLength - keep + extraByte) + 3)/4; 3073 int result[] = new int[intLength]; 3074 3075 /* Copy one's complement of input into output, leaving extra 3076 * byte (if it exists) == 0x00 */ 3077 int b = byteLength - 1; 3078 for (int i = intLength-1; i >= 0; i--) { 3079 result[i] = a[b--] & 0xff; 3080 int numBytesToTransfer = Math.min(3, b-keep+1); 3081 if (numBytesToTransfer < 0) 3082 numBytesToTransfer = 0; 3083 for (int j=8; j <= 8*numBytesToTransfer; j += 8) 3084 result[i] |= ((a[b--] & 0xff) << j); 3085 3086 // Mask indicates which bits must be complemented 3087 int mask = -1 >>> (8*(3-numBytesToTransfer)); 3088 result[i] = ~result[i] & mask; 3089 } 3090 3091 // Add one to one's complement to generate two's complement 3092 for (int i=result.length-1; i>=0; i--) { 3093 result[i] = (int)((result[i] & LONG_MASK) + 1); 3094 if (result[i] != 0) 3095 break; 3096 } 3097 3098 return result; 3099 } 3100 3101 /** 3102 * Takes an array a representing a negative 2's-complement number and 3103 * returns the minimal (no leading zero ints) unsigned whose value is -a. 3104 */ 3105 private static int[] makePositive(int a[]) { 3106 int keep, j; 3107 3108 // Find first non-sign (0xffffffff) int of input 3109 for (keep=0; keep<a.length && a[keep]==-1; keep++) 3110 ; 3111 3112 /* Allocate output array. If all non-sign ints are 0x00, we must 3113 * allocate space for one extra output int. */ 3114 for (j=keep; j<a.length && a[j]==0; j++) 3115 ; 3116 int extraInt = (j==a.length ? 1 : 0); 3117 int result[] = new int[a.length - keep + extraInt]; 3118 3119 /* Copy one's complement of input into output, leaving extra 3120 * int (if it exists) == 0x00 */ 3121 for (int i = keep; i<a.length; i++) 3122 result[i - keep + extraInt] = ~a[i]; 3123 3124 // Add one to one's complement to generate two's complement 3125 for (int i=result.length-1; ++result[i]==0; i--) 3126 ; 3127 3128 return result; 3129 } 3130 3131 /* 3132 * The following two arrays are used for fast String conversions. Both 3133 * are indexed by radix. The first is the number of digits of the given 3134 * radix that can fit in a Java long without "going negative", i.e., the 3135 * highest integer n such that radix**n < 2**63. The second is the 3136 * "long radix" that tears each number into "long digits", each of which 3137 * consists of the number of digits in the corresponding element in 3138 * digitsPerLong (longRadix[i] = i**digitPerLong[i]). Both arrays have 3139 * nonsense values in their 0 and 1 elements, as radixes 0 and 1 are not 3140 * used. 3141 */ 3142 private static int digitsPerLong[] = {0, 0, 3143 62, 39, 31, 27, 24, 22, 20, 19, 18, 18, 17, 17, 16, 16, 15, 15, 15, 14, 3144 14, 14, 14, 13, 13, 13, 13, 13, 13, 12, 12, 12, 12, 12, 12, 12, 12}; 3145 3146 private static BigInteger longRadix[] = {null, null, 3147 valueOf(0x4000000000000000L), valueOf(0x383d9170b85ff80bL), 3148 valueOf(0x4000000000000000L), valueOf(0x6765c793fa10079dL), 3149 valueOf(0x41c21cb8e1000000L), valueOf(0x3642798750226111L), 3150 valueOf(0x1000000000000000L), valueOf(0x12bf307ae81ffd59L), 3151 valueOf( 0xde0b6b3a7640000L), valueOf(0x4d28cb56c33fa539L), 3152 valueOf(0x1eca170c00000000L), valueOf(0x780c7372621bd74dL), 3153 valueOf(0x1e39a5057d810000L), valueOf(0x5b27ac993df97701L), 3154 valueOf(0x1000000000000000L), valueOf(0x27b95e997e21d9f1L), 3155 valueOf(0x5da0e1e53c5c8000L), valueOf( 0xb16a458ef403f19L), 3156 valueOf(0x16bcc41e90000000L), valueOf(0x2d04b7fdd9c0ef49L), 3157 valueOf(0x5658597bcaa24000L), valueOf( 0x6feb266931a75b7L), 3158 valueOf( 0xc29e98000000000L), valueOf(0x14adf4b7320334b9L), 3159 valueOf(0x226ed36478bfa000L), valueOf(0x383d9170b85ff80bL), 3160 valueOf(0x5a3c23e39c000000L), valueOf( 0x4e900abb53e6b71L), 3161 valueOf( 0x7600ec618141000L), valueOf( 0xaee5720ee830681L), 3162 valueOf(0x1000000000000000L), valueOf(0x172588ad4f5f0981L), 3163 valueOf(0x211e44f7d02c1000L), valueOf(0x2ee56725f06e5c71L), 3164 valueOf(0x41c21cb8e1000000L)}; 3165 3166 /* 3167 * These two arrays are the integer analogue of above. 3168 */ 3169 private static int digitsPerInt[] = {0, 0, 30, 19, 15, 13, 11, 3170 11, 10, 9, 9, 8, 8, 8, 8, 7, 7, 7, 7, 7, 7, 7, 6, 6, 6, 6, 3171 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 5}; 3172 3173 private static int intRadix[] = {0, 0, 3174 0x40000000, 0x4546b3db, 0x40000000, 0x48c27395, 0x159fd800, 3175 0x75db9c97, 0x40000000, 0x17179149, 0x3b9aca00, 0xcc6db61, 3176 0x19a10000, 0x309f1021, 0x57f6c100, 0xa2f1b6f, 0x10000000, 3177 0x18754571, 0x247dbc80, 0x3547667b, 0x4c4b4000, 0x6b5a6e1d, 3178 0x6c20a40, 0x8d2d931, 0xb640000, 0xe8d4a51, 0x1269ae40, 3179 0x17179149, 0x1cb91000, 0x23744899, 0x2b73a840, 0x34e63b41, 3180 0x40000000, 0x4cfa3cc1, 0x5c13d840, 0x6d91b519, 0x39aa400 3181 }; 3182 3183 /** 3184 * These routines provide access to the two's complement representation 3185 * of BigIntegers. 3186 */ 3187 3188 /** 3189 * Returns the length of the two's complement representation in ints, 3190 * including space for at least one sign bit. 3191 */ 3192 private int intLength() { 3193 return (bitLength() >>> 5) + 1; 3194 } 3195 3196 /* Returns sign bit */ 3197 private int signBit() { 3198 return signum < 0 ? 1 : 0; 3199 } 3200 3201 /* Returns an int of sign bits */ 3202 private int signInt() { 3203 return signum < 0 ? -1 : 0; 3204 } 3205 3206 /** 3207 * Returns the specified int of the little-endian two's complement 3208 * representation (int 0 is the least significant). The int number can 3209 * be arbitrarily high (values are logically preceded by infinitely many 3210 * sign ints). 3211 */ 3212 private int getInt(int n) { 3213 if (n < 0) 3214 return 0; 3215 if (n >= mag.length) 3216 return signInt(); 3217 3218 int magInt = mag[mag.length-n-1]; 3219 3220 return (signum >= 0 ? magInt : 3221 (n <= firstNonzeroIntNum() ? -magInt : ~magInt)); 3222 } 3223 3224 /** 3225 * Returns the index of the int that contains the first nonzero int in the 3226 * little-endian binary representation of the magnitude (int 0 is the 3227 * least significant). If the magnitude is zero, return value is undefined. 3228 */ 3229 private int firstNonzeroIntNum() { 3230 int fn = firstNonzeroIntNum - 2; 3231 if (fn == -2) { // firstNonzeroIntNum not initialized yet 3232 fn = 0; 3233 3234 // Search for the first nonzero int 3235 int i; 3236 int mlen = mag.length; 3237 for (i = mlen - 1; i >= 0 && mag[i] == 0; i--) 3238 ; 3239 fn = mlen - i - 1; 3240 firstNonzeroIntNum = fn + 2; // offset by two to initialize 3241 } 3242 return fn; 3243 } 3244 3245 /** use serialVersionUID from JDK 1.1. for interoperability */ 3246 private static final long serialVersionUID = -8287574255936472291L; 3247 3248 /** 3249 * Serializable fields for BigInteger. 3250 * 3251 * @serialField signum int 3252 * signum of this BigInteger. 3253 * @serialField magnitude int[] 3254 * magnitude array of this BigInteger. 3255 * @serialField bitCount int 3256 * number of bits in this BigInteger 3257 * @serialField bitLength int 3258 * the number of bits in the minimal two's-complement 3259 * representation of this BigInteger 3260 * @serialField lowestSetBit int 3261 * lowest set bit in the twos complement representation 3262 */ 3263 private static final ObjectStreamField[] serialPersistentFields = { 3264 new ObjectStreamField("signum", Integer.TYPE), 3265 new ObjectStreamField("magnitude", byte[].class), 3266 new ObjectStreamField("bitCount", Integer.TYPE), 3267 new ObjectStreamField("bitLength", Integer.TYPE), 3268 new ObjectStreamField("firstNonzeroByteNum", Integer.TYPE), 3269 new ObjectStreamField("lowestSetBit", Integer.TYPE) 3270 }; 3271 3272 /** 3273 * Reconstitute the {@code BigInteger} instance from a stream (that is, 3274 * deserialize it). The magnitude is read in as an array of bytes 3275 * for historical reasons, but it is converted to an array of ints 3276 * and the byte array is discarded. 3277 * Note: 3278 * The current convention is to initialize the cache fields, bitCount, 3279 * bitLength and lowestSetBit, to 0 rather than some other marker value. 3280 * Therefore, no explicit action to set these fields needs to be taken in 3281 * readObject because those fields already have a 0 value be default since 3282 * defaultReadObject is not being used. 3283 */ 3284 private void readObject(java.io.ObjectInputStream s) 3285 throws java.io.IOException, ClassNotFoundException { 3286 /* 3287 * In order to maintain compatibility with previous serialized forms, 3288 * the magnitude of a BigInteger is serialized as an array of bytes. 3289 * The magnitude field is used as a temporary store for the byte array 3290 * that is deserialized. The cached computation fields should be 3291 * transient but are serialized for compatibility reasons. 3292 */ 3293 3294 // prepare to read the alternate persistent fields 3295 ObjectInputStream.GetField fields = s.readFields(); 3296 3297 // Read the alternate persistent fields that we care about 3298 int sign = fields.get("signum", -2); 3299 byte[] magnitude = (byte[])fields.get("magnitude", null); 3300 3301 // Validate signum 3302 if (sign < -1 || sign > 1) { 3303 String message = "BigInteger: Invalid signum value"; 3304 if (fields.defaulted("signum")) 3305 message = "BigInteger: Signum not present in stream"; 3306 throw new java.io.StreamCorruptedException(message); 3307 } 3308 if ((magnitude.length == 0) != (sign == 0)) { 3309 String message = "BigInteger: signum-magnitude mismatch"; 3310 if (fields.defaulted("magnitude")) 3311 message = "BigInteger: Magnitude not present in stream"; 3312 throw new java.io.StreamCorruptedException(message); 3313 } 3314 3315 // Commit final fields via Unsafe 3316 unsafe.putIntVolatile(this, signumOffset, sign); 3317 3318 // Calculate mag field from magnitude and discard magnitude 3319 unsafe.putObjectVolatile(this, magOffset, 3320 stripLeadingZeroBytes(magnitude)); 3321 } 3322 3323 // Support for resetting final fields while deserializing 3324 private static final sun.misc.Unsafe unsafe = sun.misc.Unsafe.getUnsafe(); 3325 private static final long signumOffset; 3326 private static final long magOffset; 3327 static { 3328 try { 3329 signumOffset = unsafe.objectFieldOffset 3330 (BigInteger.class.getDeclaredField("signum")); 3331 magOffset = unsafe.objectFieldOffset 3332 (BigInteger.class.getDeclaredField("mag")); 3333 } catch (Exception ex) { 3334 throw new Error(ex); 3335 } 3336 } 3337 3338 /** 3339 * Save the {@code BigInteger} instance to a stream. 3340 * The magnitude of a BigInteger is serialized as a byte array for 3341 * historical reasons. 3342 * 3343 * @serialData two necessary fields are written as well as obsolete 3344 * fields for compatibility with older versions. 3345 */ 3346 private void writeObject(ObjectOutputStream s) throws IOException { 3347 // set the values of the Serializable fields 3348 ObjectOutputStream.PutField fields = s.putFields(); 3349 fields.put("signum", signum); 3350 fields.put("magnitude", magSerializedForm()); 3351 // The values written for cached fields are compatible with older 3352 // versions, but are ignored in readObject so don't otherwise matter. 3353 fields.put("bitCount", -1); 3354 fields.put("bitLength", -1); 3355 fields.put("lowestSetBit", -2); 3356 fields.put("firstNonzeroByteNum", -2); 3357 3358 // save them 3359 s.writeFields(); 3360 } 3361 3362 /** 3363 * Returns the mag array as an array of bytes. 3364 */ 3365 private byte[] magSerializedForm() { 3366 int len = mag.length; 3367 3368 int bitLen = (len == 0 ? 0 : ((len - 1) << 5) + bitLengthForInt(mag[0])); 3369 int byteLen = (bitLen + 7) >>> 3; 3370 byte[] result = new byte[byteLen]; 3371 3372 for (int i = byteLen - 1, bytesCopied = 4, intIndex = len - 1, nextInt = 0; 3373 i>=0; i--) { 3374 if (bytesCopied == 4) { 3375 nextInt = mag[intIndex--]; 3376 bytesCopied = 1; 3377 } else { 3378 nextInt >>>= 8; 3379 bytesCopied++; 3380 } 3381 result[i] = (byte)nextInt; 3382 } 3383 return result; 3384 } 3385 }