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 for (int i=0; i<len; i++)
1616 result[i] = a[i];
1617 primitiveLeftShift(result, result.length, nBits);
1618 return result;
1619 } else {
1620 int result[] = new int[nInts+len+1];
1621 for (int i=0; i<len; i++)
1622 result[i] = a[i];
1623 primitiveRightShift(result, result.length, 32 - nBits);
1624 return result;
1625 }
1626 }
1627 }
1628
1629 // shifts a up to len right n bits assumes no leading zeros, 0<n<32
1630 static void primitiveRightShift(int[] a, int len, int n) {
1631 int n2 = 32 - n;
1632 for (int i=len-1, c=a[i]; i>0; i--) {
1633 int b = c;
1634 c = a[i-1];
1635 a[i] = (c << n2) | (b >>> n);
1636 }
1637 a[0] >>>= n;
1638 }
1639
1640 // shifts a up to len left n bits assumes no leading zeros, 0<=n<32
1641 static void primitiveLeftShift(int[] a, int len, int n) {
1642 if (len == 0 || n == 0)
1891 b2 = new MutableBigInteger(mod);
1892
1893 MutableBigInteger r= a2.divide(b2, q);
1894 table[0] = r.toIntArray();
1895
1896 // Pad table[0] with leading zeros so its length is at least modLen
1897 if (table[0].length < modLen) {
1898 int offset = modLen - table[0].length;
1899 int[] t2 = new int[modLen];
1900 for (int i=0; i<table[0].length; i++)
1901 t2[i+offset] = table[0][i];
1902 table[0] = t2;
1903 }
1904
1905 // Set b to the square of the base
1906 int[] b = squareToLen(table[0], modLen, null);
1907 b = montReduce(b, mod, modLen, inv);
1908
1909 // Set t to high half of b
1910 int[] t = new int[modLen];
1911 for(int i=0; i<modLen; i++)
1912 t[i] = b[i];
1913
1914 // Fill in the table with odd powers of the base
1915 for (int i=1; i<tblmask; i++) {
1916 int[] prod = multiplyToLen(t, modLen, table[i-1], modLen, null);
1917 table[i] = montReduce(prod, mod, modLen, inv);
1918 }
1919
1920 // Pre load the window that slides over the exponent
1921 int bitpos = 1 << ((ebits-1) & (32-1));
1922
1923 int buf = 0;
1924 int elen = exp.length;
1925 int eIndex = 0;
1926 for (int i = 0; i <= wbits; i++) {
1927 buf = (buf << 1) | (((exp[eIndex] & bitpos) != 0)?1:0);
1928 bitpos >>>= 1;
1929 if (bitpos == 0) {
1930 eIndex++;
1931 bitpos = 1 << (32-1);
1932 elen--;
1989 a = montReduce(a, mod, modLen, inv);
1990 t = a; a = b; b = t;
1991 }
1992 }
1993
1994 // Check if done
1995 if (ebits == 0)
1996 break;
1997
1998 // Square the input
1999 if (!isone) {
2000 t = b;
2001 a = squareToLen(t, modLen, a);
2002 a = montReduce(a, mod, modLen, inv);
2003 t = a; a = b; b = t;
2004 }
2005 }
2006
2007 // Convert result out of Montgomery form and return
2008 int[] t2 = new int[2*modLen];
2009 for(int i=0; i<modLen; i++)
2010 t2[i+modLen] = b[i];
2011
2012 b = montReduce(t2, mod, modLen, inv);
2013
2014 t2 = new int[modLen];
2015 for(int i=0; i<modLen; i++)
2016 t2[i] = b[i];
2017
2018 return new BigInteger(1, t2);
2019 }
2020
2021 /**
2022 * Montgomery reduce n, modulo mod. This reduces modulo mod and divides
2023 * by 2^(32*mlen). Adapted from Colin Plumb's C library.
2024 */
2025 private static int[] montReduce(int[] n, int[] mod, int mlen, int inv) {
2026 int c=0;
2027 int len = mlen;
2028 int offset=0;
2029
2030 do {
2031 int nEnd = n[n.length-1-offset];
2032 int carry = mulAdd(n, mod, offset, mlen, inv * nEnd);
2033 c += addOne(n, offset, mlen, carry);
2034 offset++;
2035 } while(--len > 0);
2036
2137 result = result.multiply(baseToPow2).mod2(p);
2138 expOffset++;
2139 if (expOffset < limit)
2140 baseToPow2 = baseToPow2.square().mod2(p);
2141 }
2142
2143 return result;
2144 }
2145
2146 /**
2147 * Returns a BigInteger whose value is this mod(2**p).
2148 * Assumes that this {@code BigInteger >= 0} and {@code p > 0}.
2149 */
2150 private BigInteger mod2(int p) {
2151 if (bitLength() <= p)
2152 return this;
2153
2154 // Copy remaining ints of mag
2155 int numInts = (p + 31) >>> 5;
2156 int[] mag = new int[numInts];
2157 for (int i=0; i<numInts; i++)
2158 mag[i] = this.mag[i + (this.mag.length - numInts)];
2159
2160 // Mask out any excess bits
2161 int excessBits = (numInts << 5) - p;
2162 mag[0] &= (1L << (32-excessBits)) - 1;
2163
2164 return (mag[0]==0 ? new BigInteger(1, mag) : new BigInteger(mag, 1));
2165 }
2166
2167 /**
2168 * Returns a BigInteger whose value is {@code (this}<sup>-1</sup> {@code mod m)}.
2169 *
2170 * @param m the modulus.
2171 * @return {@code this}<sup>-1</sup> {@code mod m}.
2172 * @throws ArithmeticException {@code m} ≤ 0, or this BigInteger
2173 * has no multiplicative inverse mod m (that is, this BigInteger
2174 * is not <i>relatively prime</i> to m).
2175 */
2176 public BigInteger modInverse(BigInteger m) {
2177 if (m.signum != 1)
2178 throw new ArithmeticException("BigInteger: modulus not positive");
2204 * (Computes <tt>floor(this * 2<sup>n</sup>)</tt>.)
2205 *
2206 * @param n shift distance, in bits.
2207 * @return {@code this << n}
2208 * @throws ArithmeticException if the shift distance is {@code
2209 * Integer.MIN_VALUE}.
2210 * @see #shiftRight
2211 */
2212 public BigInteger shiftLeft(int n) {
2213 if (signum == 0)
2214 return ZERO;
2215 if (n==0)
2216 return this;
2217 if (n<0) {
2218 if (n == Integer.MIN_VALUE) {
2219 throw new ArithmeticException("Shift distance of Integer.MIN_VALUE not supported.");
2220 } else {
2221 return shiftRight(-n);
2222 }
2223 }
2224 int[] newMag = shiftLeft(mag,n);
2225
2226 return new BigInteger(newMag, signum);
2227 }
2228
2229 private static int[] shiftLeft(int[] mag, int n) {
2230 int nInts = n >>> 5;
2231 int nBits = n & 0x1f;
2232 int magLen = mag.length;
2233 int newMag[] = null;
2234
2235 if (nBits == 0) {
2236 newMag = new int[magLen + nInts];
2237 for (int i=0; i<magLen; i++)
2238 newMag[i] = mag[i];
2239 } else {
2240 int i = 0;
2241 int nBits2 = 32 - nBits;
2242 int highBits = mag[0] >>> nBits2;
2243 if (highBits != 0) {
2244 newMag = new int[magLen + nInts + 1];
2245 newMag[i++] = highBits;
2246 } else {
2247 newMag = new int[magLen + nInts];
2248 }
2249 int j=0;
2250 while (j < magLen-1)
2251 newMag[i++] = mag[j++] << nBits | mag[j] >>> nBits2;
2252 newMag[i] = mag[j] << nBits;
2253 }
2254 return newMag;
2255 }
2256
2257 /**
2258 * Returns a BigInteger whose value is {@code (this >> n)}. Sign
2272 if (n<0) {
2273 if (n == Integer.MIN_VALUE) {
2274 throw new ArithmeticException("Shift distance of Integer.MIN_VALUE not supported.");
2275 } else {
2276 return shiftLeft(-n);
2277 }
2278 }
2279
2280 int nInts = n >>> 5;
2281 int nBits = n & 0x1f;
2282 int magLen = mag.length;
2283 int newMag[] = null;
2284
2285 // Special case: entire contents shifted off the end
2286 if (nInts >= magLen)
2287 return (signum >= 0 ? ZERO : negConst[1]);
2288
2289 if (nBits == 0) {
2290 int newMagLen = magLen - nInts;
2291 newMag = new int[newMagLen];
2292 for (int i=0; i<newMagLen; i++)
2293 newMag[i] = mag[i];
2294 } else {
2295 int i = 0;
2296 int highBits = mag[0] >>> nBits;
2297 if (highBits != 0) {
2298 newMag = new int[magLen - nInts];
2299 newMag[i++] = highBits;
2300 } else {
2301 newMag = new int[magLen - nInts -1];
2302 }
2303
2304 int nBits2 = 32 - nBits;
2305 int j=0;
2306 while (j < magLen - nInts - 1)
2307 newMag[i++] = (mag[j++] << nBits2) | (mag[j] >>> nBits);
2308 }
2309
2310 if (signum < 0) {
2311 // Find out whether any one-bits were shifted off the end.
2312 boolean onesLost = false;
2313 for (int i=magLen-1, j=magLen-nInts; i>=j && !onesLost; i--)
2544 * For positive BigIntegers, this is equivalent to the number of bits in
2545 * the ordinary binary representation. (Computes
2546 * {@code (ceil(log2(this < 0 ? -this : this+1)))}.)
2547 *
2548 * @return number of bits in the minimal two's-complement
2549 * representation of this BigInteger, <i>excluding</i> a sign bit.
2550 */
2551 public int bitLength() {
2552 @SuppressWarnings("deprecation") int n = bitLength - 1;
2553 if (n == -1) { // bitLength not initialized yet
2554 int[] m = mag;
2555 int len = m.length;
2556 if (len == 0) {
2557 n = 0; // offset by one to initialize
2558 } else {
2559 // Calculate the bit length of the magnitude
2560 int magBitLength = ((len - 1) << 5) + bitLengthForInt(mag[0]);
2561 if (signum < 0) {
2562 // Check if magnitude is a power of two
2563 boolean pow2 = (Integer.bitCount(mag[0]) == 1);
2564 for(int i=1; i< len && pow2; i++)
2565 pow2 = (mag[i] == 0);
2566
2567 n = (pow2 ? magBitLength -1 : magBitLength);
2568 } else {
2569 n = magBitLength;
2570 }
2571 }
2572 bitLength = n + 1;
2573 }
2574 return n;
2575 }
2576
2577 /**
2578 * Returns the number of bits in the two's complement representation
2579 * of this BigInteger that differ from its sign bit. This method is
2580 * useful when implementing bit-vector style sets atop BigIntegers.
2581 *
2582 * @return number of bits in the two's complement representation
2583 * of this BigInteger that differ from its sign bit.
2584 */
|
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)
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--;
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
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");
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
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--)
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 */
|