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