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