461
462 /**
463 * Translates the decimal String representation of a BigInteger into a
464 * BigInteger. The String representation consists of an optional minus
465 * sign followed by a sequence of one or more decimal digits. The
466 * character-to-digit mapping is provided by {@code Character.digit}.
467 * The String may not contain any extraneous characters (whitespace, for
468 * example).
469 *
470 * @param val decimal String representation of BigInteger.
471 * @throws NumberFormatException {@code val} is not a valid representation
472 * of a BigInteger.
473 * @see Character#digit
474 */
475 public BigInteger(String val) {
476 this(val, 10);
477 }
478
479 /**
480 * Constructs a randomly generated BigInteger, uniformly distributed over
481 * the range {@code 0} to (2<sup>{@code numBits}</sup> - 1), inclusive.
482 * The uniformity of the distribution assumes that a fair source of random
483 * bits is provided in {@code rnd}. Note that this constructor always
484 * constructs a non-negative BigInteger.
485 *
486 * @param numBits maximum bitLength of the new BigInteger.
487 * @param rnd source of randomness to be used in computing the new
488 * BigInteger.
489 * @throws IllegalArgumentException {@code numBits} is negative.
490 * @see #bitLength()
491 */
492 public BigInteger(int numBits, Random rnd) {
493 this(1, randomBits(numBits, rnd));
494 }
495
496 private static byte[] randomBits(int numBits, Random rnd) {
497 if (numBits < 0)
498 throw new IllegalArgumentException("numBits must be non-negative");
499 int numBytes = (int)(((long)numBits+7)/8); // avoid overflow
500 byte[] randomBits = new byte[numBytes];
501
1315
1316 // Add in off-diagonal sums
1317 for (int i=len, offset=1; i>0; i--, offset+=2) {
1318 int t = x[i-1];
1319 t = mulAdd(z, x, offset, i-1, t);
1320 addOne(z, offset-1, i, t);
1321 }
1322
1323 // Shift back up and set low bit
1324 primitiveLeftShift(z, zlen, 1);
1325 z[zlen-1] |= x[len-1] & 1;
1326
1327 return z;
1328 }
1329
1330 /**
1331 * Returns a BigInteger whose value is {@code (this / val)}.
1332 *
1333 * @param val value by which this BigInteger is to be divided.
1334 * @return {@code this / val}
1335 * @throws ArithmeticException {@code val==0}
1336 */
1337 public BigInteger divide(BigInteger val) {
1338 MutableBigInteger q = new MutableBigInteger(),
1339 a = new MutableBigInteger(this.mag),
1340 b = new MutableBigInteger(val.mag);
1341
1342 a.divide(b, q);
1343 return q.toBigInteger(this.signum == val.signum ? 1 : -1);
1344 }
1345
1346 /**
1347 * Returns an array of two BigIntegers containing {@code (this / val)}
1348 * followed by {@code (this % val)}.
1349 *
1350 * @param val value by which this BigInteger is to be divided, and the
1351 * remainder computed.
1352 * @return an array of two BigIntegers: the quotient {@code (this / val)}
1353 * is the initial element, and the remainder {@code (this % val)}
1354 * is the final element.
1355 * @throws ArithmeticException {@code val==0}
1356 */
1357 public BigInteger[] divideAndRemainder(BigInteger val) {
1358 BigInteger[] result = new BigInteger[2];
1359 MutableBigInteger q = new MutableBigInteger(),
1360 a = new MutableBigInteger(this.mag),
1361 b = new MutableBigInteger(val.mag);
1362 MutableBigInteger r = a.divide(b, q);
1363 result[0] = q.toBigInteger(this.signum == val.signum ? 1 : -1);
1364 result[1] = r.toBigInteger(this.signum);
1365 return result;
1366 }
1367
1368 /**
1369 * Returns a BigInteger whose value is {@code (this % val)}.
1370 *
1371 * @param val value by which this BigInteger is to be divided, and the
1372 * remainder computed.
1373 * @return {@code this % val}
1374 * @throws ArithmeticException {@code val==0}
1375 */
1376 public BigInteger remainder(BigInteger val) {
1377 MutableBigInteger q = new MutableBigInteger(),
1378 a = new MutableBigInteger(this.mag),
1379 b = new MutableBigInteger(val.mag);
1380
1381 return a.divide(b, q).toBigInteger(this.signum);
1382 }
1383
1384 /**
1385 * Returns a BigInteger whose value is <tt>(this<sup>exponent</sup>)</tt>.
1386 * Note that {@code exponent} is an integer rather than a BigInteger.
1387 *
1388 * @param exponent exponent to which this BigInteger is to be raised.
1389 * @return <tt>this<sup>exponent</sup></tt>
1390 * @throws ArithmeticException {@code exponent} is negative. (This would
1391 * cause the operation to yield a non-integer value.)
1392 */
1393 public BigInteger pow(int exponent) {
1394 if (exponent < 0)
1530
1531 /**
1532 * Returns the signum function of this BigInteger.
1533 *
1534 * @return -1, 0 or 1 as the value of this BigInteger is negative, zero or
1535 * positive.
1536 */
1537 public int signum() {
1538 return this.signum;
1539 }
1540
1541 // Modular Arithmetic Operations
1542
1543 /**
1544 * Returns a BigInteger whose value is {@code (this mod m}). This method
1545 * differs from {@code remainder} in that it always returns a
1546 * <i>non-negative</i> BigInteger.
1547 *
1548 * @param m the modulus.
1549 * @return {@code this mod m}
1550 * @throws ArithmeticException {@code m <= 0}
1551 * @see #remainder
1552 */
1553 public BigInteger mod(BigInteger m) {
1554 if (m.signum <= 0)
1555 throw new ArithmeticException("BigInteger: modulus not positive");
1556
1557 BigInteger result = this.remainder(m);
1558 return (result.signum >= 0 ? result : result.add(m));
1559 }
1560
1561 /**
1562 * Returns a BigInteger whose value is
1563 * <tt>(this<sup>exponent</sup> mod m)</tt>. (Unlike {@code pow}, this
1564 * method permits negative exponents.)
1565 *
1566 * @param exponent the exponent.
1567 * @param m the modulus.
1568 * @return <tt>this<sup>exponent</sup> mod m</tt>
1569 * @throws ArithmeticException {@code m <= 0}
1570 * @see #modInverse
1571 */
1572 public BigInteger modPow(BigInteger exponent, BigInteger m) {
1573 if (m.signum <= 0)
1574 throw new ArithmeticException("BigInteger: modulus not positive");
1575
1576 // Trivial cases
1577 if (exponent.signum == 0)
1578 return (m.equals(ONE) ? ZERO : ONE);
1579
1580 if (this.equals(ONE))
1581 return (m.equals(ONE) ? ZERO : ONE);
1582
1583 if (this.equals(ZERO) && exponent.signum >= 0)
1584 return ZERO;
1585
1586 if (this.equals(negConst[1]) && (!exponent.testBit(0)))
1587 return (m.equals(ONE) ? ZERO : ONE);
1588
1589 boolean invertResult;
1998 return this;
1999
2000 // Copy remaining ints of mag
2001 int numInts = (p + 31) >>> 5;
2002 int[] mag = new int[numInts];
2003 for (int i=0; i<numInts; i++)
2004 mag[i] = this.mag[i + (this.mag.length - numInts)];
2005
2006 // Mask out any excess bits
2007 int excessBits = (numInts << 5) - p;
2008 mag[0] &= (1L << (32-excessBits)) - 1;
2009
2010 return (mag[0]==0 ? new BigInteger(1, mag) : new BigInteger(mag, 1));
2011 }
2012
2013 /**
2014 * Returns a BigInteger whose value is {@code (this}<sup>-1</sup> {@code mod m)}.
2015 *
2016 * @param m the modulus.
2017 * @return {@code this}<sup>-1</sup> {@code mod m}.
2018 * @throws ArithmeticException {@code m <= 0}, or this BigInteger
2019 * has no multiplicative inverse mod m (that is, this BigInteger
2020 * is not <i>relatively prime</i> to m).
2021 */
2022 public BigInteger modInverse(BigInteger m) {
2023 if (m.signum != 1)
2024 throw new ArithmeticException("BigInteger: modulus not positive");
2025
2026 if (m.equals(ONE))
2027 return ZERO;
2028
2029 // Calculate (this mod m)
2030 BigInteger modVal = this;
2031 if (signum < 0 || (this.compareMagnitude(m) >= 0))
2032 modVal = this.mod(m);
2033
2034 if (modVal.equals(ONE))
2035 return ONE;
2036
2037 MutableBigInteger a = new MutableBigInteger(modVal);
2038 MutableBigInteger b = new MutableBigInteger(m);
2432 for (int i=0; i<mag.length; i++)
2433 bc += Integer.bitCount(mag[i]);
2434 if (signum < 0) {
2435 // Count the trailing zeros in the magnitude
2436 int magTrailingZeroCount = 0, j;
2437 for (j=mag.length-1; mag[j]==0; j--)
2438 magTrailingZeroCount += 32;
2439 magTrailingZeroCount += Integer.numberOfTrailingZeros(mag[j]);
2440 bc += magTrailingZeroCount - 1;
2441 }
2442 bitCount = bc + 1;
2443 }
2444 return bc;
2445 }
2446
2447 // Primality Testing
2448
2449 /**
2450 * Returns {@code true} if this BigInteger is probably prime,
2451 * {@code false} if it's definitely composite. If
2452 * {@code certainty} is {@code <= 0}, {@code true} is
2453 * returned.
2454 *
2455 * @param certainty a measure of the uncertainty that the caller is
2456 * willing to tolerate: if the call returns {@code true}
2457 * the probability that this BigInteger is prime exceeds
2458 * (1 - 1/2<sup>{@code certainty}</sup>). The execution time of
2459 * this method is proportional to the value of this parameter.
2460 * @return {@code true} if this BigInteger is probably prime,
2461 * {@code false} if it's definitely composite.
2462 */
2463 public boolean isProbablePrime(int certainty) {
2464 if (certainty <= 0)
2465 return true;
2466 BigInteger w = this.abs();
2467 if (w.equals(TWO))
2468 return true;
2469 if (!w.testBit(0) || w.equals(ONE))
2470 return false;
2471
2472 return w.primeToCertainty(certainty, null);
|
461
462 /**
463 * Translates the decimal String representation of a BigInteger into a
464 * BigInteger. The String representation consists of an optional minus
465 * sign followed by a sequence of one or more decimal digits. The
466 * character-to-digit mapping is provided by {@code Character.digit}.
467 * The String may not contain any extraneous characters (whitespace, for
468 * example).
469 *
470 * @param val decimal String representation of BigInteger.
471 * @throws NumberFormatException {@code val} is not a valid representation
472 * of a BigInteger.
473 * @see Character#digit
474 */
475 public BigInteger(String val) {
476 this(val, 10);
477 }
478
479 /**
480 * Constructs a randomly generated BigInteger, uniformly distributed over
481 * the range 0 to (2<sup>{@code numBits}</sup> - 1), inclusive.
482 * The uniformity of the distribution assumes that a fair source of random
483 * bits is provided in {@code rnd}. Note that this constructor always
484 * constructs a non-negative BigInteger.
485 *
486 * @param numBits maximum bitLength of the new BigInteger.
487 * @param rnd source of randomness to be used in computing the new
488 * BigInteger.
489 * @throws IllegalArgumentException {@code numBits} is negative.
490 * @see #bitLength()
491 */
492 public BigInteger(int numBits, Random rnd) {
493 this(1, randomBits(numBits, rnd));
494 }
495
496 private static byte[] randomBits(int numBits, Random rnd) {
497 if (numBits < 0)
498 throw new IllegalArgumentException("numBits must be non-negative");
499 int numBytes = (int)(((long)numBits+7)/8); // avoid overflow
500 byte[] randomBits = new byte[numBytes];
501
1315
1316 // Add in off-diagonal sums
1317 for (int i=len, offset=1; i>0; i--, offset+=2) {
1318 int t = x[i-1];
1319 t = mulAdd(z, x, offset, i-1, t);
1320 addOne(z, offset-1, i, t);
1321 }
1322
1323 // Shift back up and set low bit
1324 primitiveLeftShift(z, zlen, 1);
1325 z[zlen-1] |= x[len-1] & 1;
1326
1327 return z;
1328 }
1329
1330 /**
1331 * Returns a BigInteger whose value is {@code (this / val)}.
1332 *
1333 * @param val value by which this BigInteger is to be divided.
1334 * @return {@code this / val}
1335 * @throws ArithmeticException if {@code val} is zero.
1336 */
1337 public BigInteger divide(BigInteger val) {
1338 MutableBigInteger q = new MutableBigInteger(),
1339 a = new MutableBigInteger(this.mag),
1340 b = new MutableBigInteger(val.mag);
1341
1342 a.divide(b, q);
1343 return q.toBigInteger(this.signum == val.signum ? 1 : -1);
1344 }
1345
1346 /**
1347 * Returns an array of two BigIntegers containing {@code (this / val)}
1348 * followed by {@code (this % val)}.
1349 *
1350 * @param val value by which this BigInteger is to be divided, and the
1351 * remainder computed.
1352 * @return an array of two BigIntegers: the quotient {@code (this / val)}
1353 * is the initial element, and the remainder {@code (this % val)}
1354 * is the final element.
1355 * @throws ArithmeticException if {@code val} is zero.
1356 */
1357 public BigInteger[] divideAndRemainder(BigInteger val) {
1358 BigInteger[] result = new BigInteger[2];
1359 MutableBigInteger q = new MutableBigInteger(),
1360 a = new MutableBigInteger(this.mag),
1361 b = new MutableBigInteger(val.mag);
1362 MutableBigInteger r = a.divide(b, q);
1363 result[0] = q.toBigInteger(this.signum == val.signum ? 1 : -1);
1364 result[1] = r.toBigInteger(this.signum);
1365 return result;
1366 }
1367
1368 /**
1369 * Returns a BigInteger whose value is {@code (this % val)}.
1370 *
1371 * @param val value by which this BigInteger is to be divided, and the
1372 * remainder computed.
1373 * @return {@code this % val}
1374 * @throws ArithmeticException if {@code val} is zero.
1375 */
1376 public BigInteger remainder(BigInteger val) {
1377 MutableBigInteger q = new MutableBigInteger(),
1378 a = new MutableBigInteger(this.mag),
1379 b = new MutableBigInteger(val.mag);
1380
1381 return a.divide(b, q).toBigInteger(this.signum);
1382 }
1383
1384 /**
1385 * Returns a BigInteger whose value is <tt>(this<sup>exponent</sup>)</tt>.
1386 * Note that {@code exponent} is an integer rather than a BigInteger.
1387 *
1388 * @param exponent exponent to which this BigInteger is to be raised.
1389 * @return <tt>this<sup>exponent</sup></tt>
1390 * @throws ArithmeticException {@code exponent} is negative. (This would
1391 * cause the operation to yield a non-integer value.)
1392 */
1393 public BigInteger pow(int exponent) {
1394 if (exponent < 0)
1530
1531 /**
1532 * Returns the signum function of this BigInteger.
1533 *
1534 * @return -1, 0 or 1 as the value of this BigInteger is negative, zero or
1535 * positive.
1536 */
1537 public int signum() {
1538 return this.signum;
1539 }
1540
1541 // Modular Arithmetic Operations
1542
1543 /**
1544 * Returns a BigInteger whose value is {@code (this mod m}). This method
1545 * differs from {@code remainder} in that it always returns a
1546 * <i>non-negative</i> BigInteger.
1547 *
1548 * @param m the modulus.
1549 * @return {@code this mod m}
1550 * @throws ArithmeticException {@code m} ≤ 0
1551 * @see #remainder
1552 */
1553 public BigInteger mod(BigInteger m) {
1554 if (m.signum <= 0)
1555 throw new ArithmeticException("BigInteger: modulus not positive");
1556
1557 BigInteger result = this.remainder(m);
1558 return (result.signum >= 0 ? result : result.add(m));
1559 }
1560
1561 /**
1562 * Returns a BigInteger whose value is
1563 * <tt>(this<sup>exponent</sup> mod m)</tt>. (Unlike {@code pow}, this
1564 * method permits negative exponents.)
1565 *
1566 * @param exponent the exponent.
1567 * @param m the modulus.
1568 * @return <tt>this<sup>exponent</sup> mod m</tt>
1569 * @throws ArithmeticException {@code m} ≤ 0 or the exponent is
1570 * negative and this BigInteger is not <i>relatively
1571 * prime</i> to {@code m}.
1572 * @see #modInverse
1573 */
1574 public BigInteger modPow(BigInteger exponent, BigInteger m) {
1575 if (m.signum <= 0)
1576 throw new ArithmeticException("BigInteger: modulus not positive");
1577
1578 // Trivial cases
1579 if (exponent.signum == 0)
1580 return (m.equals(ONE) ? ZERO : ONE);
1581
1582 if (this.equals(ONE))
1583 return (m.equals(ONE) ? ZERO : ONE);
1584
1585 if (this.equals(ZERO) && exponent.signum >= 0)
1586 return ZERO;
1587
1588 if (this.equals(negConst[1]) && (!exponent.testBit(0)))
1589 return (m.equals(ONE) ? ZERO : ONE);
1590
1591 boolean invertResult;
2000 return this;
2001
2002 // Copy remaining ints of mag
2003 int numInts = (p + 31) >>> 5;
2004 int[] mag = new int[numInts];
2005 for (int i=0; i<numInts; i++)
2006 mag[i] = this.mag[i + (this.mag.length - numInts)];
2007
2008 // Mask out any excess bits
2009 int excessBits = (numInts << 5) - p;
2010 mag[0] &= (1L << (32-excessBits)) - 1;
2011
2012 return (mag[0]==0 ? new BigInteger(1, mag) : new BigInteger(mag, 1));
2013 }
2014
2015 /**
2016 * Returns a BigInteger whose value is {@code (this}<sup>-1</sup> {@code mod m)}.
2017 *
2018 * @param m the modulus.
2019 * @return {@code this}<sup>-1</sup> {@code mod m}.
2020 * @throws ArithmeticException {@code m} ≤ 0, or this BigInteger
2021 * has no multiplicative inverse mod m (that is, this BigInteger
2022 * is not <i>relatively prime</i> to m).
2023 */
2024 public BigInteger modInverse(BigInteger m) {
2025 if (m.signum != 1)
2026 throw new ArithmeticException("BigInteger: modulus not positive");
2027
2028 if (m.equals(ONE))
2029 return ZERO;
2030
2031 // Calculate (this mod m)
2032 BigInteger modVal = this;
2033 if (signum < 0 || (this.compareMagnitude(m) >= 0))
2034 modVal = this.mod(m);
2035
2036 if (modVal.equals(ONE))
2037 return ONE;
2038
2039 MutableBigInteger a = new MutableBigInteger(modVal);
2040 MutableBigInteger b = new MutableBigInteger(m);
2434 for (int i=0; i<mag.length; i++)
2435 bc += Integer.bitCount(mag[i]);
2436 if (signum < 0) {
2437 // Count the trailing zeros in the magnitude
2438 int magTrailingZeroCount = 0, j;
2439 for (j=mag.length-1; mag[j]==0; j--)
2440 magTrailingZeroCount += 32;
2441 magTrailingZeroCount += Integer.numberOfTrailingZeros(mag[j]);
2442 bc += magTrailingZeroCount - 1;
2443 }
2444 bitCount = bc + 1;
2445 }
2446 return bc;
2447 }
2448
2449 // Primality Testing
2450
2451 /**
2452 * Returns {@code true} if this BigInteger is probably prime,
2453 * {@code false} if it's definitely composite. If
2454 * {@code certainty} is ≤ 0, {@code true} is
2455 * returned.
2456 *
2457 * @param certainty a measure of the uncertainty that the caller is
2458 * willing to tolerate: if the call returns {@code true}
2459 * the probability that this BigInteger is prime exceeds
2460 * (1 - 1/2<sup>{@code certainty}</sup>). The execution time of
2461 * this method is proportional to the value of this parameter.
2462 * @return {@code true} if this BigInteger is probably prime,
2463 * {@code false} if it's definitely composite.
2464 */
2465 public boolean isProbablePrime(int certainty) {
2466 if (certainty <= 0)
2467 return true;
2468 BigInteger w = this.abs();
2469 if (w.equals(TWO))
2470 return true;
2471 if (!w.testBit(0) || w.equals(ONE))
2472 return false;
2473
2474 return w.primeToCertainty(certainty, null);
|