1 /* 2 * Licensed to the Apache Software Foundation (ASF) under one or more 3 * contributor license agreements. See the NOTICE file distributed with 4 * this work for additional information regarding copyright ownership. 5 * The ASF licenses this file to You under the Apache License, Version 2.0 6 * (the "License"); you may not use this file except in compliance with 7 * the License. You may obtain a copy of the License at 8 * 9 * http://www.apache.org/licenses/LICENSE-2.0 10 * 11 * Unless required by applicable law or agreed to in writing, software 12 * distributed under the License is distributed on an "AS IS" BASIS, 13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 * See the License for the specific language governing permissions and 15 * limitations under the License. 16 */ 17 18 package java.math; 19 20 import java.io.IOException; 21 import java.io.ObjectInputStream; 22 import java.io.ObjectOutputStream; 23 import java.io.Serializable; 24 import java.util.Random; 25 26 /** 27 * An immutable arbitrary-precision signed integer. 28 * 29 * <h3>Fast Cryptography</h3> 30 * This implementation is efficient for operations traditionally used in 31 * cryptography, such as the generation of large prime numbers and computation 32 * of the modular inverse. 33 * 34 * <h3>Slow Two's Complement Bitwise Operations</h3> 35 * This API includes operations for bitwise operations in two's complement 36 * representation. Two's complement is not the internal representation used by 37 * this implementation, so such methods may be inefficient. Use {@link 38 * java.util.BitSet} for high-performance bitwise operations on 39 * arbitrarily-large sequences of bits. 40 */ 41 public class BigInteger extends Number 42 implements Comparable<BigInteger>, Serializable { 43 44 /** This is the serialVersionUID used by the sun implementation. */ 45 private static final long serialVersionUID = -8287574255936472291L; 46 47 private transient BigInt bigInt; 48 49 private transient boolean nativeIsValid = false; 50 51 private transient boolean javaIsValid = false; 52 53 /** The magnitude of this in the little-endian representation. */ 54 transient int[] digits; 55 56 /** 57 * The length of this in measured in ints. Can be less than 58 * digits.length(). 59 */ 60 transient int numberLength; 61 62 /** The sign of this. */ 63 transient int sign; 64 65 /** The {@code BigInteger} constant 0. */ 66 public static final BigInteger ZERO = new BigInteger(0, 0); 67 68 /** The {@code BigInteger} constant 1. */ 69 public static final BigInteger ONE = new BigInteger(1, 1); 70 71 /** The {@code BigInteger} constant 10. */ 72 public static final BigInteger TEN = new BigInteger(1, 10); 73 74 /** The {@code BigInteger} constant -1. */ 75 static final BigInteger MINUS_ONE = new BigInteger(-1, 1); 76 77 /** All the {@code BigInteger} numbers in the range [0,10] are cached. */ 78 static final BigInteger[] SMALL_VALUES = { ZERO, ONE, new BigInteger(1, 2), 79 new BigInteger(1, 3), new BigInteger(1, 4), new BigInteger(1, 5), 80 new BigInteger(1, 6), new BigInteger(1, 7), new BigInteger(1, 8), 81 new BigInteger(1, 9), TEN }; 82 83 private transient int firstNonzeroDigit = -2; 84 85 /** sign field, used for serialization. */ 86 private int signum; 87 88 /** absolute value field, used for serialization */ 89 private byte[] magnitude; 90 91 /** Cache for the hash code. */ 92 private transient int hashCode = 0; 93 BigInteger(BigInt bigInt)94 BigInteger(BigInt bigInt) { 95 if (bigInt == null || bigInt.getNativeBIGNUM() == 0) { 96 throw new AssertionError(); 97 } 98 setBigInt(bigInt); 99 } 100 BigInteger(int sign, long value)101 BigInteger(int sign, long value) { 102 BigInt bigInt = new BigInt(); 103 bigInt.putULongInt(value, (sign < 0)); 104 setBigInt(bigInt); 105 } 106 107 /** 108 * Constructs a number without creating new space. This construct should be 109 * used only if the three fields of representation are known. 110 * 111 * @param sign the sign of the number. 112 * @param numberLength the length of the internal array. 113 * @param digits a reference of some array created before. 114 */ BigInteger(int sign, int numberLength, int[] digits)115 BigInteger(int sign, int numberLength, int[] digits) { 116 setJavaRepresentation(sign, numberLength, digits); 117 } 118 119 /** 120 * Constructs a random non-negative {@code BigInteger} instance in the range 121 * {@code [0, pow(2, numBits)-1]}. 122 * 123 * @param numBits maximum length of the new {@code BigInteger} in bits. 124 * @param random is the random number generator to be used. 125 * @throws IllegalArgumentException if {@code numBits} < 0. 126 */ BigInteger(int numBits, Random random)127 public BigInteger(int numBits, Random random) { 128 if (numBits < 0) { 129 throw new IllegalArgumentException("numBits < 0: " + numBits); 130 } 131 if (numBits == 0) { 132 setJavaRepresentation(0, 1, new int[] { 0 }); 133 } else { 134 int sign = 1; 135 int numberLength = (numBits + 31) >> 5; 136 int[] digits = new int[numberLength]; 137 for (int i = 0; i < numberLength; i++) { 138 digits[i] = random.nextInt(); 139 } 140 // Clear any extra bits. 141 digits[numberLength - 1] >>>= (-numBits) & 31; 142 setJavaRepresentation(sign, numberLength, digits); 143 } 144 javaIsValid = true; 145 } 146 147 /** 148 * Constructs a random {@code BigInteger} instance in the range {@code [0, 149 * pow(2, bitLength)-1]} which is probably prime. The probability that the 150 * returned {@code BigInteger} is prime is greater than 151 * {@code 1 - 1/2<sup>certainty</sup>)}. 152 * 153 * <p><b>Note:</b> the {@code Random} argument is ignored if 154 * {@code bitLength >= 16}, where this implementation will use OpenSSL's 155 * {@code BN_generate_prime_ex} as a source of cryptographically strong pseudo-random numbers. 156 * 157 * @param bitLength length of the new {@code BigInteger} in bits. 158 * @param certainty tolerated primality uncertainty. 159 * @throws ArithmeticException if {@code bitLength < 2}. 160 * @see <a href="http://www.openssl.org/docs/crypto/BN_rand.html"> 161 * Specification of random generator used from OpenSSL library</a> 162 */ BigInteger(int bitLength, int certainty, Random random)163 public BigInteger(int bitLength, int certainty, Random random) { 164 if (bitLength < 2) { 165 throw new ArithmeticException("bitLength < 2: " + bitLength); 166 } 167 if (bitLength < 16) { 168 // We have to generate short primes ourselves, because OpenSSL bottoms out at 16 bits. 169 int candidate; 170 do { 171 candidate = random.nextInt() & ((1 << bitLength) - 1); 172 candidate |= (1 << (bitLength - 1)); // Set top bit. 173 if (bitLength > 2) { 174 candidate |= 1; // Any prime longer than 2 bits must have the bottom bit set. 175 } 176 } while (!isSmallPrime(candidate)); 177 BigInt prime = new BigInt(); 178 prime.putULongInt(candidate, false); 179 setBigInt(prime); 180 } else { 181 // We need a loop here to work around an OpenSSL bug; http://b/8588028. 182 do { 183 setBigInt(BigInt.generatePrimeDefault(bitLength)); 184 } while (bitLength() != bitLength); 185 } 186 } 187 isSmallPrime(int x)188 private static boolean isSmallPrime(int x) { 189 if (x == 2) { 190 return true; 191 } 192 if ((x % 2) == 0) { 193 return false; 194 } 195 final int max = (int) Math.sqrt(x); 196 for (int i = 3; i <= max; i += 2) { 197 if ((x % i) == 0) { 198 return false; 199 } 200 } 201 return true; 202 } 203 204 /** 205 * Constructs a new {@code BigInteger} by parsing {@code value}. The string 206 * representation consists of an optional plus or minus sign followed by a 207 * non-empty sequence of decimal digits. Digits are interpreted as if by 208 * {@code Character.digit(char,10)}. 209 * 210 * @param value string representation of the new {@code BigInteger}. 211 * @throws NullPointerException if {@code value == null}. 212 * @throws NumberFormatException if {@code value} is not a valid 213 * representation of a {@code BigInteger}. 214 */ BigInteger(String value)215 public BigInteger(String value) { 216 BigInt bigInt = new BigInt(); 217 bigInt.putDecString(value); 218 setBigInt(bigInt); 219 } 220 221 /** 222 * Constructs a new {@code BigInteger} instance by parsing {@code value}. 223 * The string representation consists of an optional plus or minus sign 224 * followed by a non-empty sequence of digits in the specified radix. Digits 225 * are interpreted as if by {@code Character.digit(char, radix)}. 226 * 227 * @param value string representation of the new {@code BigInteger}. 228 * @param radix the base to be used for the conversion. 229 * @throws NullPointerException if {@code value == null}. 230 * @throws NumberFormatException if {@code value} is not a valid 231 * representation of a {@code BigInteger} or if {@code radix < 232 * Character.MIN_RADIX} or {@code radix > Character.MAX_RADIX}. 233 */ BigInteger(String value, int radix)234 public BigInteger(String value, int radix) { 235 if (value == null) { 236 throw new NullPointerException("value == null"); 237 } 238 if (radix == 10) { 239 BigInt bigInt = new BigInt(); 240 bigInt.putDecString(value); 241 setBigInt(bigInt); 242 } else if (radix == 16) { 243 BigInt bigInt = new BigInt(); 244 bigInt.putHexString(value); 245 setBigInt(bigInt); 246 } else { 247 if (radix < Character.MIN_RADIX || radix > Character.MAX_RADIX) { 248 throw new NumberFormatException("Invalid radix: " + radix); 249 } 250 if (value.isEmpty()) { 251 throw new NumberFormatException("value.isEmpty()"); 252 } 253 BigInteger.parseFromString(this, value, radix); 254 } 255 } 256 257 /** 258 * Constructs a new {@code BigInteger} instance with the given sign and 259 * magnitude. 260 * 261 * @param signum sign of the new {@code BigInteger} (-1 for negative, 0 for 262 * zero, 1 for positive). 263 * @param magnitude magnitude of the new {@code BigInteger} with the most 264 * significant byte first. 265 * @throws NullPointerException if {@code magnitude == null}. 266 * @throws NumberFormatException if the sign is not one of -1, 0, 1 or if 267 * the sign is zero and the magnitude contains non-zero entries. 268 */ BigInteger(int signum, byte[] magnitude)269 public BigInteger(int signum, byte[] magnitude) { 270 if (magnitude == null) { 271 throw new NullPointerException("magnitude == null"); 272 } 273 if (signum < -1 || signum > 1) { 274 throw new NumberFormatException("Invalid signum: " + signum); 275 } 276 if (signum == 0) { 277 for (byte element : magnitude) { 278 if (element != 0) { 279 throw new NumberFormatException("signum-magnitude mismatch"); 280 } 281 } 282 } 283 BigInt bigInt = new BigInt(); 284 bigInt.putBigEndian(magnitude, signum < 0); 285 setBigInt(bigInt); 286 } 287 288 /** 289 * Constructs a new {@code BigInteger} from the given two's complement 290 * representation. The most significant byte is the entry at index 0. The 291 * most significant bit of this entry determines the sign of the new {@code 292 * BigInteger} instance. The array must be nonempty. 293 * 294 * @param value two's complement representation of the new {@code 295 * BigInteger}. 296 * @throws NullPointerException if {@code value == null}. 297 * @throws NumberFormatException if the length of {@code value} is zero. 298 */ BigInteger(byte[] value)299 public BigInteger(byte[] value) { 300 if (value.length == 0) { 301 throw new NumberFormatException("value.length == 0"); 302 } 303 BigInt bigInt = new BigInt(); 304 bigInt.putBigEndianTwosComplement(value); 305 setBigInt(bigInt); 306 } 307 308 /** 309 * Returns the internal native representation of this big integer, computing 310 * it if necessary. 311 */ getBigInt()312 BigInt getBigInt() { 313 if (nativeIsValid) { 314 return bigInt; 315 } 316 317 synchronized (this) { 318 if (nativeIsValid) { 319 return bigInt; 320 } 321 BigInt bigInt = new BigInt(); 322 bigInt.putLittleEndianInts(digits, (sign < 0)); 323 setBigInt(bigInt); 324 return bigInt; 325 } 326 } 327 setBigInt(BigInt bigInt)328 private void setBigInt(BigInt bigInt) { 329 this.bigInt = bigInt; 330 this.nativeIsValid = true; 331 } 332 setJavaRepresentation(int sign, int numberLength, int[] digits)333 private void setJavaRepresentation(int sign, int numberLength, int[] digits) { 334 // decrement numberLength to drop leading zeroes... 335 while (numberLength > 0 && digits[--numberLength] == 0) { 336 ; 337 } 338 // ... and then increment it back because we always drop one too many 339 if (digits[numberLength++] == 0) { 340 sign = 0; 341 } 342 this.sign = sign; 343 this.digits = digits; 344 this.numberLength = numberLength; 345 this.javaIsValid = true; 346 } 347 prepareJavaRepresentation()348 void prepareJavaRepresentation() { 349 if (javaIsValid) { 350 return; 351 } 352 353 synchronized (this) { 354 if (javaIsValid) { 355 return; 356 } 357 int sign = bigInt.sign(); 358 int[] digits = (sign != 0) ? bigInt.littleEndianIntsMagnitude() : new int[] { 0 }; 359 setJavaRepresentation(sign, digits.length, digits); 360 } 361 } 362 363 /** Returns a {@code BigInteger} whose value is equal to {@code value}. */ valueOf(long value)364 public static BigInteger valueOf(long value) { 365 if (value < 0) { 366 if (value != -1) { 367 return new BigInteger(-1, -value); 368 } 369 return MINUS_ONE; 370 } else if (value < SMALL_VALUES.length) { 371 return SMALL_VALUES[(int) value]; 372 } else {// (value > 10) 373 return new BigInteger(1, value); 374 } 375 } 376 377 /** 378 * Returns the two's complement representation of this {@code BigInteger} in 379 * a byte array. 380 */ toByteArray()381 public byte[] toByteArray() { 382 return twosComplement(); 383 } 384 385 /** 386 * Returns a {@code BigInteger} whose value is the absolute value of {@code 387 * this}. 388 */ abs()389 public BigInteger abs() { 390 BigInt bigInt = getBigInt(); 391 if (bigInt.sign() >= 0) { 392 return this; 393 } 394 BigInt a = bigInt.copy(); 395 a.setSign(1); 396 return new BigInteger(a); 397 } 398 399 /** 400 * Returns a {@code BigInteger} whose value is the {@code -this}. 401 */ negate()402 public BigInteger negate() { 403 BigInt bigInt = getBigInt(); 404 int sign = bigInt.sign(); 405 if (sign == 0) { 406 return this; 407 } 408 BigInt a = bigInt.copy(); 409 a.setSign(-sign); 410 return new BigInteger(a); 411 } 412 413 /** 414 * Returns a {@code BigInteger} whose value is {@code this + value}. 415 */ add(BigInteger value)416 public BigInteger add(BigInteger value) { 417 BigInt lhs = getBigInt(); 418 BigInt rhs = value.getBigInt(); 419 if (rhs.sign() == 0) { 420 return this; 421 } 422 if (lhs.sign() == 0) { 423 return value; 424 } 425 return new BigInteger(BigInt.addition(lhs, rhs)); 426 } 427 428 /** 429 * Returns a {@code BigInteger} whose value is {@code this - value}. 430 */ subtract(BigInteger value)431 public BigInteger subtract(BigInteger value) { 432 BigInt lhs = getBigInt(); 433 BigInt rhs = value.getBigInt(); 434 if (rhs.sign() == 0) { 435 return this; 436 } 437 return new BigInteger(BigInt.subtraction(lhs, rhs)); 438 } 439 440 /** 441 * Returns the sign of this {@code BigInteger}. 442 * 443 * @return {@code -1} if {@code this < 0}, {@code 0} if {@code this == 0}, 444 * {@code 1} if {@code this > 0}. 445 */ signum()446 public int signum() { 447 if (javaIsValid) { 448 return sign; 449 } 450 return getBigInt().sign(); 451 } 452 453 /** 454 * Returns a {@code BigInteger} whose value is {@code this >> n}. For 455 * negative arguments, the result is also negative. The shift distance may 456 * be negative which means that {@code this} is shifted left. 457 * 458 * <p><b>Implementation Note:</b> Usage of this method on negative values is 459 * not recommended as the current implementation is not efficient. 460 * 461 * @param n shift distance 462 * @return {@code this >> n} if {@code n >= 0}; {@code this << (-n)} 463 * otherwise 464 */ shiftRight(int n)465 public BigInteger shiftRight(int n) { 466 return shiftLeft(-n); 467 } 468 469 /** 470 * Returns a {@code BigInteger} whose value is {@code this << n}. The 471 * result is equivalent to {@code this * pow(2, n)} if n >= 0. The shift 472 * distance may be negative which means that {@code this} is shifted right. 473 * The result then corresponds to {@code floor(this / pow(2, -n))}. 474 * 475 * <p><b>Implementation Note:</b> Usage of this method on negative values is 476 * not recommended as the current implementation is not efficient. 477 * 478 * @param n shift distance. 479 * @return {@code this << n} if {@code n >= 0}; {@code this >> (-n)}. 480 * otherwise 481 */ shiftLeft(int n)482 public BigInteger shiftLeft(int n) { 483 if (n == 0) { 484 return this; 485 } 486 int sign = signum(); 487 if (sign == 0) { 488 return this; 489 } 490 if ((sign > 0) || (n >= 0)) { 491 return new BigInteger(BigInt.shift(getBigInt(), n)); 492 } else { 493 // Negative numbers faking 2's complement: 494 // Not worth optimizing this: 495 // Sticking to Harmony Java implementation. 496 return BitLevel.shiftRight(this, -n); 497 } 498 } 499 shiftLeftOneBit()500 BigInteger shiftLeftOneBit() { 501 return (signum() == 0) ? this : BitLevel.shiftLeftOneBit(this); 502 } 503 504 /** 505 * Returns the length of the value's two's complement representation without 506 * leading zeros for positive numbers / without leading ones for negative 507 * values. 508 * 509 * <p>The two's complement representation of {@code this} will be at least 510 * {@code bitLength() + 1} bits long. 511 * 512 * <p>The value will fit into an {@code int} if {@code bitLength() < 32} or 513 * into a {@code long} if {@code bitLength() < 64}. 514 * 515 * @return the length of the minimal two's complement representation for 516 * {@code this} without the sign bit. 517 */ bitLength()518 public int bitLength() { 519 // Optimization to avoid unnecessary duplicate representation: 520 if (!nativeIsValid && javaIsValid) { 521 return BitLevel.bitLength(this); 522 } 523 return getBigInt().bitLength(); 524 } 525 526 /** 527 * Tests whether the bit at position n in {@code this} is set. The result is 528 * equivalent to {@code this & pow(2, n) != 0}. 529 * 530 * <p><b>Implementation Note:</b> Usage of this method is not recommended as 531 * the current implementation is not efficient. 532 * 533 * @param n position where the bit in {@code this} has to be inspected. 534 * @throws ArithmeticException if {@code n < 0}. 535 */ testBit(int n)536 public boolean testBit(int n) { 537 if (n < 0) { 538 throw new ArithmeticException("n < 0: " + n); 539 } 540 int sign = signum(); 541 if (sign > 0 && nativeIsValid && !javaIsValid) { 542 return getBigInt().isBitSet(n); 543 } else { 544 // Negative numbers faking 2's complement: 545 // Not worth optimizing this: 546 // Sticking to Harmony Java implementation. 547 prepareJavaRepresentation(); 548 if (n == 0) { 549 return ((digits[0] & 1) != 0); 550 } 551 int intCount = n >> 5; 552 if (intCount >= numberLength) { 553 return (sign < 0); 554 } 555 int digit = digits[intCount]; 556 n = (1 << (n & 31)); // int with 1 set to the needed position 557 if (sign < 0) { 558 int firstNonZeroDigit = getFirstNonzeroDigit(); 559 if (intCount < firstNonZeroDigit) { 560 return false; 561 } else if (firstNonZeroDigit == intCount) { 562 digit = -digit; 563 } else { 564 digit = ~digit; 565 } 566 } 567 return ((digit & n) != 0); 568 } 569 } 570 571 /** 572 * Returns a {@code BigInteger} which has the same binary representation 573 * as {@code this} but with the bit at position n set. The result is 574 * equivalent to {@code this | pow(2, n)}. 575 * 576 * <p><b>Implementation Note:</b> Usage of this method is not recommended as 577 * the current implementation is not efficient. 578 * 579 * @param n position where the bit in {@code this} has to be set. 580 * @throws ArithmeticException if {@code n < 0}. 581 */ setBit(int n)582 public BigInteger setBit(int n) { 583 prepareJavaRepresentation(); 584 if (!testBit(n)) { 585 return BitLevel.flipBit(this, n); 586 } else { 587 return this; 588 } 589 } 590 591 /** 592 * Returns a {@code BigInteger} which has the same binary representation 593 * as {@code this} but with the bit at position n cleared. The result is 594 * equivalent to {@code this & ~pow(2, n)}. 595 * 596 * <p><b>Implementation Note:</b> Usage of this method is not recommended as 597 * the current implementation is not efficient. 598 * 599 * @param n position where the bit in {@code this} has to be cleared. 600 * @throws ArithmeticException if {@code n < 0}. 601 */ clearBit(int n)602 public BigInteger clearBit(int n) { 603 prepareJavaRepresentation(); 604 if (testBit(n)) { 605 return BitLevel.flipBit(this, n); 606 } else { 607 return this; 608 } 609 } 610 611 /** 612 * Returns a {@code BigInteger} which has the same binary representation 613 * as {@code this} but with the bit at position n flipped. The result is 614 * equivalent to {@code this ^ pow(2, n)}. 615 * 616 * <p><b>Implementation Note:</b> Usage of this method is not recommended as 617 * the current implementation is not efficient. 618 * 619 * @param n position where the bit in {@code this} has to be flipped. 620 * @throws ArithmeticException if {@code n < 0}. 621 */ flipBit(int n)622 public BigInteger flipBit(int n) { 623 prepareJavaRepresentation(); 624 if (n < 0) { 625 throw new ArithmeticException("n < 0: " + n); 626 } 627 return BitLevel.flipBit(this, n); 628 } 629 630 /** 631 * Returns the position of the lowest set bit in the two's complement 632 * representation of this {@code BigInteger}. If all bits are zero (this==0) 633 * then -1 is returned as result. 634 * 635 * <p><b>Implementation Note:</b> Usage of this method is not recommended as 636 * the current implementation is not efficient. 637 */ getLowestSetBit()638 public int getLowestSetBit() { 639 prepareJavaRepresentation(); 640 if (sign == 0) { 641 return -1; 642 } 643 // (sign != 0) implies that exists some non zero digit 644 int i = getFirstNonzeroDigit(); 645 return ((i << 5) + Integer.numberOfTrailingZeros(digits[i])); 646 } 647 648 /** 649 * Returns the number of bits in the two's complement representation of 650 * {@code this} which differ from the sign bit. If {@code this} is negative, 651 * the result is equivalent to the number of bits set in the two's 652 * complement representation of {@code -this - 1}. 653 * 654 * <p>Use {@code bitLength(0)} to find the length of the binary value in 655 * bits. 656 * 657 * <p><b>Implementation Note:</b> Usage of this method is not recommended as 658 * the current implementation is not efficient. 659 */ bitCount()660 public int bitCount() { 661 prepareJavaRepresentation(); 662 return BitLevel.bitCount(this); 663 } 664 665 /** 666 * Returns a {@code BigInteger} whose value is {@code ~this}. The result 667 * of this operation is {@code -this-1}. 668 * 669 * <p><b>Implementation Note:</b> Usage of this method is not recommended as 670 * the current implementation is not efficient. 671 */ not()672 public BigInteger not() { 673 this.prepareJavaRepresentation(); 674 return Logical.not(this); 675 } 676 677 /** 678 * Returns a {@code BigInteger} whose value is {@code this & value}. 679 * 680 * <p><b>Implementation Note:</b> Usage of this method is not recommended 681 * as the current implementation is not efficient. 682 * 683 * @param value value to be and'ed with {@code this}. 684 * @throws NullPointerException if {@code value == null}. 685 */ and(BigInteger value)686 public BigInteger and(BigInteger value) { 687 this.prepareJavaRepresentation(); 688 value.prepareJavaRepresentation(); 689 return Logical.and(this, value); 690 } 691 692 /** 693 * Returns a {@code BigInteger} whose value is {@code this | value}. 694 * 695 * <p><b>Implementation Note:</b> Usage of this method is not recommended as 696 * the current implementation is not efficient. 697 * 698 * @param value value to be or'ed with {@code this}. 699 * @throws NullPointerException if {@code value == null}. 700 */ or(BigInteger value)701 public BigInteger or(BigInteger value) { 702 this.prepareJavaRepresentation(); 703 value.prepareJavaRepresentation(); 704 return Logical.or(this, value); 705 } 706 707 /** 708 * Returns a {@code BigInteger} whose value is {@code this ^ value}. 709 * 710 * <p><b>Implementation Note:</b> Usage of this method is not recommended as 711 * the current implementation is not efficient. 712 * 713 * @param value value to be xor'ed with {@code this} 714 * @throws NullPointerException if {@code value == null} 715 */ xor(BigInteger value)716 public BigInteger xor(BigInteger value) { 717 this.prepareJavaRepresentation(); 718 value.prepareJavaRepresentation(); 719 return Logical.xor(this, value); 720 } 721 722 /** 723 * Returns a {@code BigInteger} whose value is {@code this & ~value}. 724 * Evaluating {@code x.andNot(value)} returns the same result as {@code 725 * x.and(value.not())}. 726 * 727 * <p><b>Implementation Note:</b> Usage of this method is not recommended 728 * as the current implementation is not efficient. 729 * 730 * @param value value to be not'ed and then and'ed with {@code this}. 731 * @throws NullPointerException if {@code value == null}. 732 */ andNot(BigInteger value)733 public BigInteger andNot(BigInteger value) { 734 this.prepareJavaRepresentation(); 735 value.prepareJavaRepresentation(); 736 return Logical.andNot(this, value); 737 } 738 739 /** 740 * Returns this {@code BigInteger} as an int value. If {@code this} is too 741 * big to be represented as an int, then {@code this % (1 << 32)} is 742 * returned. 743 */ 744 @Override intValue()745 public int intValue() { 746 if (nativeIsValid && bigInt.twosCompFitsIntoBytes(4)) { 747 return (int) bigInt.longInt(); 748 } 749 this.prepareJavaRepresentation(); 750 return (sign * digits[0]); 751 } 752 753 /** 754 * Returns this {@code BigInteger} as a long value. If {@code this} is too 755 * big to be represented as a long, then {@code this % pow(2, 64)} is 756 * returned. 757 */ 758 @Override longValue()759 public long longValue() { 760 if (nativeIsValid && bigInt.twosCompFitsIntoBytes(8)) { 761 return bigInt.longInt(); 762 } 763 prepareJavaRepresentation(); 764 long value = numberLength > 1 765 ? ((long) digits[1]) << 32 | digits[0] & 0xFFFFFFFFL 766 : digits[0] & 0xFFFFFFFFL; 767 return sign * value; 768 } 769 770 /** 771 * Returns this {@code BigInteger} as a float. If {@code this} is too big to 772 * be represented as a float, then {@code Float.POSITIVE_INFINITY} or 773 * {@code Float.NEGATIVE_INFINITY} is returned. Note that not all integers 774 * in the range {@code [-Float.MAX_VALUE, Float.MAX_VALUE]} can be exactly 775 * represented as a float. 776 */ 777 @Override floatValue()778 public float floatValue() { 779 return (float) doubleValue(); 780 } 781 782 /** 783 * Returns this {@code BigInteger} as a double. If {@code this} is too big 784 * to be represented as a double, then {@code Double.POSITIVE_INFINITY} or 785 * {@code Double.NEGATIVE_INFINITY} is returned. Note that not all integers 786 * in the range {@code [-Double.MAX_VALUE, Double.MAX_VALUE]} can be exactly 787 * represented as a double. 788 */ 789 @Override doubleValue()790 public double doubleValue() { 791 return Conversion.bigInteger2Double(this); 792 } 793 794 /** 795 * Compares this {@code BigInteger} with {@code value}. Returns {@code -1} 796 * if {@code this < value}, {@code 0} if {@code this == value} and {@code 1} 797 * if {@code this > value}, . 798 * 799 * @param value value to be compared with {@code this}. 800 * @throws NullPointerException if {@code value == null}. 801 */ compareTo(BigInteger value)802 public int compareTo(BigInteger value) { 803 return BigInt.cmp(getBigInt(), value.getBigInt()); 804 } 805 806 /** 807 * Returns the minimum of this {@code BigInteger} and {@code value}. 808 * 809 * @param value value to be used to compute the minimum with {@code this}. 810 * @throws NullPointerException if {@code value == null}. 811 */ min(BigInteger value)812 public BigInteger min(BigInteger value) { 813 return this.compareTo(value) == -1 ? this : value; 814 } 815 816 /** 817 * Returns the maximum of this {@code BigInteger} and {@code value}. 818 * 819 * @param value value to be used to compute the maximum with {@code this} 820 * @throws NullPointerException if {@code value == null} 821 */ max(BigInteger value)822 public BigInteger max(BigInteger value) { 823 return this.compareTo(value) == 1 ? this : value; 824 } 825 826 @Override hashCode()827 public int hashCode() { 828 if (hashCode == 0) { 829 prepareJavaRepresentation(); 830 int hash = 0; 831 for (int i = 0; i < numberLength; ++i) { 832 hash = hash * 33 + digits[i]; 833 } 834 hashCode = hash * sign; 835 } 836 return hashCode; 837 } 838 839 @Override equals(Object x)840 public boolean equals(Object x) { 841 if (this == x) { 842 return true; 843 } 844 if (x instanceof BigInteger) { 845 return this.compareTo((BigInteger) x) == 0; 846 } 847 return false; 848 } 849 850 /** 851 * Returns a string representation of this {@code BigInteger} in decimal 852 * form. 853 */ 854 @Override toString()855 public String toString() { 856 return getBigInt().decString(); 857 } 858 859 /** 860 * Returns a string containing a string representation of this {@code 861 * BigInteger} with base radix. If {@code radix < Character.MIN_RADIX} or 862 * {@code radix > Character.MAX_RADIX} then a decimal representation is 863 * returned. The characters of the string representation are generated with 864 * method {@code Character.forDigit}. 865 * 866 * @param radix base to be used for the string representation. 867 */ toString(int radix)868 public String toString(int radix) { 869 if (radix == 10) { 870 return getBigInt().decString(); 871 } else { 872 prepareJavaRepresentation(); 873 return Conversion.bigInteger2String(this, radix); 874 } 875 } 876 877 /** 878 * Returns a {@code BigInteger} whose value is greatest common divisor 879 * of {@code this} and {@code value}. If {@code this == 0} and {@code 880 * value == 0} then zero is returned, otherwise the result is positive. 881 * 882 * @param value value with which the greatest common divisor is computed. 883 * @throws NullPointerException if {@code value == null}. 884 */ gcd(BigInteger value)885 public BigInteger gcd(BigInteger value) { 886 return new BigInteger(BigInt.gcd(getBigInt(), value.getBigInt())); 887 } 888 889 /** 890 * Returns a {@code BigInteger} whose value is {@code this * value}. 891 * 892 * @throws NullPointerException if {@code value == null}. 893 */ multiply(BigInteger value)894 public BigInteger multiply(BigInteger value) { 895 return new BigInteger(BigInt.product(getBigInt(), value.getBigInt())); 896 } 897 898 /** 899 * Returns a {@code BigInteger} whose value is {@code pow(this, exp)}. 900 * 901 * @throws ArithmeticException if {@code exp < 0}. 902 */ pow(int exp)903 public BigInteger pow(int exp) { 904 if (exp < 0) { 905 throw new ArithmeticException("exp < 0: " + exp); 906 } 907 return new BigInteger(BigInt.exp(getBigInt(), exp)); 908 } 909 910 /** 911 * Returns a two element {@code BigInteger} array containing 912 * {@code this / divisor} at index 0 and {@code this % divisor} at index 1. 913 * 914 * @param divisor value by which {@code this} is divided. 915 * @throws NullPointerException if {@code divisor == null}. 916 * @throws ArithmeticException if {@code divisor == 0}. 917 * @see #divide 918 * @see #remainder 919 */ divideAndRemainder(BigInteger divisor)920 public BigInteger[] divideAndRemainder(BigInteger divisor) { 921 BigInt divisorBigInt = divisor.getBigInt(); 922 BigInt quotient = new BigInt(); 923 BigInt remainder = new BigInt(); 924 BigInt.division(getBigInt(), divisorBigInt, quotient, remainder); 925 return new BigInteger[] {new BigInteger(quotient), new BigInteger(remainder) }; 926 } 927 928 /** 929 * Returns a {@code BigInteger} whose value is {@code this / divisor}. 930 * 931 * @param divisor value by which {@code this} is divided. 932 * @return {@code this / divisor}. 933 * @throws NullPointerException if {@code divisor == null}. 934 * @throws ArithmeticException if {@code divisor == 0}. 935 */ divide(BigInteger divisor)936 public BigInteger divide(BigInteger divisor) { 937 BigInt quotient = new BigInt(); 938 BigInt.division(getBigInt(), divisor.getBigInt(), quotient, null); 939 return new BigInteger(quotient); 940 } 941 942 /** 943 * Returns a {@code BigInteger} whose value is {@code this % divisor}. 944 * Regarding signs this methods has the same behavior as the % operator on 945 * ints: the sign of the remainder is the same as the sign of this. 946 * 947 * @param divisor value by which {@code this} is divided. 948 * @throws NullPointerException if {@code divisor == null}. 949 * @throws ArithmeticException if {@code divisor == 0}. 950 */ remainder(BigInteger divisor)951 public BigInteger remainder(BigInteger divisor) { 952 BigInt remainder = new BigInt(); 953 BigInt.division(getBigInt(), divisor.getBigInt(), null, remainder); 954 return new BigInteger(remainder); 955 } 956 957 /** 958 * Returns a {@code BigInteger} whose value is {@code 1/this mod m}. The 959 * modulus {@code m} must be positive. The result is guaranteed to be in the 960 * interval {@code [0, m)} (0 inclusive, m exclusive). If {@code this} is 961 * not relatively prime to m, then an exception is thrown. 962 * 963 * @param m the modulus. 964 * @throws NullPointerException if {@code m == null} 965 * @throws ArithmeticException if {@code m < 0 or} if {@code this} is not 966 * relatively prime to {@code m} 967 */ modInverse(BigInteger m)968 public BigInteger modInverse(BigInteger m) { 969 if (m.signum() <= 0) { 970 throw new ArithmeticException("modulus not positive"); 971 } 972 return new BigInteger(BigInt.modInverse(getBigInt(), m.getBigInt())); 973 } 974 975 /** 976 * Returns a {@code BigInteger} whose value is {@code 977 * pow(this, exponent) mod modulus}. The modulus must be positive. The 978 * result is guaranteed to be in the interval {@code [0, modulus)}. 979 * If the exponent is negative, then 980 * {@code pow(this.modInverse(modulus), -exponent) mod modulus} is computed. 981 * The inverse of this only exists if {@code this} is relatively prime to the modulus, 982 * otherwise an exception is thrown. 983 * 984 * @throws NullPointerException if {@code modulus == null} or {@code exponent == null}. 985 * @throws ArithmeticException if {@code modulus < 0} or if {@code exponent < 0} and 986 * not relatively prime to {@code modulus}. 987 */ modPow(BigInteger exponent, BigInteger modulus)988 public BigInteger modPow(BigInteger exponent, BigInteger modulus) { 989 if (modulus.signum() <= 0) { 990 throw new ArithmeticException("modulus.signum() <= 0"); 991 } 992 int exponentSignum = exponent.signum(); 993 if (exponentSignum == 0) { // OpenSSL gets this case wrong; http://b/8574367. 994 return ONE.mod(modulus); 995 } 996 BigInteger base = exponentSignum < 0 ? modInverse(modulus) : this; 997 return new BigInteger(BigInt.modExp(base.getBigInt(), exponent.getBigInt(), modulus.getBigInt())); 998 } 999 1000 /** 1001 * Returns a {@code BigInteger} whose value is {@code this mod m}. The 1002 * modulus {@code m} must be positive. The result is guaranteed to be in the 1003 * interval {@code [0, m)} (0 inclusive, m exclusive). The behavior of this 1004 * function is not equivalent to the behavior of the % operator defined for 1005 * the built-in {@code int}'s. 1006 * 1007 * @param m the modulus. 1008 * @return {@code this mod m}. 1009 * @throws NullPointerException if {@code m == null}. 1010 * @throws ArithmeticException if {@code m < 0}. 1011 */ 1012 public BigInteger mod(BigInteger m) { 1013 if (m.signum() <= 0) { 1014 throw new ArithmeticException("m.signum() <= 0"); 1015 } 1016 return new BigInteger(BigInt.modulus(getBigInt(), m.getBigInt())); 1017 } 1018 1019 /** 1020 * Tests whether this {@code BigInteger} is probably prime. If {@code true} 1021 * is returned, then this is prime with a probability greater than 1022 * {@code 1 - 1/2<sup>certainty</sup>)}. If {@code false} is returned, then this 1023 * is definitely composite. If the argument {@code certainty} <= 0, then 1024 * this method returns true. 1025 * 1026 * @param certainty tolerated primality uncertainty. 1027 * @return {@code true}, if {@code this} is probably prime, {@code false} 1028 * otherwise. 1029 */ 1030 public boolean isProbablePrime(int certainty) { 1031 if (certainty <= 0) { 1032 return true; 1033 } 1034 return getBigInt().isPrime(certainty); 1035 } 1036 1037 /** 1038 * Returns the smallest integer x > {@code this} which is probably prime as 1039 * a {@code BigInteger} instance. The probability that the returned {@code 1040 * BigInteger} is prime is greater than {@code 1 - 1/2<sup>100</sup>}. 1041 * 1042 * @return smallest integer > {@code this} which is probably prime. 1043 * @throws ArithmeticException if {@code this < 0}. 1044 */ 1045 public BigInteger nextProbablePrime() { 1046 if (sign < 0) { 1047 throw new ArithmeticException("sign < 0"); 1048 } 1049 return Primality.nextProbablePrime(this); 1050 } 1051 1052 /** 1053 * Returns a random positive {@code BigInteger} instance in the range {@code 1054 * [0, pow(2, bitLength)-1]} which is probably prime. The probability that 1055 * the returned {@code BigInteger} is prime is greater than {@code 1 - 1/2<sup>100</sup>)}. 1056 * 1057 * @param bitLength length of the new {@code BigInteger} in bits. 1058 * @return probably prime random {@code BigInteger} instance. 1059 * @throws IllegalArgumentException if {@code bitLength < 2}. 1060 */ 1061 public static BigInteger probablePrime(int bitLength, Random random) { 1062 return new BigInteger(bitLength, 100, random); 1063 } 1064 1065 /* Private Methods */ 1066 1067 /** 1068 * Returns the two's complement representation of this BigInteger in a byte 1069 * array. 1070 */ 1071 private byte[] twosComplement() { 1072 prepareJavaRepresentation(); 1073 if (this.sign == 0) { 1074 return new byte[] { 0 }; 1075 } 1076 BigInteger temp = this; 1077 int bitLen = bitLength(); 1078 int iThis = getFirstNonzeroDigit(); 1079 int bytesLen = (bitLen >> 3) + 1; 1080 /* Puts the little-endian int array representing the magnitude 1081 * of this BigInteger into the big-endian byte array. */ 1082 byte[] bytes = new byte[bytesLen]; 1083 int firstByteNumber = 0; 1084 int highBytes; 1085 int bytesInInteger = 4; 1086 int hB; 1087 1088 if (bytesLen - (numberLength << 2) == 1) { 1089 bytes[0] = (byte) ((sign < 0) ? -1 : 0); 1090 highBytes = 4; 1091 firstByteNumber++; 1092 } else { 1093 hB = bytesLen & 3; 1094 highBytes = (hB == 0) ? 4 : hB; 1095 } 1096 1097 int digitIndex = iThis; 1098 bytesLen -= iThis << 2; 1099 1100 if (sign < 0) { 1101 int digit = -temp.digits[digitIndex]; 1102 digitIndex++; 1103 if (digitIndex == numberLength) { 1104 bytesInInteger = highBytes; 1105 } 1106 for (int i = 0; i < bytesInInteger; i++, digit >>= 8) { 1107 bytes[--bytesLen] = (byte) digit; 1108 } 1109 while (bytesLen > firstByteNumber) { 1110 digit = ~temp.digits[digitIndex]; 1111 digitIndex++; 1112 if (digitIndex == numberLength) { 1113 bytesInInteger = highBytes; 1114 } 1115 for (int i = 0; i < bytesInInteger; i++, digit >>= 8) { 1116 bytes[--bytesLen] = (byte) digit; 1117 } 1118 } 1119 } else { 1120 while (bytesLen > firstByteNumber) { 1121 int digit = temp.digits[digitIndex]; 1122 digitIndex++; 1123 if (digitIndex == numberLength) { 1124 bytesInInteger = highBytes; 1125 } 1126 for (int i = 0; i < bytesInInteger; i++, digit >>= 8) { 1127 bytes[--bytesLen] = (byte) digit; 1128 } 1129 } 1130 } 1131 return bytes; 1132 } 1133 1134 1135 static int multiplyByInt(int[] res, int[] a, int aSize, int factor) { 1136 long carry = 0; 1137 1138 for (int i = 0; i < aSize; i++) { 1139 carry += (a[i] & 0xFFFFFFFFL) * (factor & 0xFFFFFFFFL); 1140 res[i] = (int) carry; 1141 carry >>>= 32; 1142 } 1143 return (int) carry; 1144 } 1145 1146 static int inplaceAdd(int[] a, int aSize, int addend) { 1147 long carry = addend & 0xFFFFFFFFL; 1148 1149 for (int i = 0; (carry != 0) && (i < aSize); i++) { 1150 carry += a[i] & 0xFFFFFFFFL; 1151 a[i] = (int) carry; 1152 carry >>= 32; 1153 } 1154 return (int) carry; 1155 } 1156 1157 /** @see BigInteger#BigInteger(String, int) */ parseFromString(BigInteger bi, String value, int radix)1158 private static void parseFromString(BigInteger bi, String value, int radix) { 1159 int stringLength = value.length(); 1160 int endChar = stringLength; 1161 1162 int sign; 1163 int startChar; 1164 if (value.charAt(0) == '-') { 1165 sign = -1; 1166 startChar = 1; 1167 stringLength--; 1168 } else { 1169 sign = 1; 1170 startChar = 0; 1171 } 1172 1173 /* 1174 * We use the following algorithm: split a string into portions of n 1175 * characters and convert each portion to an integer according to the 1176 * radix. Then convert an pow(radix, n) based number to binary using the 1177 * multiplication method. See D. Knuth, The Art of Computer Programming, 1178 * vol. 2. 1179 */ 1180 1181 int charsPerInt = Conversion.digitFitInInt[radix]; 1182 int bigRadixDigitsLength = stringLength / charsPerInt; 1183 int topChars = stringLength % charsPerInt; 1184 1185 if (topChars != 0) { 1186 bigRadixDigitsLength++; 1187 } 1188 int[] digits = new int[bigRadixDigitsLength]; 1189 // Get the maximal power of radix that fits in int 1190 int bigRadix = Conversion.bigRadices[radix - 2]; 1191 // Parse an input string and accumulate the BigInteger's magnitude 1192 int digitIndex = 0; // index of digits array 1193 int substrEnd = startChar + ((topChars == 0) ? charsPerInt : topChars); 1194 1195 for (int substrStart = startChar; substrStart < endChar; 1196 substrStart = substrEnd, substrEnd = substrStart + charsPerInt) { 1197 int bigRadixDigit = Integer.parseInt(value.substring(substrStart, substrEnd), radix); 1198 int newDigit = multiplyByInt(digits, digits, digitIndex, bigRadix); 1199 newDigit += inplaceAdd(digits, digitIndex, bigRadixDigit); 1200 digits[digitIndex++] = newDigit; 1201 } 1202 int numberLength = digitIndex; 1203 bi.setJavaRepresentation(sign, numberLength, digits); 1204 } 1205 getFirstNonzeroDigit()1206 int getFirstNonzeroDigit() { 1207 if (firstNonzeroDigit == -2) { 1208 int i; 1209 if (this.sign == 0) { 1210 i = -1; 1211 } else { 1212 for (i = 0; digits[i] == 0; i++) { 1213 ; 1214 } 1215 } 1216 firstNonzeroDigit = i; 1217 } 1218 return firstNonzeroDigit; 1219 } 1220 1221 /** 1222 * Returns a copy of the current instance to achieve immutability 1223 */ copy()1224 BigInteger copy() { 1225 prepareJavaRepresentation(); 1226 int[] copyDigits = new int[numberLength]; 1227 System.arraycopy(digits, 0, copyDigits, 0, numberLength); 1228 return new BigInteger(sign, numberLength, copyDigits); 1229 } 1230 1231 /** 1232 * Assigns all transient fields upon deserialization of a {@code BigInteger} 1233 * instance. 1234 */ readObject(ObjectInputStream in)1235 private void readObject(ObjectInputStream in) 1236 throws IOException, ClassNotFoundException { 1237 in.defaultReadObject(); 1238 BigInt bigInt = new BigInt(); 1239 bigInt.putBigEndian(magnitude, signum < 0); 1240 setBigInt(bigInt); 1241 } 1242 1243 /** 1244 * Prepares this {@code BigInteger} for serialization, i.e. the 1245 * non-transient fields {@code signum} and {@code magnitude} are assigned. 1246 */ writeObject(ObjectOutputStream out)1247 private void writeObject(ObjectOutputStream out) throws IOException { 1248 BigInt bigInt = getBigInt(); 1249 signum = bigInt.sign(); 1250 magnitude = bigInt.bigEndianMagnitude(); 1251 out.defaultWriteObject(); 1252 } 1253 } 1254