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