## src/share/classes/java/math/BigInteger.java

 ``` `````` 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{@code numBits} - 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 (thisexponent). 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 thisexponent 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 * non-negative 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 * (thisexponent mod m). (Unlike {@code pow}, this 1564 * method permits negative exponents.) 1565 * 1566 * @param exponent the exponent. 1567 * @param m the modulus. 1568 * @return thisexponent mod m 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-1 {@code mod m)}. 2015 * 2016 * @param m the modulus. 2017 * @return {@code this}-1 {@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 relatively prime 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{@code certainty}). 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{@code numBits} - 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 (thisexponent). 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 thisexponent 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 * non-negative 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 * (thisexponent mod m). (Unlike {@code pow}, this 1564 * method permits negative exponents.) 1565 * 1566 * @param exponent the exponent. 1567 * @param m the modulus. 1568 * @return thisexponent mod m 1569 * @throws ArithmeticException {@code m} ≤ 0 or the exponent is 1570 * negative and this BigInteger is not relatively 1571 * prime 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-1 {@code mod m)}. 2017 * 2018 * @param m the modulus. 2019 * @return {@code this}-1 {@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 relatively prime 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{@code certainty}). 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); ```