2 * Copyright (c) 1996, 2007, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
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).
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.
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
27 * Portions Copyright (c) 1995 Colin Plumb. All rights reserved.
32 import java.util.Random;
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.
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
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.
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.
64 * <p>Comparison operations perform signed integer comparisons, analogous to
65 * those performed by Java's relational and equality operators.
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)},
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.
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.
89 * <p>All methods and constructors in this class throw
90 * {@code NullPointerException} when passed
91 * a null object reference for any input parameter.
95 * @author Michael McCloskey
99 public class BigInteger extends Number implements Comparable<BigInteger> {
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.
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.
121 // These "redundant fields" are initialized with recognizable nonsense
122 // values, and cached the first time they are needed (or never, if they
126 * One plus the bitCount of this BigInteger. Zeros means unitialized.
130 * @deprecated Deprecated since logical value is offset from stored
131 * value and correction factor is applied in accessor method.
134 private int bitCount;
137 * One plus the bitLength of this BigInteger. Zeros means unitialized.
138 * (either value is acceptable).
142 * @deprecated Deprecated since logical value is offset from stored
143 * value and correction factor is applied in accessor method.
146 private int bitLength;
149 * Two plus the lowest set bit of this BigInteger, as returned by
153 * @see #getLowestSetBit
154 * @deprecated Deprecated since logical value is offset from stored
155 * value and correction factor is applied in accessor method.
158 private int lowestSetBit;
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.
169 private int firstNonzeroIntNum;
172 * This mask is used to obtain the value of an int as if it were unsigned.
174 final static long LONG_MASK = 0xffffffffL;
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.
184 * @param val big-endian two's-complement binary representation of
186 * @throws NumberFormatException {@code val} is zero bytes long.
188 public BigInteger(byte[] val) {
190 throw new NumberFormatException("Zero length BigInteger");
193 mag = makePositive(val);
196 mag = stripLeadingZeroBytes(val);
197 signum = (mag.length == 0 ? 0 : 1);
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.
207 private BigInteger(int[] val) {
209 throw new NumberFormatException("Zero length BigInteger");
212 mag = makePositive(val);
215 mag = trustedStripLeadingZeroInts(val);
216 signum = (mag.length == 0 ? 0 : 1);
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.
228 * @param signum signum of the number (-1 for negative, 0 for zero, 1
230 * @param magnitude big-endian binary representation of the magnitude of
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.
236 public BigInteger(int signum, byte[] magnitude) {
237 this.mag = stripLeadingZeroBytes(magnitude);
239 if (signum < -1 || signum > 1)
240 throw(new NumberFormatException("Invalid signum value"));
242 if (this.mag.length==0) {
246 throw(new NumberFormatException("signum-magnitude mismatch"));
247 this.signum = signum;
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.
257 private BigInteger(int signum, int[] magnitude) {
258 this.mag = stripLeadingZeroInts(magnitude);
260 if (signum < -1 || signum > 1)
261 throw(new NumberFormatException("Invalid signum value"));
263 if (this.mag.length==0) {
267 throw(new NumberFormatException("signum-magnitude mismatch"));
268 this.signum = signum;
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).
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
289 public BigInteger(String val, int radix) {
290 int cursor = 0, numDigits;
291 final int len = val.length();
293 if (radix < Character.MIN_RADIX || radix > Character.MAX_RADIX)
294 throw new NumberFormatException("Radix out of range");
296 throw new NumberFormatException("Zero length BigInteger");
298 // Check for at most one leading sign
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) {
307 throw new NumberFormatException("Zero length BigInteger");
312 throw new NumberFormatException("Illegal embedded sign character");
314 // Skip leading zeros and compute number of digits in magnitude
315 while (cursor < len &&
316 Character.digit(val.charAt(cursor), radix) == 0)
324 numDigits = len - cursor;
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];
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");
342 // Process remaining digit groups
343 int superRadix = intRadix[radix];
345 while (cursor < len) {
346 group = val.substring(cursor, cursor += digitsPerInt[radix]);
347 groupVal = Integer.parseInt(group, radix);
349 throw new NumberFormatException("Illegal digit");
350 destructiveMulAdd(magnitude, superRadix, groupVal);
352 // Required for cases where the array was overallocated.
353 mag = trustedStripLeadingZeroInts(magnitude);
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;
361 // Check for leading minus sign
365 throw new NumberFormatException("Zero length BigInteger");
368 } else if (val[0] == '+') {
370 throw new NumberFormatException("Zero length BigInteger");
374 // Skip leading zeros and compute number of digits in magnitude
375 while (cursor < len && Character.digit(val[cursor], 10) == 0)
383 numDigits = len - cursor;
386 // Pre-allocate array of expected size
391 int numBits = (int)(((numDigits * bitsPerDigit[10]) >>> 10) + 1);
392 numWords = (numBits + 31) >>> 5;
394 int[] magnitude = new int[numWords];
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);
402 // Process remaining digit groups
403 while (cursor < len) {
404 int groupVal = parseInt(val, cursor, cursor += digitsPerInt[10]);
405 destructiveMulAdd(magnitude, intRadix[10], groupVal);
407 mag = trustedStripLeadingZeroInts(magnitude);
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);
416 throw new NumberFormatException(new String(source));
418 for (int index = start; index<end; index++) {
419 int nextVal = Character.digit(source[index], 10);
421 throw new NumberFormatException(new String(source));
422 result = 10*result + nextVal;
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,
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;
445 for (int i = len-1; i >= 0; i--) {
446 product = ylong * (x[i] & LONG_MASK) + carry;
448 carry = product >>> 32;
451 // Perform the addition
452 long sum = (x[len-1] & LONG_MASK) + zlong;
455 for (int i = len-2; i >= 0; i--) {
456 sum = (x[i] & LONG_MASK) + carry;
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
470 * @param val decimal String representation of BigInteger.
471 * @throws NumberFormatException {@code val} is not a valid representation
473 * @see Character#digit
475 public BigInteger(String val) {
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.
486 * @param numBits maximum bitLength of the new BigInteger.
487 * @param rnd source of randomness to be used in computing the new
489 * @throws IllegalArgumentException {@code numBits} is negative.
492 public BigInteger(int numBits, Random rnd) {
493 this(1, randomBits(numBits, rnd));
496 private static byte[] randomBits(int numBits, Random rnd) {
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];
502 // Generate random bytes and mask out any excess bits
504 rnd.nextBytes(randomBits);
505 int excessBits = 8*numBytes - numBits;
506 randomBits[0] &= (1 << (8-excessBits)) - 1;
512 * Constructs a randomly generated positive BigInteger that is probably
513 * prime, with the specified bitLength.
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.
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}.
530 public BigInteger(int bitLength, int certainty, Random rnd) {
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));
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;
546 // Certainty required to meet the spec of probablePrime
547 private static final int DEFAULT_PRIME_CERTAINTY = 100;
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>.
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}.
562 public static BigInteger probablePrime(int bitLength, Random rnd) {
564 throw new ArithmeticException("bitLength < 2");
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));
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
577 * This method assumes bitLength > 1.
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
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
591 temp[magLen-1] |= 1; // Make odd if bitlen > 2
593 BigInteger p = new BigInteger(temp, 1);
595 // Do cheap "pre-test" if applicable
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
604 // All candidates of bitLength 2 and 3 are prime by this point
608 // Do expensive test if we survive pre-test (or it's inapplicable)
609 if (p.primeToCertainty(certainty, rnd))
614 private static final BigInteger SMALL_PRIME_PRODUCT
615 = valueOf(3L*5*7*11*13*17*19*23*29*31*37*41);
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
623 private static BigInteger largePrime(int bitLength, int certainty, Random rnd) {
625 p = new BigInteger(bitLength, rnd).setBit(bitLength-1);
626 p.mag[p.mag.length-1] &= 0xfffffffe;
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);
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);
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}.
651 * @return the first integer greater than this {@code BigInteger} that
653 * @throws ArithmeticException {@code this < 0}.
656 public BigInteger nextProbablePrime() {
658 throw new ArithmeticException("start < 0: " + this);
660 // Handle trivial cases
661 if ((this.signum == 0) || this.equals(ONE))
664 BigInteger result = this.add(ONE);
666 // Fastpath for small numbers
667 if (result.bitLength() < SMALL_PRIME_THRESHOLD) {
669 // Ensure an odd number
670 if (!result.testBit(0))
671 result = result.add(ONE);
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
685 // All candidates of bitLength 2 and 3 are prime by this point
686 if (result.bitLength() < 4)
689 // The expensive test
690 if (result.primeToCertainty(DEFAULT_PRIME_CERTAINTY, null))
693 result = result.add(TWO);
697 // Start at previous even number
698 if (result.testBit(0))
699 result = result.subtract(ONE);
701 // Looking for the next large prime
702 int searchLen = (result.bitLength() / 20) * 64;
705 BitSieve searchSieve = new BitSieve(result, searchLen);
706 BigInteger candidate = searchSieve.retrieve(result,
707 DEFAULT_PRIME_CERTAINTY, null);
708 if (candidate != null)
710 result = result.add(BigInteger.valueOf(2 * searchLen));
715 * Returns {@code true} if this BigInteger is probably prime,
716 * {@code false} if it's definitely composite.
718 * This method assumes bitLength > 2.
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.
728 boolean primeToCertainty(int certainty, Random random) {
730 int n = (Math.min(certainty, Integer.MAX_VALUE-1)+1)/2;
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) {
738 rounds = n < rounds ? n : rounds;
739 return passesMillerRabin(rounds, random);
742 if (sizeInBits < 256) {
744 } else if (sizeInBits < 512) {
746 } else if (sizeInBits < 768) {
748 } else if (sizeInBits < 1024) {
753 rounds = n < rounds ? n : rounds;
755 return passesMillerRabin(rounds, random) && passesLucasLehmer();
759 * Returns true iff this BigInteger is a Lucas-Lehmer probable prime.
761 * The following assumptions are made:
762 * This BigInteger is a positive, odd number.
764 private boolean passesLucasLehmer() {
765 BigInteger thisPlusOne = this.add(ONE);
769 while (jacobiSymbol(d, this) != -1) {
770 // 5, -7, 9, -11, ...
771 d = (d<0) ? Math.abs(d)+2 : -(d+2);
775 BigInteger u = lucasLehmerSequence(d, thisPlusOne, this);
778 return u.mod(this).equals(ZERO);
782 * Computes Jacobi(p,n).
783 * Assumes n positive, odd, n>=3.
785 private static int jacobiSymbol(int p, BigInteger n) {
789 // Algorithm and comments adapted from Colin Plumb's C library.
791 int u = n.mag[n.mag.length-1];
797 if ((n8 == 3) || (n8 == 7))
798 j = -j; // 3 (011) or 7 (111) mod 8
801 // Get rid of factors of 2 in p
806 if (((u ^ (u>>1)) & 2) != 0)
807 j = -j; // 3 (011) or 5 (101) mod 8
811 // Then, apply quadratic reciprocity
812 if ((p & u & 2) != 0) // p = u = 3 (mod 4)?
814 // And reduce u mod p
815 u = n.mod(BigInteger.valueOf(p)).intValue();
817 // Now compute Jacobi(u,p), u < p
823 if (((p ^ (p>>1)) & 2) != 0)
824 j = -j; // 3 (011) or 5 (101) mod 8
828 // Now both u and p are odd, so use quadratic reciprocity
830 int t = u; u = p; p = t;
831 if ((u & p & 2) != 0) // u = p = 3 (mod 4)?
833 // Now u >= p, so it can be reduced
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;
844 for (int i=k.bitLength()-2; i>=0; i--) {
845 u2 = u.multiply(v).mod(n);
847 v2 = v.square().add(d.multiply(u.square())).mod(n);
851 v2 = v2.shiftRight(1);
855 u2 = u.add(v).mod(n);
859 u2 = u2.shiftRight(1);
860 v2 = v.add(d.multiply(u)).mod(n);
863 v2 = v2.shiftRight(1);
871 private static volatile Random staticRandom;
873 private static Random getSecureRandom() {
874 if (staticRandom == null) {
875 staticRandom = new java.security.SecureRandom();
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
885 * The following assumptions are made:
886 * This BigInteger is a positive, odd number greater than 2.
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();
898 rnd = getSecureRandom();
900 for (int i=0; i<iterations; i++) {
901 // Generate a uniform random on (1, this)
904 b = new BigInteger(this.bitLength(), rnd);
905 } while (b.compareTo(ONE) <= 0 || b.compareTo(this) >= 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)
912 z = z.modPow(TWO, this);
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.
923 BigInteger(int[] magnitude, int signum) {
924 this.signum = (magnitude.length==0 ? 0 : signum);
925 this.mag = magnitude;
929 * This private constructor is for internal use and assumes that its
930 * arguments are correct.
932 private BigInteger(byte[] magnitude, int signum) {
933 this.signum = (magnitude.length==0 ? 0 : signum);
934 this.mag = stripLeadingZeroBytes(magnitude);
937 //Static Factory Methods
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.
945 * @param val value of the BigInteger to return.
946 * @return a BigInteger with the specified value.
948 public static BigInteger valueOf(long val) {
949 // If -MAX_CONSTANT < val < MAX_CONSTANT, return stashed constant
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];
957 return new BigInteger(val);
961 * Constructs a BigInteger with the specified value, which may not be zero.
963 private BigInteger(long val) {
971 int highWord = (int)(val >>> 32);
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).
987 private static BigInteger valueOf(int val[]) {
988 return (val[0]>0 ? new BigInteger(val, 1) : new BigInteger(val));
994 * Initialize static constant array when class is loaded.
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];
1000 for (int i = 1; i <= MAX_CONSTANT; i++) {
1001 int[] magnitude = new int[1];
1003 posConst[i] = new BigInteger(magnitude, 1);
1004 negConst[i] = new BigInteger(magnitude, -1);
1009 * The BigInteger constant zero.
1013 public static final BigInteger ZERO = new BigInteger(new int[0], 0);
1016 * The BigInteger constant one.
1020 public static final BigInteger ONE = valueOf(1);
1023 * The BigInteger constant two. (Not exported.)
1025 private static final BigInteger TWO = valueOf(2);
1028 * The BigInteger constant ten.
1032 public static final BigInteger TEN = valueOf(10);
1034 // Arithmetic Operations
1037 * Returns a BigInteger whose value is {@code (this + val)}.
1039 * @param val value to be added to this BigInteger.
1040 * @return {@code this + val}
1042 public BigInteger add(BigInteger val) {
1043 if (val.signum == 0)
1047 if (val.signum == signum)
1048 return new BigInteger(add(mag, val.mag), signum);
1050 int cmp = compareMagnitude(val);
1053 int[] resultMag = (cmp > 0 ? subtract(mag, val.mag)
1054 : subtract(val.mag, mag));
1055 resultMag = trustedStripLeadingZeroInts(resultMag);
1057 return new BigInteger(resultMag, cmp == signum ? 1 : -1);
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
1065 private static int[] add(int[] x, int[] y) {
1066 // If x is shorter, swap the two arrays
1067 if (x.length < y.length) {
1073 int xIndex = x.length;
1074 int yIndex = y.length;
1075 int result[] = new int[xIndex];
1078 // Add common parts of both numbers
1080 sum = (x[--xIndex] & LONG_MASK) +
1081 (y[--yIndex] & LONG_MASK) + (sum >>> 32);
1082 result[xIndex] = (int)sum;
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);
1090 // Copy remainder of longer number
1092 result[--xIndex] = x[xIndex];
1094 // Grow result if necessary
1096 int bigger[] = new int[result.length + 1];
1097 System.arraycopy(result, 0, bigger, 1, result.length);
1105 * Returns a BigInteger whose value is {@code (this - val)}.
1107 * @param val value to be subtracted from this BigInteger.
1108 * @return {@code this - val}
1110 public BigInteger subtract(BigInteger val) {
1111 if (val.signum == 0)
1114 return val.negate();
1115 if (val.signum != signum)
1116 return new BigInteger(add(mag, val.mag), signum);
1118 int cmp = compareMagnitude(val);
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);
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
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;
1139 // Subtract common parts of both numbers
1140 while(littleIndex > 0) {
1141 difference = (big[--bigIndex] & LONG_MASK) -
1142 (little[--littleIndex] & LONG_MASK) +
1144 result[bigIndex] = (int)difference;
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);
1152 // Copy remainder of longer number
1153 while (bigIndex > 0)
1154 result[--bigIndex] = big[bigIndex];
1160 * Returns a BigInteger whose value is {@code (this * val)}.
1162 * @param val value to be multiplied by this BigInteger.
1163 * @return {@code this * val}
1165 public BigInteger multiply(BigInteger val) {
1166 if (val.signum == 0 || signum == 0)
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);
1176 * Package private methods used by BigDecimal code to multiply a BigInteger
1177 * with a long. Assumes v is not equal to INFLATED.
1179 BigInteger multiply(long v) {
1180 if (v == 0 || signum == 0)
1182 if (v == BigDecimal.INFLATED)
1183 return multiply(BigInteger.valueOf(v));
1184 int rsign = (v > 0 ? signum : -signum);
1187 long dh = v >>> 32; // higher order bits
1188 long dl = v & LONG_MASK; // lower order bits
1190 int xlen = mag.length;
1192 int[] rmag = (dh == 0L) ? (new int[xlen + 1]) : (new int[xlen + 2]);
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;
1200 rmag[rstart] = (int)carry;
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;
1210 rmag[0] = (int)carry;
1213 rmag = java.util.Arrays.copyOfRange(rmag, 1, rmag.length);
1214 return new BigInteger(rmag, rsign);
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.
1221 private int[] multiplyToLen(int[] x, int xlen, int[] y, int ylen, int[] z) {
1222 int xstart = xlen - 1;
1223 int ystart = ylen - 1;
1225 if (z == null || z.length < (xlen+ ylen))
1226 z = new int[xlen+ylen];
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;
1235 z[xstart] = (int)carry;
1237 for (int i = xstart-1; i >= 0; i--) {
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;
1252 * Returns a BigInteger whose value is {@code (this<sup>2</sup>)}.
1254 * @return {@code this<sup>2</sup>}
1256 private BigInteger square() {
1259 int[] z = squareToLen(mag, mag.length, null);
1260 return new BigInteger(trustedStripLeadingZeroInts(z), 1);
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.
1267 private static final int[] squareToLen(int[] x, int len, int[] z) {
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:
1275 * ==================
1282 * Note that everything above the main diagonal:
1283 * ae be ce de = (abcd) * e
1284 * ad bd cd = (abc) * d
1288 * is a copy of everything below the main diagonal:
1294 * Thus, the sum is 2 * (off the diagonal) + diagonal.
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.
1302 int zlen = len << 1;
1303 if (z == null || z.length < zlen)
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;
1316 // Add in off-diagonal sums
1317 for (int i=len, offset=1; i>0; i--, offset+=2) {
1319 t = mulAdd(z, x, offset, i-1, t);
1320 addOne(z, offset-1, i, t);
1323 // Shift back up and set low bit
1324 primitiveLeftShift(z, zlen, 1);
1325 z[zlen-1] |= x[len-1] & 1;
1331 * Returns a BigInteger whose value is {@code (this / val)}.
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.
1337 public BigInteger divide(BigInteger val) {
1338 MutableBigInteger q = new MutableBigInteger(),
1339 a = new MutableBigInteger(this.mag),
1340 b = new MutableBigInteger(val.mag);
1343 return q.toBigInteger(this.signum == val.signum ? 1 : -1);
1347 * Returns an array of two BigIntegers containing {@code (this / val)}
1348 * followed by {@code (this % val)}.
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.
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);
1369 * Returns a BigInteger whose value is {@code (this % val)}.
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.
1376 public BigInteger remainder(BigInteger val) {
1377 MutableBigInteger q = new MutableBigInteger(),
1378 a = new MutableBigInteger(this.mag),
1379 b = new MutableBigInteger(val.mag);
1381 return a.divide(b, q).toBigInteger(this.signum);
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.
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.)
1393 public BigInteger pow(int exponent) {
1395 throw new ArithmeticException("Negative exponent");
1397 return (exponent==0 ? ONE : this);
1399 // Perform exponentiation using repeated squaring trick
1400 int newSign = (signum<0 && (exponent&1)==1 ? -1 : 1);
1401 int[] baseToPow2 = this.mag;
1404 while (exponent != 0) {
1405 if ((exponent & 1)==1) {
1406 result = multiplyToLen(result, result.length,
1407 baseToPow2, baseToPow2.length, null);
1408 result = trustedStripLeadingZeroInts(result);
1410 if ((exponent >>>= 1) != 0) {
1411 baseToPow2 = squareToLen(baseToPow2, baseToPow2.length, null);
1412 baseToPow2 = trustedStripLeadingZeroInts(baseToPow2);
1415 return new BigInteger(result, newSign);
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}.
1423 * @param val value with which the GCD is to be computed.
1424 * @return {@code GCD(abs(this), abs(val))}
1426 public BigInteger gcd(BigInteger val) {
1427 if (val.signum == 0)
1429 else if (this.signum == 0)
1432 MutableBigInteger a = new MutableBigInteger(this);
1433 MutableBigInteger b = new MutableBigInteger(val);
1435 MutableBigInteger result = a.hybridGCD(b);
1437 return result.toBigInteger(1);
1441 * Package private method to return bit length for an integer.
1443 static int bitLengthForInt(int n) {
1444 return 32 - Integer.numberOfLeadingZeros(n);
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.
1451 private static int[] leftShift(int[] a, int len, int n) {
1452 int nInts = n >>> 5;
1454 int bitsInHighWord = bitLengthForInt(a[0]);
1456 // If shift can be done without recopy, do so
1457 if (n <= (32-bitsInHighWord)) {
1458 primitiveLeftShift(a, len, nBits);
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++)
1465 primitiveLeftShift(result, result.length, nBits);
1468 int result[] = new int[nInts+len+1];
1469 for (int i=0; i<len; i++)
1471 primitiveRightShift(result, result.length, 32 - nBits);
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) {
1480 for (int i=len-1, c=a[i]; i>0; i--) {
1483 a[i] = (c << n2) | (b >>> n);
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)
1494 for (int i=0, c=a[i], m=i+len-1; i<m; i++) {
1497 a[i] = (b << n) | (c >>> n2);
1503 * Calculate bitlength of contents of the first len elements an int array,
1504 * assuming there are no leading zero ints.
1506 private static int bitLength(int[] val, int len) {
1509 return ((len - 1) << 5) + bitLengthForInt(val[0]);
1513 * Returns a BigInteger whose value is the absolute value of this
1516 * @return {@code abs(this)}
1518 public BigInteger abs() {
1519 return (signum >= 0 ? this : this.negate());
1523 * Returns a BigInteger whose value is {@code (-this)}.
1525 * @return {@code -this}
1527 public BigInteger negate() {
1528 return new BigInteger(this.mag, -this.signum);
1532 * Returns the signum function of this BigInteger.
1534 * @return -1, 0 or 1 as the value of this BigInteger is negative, zero or
1537 public int signum() {
1541 // Modular Arithmetic Operations
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.
1548 * @param m the modulus.
1549 * @return {@code this mod m}
1550 * @throws ArithmeticException {@code m} ≤ 0
1553 public BigInteger mod(BigInteger m) {
1555 throw new ArithmeticException("BigInteger: modulus not positive");
1557 BigInteger result = this.remainder(m);
1558 return (result.signum >= 0 ? result : result.add(m));
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.)
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}.
1574 public BigInteger modPow(BigInteger exponent, BigInteger m) {
1576 throw new ArithmeticException("BigInteger: modulus not positive");
1579 if (exponent.signum == 0)
1580 return (m.equals(ONE) ? ZERO : ONE);
1582 if (this.equals(ONE))
1583 return (m.equals(ONE) ? ZERO : ONE);
1585 if (this.equals(ZERO) && exponent.signum >= 0)
1588 if (this.equals(negConst[1]) && (!exponent.testBit(0)))
1589 return (m.equals(ONE) ? ZERO : ONE);
1591 boolean invertResult;
1592 if ((invertResult = (exponent.signum < 0)))
1593 exponent = exponent.negate();
1595 BigInteger base = (this.signum < 0 || this.compareTo(m) >= 0
1596 ? this.mod(m) : this);
1598 if (m.testBit(0)) { // odd modulus
1599 result = base.oddModPow(exponent, m);
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.
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
1610 BigInteger m1 = m.shiftRight(p); // m/2**p
1611 BigInteger m2 = ONE.shiftLeft(p); // 2**p
1613 // Calculate new base from m1
1614 BigInteger base2 = (this.signum < 0 || this.compareTo(m1) >= 0
1615 ? this.mod(m1) : this);
1617 // Caculate (base ** exponent) mod m1.
1618 BigInteger a1 = (m1.equals(ONE) ? ZERO :
1619 base2.oddModPow(exponent, m1));
1621 // Calculate (this ** exponent) mod m2
1622 BigInteger a2 = base.modPow2(exponent, p);
1624 // Combine results using Chinese Remainder Theorem
1625 BigInteger y1 = m2.modInverse(m1);
1626 BigInteger y2 = m1.modInverse(m2);
1628 result = a1.multiply(m2).multiply(y1).add
1629 (a2.multiply(m1).multiply(y2)).mod(m);
1632 return (invertResult ? result.modInverse(m) : result);
1635 static int[] bnExpModThreshTable = {7, 25, 81, 241, 673, 1793,
1636 Integer.MAX_VALUE}; // Sentinel
1639 * Returns a BigInteger whose value is x to the power of y mod z.
1640 * Assumes: z is odd && x < z.
1642 private BigInteger oddModPow(BigInteger y, BigInteger z) {
1644 * The algorithm is adapted from Colin Plumb's C library.
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
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.
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.
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.
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.)
1700 // Special case for exponent of one
1704 // Special case for base of zero
1708 int[] base = mag.clone();
1711 int modLen = mod.length;
1713 // Select an appropriate window size
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]) {
1723 // Calculate appropriate table size
1724 int tblmask = 1 << wbits;
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];
1731 // Compute the modular inverse
1732 int inv = -MutableBigInteger.inverseMod32(mod[modLen-1]);
1734 // Convert base to Montgomery form
1735 int[] a = leftShift(base, base.length, modLen << 5);
1737 MutableBigInteger q = new MutableBigInteger(),
1738 a2 = new MutableBigInteger(a),
1739 b2 = new MutableBigInteger(mod);
1741 MutableBigInteger r= a2.divide(b2, q);
1742 table[0] = r.toIntArray();
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];
1753 // Set b to the square of the base
1754 int[] b = squareToLen(table[0], modLen, null);
1755 b = montReduce(b, mod, modLen, inv);
1757 // Set t to high half of b
1758 int[] t = new int[modLen];
1759 for(int i=0; i<modLen; i++)
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);
1768 // Pre load the window that slides over the exponent
1769 int bitpos = 1 << ((ebits-1) & (32-1));
1772 int elen = exp.length;
1774 for (int i = 0; i <= wbits; i++) {
1775 buf = (buf << 1) | (((exp[eIndex] & bitpos) != 0)?1:0);
1779 bitpos = 1 << (32-1);
1784 int multpos = ebits;
1786 // The first iteration, which is hoisted out of the main loop
1788 boolean isone = true;
1790 multpos = ebits - wbits;
1791 while ((buf & 1) == 0) {
1796 int[] mult = table[buf >>> 1];
1799 if (multpos == ebits)
1805 // Advance the window
1809 buf |= ((exp[eIndex] & bitpos) != 0) ? 1 : 0;
1813 bitpos = 1 << (32-1);
1818 // Examine the window for pending multiplies
1819 if ((buf & tblmask) != 0) {
1820 multpos = ebits - wbits;
1821 while ((buf & 1) == 0) {
1825 mult = table[buf >>> 1];
1830 if (ebits == multpos) {
1836 a = multiplyToLen(t, modLen, mult, modLen, a);
1837 a = montReduce(a, mod, modLen, inv);
1838 t = a; a = b; b = t;
1849 a = squareToLen(t, modLen, a);
1850 a = montReduce(a, mod, modLen, inv);
1851 t = a; a = b; b = t;
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];
1860 b = montReduce(t2, mod, modLen, inv);
1862 t2 = new int[modLen];
1863 for(int i=0; i<modLen; i++)
1866 return new BigInteger(1, t2);
1870 * Montgomery reduce n, modulo mod. This reduces modulo mod and divides
1871 * by 2^(32*mlen). Adapted from Colin Plumb's C library.
1873 private static int[] montReduce(int[] n, int[] mod, int mlen, int inv) {
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);
1886 c += subN(n, mod, mlen);
1888 while (intArrayCmpToLen(n, mod, mlen) >= 0)
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.
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;
1912 * Subtracts two numbers of same length, returning borrow.
1914 private static int subN(int[] a, int[] b, int len) {
1918 sum = (a[len] & LONG_MASK) -
1919 (b[len] & LONG_MASK) + (sum >> 32);
1923 return (int)(sum >> 32);
1927 * Multiply an array by one word k and add to result, return the carry
1929 static int mulAdd(int[] out, int[] in, int offset, int len, int k) {
1930 long kLong = k & LONG_MASK;
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;
1944 * Add one word to the number a mlen words into a. Return the resulting
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);
1952 if ((t >>> 32) == 0)
1954 while (--mlen >= 0) {
1955 if (--offset < 0) { // Carry out of number
1967 * Returns a BigInteger whose value is (this ** exponent) mod (2**p)
1969 private BigInteger modPow2(BigInteger exponent, int p) {
1971 * Perform exponentiation using repeated squaring trick, chopping off
1972 * high order bits as indicated by modulus.
1974 BigInteger result = valueOf(1);
1975 BigInteger baseToPow2 = this.mod2(p);
1978 int limit = exponent.bitLength();
1980 if (this.testBit(0))
1981 limit = (p-1) < limit ? (p-1) : limit;
1983 while (expOffset < limit) {
1984 if (exponent.testBit(expOffset))
1985 result = result.multiply(baseToPow2).mod2(p);
1987 if (expOffset < limit)
1988 baseToPow2 = baseToPow2.square().mod2(p);
1995 * Returns a BigInteger whose value is this mod(2**p).
1996 * Assumes that this {@code BigInteger >= 0} and {@code p > 0}.
1998 private BigInteger mod2(int p) {
1999 if (bitLength() <= p)
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)];
2008 // Mask out any excess bits
2009 int excessBits = (numInts << 5) - p;
2010 mag[0] &= (1L << (32-excessBits)) - 1;
2012 return (mag[0]==0 ? new BigInteger(1, mag) : new BigInteger(mag, 1));
2016 * Returns a BigInteger whose value is {@code (this}<sup>-1</sup> {@code mod m)}.
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).
2024 public BigInteger modInverse(BigInteger m) {
2026 throw new ArithmeticException("BigInteger: modulus not positive");
2031 // Calculate (this mod m)
2032 BigInteger modVal = this;
2033 if (signum < 0 || (this.compareMagnitude(m) >= 0))
2034 modVal = this.mod(m);
2036 if (modVal.equals(ONE))
2039 MutableBigInteger a = new MutableBigInteger(modVal);
2040 MutableBigInteger b = new MutableBigInteger(m);
2042 MutableBigInteger result = a.mutableModInverse(b);
2043 return result.toBigInteger(1);
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>.)
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}.
2060 public BigInteger shiftLeft(int n) {
2066 if (n == Integer.MIN_VALUE) {
2067 throw new ArithmeticException("Shift distance of Integer.MIN_VALUE not supported.");
2069 return shiftRight(-n);
2073 int nInts = n >>> 5;
2074 int nBits = n & 0x1f;
2075 int magLen = mag.length;
2076 int newMag[] = null;
2079 newMag = new int[magLen + nInts];
2080 for (int i=0; i<magLen; i++)
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;
2090 newMag = new int[magLen + nInts];
2093 while (j < magLen-1)
2094 newMag[i++] = mag[j++] << nBits | mag[j] >>> nBits2;
2095 newMag[i] = mag[j] << nBits;
2098 return new BigInteger(newMag, signum);
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>.)
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}.
2113 public BigInteger shiftRight(int n) {
2117 if (n == Integer.MIN_VALUE) {
2118 throw new ArithmeticException("Shift distance of Integer.MIN_VALUE not supported.");
2120 return shiftLeft(-n);
2124 int nInts = n >>> 5;
2125 int nBits = n & 0x1f;
2126 int magLen = mag.length;
2127 int newMag[] = null;
2129 // Special case: entire contents shifted off the end
2130 if (nInts >= magLen)
2131 return (signum >= 0 ? ZERO : negConst[1]);
2134 int newMagLen = magLen - nInts;
2135 newMag = new int[newMagLen];
2136 for (int i=0; i<newMagLen; i++)
2140 int highBits = mag[0] >>> nBits;
2141 if (highBits != 0) {
2142 newMag = new int[magLen - nInts];
2143 newMag[i++] = highBits;
2145 newMag = new int[magLen - nInts -1];
2148 int nBits2 = 32 - nBits;
2150 while (j < magLen - nInts - 1)
2151 newMag[i++] = (mag[j++] << nBits2) | (mag[j] >>> nBits);
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);
2163 newMag = javaIncrement(newMag);
2166 return new BigInteger(newMag, signum);
2169 int[] javaIncrement(int[] val) {
2171 for (int i=val.length-1; i >= 0 && lastSum == 0; i--)
2172 lastSum = (val[i] += 1);
2174 val = new int[val.length+1];
2180 // Bitwise Operations
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
2187 * @param val value to be AND'ed with this BigInteger.
2188 * @return {@code this & val}
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));
2196 return valueOf(result);
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
2204 * @param val value to be OR'ed with this BigInteger.
2205 * @return {@code this | val}
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));
2213 return valueOf(result);
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.)
2221 * @param val value to be XOR'ed with this BigInteger.
2222 * @return {@code this ^ val}
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));
2230 return valueOf(result);
2234 * Returns a BigInteger whose value is {@code (~this)}. (This method
2235 * returns a negative value if and only if this BigInteger is
2238 * @return {@code ~this}
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);
2245 return valueOf(result);
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
2255 * @param val value to be complemented and AND'ed with this BigInteger.
2256 * @return {@code this & ~val}
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));
2264 return valueOf(result);
2268 // Single Bit Operations
2271 * Returns {@code true} if and only if the designated bit is set.
2272 * (Computes {@code ((this & (1<<n)) != 0)}.)
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.
2278 public boolean testBit(int n) {
2280 throw new ArithmeticException("Negative bit address");
2282 return (getInt(n >>> 5) & (1 << (n & 31))) != 0;
2286 * Returns a BigInteger whose value is equivalent to this BigInteger
2287 * with the designated bit set. (Computes {@code (this | (1<<n))}.)
2289 * @param n index of bit to set.
2290 * @return {@code this | (1<<n)}
2291 * @throws ArithmeticException {@code n} is negative.
2293 public BigInteger setBit(int n) {
2295 throw new ArithmeticException("Negative bit address");
2297 int intNum = n >>> 5;
2298 int[] result = new int[Math.max(intLength(), intNum+2)];
2300 for (int i=0; i<result.length; i++)
2301 result[result.length-i-1] = getInt(i);
2303 result[result.length-intNum-1] |= (1 << (n & 31));
2305 return valueOf(result);
2309 * Returns a BigInteger whose value is equivalent to this BigInteger
2310 * with the designated bit cleared.
2311 * (Computes {@code (this & ~(1<<n))}.)
2313 * @param n index of bit to clear.
2314 * @return {@code this & ~(1<<n)}
2315 * @throws ArithmeticException {@code n} is negative.
2317 public BigInteger clearBit(int n) {
2319 throw new ArithmeticException("Negative bit address");
2321 int intNum = n >>> 5;
2322 int[] result = new int[Math.max(intLength(), ((n + 1) >>> 5) + 1)];
2324 for (int i=0; i<result.length; i++)
2325 result[result.length-i-1] = getInt(i);
2327 result[result.length-intNum-1] &= ~(1 << (n & 31));
2329 return valueOf(result);
2333 * Returns a BigInteger whose value is equivalent to this BigInteger
2334 * with the designated bit flipped.
2335 * (Computes {@code (this ^ (1<<n))}.)
2337 * @param n index of bit to flip.
2338 * @return {@code this ^ (1<<n)}
2339 * @throws ArithmeticException {@code n} is negative.
2341 public BigInteger flipBit(int n) {
2343 throw new ArithmeticException("Negative bit address");
2345 int intNum = n >>> 5;
2346 int[] result = new int[Math.max(intLength(), intNum+2)];
2348 for (int i=0; i<result.length; i++)
2349 result[result.length-i-1] = getInt(i);
2351 result[result.length-intNum-1] ^= (1 << (n & 31));
2353 return valueOf(result);
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))}.)
2362 * @return index of the rightmost one bit in this BigInteger.
2364 public int getLowestSetBit() {
2365 @SuppressWarnings("deprecation") int lsb = lowestSetBit - 2;
2366 if (lsb == -2) { // lowestSetBit not initialized yet
2371 // Search for lowest order nonzero int
2373 for (i=0; (b = getInt(i))==0; i++)
2375 lsb += (i << 5) + Integer.numberOfTrailingZeros(b);
2377 lowestSetBit = lsb + 2;
2383 // Miscellaneous Bit Operations
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)))}.)
2392 * @return number of bits in the minimal two's-complement
2393 * representation of this BigInteger, <i>excluding</i> a sign bit.
2395 public int bitLength() {
2396 @SuppressWarnings("deprecation") int n = bitLength - 1;
2397 if (n == -1) { // bitLength not initialized yet
2401 n = 0; // offset by one to initialize
2403 // Calculate the bit length of the magnitude
2404 int magBitLength = ((len - 1) << 5) + bitLengthForInt(mag[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);
2411 n = (pow2 ? magBitLength -1 : magBitLength);
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.
2426 * @return number of bits in the two's complement representation
2427 * of this BigInteger that differ from its sign bit.
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]);
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;
2449 // Primality Testing
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
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.
2465 public boolean isProbablePrime(int certainty) {
2468 BigInteger w = this.abs();
2471 if (!w.testBit(0) || w.equals(ONE))
2474 return w.primeToCertainty(certainty, null);
2477 // Comparison Operations
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.
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}.
2492 public int compareTo(BigInteger val) {
2493 if (signum == val.signum) {
2496 return compareMagnitude(val);
2498 return val.compareMagnitude(this);
2503 return signum > val.signum ? 1 : -1;
2507 * Compares the magnitude array of this BigInteger with the specified
2508 * BigInteger's. This is the version of compareTo ignoring sign.
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.
2514 final int compareMagnitude(BigInteger val) {
2516 int len1 = m1.length;
2518 int len2 = m2.length;
2523 for (int i = 0; i < len1; i++) {
2527 return ((a & LONG_MASK) < (b & LONG_MASK)) ? -1 : 1;
2533 * Compares this BigInteger with the specified Object for equality.
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.
2539 public boolean equals(Object x) {
2540 // This test is just an optimization, which may or may not help
2544 if (!(x instanceof BigInteger))
2547 BigInteger xInt = (BigInteger) x;
2548 if (xInt.signum != signum)
2553 int[] xm = xInt.mag;
2554 if (len != xm.length)
2557 for (int i = 0; i < len; i++)
2565 * Returns the minimum of this BigInteger and {@code val}.
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.
2571 public BigInteger min(BigInteger val) {
2572 return (compareTo(val)<0 ? this : val);
2576 * Returns the maximum of this BigInteger and {@code val}.
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.
2582 public BigInteger max(BigInteger val) {
2583 return (compareTo(val)>0 ? this : val);
2590 * Returns the hash code for this BigInteger.
2592 * @return hash code for this BigInteger.
2594 public int hashCode() {
2597 for (int i=0; i<mag.length; i++)
2598 hashCode = (int)(31*hashCode + (mag[i] & LONG_MASK));
2600 return hashCode * signum;
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.)
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)
2620 public String toString(int radix) {
2623 if (radix < Character.MIN_RADIX || radix > Character.MAX_RADIX)
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];
2630 // Translate number to string, a digit group at a time
2631 BigInteger tmp = this.abs();
2633 while (tmp.signum != 0) {
2634 BigInteger d = longRadix[radix];
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);
2643 digitGroup[numGroups++] = Long.toString(r2.longValue(), radix);
2647 // Put sign (if any) and first digit group into result buffer
2648 StringBuilder buf = new StringBuilder(numGroups*digitsPerLong[radix]+1);
2651 buf.append(digitGroup[numGroups-1]);
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]);
2661 return buf.toString();
2664 /* zero[i] is a string of i consecutive zeros. */
2665 private static String zeros[] = new String[64];
2668 "000000000000000000000000000000000000000000000000000000000000000";
2669 for (int i=0; i<63; i++)
2670 zeros[i] = zeros[63].substring(0, i);
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.)
2681 * @return decimal String representation of this BigInteger.
2682 * @see Character#forDigit
2683 * @see #BigInteger(java.lang.String)
2685 public String toString() {
2686 return toString(10);
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.)
2699 * @return a byte array containing the two's-complement representation of
2701 * @see #BigInteger(byte[])
2703 public byte[] toByteArray() {
2704 int byteLen = bitLength()/8 + 1;
2705 byte[] byteArray = new byte[byteLen];
2707 for (int i=byteLen-1, bytesCopied=4, nextInt=0, intIndex=0; i>=0; i--) {
2708 if (bytesCopied == 4) {
2709 nextInt = getInt(intIndex++);
2715 byteArray[i] = (byte)nextInt;
2721 * Converts this BigInteger to an {@code int}. This
2722 * conversion is analogous to a
2723 * <i>narrowing primitive conversion</i> from {@code long} to
2724 * {@code int} as defined in section 5.1.3 of
2725 * <cite>The Java™ Language Specification</cite>:
2726 * if this BigInteger is too big to fit in an
2727 * {@code int}, only the low-order 32 bits are returned.
2728 * Note that this conversion can lose information about the
2729 * overall magnitude of the BigInteger value as well as return a
2730 * result with the opposite sign.
2732 * @return this BigInteger converted to an {@code int}.
2734 public int intValue() {
2741 * Converts this BigInteger to a {@code long}. This
2742 * conversion is analogous to a
2743 * <i>narrowing primitive conversion</i> from {@code long} to
2744 * {@code int} as defined in section 5.1.3 of
2745 * <cite>The Java™ Language Specification</cite>:
2746 * if this BigInteger is too big to fit in a
2747 * {@code long}, only the low-order 64 bits are returned.
2748 * Note that this conversion can lose information about the
2749 * overall magnitude of the BigInteger value as well as return a
2750 * result with the opposite sign.
2752 * @return this BigInteger converted to a {@code long}.
2754 public long longValue() {
2757 for (int i=1; i>=0; i--)
2758 result = (result << 32) + (getInt(i) & LONG_MASK);
2763 * Converts this BigInteger to a {@code float}. This
2764 * conversion is similar to the
2765 * <i>narrowing primitive conversion</i> from {@code double} to
2766 * {@code float} as defined in section 5.1.3 of
2767 * <cite>The Java™ Language Specification</cite>:
2768 * if this BigInteger has too great a magnitude
2769 * to represent as a {@code float}, it will be converted to
2770 * {@link Float#NEGATIVE_INFINITY} or {@link
2771 * Float#POSITIVE_INFINITY} as appropriate. Note that even when
2772 * the return value is finite, this conversion can lose
2773 * information about the precision of the BigInteger value.
2775 * @return this BigInteger converted to a {@code float}.
2777 public float floatValue() {
2778 // Somewhat inefficient, but guaranteed to work.
2779 return Float.parseFloat(this.toString());
2783 * Converts this BigInteger to a {@code double}. This
2784 * conversion is similar to the
2785 * <i>narrowing primitive conversion</i> from {@code double} to
2786 * {@code float} as defined in section 5.1.3 of
2787 * <cite>The Java™ Language Specification</cite>:
2788 * if this BigInteger has too great a magnitude
2789 * to represent as a {@code double}, it will be converted to
2790 * {@link Double#NEGATIVE_INFINITY} or {@link
2791 * Double#POSITIVE_INFINITY} as appropriate. Note that even when
2792 * the return value is finite, this conversion can lose
2793 * information about the precision of the BigInteger value.
2795 * @return this BigInteger converted to a {@code double}.
2797 public double doubleValue() {
2798 // Somewhat inefficient, but guaranteed to work.
2799 return Double.parseDouble(this.toString());
2803 * Returns a copy of the input array stripped of any leading zero bytes.
2805 private static int[] stripLeadingZeroInts(int val[]) {
2806 int vlen = val.length;
2809 // Find first nonzero byte
2810 for (keep = 0; keep < vlen && val[keep] == 0; keep++)
2812 return java.util.Arrays.copyOfRange(val, keep, vlen);
2816 * Returns the input array stripped of any leading zero bytes.
2817 * Since the source is trusted the copying may be skipped.
2819 private static int[] trustedStripLeadingZeroInts(int val[]) {
2820 int vlen = val.length;
2823 // Find first nonzero byte
2824 for (keep = 0; keep < vlen && val[keep] == 0; keep++)
2826 return keep == 0 ? val : java.util.Arrays.copyOfRange(val, keep, vlen);
2830 * Returns a copy of the input array stripped of any leading zero bytes.
2832 private static int[] stripLeadingZeroBytes(byte a[]) {
2833 int byteLength = a.length;
2836 // Find first nonzero byte
2837 for (keep = 0; keep < byteLength && a[keep]==0; keep++)
2840 // Allocate new array and copy relevant part of input array
2841 int intLength = ((byteLength - keep) + 3) >>> 2;
2842 int[] result = new int[intLength];
2843 int b = byteLength - 1;
2844 for (int i = intLength-1; i >= 0; i--) {
2845 result[i] = a[b--] & 0xff;
2846 int bytesRemaining = b - keep + 1;
2847 int bytesToTransfer = Math.min(3, bytesRemaining);
2848 for (int j=8; j <= (bytesToTransfer << 3); j += 8)
2849 result[i] |= ((a[b--] & 0xff) << j);
2855 * Takes an array a representing a negative 2's-complement number and
2856 * returns the minimal (no leading zero bytes) unsigned whose value is -a.
2858 private static int[] makePositive(byte a[]) {
2860 int byteLength = a.length;
2862 // Find first non-sign (0xff) byte of input
2863 for (keep=0; keep<byteLength && a[keep]==-1; keep++)
2867 /* Allocate output array. If all non-sign bytes are 0x00, we must
2868 * allocate space for one extra output byte. */
2869 for (k=keep; k<byteLength && a[k]==0; k++)
2872 int extraByte = (k==byteLength) ? 1 : 0;
2873 int intLength = ((byteLength - keep + extraByte) + 3)/4;
2874 int result[] = new int[intLength];
2876 /* Copy one's complement of input into output, leaving extra
2877 * byte (if it exists) == 0x00 */
2878 int b = byteLength - 1;
2879 for (int i = intLength-1; i >= 0; i--) {
2880 result[i] = a[b--] & 0xff;
2881 int numBytesToTransfer = Math.min(3, b-keep+1);
2882 if (numBytesToTransfer < 0)
2883 numBytesToTransfer = 0;
2884 for (int j=8; j <= 8*numBytesToTransfer; j += 8)
2885 result[i] |= ((a[b--] & 0xff) << j);
2887 // Mask indicates which bits must be complemented
2888 int mask = -1 >>> (8*(3-numBytesToTransfer));
2889 result[i] = ~result[i] & mask;
2892 // Add one to one's complement to generate two's complement
2893 for (int i=result.length-1; i>=0; i--) {
2894 result[i] = (int)((result[i] & LONG_MASK) + 1);
2903 * Takes an array a representing a negative 2's-complement number and
2904 * returns the minimal (no leading zero ints) unsigned whose value is -a.
2906 private static int[] makePositive(int a[]) {
2909 // Find first non-sign (0xffffffff) int of input
2910 for (keep=0; keep<a.length && a[keep]==-1; keep++)
2913 /* Allocate output array. If all non-sign ints are 0x00, we must
2914 * allocate space for one extra output int. */
2915 for (j=keep; j<a.length && a[j]==0; j++)
2917 int extraInt = (j==a.length ? 1 : 0);
2918 int result[] = new int[a.length - keep + extraInt];
2920 /* Copy one's complement of input into output, leaving extra
2921 * int (if it exists) == 0x00 */
2922 for (int i = keep; i<a.length; i++)
2923 result[i - keep + extraInt] = ~a[i];
2925 // Add one to one's complement to generate two's complement
2926 for (int i=result.length-1; ++result[i]==0; i--)
2933 * The following two arrays are used for fast String conversions. Both
2934 * are indexed by radix. The first is the number of digits of the given
2935 * radix that can fit in a Java long without "going negative", i.e., the
2936 * highest integer n such that radix**n < 2**63. The second is the
2937 * "long radix" that tears each number into "long digits", each of which
2938 * consists of the number of digits in the corresponding element in
2939 * digitsPerLong (longRadix[i] = i**digitPerLong[i]). Both arrays have
2940 * nonsense values in their 0 and 1 elements, as radixes 0 and 1 are not
2943 private static int digitsPerLong[] = {0, 0,
2944 62, 39, 31, 27, 24, 22, 20, 19, 18, 18, 17, 17, 16, 16, 15, 15, 15, 14,
2945 14, 14, 14, 13, 13, 13, 13, 13, 13, 12, 12, 12, 12, 12, 12, 12, 12};
2947 private static BigInteger longRadix[] = {null, null,
2948 valueOf(0x4000000000000000L), valueOf(0x383d9170b85ff80bL),
2949 valueOf(0x4000000000000000L), valueOf(0x6765c793fa10079dL),
2950 valueOf(0x41c21cb8e1000000L), valueOf(0x3642798750226111L),
2951 valueOf(0x1000000000000000L), valueOf(0x12bf307ae81ffd59L),
2952 valueOf( 0xde0b6b3a7640000L), valueOf(0x4d28cb56c33fa539L),
2953 valueOf(0x1eca170c00000000L), valueOf(0x780c7372621bd74dL),
2954 valueOf(0x1e39a5057d810000L), valueOf(0x5b27ac993df97701L),
2955 valueOf(0x1000000000000000L), valueOf(0x27b95e997e21d9f1L),
2956 valueOf(0x5da0e1e53c5c8000L), valueOf( 0xb16a458ef403f19L),
2957 valueOf(0x16bcc41e90000000L), valueOf(0x2d04b7fdd9c0ef49L),
2958 valueOf(0x5658597bcaa24000L), valueOf( 0x6feb266931a75b7L),
2959 valueOf( 0xc29e98000000000L), valueOf(0x14adf4b7320334b9L),
2960 valueOf(0x226ed36478bfa000L), valueOf(0x383d9170b85ff80bL),
2961 valueOf(0x5a3c23e39c000000L), valueOf( 0x4e900abb53e6b71L),
2962 valueOf( 0x7600ec618141000L), valueOf( 0xaee5720ee830681L),
2963 valueOf(0x1000000000000000L), valueOf(0x172588ad4f5f0981L),
2964 valueOf(0x211e44f7d02c1000L), valueOf(0x2ee56725f06e5c71L),
2965 valueOf(0x41c21cb8e1000000L)};
2968 * These two arrays are the integer analogue of above.
2970 private static int digitsPerInt[] = {0, 0, 30, 19, 15, 13, 11,
2971 11, 10, 9, 9, 8, 8, 8, 8, 7, 7, 7, 7, 7, 7, 7, 6, 6, 6, 6,
2972 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 5};
2974 private static int intRadix[] = {0, 0,
2975 0x40000000, 0x4546b3db, 0x40000000, 0x48c27395, 0x159fd800,
2976 0x75db9c97, 0x40000000, 0x17179149, 0x3b9aca00, 0xcc6db61,
2977 0x19a10000, 0x309f1021, 0x57f6c100, 0xa2f1b6f, 0x10000000,
2978 0x18754571, 0x247dbc80, 0x3547667b, 0x4c4b4000, 0x6b5a6e1d,
2979 0x6c20a40, 0x8d2d931, 0xb640000, 0xe8d4a51, 0x1269ae40,
2980 0x17179149, 0x1cb91000, 0x23744899, 0x2b73a840, 0x34e63b41,
2981 0x40000000, 0x4cfa3cc1, 0x5c13d840, 0x6d91b519, 0x39aa400
2985 * These routines provide access to the two's complement representation
2990 * Returns the length of the two's complement representation in ints,
2991 * including space for at least one sign bit.
2993 private int intLength() {
2994 return (bitLength() >>> 5) + 1;
2997 /* Returns sign bit */
2998 private int signBit() {
2999 return signum < 0 ? 1 : 0;
3002 /* Returns an int of sign bits */
3003 private int signInt() {
3004 return signum < 0 ? -1 : 0;
3008 * Returns the specified int of the little-endian two's complement
3009 * representation (int 0 is the least significant). The int number can
3010 * be arbitrarily high (values are logically preceded by infinitely many
3013 private int getInt(int n) {
3016 if (n >= mag.length)
3019 int magInt = mag[mag.length-n-1];
3021 return (signum >= 0 ? magInt :
3022 (n <= firstNonzeroIntNum() ? -magInt : ~magInt));
3026 * Returns the index of the int that contains the first nonzero int in the
3027 * little-endian binary representation of the magnitude (int 0 is the
3028 * least significant). If the magnitude is zero, return value is undefined.
3030 private int firstNonzeroIntNum() {
3031 int fn = firstNonzeroIntNum - 2;
3032 if (fn == -2) { // firstNonzeroIntNum not initialized yet
3035 // Search for the first nonzero int
3037 int mlen = mag.length;
3038 for (i = mlen - 1; i >= 0 && mag[i] == 0; i--)
3041 firstNonzeroIntNum = fn + 2; // offset by two to initialize
3046 /** use serialVersionUID from JDK 1.1. for interoperability */
3047 private static final long serialVersionUID = -8287574255936472291L;
3050 * Serializable fields for BigInteger.
3052 * @serialField signum int
3053 * signum of this BigInteger.
3054 * @serialField magnitude int[]
3055 * magnitude array of this BigInteger.
3056 * @serialField bitCount int
3057 * number of bits in this BigInteger
3058 * @serialField bitLength int
3059 * the number of bits in the minimal two's-complement
3060 * representation of this BigInteger
3061 * @serialField lowestSetBit int
3062 * lowest set bit in the twos complement representation
3064 private static final ObjectStreamField[] serialPersistentFields = {
3065 new ObjectStreamField("signum", Integer.TYPE),
3066 new ObjectStreamField("magnitude", byte[].class),
3067 new ObjectStreamField("bitCount", Integer.TYPE),
3068 new ObjectStreamField("bitLength", Integer.TYPE),
3069 new ObjectStreamField("firstNonzeroByteNum", Integer.TYPE),
3070 new ObjectStreamField("lowestSetBit", Integer.TYPE)
3074 * Reconstitute the {@code BigInteger} instance from a stream (that is,
3075 * deserialize it). The magnitude is read in as an array of bytes
3076 * for historical reasons, but it is converted to an array of ints
3077 * and the byte array is discarded.
3079 * The current convention is to initialize the cache fields, bitCount,
3080 * bitLength and lowestSetBit, to 0 rather than some other marker value.
3081 * Therefore, no explicit action to set these fields needs to be taken in
3082 * readObject because those fields already have a 0 value be default since
3083 * defaultReadObject is not being used.
3085 private void readObject(java.io.ObjectInputStream s)
3086 throws java.io.IOException, ClassNotFoundException {
3088 * In order to maintain compatibility with previous serialized forms,
3089 * the magnitude of a BigInteger is serialized as an array of bytes.
3090 * The magnitude field is used as a temporary store for the byte array
3091 * that is deserialized. The cached computation fields should be
3092 * transient but are serialized for compatibility reasons.
3095 // prepare to read the alternate persistent fields
3096 ObjectInputStream.GetField fields = s.readFields();
3098 // Read the alternate persistent fields that we care about
3099 int sign = fields.get("signum", -2);
3100 byte[] magnitude = (byte[])fields.get("magnitude", null);
3103 if (sign < -1 || sign > 1) {
3104 String message = "BigInteger: Invalid signum value";
3105 if (fields.defaulted("signum"))
3106 message = "BigInteger: Signum not present in stream";
3107 throw new java.io.StreamCorruptedException(message);
3109 if ((magnitude.length == 0) != (sign == 0)) {
3110 String message = "BigInteger: signum-magnitude mismatch";
3111 if (fields.defaulted("magnitude"))
3112 message = "BigInteger: Magnitude not present in stream";
3113 throw new java.io.StreamCorruptedException(message);
3116 // Commit final fields via Unsafe
3117 unsafe.putIntVolatile(this, signumOffset, sign);
3119 // Calculate mag field from magnitude and discard magnitude
3120 unsafe.putObjectVolatile(this, magOffset,
3121 stripLeadingZeroBytes(magnitude));
3124 // Support for resetting final fields while deserializing
3125 private static final sun.misc.Unsafe unsafe = sun.misc.Unsafe.getUnsafe();
3126 private static final long signumOffset;
3127 private static final long magOffset;
3130 signumOffset = unsafe.objectFieldOffset
3131 (BigInteger.class.getDeclaredField("signum"));
3132 magOffset = unsafe.objectFieldOffset
3133 (BigInteger.class.getDeclaredField("mag"));
3134 } catch (Exception ex) {
3135 throw new Error(ex);
3140 * Save the {@code BigInteger} instance to a stream.
3141 * The magnitude of a BigInteger is serialized as a byte array for
3142 * historical reasons.
3144 * @serialData two necessary fields are written as well as obsolete
3145 * fields for compatibility with older versions.
3147 private void writeObject(ObjectOutputStream s) throws IOException {
3148 // set the values of the Serializable fields
3149 ObjectOutputStream.PutField fields = s.putFields();
3150 fields.put("signum", signum);
3151 fields.put("magnitude", magSerializedForm());
3152 // The values written for cached fields are compatible with older
3153 // versions, but are ignored in readObject so don't otherwise matter.
3154 fields.put("bitCount", -1);
3155 fields.put("bitLength", -1);
3156 fields.put("lowestSetBit", -2);
3157 fields.put("firstNonzeroByteNum", -2);
3164 * Returns the mag array as an array of bytes.
3166 private byte[] magSerializedForm() {
3167 int len = mag.length;
3169 int bitLen = (len == 0 ? 0 : ((len - 1) << 5) + bitLengthForInt(mag[0]));
3170 int byteLen = (bitLen + 7) >>> 3;
3171 byte[] result = new byte[byteLen];
3173 for (int i = byteLen - 1, bytesCopied = 4, intIndex = len - 1, nextInt = 0;
3175 if (bytesCopied == 4) {
3176 nextInt = mag[intIndex--];
3182 result[i] = (byte)nextInt;