+ 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;
+ }
+