29 |
29 |
30 package java.math; |
30 package java.math; |
31 |
31 |
32 import java.util.Random; |
32 import java.util.Random; |
33 import java.io.*; |
33 import java.io.*; |
|
34 import java.util.Arrays; |
34 |
35 |
35 /** |
36 /** |
36 * Immutable arbitrary-precision integers. All operations behave as if |
37 * Immutable arbitrary-precision integers. All operations behave as if |
37 * BigIntegers were represented in two's-complement notation (like Java's |
38 * 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 types). BigInteger provides analogues to all of Java's |
1610 primitiveLeftShift(a, len, nBits); |
1611 primitiveLeftShift(a, len, nBits); |
1611 return a; |
1612 return a; |
1612 } else { // Array must be resized |
1613 } else { // Array must be resized |
1613 if (nBits <= (32-bitsInHighWord)) { |
1614 if (nBits <= (32-bitsInHighWord)) { |
1614 int result[] = new int[nInts+len]; |
1615 int result[] = new int[nInts+len]; |
1615 for (int i=0; i<len; i++) |
1616 System.arraycopy(a, 0, result, 0, len); |
1616 result[i] = a[i]; |
|
1617 primitiveLeftShift(result, result.length, nBits); |
1617 primitiveLeftShift(result, result.length, nBits); |
1618 return result; |
1618 return result; |
1619 } else { |
1619 } else { |
1620 int result[] = new int[nInts+len+1]; |
1620 int result[] = new int[nInts+len+1]; |
1621 for (int i=0; i<len; i++) |
1621 System.arraycopy(a, 0, result, 0, len); |
1622 result[i] = a[i]; |
|
1623 primitiveRightShift(result, result.length, 32 - nBits); |
1622 primitiveRightShift(result, result.length, 32 - nBits); |
1624 return result; |
1623 return result; |
1625 } |
1624 } |
1626 } |
1625 } |
1627 } |
1626 } |
1905 // Set b to the square of the base |
1904 // Set b to the square of the base |
1906 int[] b = squareToLen(table[0], modLen, null); |
1905 int[] b = squareToLen(table[0], modLen, null); |
1907 b = montReduce(b, mod, modLen, inv); |
1906 b = montReduce(b, mod, modLen, inv); |
1908 |
1907 |
1909 // Set t to high half of b |
1908 // Set t to high half of b |
1910 int[] t = new int[modLen]; |
1909 int[] t = Arrays.copyOf(b, modLen); |
1911 for(int i=0; i<modLen; i++) |
|
1912 t[i] = b[i]; |
|
1913 |
1910 |
1914 // Fill in the table with odd powers of the base |
1911 // Fill in the table with odd powers of the base |
1915 for (int i=1; i<tblmask; i++) { |
1912 for (int i=1; i<tblmask; i++) { |
1916 int[] prod = multiplyToLen(t, modLen, table[i-1], modLen, null); |
1913 int[] prod = multiplyToLen(t, modLen, table[i-1], modLen, null); |
1917 table[i] = montReduce(prod, mod, modLen, inv); |
1914 table[i] = montReduce(prod, mod, modLen, inv); |
2004 } |
2001 } |
2005 } |
2002 } |
2006 |
2003 |
2007 // Convert result out of Montgomery form and return |
2004 // Convert result out of Montgomery form and return |
2008 int[] t2 = new int[2*modLen]; |
2005 int[] t2 = new int[2*modLen]; |
2009 for(int i=0; i<modLen; i++) |
2006 System.arraycopy(b, 0, t2, modLen, modLen); |
2010 t2[i+modLen] = b[i]; |
|
2011 |
2007 |
2012 b = montReduce(t2, mod, modLen, inv); |
2008 b = montReduce(t2, mod, modLen, inv); |
2013 |
2009 |
2014 t2 = new int[modLen]; |
2010 t2 = Arrays.copyOf(b, modLen); |
2015 for(int i=0; i<modLen; i++) |
|
2016 t2[i] = b[i]; |
|
2017 |
2011 |
2018 return new BigInteger(1, t2); |
2012 return new BigInteger(1, t2); |
2019 } |
2013 } |
2020 |
2014 |
2021 /** |
2015 /** |
2152 return this; |
2146 return this; |
2153 |
2147 |
2154 // Copy remaining ints of mag |
2148 // Copy remaining ints of mag |
2155 int numInts = (p + 31) >>> 5; |
2149 int numInts = (p + 31) >>> 5; |
2156 int[] mag = new int[numInts]; |
2150 int[] mag = new int[numInts]; |
2157 for (int i=0; i<numInts; i++) |
2151 System.arraycopy(this.mag, (this.mag.length - numInts), mag, 0, numInts); |
2158 mag[i] = this.mag[i + (this.mag.length - numInts)]; |
|
2159 |
2152 |
2160 // Mask out any excess bits |
2153 // Mask out any excess bits |
2161 int excessBits = (numInts << 5) - p; |
2154 int excessBits = (numInts << 5) - p; |
2162 mag[0] &= (1L << (32-excessBits)) - 1; |
2155 mag[0] &= (1L << (32-excessBits)) - 1; |
2163 |
2156 |
2219 throw new ArithmeticException("Shift distance of Integer.MIN_VALUE not supported."); |
2212 throw new ArithmeticException("Shift distance of Integer.MIN_VALUE not supported."); |
2220 } else { |
2213 } else { |
2221 return shiftRight(-n); |
2214 return shiftRight(-n); |
2222 } |
2215 } |
2223 } |
2216 } |
2224 int[] newMag = shiftLeft(mag,n); |
2217 int[] newMag = shiftLeft(mag, n); |
2225 |
2218 |
2226 return new BigInteger(newMag, signum); |
2219 return new BigInteger(newMag, signum); |
2227 } |
2220 } |
2228 |
2221 |
2229 private static int[] shiftLeft(int[] mag, int n) { |
2222 private static int[] shiftLeft(int[] mag, int n) { |
2232 int magLen = mag.length; |
2225 int magLen = mag.length; |
2233 int newMag[] = null; |
2226 int newMag[] = null; |
2234 |
2227 |
2235 if (nBits == 0) { |
2228 if (nBits == 0) { |
2236 newMag = new int[magLen + nInts]; |
2229 newMag = new int[magLen + nInts]; |
2237 for (int i=0; i<magLen; i++) |
2230 System.arraycopy(mag, 0, newMag, 0, magLen); |
2238 newMag[i] = mag[i]; |
|
2239 } else { |
2231 } else { |
2240 int i = 0; |
2232 int i = 0; |
2241 int nBits2 = 32 - nBits; |
2233 int nBits2 = 32 - nBits; |
2242 int highBits = mag[0] >>> nBits2; |
2234 int highBits = mag[0] >>> nBits2; |
2243 if (highBits != 0) { |
2235 if (highBits != 0) { |
2286 if (nInts >= magLen) |
2278 if (nInts >= magLen) |
2287 return (signum >= 0 ? ZERO : negConst[1]); |
2279 return (signum >= 0 ? ZERO : negConst[1]); |
2288 |
2280 |
2289 if (nBits == 0) { |
2281 if (nBits == 0) { |
2290 int newMagLen = magLen - nInts; |
2282 int newMagLen = magLen - nInts; |
2291 newMag = new int[newMagLen]; |
2283 newMag = Arrays.copyOf(mag, newMagLen); |
2292 for (int i=0; i<newMagLen; i++) |
|
2293 newMag[i] = mag[i]; |
|
2294 } else { |
2284 } else { |
2295 int i = 0; |
2285 int i = 0; |
2296 int highBits = mag[0] >>> nBits; |
2286 int highBits = mag[0] >>> nBits; |
2297 if (highBits != 0) { |
2287 if (highBits != 0) { |
2298 newMag = new int[magLen - nInts]; |
2288 newMag = new int[magLen - nInts]; |
2559 // Calculate the bit length of the magnitude |
2549 // Calculate the bit length of the magnitude |
2560 int magBitLength = ((len - 1) << 5) + bitLengthForInt(mag[0]); |
2550 int magBitLength = ((len - 1) << 5) + bitLengthForInt(mag[0]); |
2561 if (signum < 0) { |
2551 if (signum < 0) { |
2562 // Check if magnitude is a power of two |
2552 // Check if magnitude is a power of two |
2563 boolean pow2 = (Integer.bitCount(mag[0]) == 1); |
2553 boolean pow2 = (Integer.bitCount(mag[0]) == 1); |
2564 for(int i=1; i< len && pow2; i++) |
2554 for (int i=1; i< len && pow2; i++) |
2565 pow2 = (mag[i] == 0); |
2555 pow2 = (mag[i] == 0); |
2566 |
2556 |
2567 n = (pow2 ? magBitLength -1 : magBitLength); |
2557 n = (pow2 ? magBitLength -1 : magBitLength); |
2568 } else { |
2558 } else { |
2569 n = magBitLength; |
2559 n = magBitLength; |