hello there, this patch fixes a bug in the Euler criterion test implementation, removed some unused methods and makes the BigInteger.isProbablePrime the main (for the time being) primality test.
2006-01-30 Raif S. Naffah <[EMAIL PROTECTED]> * gnu/java/security/util/Prime2.java (passEulerCriterion): Was incorrectly failing primality test for some known primes. Fixed. (passFermatLittleTheorem): Removed. (passMillerRabin): Removed. (isProbablePrime): Cache primes that pass the primality tests. Use BigInteger.isProbablePrime(int) for primality tests. (debugBI): New static debugging method. a Mauve testlet (gnu.testlet.gnu.java.security.util.TestOfPrime2 has been added for the Euler criterion fix. cheers; rsn
Index: Prime2.java =================================================================== RCS file: /cvsroot/classpath/classpath/gnu/java/security/util/Prime2.java,v retrieving revision 1.1 diff -u -r1.1 Prime2.java --- Prime2.java 26 Jan 2006 02:25:11 -0000 1.1 +++ Prime2.java 29 Jan 2006 13:48:18 -0000 @@ -38,13 +38,10 @@ package gnu.java.security.util; -import gnu.java.security.Properties; - import java.io.PrintWriter; import java.lang.ref.WeakReference; import java.math.BigInteger; import java.util.Map; -import java.util.Random; import java.util.WeakHashMap; /** @@ -189,7 +186,7 @@ /** * <p>Java port of Colin Plumb primality test (Euler Criterion) * implementation for a base of 2 --from bnlib-1.1 release, function - * primeTest() in prime.c. this is his comments; (bn is our w).</p> + * primeTest() in prime.c. this is his comments.</p> * * <p>"Now, check that bn is prime. If it passes to the base 2, it's prime * beyond all reasonable doubt, and everything else is just gravy, but it @@ -234,86 +231,61 @@ * All primes <code>== 1 (mod 4)</code> can be expressed as <code>a^2 + * (2*b)^2</code>, but I see no cheap way to evaluate this condition."</p> * - * @param w the number to test. + * @param bn the number to test. * @return <code>true</code> iff the designated number passes Euler criterion * as implemented by Colin Plumb in his <i>bnlib</i> version 1.1. */ - - // FIXME this method incorrectly returns false for certain primes, notably - // 38737, 61681, 65537, 229153, and 274177. - public static boolean passEulerCriterion(final BigInteger w) + public static boolean passEulerCriterion(final BigInteger bn) { - // first check if it's already a known prime - WeakReference obj = (WeakReference) knownPrimes.get(w); - if (obj != null && w.equals(obj.get())) - { - if (DEBUG && debuglevel > 4) - { - debug("found in known primes"); - } - return true; - } - - BigInteger w_minus_one = w.subtract(ONE); - BigInteger e = w_minus_one; + BigInteger bn_minus_one = bn.subtract(ONE); + BigInteger e = bn_minus_one; // l is the 3 least-significant bits of e int l = e.and(BigInteger.valueOf(7L)).intValue(); int j = 1; // Where to start in prime array for strong prime tests - BigInteger A; + BigInteger a; int k; - if ((l & 7) != 0) + if (l != 0) { e = e.shiftRight(1); - A = TWO.modPow(e, w); - if ((l & 7) == 6) - { // bn == 7 mod 8, expect +1 - if (A.bitCount() != 1) + a = TWO.modPow(e, bn); + if (l == 6) // bn == 7 mod 8, expect +1 + { + if (a.bitLength() != 1) { - if (DEBUG && debuglevel > 4) - { - debug(w.toString(16) + " fails Euler criterion #1..."); - } + debugBI("Fails Euler criterion #1", bn); return false; // Not prime } k = 1; } - else - { // bn == 3 or 5 mod 8, expect -1 == bn-1 - A = A.add(ONE); - if (!A.equals(w)) + else // bn == 3 or 5 mod 8, expect -1 == bn-1 + { + a = a.add(ONE); + if (a.compareTo(bn) != 0) { - if (DEBUG && debuglevel > 4) - { - debug(w.toString(16) + " fails Euler criterion #2..."); - } + debugBI("Fails Euler criterion #2", bn); return false; // Not prime } k = 1; - if ((l & 4) != 0) - { // bn == 5 mod 8, make odd for strong tests + if ((l & 4) != 0) // bn == 5 mod 8, make odd for strong tests + { e = e.shiftRight(1); k = 2; } } } - else - { // bn == 1 mod 8, expect 2^((bn-1)/4) == +/-1 mod bn + else // bn == 1 mod 8, expect 2^((bn-1)/4) == +/-1 mod bn + { e = e.shiftRight(2); - A = TWO.modPow(e, w); - if (A.bitCount() == 1) - { - j = 0; // Re-do strong prime test to base 2 - } + a = TWO.modPow(e, bn); + if (a.bitLength() == 1) + j = 0; // Re-do strong prime test to base 2 else { - A = A.add(ONE); - if (!A.equals(w)) + a = a.add(ONE); + if (a.compareTo(bn) != 0) { - if (DEBUG && debuglevel > 4) - { - debug(w.toString(16) + " fails Euler criterion #3..."); - } + debugBI("Fails Euler criterion #3", bn); return false; // Not prime } } @@ -329,187 +301,38 @@ // when the previous test was as good as a strong prime test, but 1/8 of // the time, j = 0 because the strong prime test to the base 2 needs to // be re-done. - //for (int i = j; i < SMALL_PRIME_COUNT; i++) { - for (int i = j; i < 13; i++) - { // try only the first 13 primes - A = SMALL_PRIME[i]; - A = A.modPow(e, w); - if (A.bitCount() == 1) - { - continue; // Passed this test - } + for (int i = j; i < 7; i++) // try only the first 7 primes + { + a = SMALL_PRIME[i]; + a = a.modPow(e, bn); + if (a.bitLength() == 1) + continue; // Passed this test + l = k; while (true) { - // A = A.add(ONE); - // if (A.equals(w)) { // Was result bn-1? - if (A.equals(w_minus_one)) - { // Was result bn-1? - break; // Prime - } - if (--l == 0) - { // Reached end, not -1? luck? - if (DEBUG && debuglevel > 4) - { - debug(w.toString(16) + " fails Euler criterion #4..."); - } +// a = a.add(ONE); +// if (a.compareTo(w) == 0) { // Was result bn-1? + if (a.compareTo(bn_minus_one) == 0) // Was result bn-1? + break; // Prime + + if (--l == 0) // Reached end, not -1? luck? + { + debugBI("Fails Euler criterion #4", bn); return false; // Failed, not prime } // This portion is executed, on average, once - // A = A.subtract(ONE); // Put a back where it was - A = A.modPow(TWO, w); - if (A.bitCount() == 1) +// a = a.subtract(ONE); // Put a back where it was + a = a.modPow(TWO, bn); + if (a.bitLength() == 1) { - if (DEBUG && debuglevel > 4) - { - debug(w.toString(16) + " fails Euler criterion #5..."); - } + debugBI("Fails Euler criterion #5", bn); return false; // Failed, not prime } } // It worked (to the base primes[i]) } - if (DEBUG && debuglevel > 4) - { - debug(w.toString(16) + " passes Euler criterion..."); - } - - // store it in the known primes weak hash-map - knownPrimes.put(w, new WeakReference(w)); - - return true; - } - - /** - * <p>Checks Fermat's Little Theorem for base <i>b</i>; i.e. - * <code><i>b</i>**(w-1) == 1 (mod w)</code>.</p> - * - * @param w the number to test. - * @param t the number of random bases to test. - * @return <code>true</code> iff <code><i>b</i>**(w-1) == 1 (mod w)</code>, - * for some <i>b</i>. - */ - public static boolean passFermatLittleTheorem(final BigInteger w, int t) - { - final BigInteger w_minus_one = w.subtract(ONE); - if (t <= 0) - { - t = 10; // XXX - } - if (!TWO.modPow(w_minus_one, w).equals(ONE)) - { - if (DEBUG && debuglevel > 4) - { - debug(w.toString(16) + " fails Fermat's little theorem for base 2"); - } - return false; - } - for (int i = 0; i < t; i++) - { - byte[] buf = new byte[(w.bitLength() + 7) / 8 - 1]; - BigInteger base = null; - do - { - new Random ().nextBytes(buf); - base = new BigInteger(1, buf); - } - while (base.compareTo(TWO) < 0 || base.compareTo(w_minus_one) > 0); - if (!base.modPow(w_minus_one, w).equals(ONE)) - { - if (DEBUG && debuglevel > 4) - { - debug(w.toString(16) - + " fails Fermat's little theorem for base " - + base.toString(16)); - } - return false; - } - } - if (DEBUG && debuglevel > 4) - { - debug(w.toString(16) + " passes Fermat's little theorem for " + t - + " bases..."); - } - return true; - } - - /** - * <p>Applies the Miller-Rabin strong probabilistic primality test.</p> - * - * <p>The HAC (Handbook of Applied Cryptography), Alfred Menezes & al. Note - * 4.57 states that for <code>q</code>, <code>n=18</code> is enough while - * for <code>p</code>, <code>n=6</code> (512 bits) or <code>n=3</cdoe> (1024 - * bits) are enough to yield <i>robust</i> primality tests. The values used - * are from table 4.4 given in Note 4.49.</p> - * - * @param w the number to test. - * @return <code>true</code> iff the designated number passes the Miller- - * Rabin probabilistic primality test for a computed number of rounds. - */ - public static boolean passMillerRabin(BigInteger n, int t) - { - int nbytes = (n.bitLength() + 7) / 8; - byte[] ab = new byte[nbytes]; - - // 1. Write n - 1 = 2^s * r. - BigInteger n_minus_1 = n.subtract(ONE); - BigInteger r = n_minus_1; - int s = 0; - while (!r.testBit(0)) - { - r = r.shiftRight(1); - s++; - } - - // 2. For i from 1 to t, do: - for (int i = 0; i < t; i++) - { - - // 2.1 Choose a random integer a, 2 <= a <= n - 2. - BigInteger a; - do - { - new Random ().nextBytes(ab); - a = new BigInteger(1, ab); - } - while (a.compareTo(TWO) < 0 || a.compareTo(n) > 0); - - // 2.2 Compute y = a^r mod n. - BigInteger y = a.modPow(r, n); - - // If y != 1 and y != n - 1, then: - if (!y.equals(ONE) && !y.equals(n_minus_1)) - { - for (int j = 1; j < s - 1 && !y.equals(n_minus_1); j++) - { - // Compute y = y^2 mod n. - y = y.modPow(TWO, n); - - // If y = 1 return "composite" - if (y.equals(ONE)) - { - if (DEBUG && debuglevel > 4) - { - debug(n.toString(16) + " fails Miller-Rabin test..."); - } - return false; - } - } - // If y != n - 1 return "composite" - if (!y.equals(n_minus_1)) - { - if (DEBUG && debuglevel > 4) - { - debug(n.toString(16) + " fails Miller-Rabin test..."); - } - return false; - } - } - } - if (DEBUG && debuglevel > 4) - { - debug(n.toString(16) + " passes Miller-Rabin test..."); - } + debugBI("Passes Euler criterion", bn); return true; } @@ -519,114 +342,76 @@ } /** - * <p>This implementation does not rely solely on the Miller-Rabin strong - * probabilistic primality test to claim the primality of the designated - * number. It instead, tries dividing the designated number by the first 1000 - * small primes, and if no divisor was found, invokes a port of Colin Plumb's - * implementation of the Euler Criterion, then tries the Miller-Rabin test.</p> + * Wrapper around [EMAIL PROTECTED] BigInteger#isProbablePrime(int)} with few pre-checks. * * @param w the integer to test. * @param certainty the certainty with which to compute the test. - * @param doMillerRabin if <code>true</code> and the designated integer was - * already found to be a probable prime, then also do a Miller-Rabin test. - * @return <code>true</code> iff the designated number has no small prime - * divisor passes the Euler criterion, and optionally a Miller-Rabin test. */ public static boolean isProbablePrime(BigInteger w, int certainty) { // Nonnumbers are not prime. if (w == null) - { return false; - } // eliminate trivial cases when w == 0 or 1 if (w.equals(ZERO) || w.equals(ONE)) - { return false; - } // Test if w is a known small prime. for (int i = 0; i < SMALL_PRIME_COUNT; i++) - { if (w.equals(SMALL_PRIME[i])) { if (DEBUG && debuglevel > 4) - { debug(w.toString(16) + " is a small prime"); - } return true; } + + // Check if it's already a known prime + WeakReference obj = (WeakReference) knownPrimes.get(w); + if (obj != null && w.equals(obj.get())) + { + if (DEBUG && debuglevel > 4) + debug("found in known primes"); + return true; } // trial division with first 1000 primes if (hasSmallPrimeDivisor(w)) { if (DEBUG && debuglevel > 4) - { debug(w.toString(16) + " has a small prime divisor. Rejected..."); - } return false; } - // Do a check with Fermat's little theorem. - // if (passFermatLittleTheorem(w, certainty)) { - // if (DEBUG && debuglevel > 4) { - // debug(w.toString(16)+" passes Fermat's little theorem..."); - // } - // } else { - // if (DEBUG && debuglevel > 4) { - // debug(w.toString(16)+" fails Fermat's little theorem. Rejected..."); - // } - // return false; - // } - - // Euler's criterion. - // if (passEulerCriterion(w)) { - // if (DEBUG && debuglevel > 4) { - // debug(w.toString(16)+" passes Euler's criterion..."); - // } - // } else { - // if (DEBUG && debuglevel > 4) { - // debug(w.toString(16)+" fails Euler's criterion. Rejected..."); - // } - // return false; - // } +// Euler's criterion. +// if (passEulerCriterion(w)) { +// if (DEBUG && debuglevel > 4) { +// debug(w.toString(16)+" passes Euler's criterion..."); +// } +// } else { +// if (DEBUG && debuglevel > 4) { +// debug(w.toString(16)+" fails Euler's criterion. Rejected..."); +// } +// return false; +// } +// +// if (DEBUG && debuglevel > 4) +// { +// debug(w.toString(16) + " is probable prime. Accepted..."); +// } + + boolean result = w.isProbablePrime(certainty); + if (result && certainty > 0) // store it in the known primes weak hash-map + knownPrimes.put(w, new WeakReference(w)); - // Miller-Rabin probabilistic primality test. - if (passMillerRabin(w, certainty)) - { - if (DEBUG && debuglevel > 4) - { - debug(w.toString(16) + " passes Miller-Rabin PPT..."); - } - } - else - { - if (DEBUG && debuglevel > 4) - { - debug(w.toString(16) + " fails Miller-Rabin PPT. Rejected..."); - } - return false; - } - - if (DEBUG && debuglevel > 4) - { - debug(w.toString(16) + " is probable prime. Accepted..."); - } + return result; + } - // now compare to JDK primality test - if (DEBUG && debuglevel > 0 && !w.isProbablePrime(certainty)) - { - System.err.println("The gnu.crypto library and the JDK disagree on " - + "whether 0x" + w.toString(16) - + " is a probable prime or not."); - System.err.println("While this library claims it is, the JDK claims" - + " the opposite."); - System.err.println("Please contact the maintainer of this library, " - + "and provide this message for further investigation. TIA"); - } + // helper methods ----------------------------------------------------------- - return true; + private static final void debugBI(String msg, BigInteger bn) + { + if (DEBUG && debuglevel > 4) + debug("*** " + msg + ": 0x" + bn.toString(16)); } }
pgpiuXVdGosfv.pgp
Description: PGP signature