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
