diff options
author | Warren Levy <warrenl@cygnus.com> | 2000-02-14 10:23:29 +0000 |
---|---|---|
committer | Warren Levy <warrenl@gcc.gnu.org> | 2000-02-14 10:23:29 +0000 |
commit | 34540fe35ebce1d18cf6a43983c669db5df61b36 (patch) | |
tree | 25b7abd6d60029d846218b9f467ae92b950c211c | |
parent | eb3e566556e0588e7f4433e881ebe238346dd704 (diff) | |
download | gcc-34540fe35ebce1d18cf6a43983c669db5df61b36.zip gcc-34540fe35ebce1d18cf6a43983c669db5df61b36.tar.gz gcc-34540fe35ebce1d18cf6a43983c669db5df61b36.tar.bz2 |
MPN.java (findLowestBit): Made methods public.
* gnu/gcj/math/MPN.java(findLowestBit): Made methods public.
* java/math/BigInteger.java(BigInteger(int,int,java.util.Random):
New constructor.
(min): Implemented.
(max): Implemented.
(modPow): Rewritten to not use the naive, slow, brute force approach.
(isProbablePrime): Implemented.
(testBit): Implemented.
(flipBit): Implemented.
(getLowestSetBit): Implemented.
From-SVN: r31966
-rw-r--r-- | libjava/ChangeLog | 16 | ||||
-rw-r--r-- | libjava/gnu/gcj/math/MPN.java | 4 | ||||
-rw-r--r-- | libjava/java/math/BigInteger.java | 174 |
3 files changed, 171 insertions, 23 deletions
diff --git a/libjava/ChangeLog b/libjava/ChangeLog index 8551df7..0a9aa3e 100644 --- a/libjava/ChangeLog +++ b/libjava/ChangeLog @@ -1,3 +1,17 @@ +2000-02-14 Warren Levy <warrenl@cygnus.com> + + * gnu/gcj/math/MPN.java(findLowestBit): Made methods public. + + * java/math/BigInteger.java(BigInteger(int,int,java.util.Random): + New constructor. + (min): Implemented. + (max): Implemented. + (modPow): Rewritten to not use the naive, slow, brute force approach. + (isProbablePrime): Implemented. + (testBit): Implemented. + (flipBit): Implemented. + (getLowestSetBit): Implemented. + 2000-02-16 Anthony Green <green@redhat.com> * configure.host: Use the same options for i386 and i486 as we do @@ -17,7 +31,7 @@ Fri Feb 11 19:48:08 2000 Anthony Green <green@cygnus.com> * interpret.cc (continue1): Use STOREA, not STOREI, to implement astore instruction. From Hans Boehm. -2000-02-04 Warren Levy <warrenl@cygnus.com> +2000-02-11 Warren Levy <warrenl@cygnus.com> * java/math/BigInteger.java(BigInteger(String, int)): New constructor. (BigInteger(String)): New constructor. diff --git a/libjava/gnu/gcj/math/MPN.java b/libjava/gnu/gcj/math/MPN.java index 5bbabfd..6ae60f2 100644 --- a/libjava/gnu/gcj/math/MPN.java +++ b/libjava/gnu/gcj/math/MPN.java @@ -571,7 +571,7 @@ public class MPN /** Return least i such that word&(1<<i). Assumes word!=0. */ - static int findLowestBit (int word) + public static int findLowestBit (int word) { int i = 0; while ((word & 0xF) == 0) @@ -591,7 +591,7 @@ public class MPN /** Return least i such that words & (1<<i). Assumes there is such an i. */ - static int findLowestBit (int[] words) + public static int findLowestBit (int[] words) { for (int i = 0; ; i++) { diff --git a/libjava/java/math/BigInteger.java b/libjava/java/math/BigInteger.java index e16a26e..3a5a26b 100644 --- a/libjava/java/math/BigInteger.java +++ b/libjava/java/math/BigInteger.java @@ -19,7 +19,9 @@ import java.util.Random; /** * Written using on-line Java Platform 1.2 API Specification, as well - * as "The Java Class Libraries", 2nd edition (Addison-Wesley, 1998). + * as "The Java Class Libraries", 2nd edition (Addison-Wesley, 1998) and + * "Applied Cryptography, Second Edition" by Bruce Schneier (Wiley, 1996). + * * Based primarily on IntNum.java BitOps.java by Per Bothner <per@bothner.com> * (found in Kawa 1.6.62). @@ -60,6 +62,15 @@ public class BigInteger extends Number implements Comparable private static final int TRUNCATE = 3; private static final int ROUND = 4; + /** When checking the probability of primes, it is most efficient to + * first check the factoring of small primes, so we'll use this array. + */ + private static final int[] primes = + { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, + 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, + 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, + 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251 }; + private BigInteger() { } @@ -138,6 +149,21 @@ public class BigInteger extends Number implements Comparable this.words = result.words; } + public BigInteger(int bitLength, int certainty, Random rnd) + { + this(bitLength, rnd); + + // Keep going until we find a probable prime. + while (true) + { + if (isProbablePrime(certainty)) + return; + + BigInteger next = new BigInteger(bitLength, rnd); + this.ival = next.ival; + this.words = next.words; + } + } /** Return a (possibly-shared) BigInteger with a given long value. */ private static BigInteger make(long value) @@ -290,6 +316,16 @@ public class BigInteger extends Number implements Comparable return compareTo(this, val); } + public BigInteger min(BigInteger val) + { + return compareTo(this, val) < 0 ? this : val; + } + + public BigInteger max(BigInteger val) + { + return compareTo(this, val) > 0 ? this : val; + } + private final boolean isOdd() { int low = words == null ? ival : words[0]; @@ -1121,7 +1157,29 @@ public class BigInteger extends Number implements Comparable if (exponent.isOne()) return mod(m); - return pow(exponent).mod(m); + // To do this naively by first raising this to the power of exponent + // and then performing modulo m would be extremely expensive, especially + // for very large numbers. The solution is found in Number Theory + // where a combination of partial powers and modulos can be done easily. + // + // We'll use the algorithm for Additive Chaining which can be found on + // p. 244 of "Applied Cryptography, Second Edition" by Bruce Schneier. + BigInteger s, t, u; + int i; + + s = ONE; + t = this; + u = exponent; + + while (!u.isZero()) + { + if (u.and(ONE).isOne()) + s = times(s, t).mod(m); + u = u.shiftRight(1); + t = times(t, t).mod(m); + } + + return s; } /** Calculate Greatest Common Divisor for non-negative ints. */ @@ -1184,6 +1242,72 @@ public class BigInteger extends Number implements Comparable return result.canonicalize(); } + public boolean isProbablePrime(int certainty) + { + /** We'll use the Rabin-Miller algorithm for doing a probabilistic + * primality test. It is fast, easy and has faster decreasing odds of a + * composite passing than with other tests. This means that this + * method will actually have a probability much greater than the + * 1 - .5^certainty specified in the JCL (p. 117), but I don't think + * anyone will complain about better performance with greater certainty. + * + * The Rabin-Miller algorithm can be found on pp. 259-261 of "Applied + * Cryptography, Second Edition" by Bruce Schneier. + */ + + // First rule out small prime factors and assure the number is odd. + for (int i = 0; i < primes.length; i++) + { + if (words == null && ival == primes[i]) + return true; + if (remainder(make(primes[i])).isZero()) + return false; + } + + // Now perform the Rabin-Miller test. + // NB: I know that this can be simplified programatically, but + // I have tried to keep it as close as possible to the algorithm + // as written in the Schneier book for reference purposes. + + // Set b to the number of times 2 evenly divides (this - 1). + // I.e. 2^b is the largest power of 2 that divides (this - 1). + BigInteger pMinus1 = add(this, -1); + int b = pMinus1.getLowestSetBit(); + + // Set m such that this = 1 + 2^b * m. + BigInteger m = pMinus1.divide(make(2L << b - 1)); + + Random rand = new Random(); + while (certainty-- > 0) + { + // Pick a random number greater than 1 and less than this. + // The algorithm says to pick a small number to make the calculations + // go faster, but it doesn't say how small; we'll use 2 to 1024. + int a = rand.nextInt(); + a = (a < 0 ? -a : a) % 1023 + 2; + + BigInteger z = make(a).modPow(m, this); + if (z.isOne() || z.equals(pMinus1)) + continue; // Passes the test; may be prime. + + int i; + for (i = 0; i < b; ) + { + if (z.isOne()) + return false; + i++; + if (z.equals(pMinus1)) + break; // Passes the test; may be prime. + + z = z.modPow(make(2), this); + } + + if (i == b && !z.equals(pMinus1)) + return false; + } + return true; + } + private void setInvert() { if (words == null) @@ -1727,7 +1851,7 @@ public class BigInteger extends Number implements Comparable case 1: return x.and(y); case 3: return x; case 5: return y; - case 15: return smallFixNums[-1 - minFixNum]; // Returns -1. + case 15: return make(-1); } BigInteger result = new BigInteger(); setBitOp(result, op, x, y); @@ -1998,6 +2122,33 @@ public class BigInteger extends Number implements Comparable return or(ONE.shiftLeft(n)); } + public boolean testBit(int n) + { + if (n < 0) + throw new ArithmeticException(); + + return !and(ONE.shiftLeft(n)).isZero(); + } + + public BigInteger flipBit(int n) + { + if (n < 0) + throw new ArithmeticException(); + + return xor(ONE.shiftLeft(n)); + } + + public int getLowestSetBit() + { + if (isZero()) + return -1; + + if (words == null) + return MPN.findLowestBit(ival); + else + return MPN.findLowestBit(words); + } + // bit4count[I] is number of '1' bits in I. private static final byte[] bit4_count = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4}; @@ -2039,21 +2190,4 @@ public class BigInteger extends Number implements Comparable } return isNegative() ? x_len * 32 - i : i; } - -/* TODO: - - public BigInteger(int bitLength, int certainty, Random rnd) - - public boolean testBit(int n) - - public BigInteger flipBit(int n) - - public int getLowestSetBit() - - public boolean isProbablePrime(int certainty) - - public BigInteger min(BigInteger val) - - public BigInteger max(BigInteger val) -*/ } |