2 Copyright (C) 2001, 2002, 2003, 2006 Free Software Foundation, Inc.
4 This file is a part of GNU Classpath.
6 GNU Classpath is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2 of the License, or (at
9 your option) any later version.
11 GNU Classpath is distributed in the hope that it will be useful, but
12 WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GNU Classpath; if not, write to the Free Software
18 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301
21 Linking this library statically or dynamically with other modules is
22 making a combined work based on this library. Thus, the terms and
23 conditions of the GNU General Public License cover the whole
26 As a special exception, the copyright holders of this library give you
27 permission to link this library with independent modules to produce an
28 executable, regardless of the license terms of these independent
29 modules, and to copy and distribute the resulting executable under
30 terms of your choice, provided that you also meet, for each linked
31 independent module, the terms and conditions of the license of that
32 module. An independent module is a module which is not derived from
33 or based on this library. If you modify this library, you may extend
34 this exception to your version of the library, but you are not
35 obligated to do so. If you do not wish to do so, delete this
36 exception statement from your version. */
39 package gnu
.java
.security
.util
;
41 import java
.io
.PrintWriter
;
42 import java
.lang
.ref
.WeakReference
;
43 import java
.math
.BigInteger
;
45 import java
.util
.WeakHashMap
;
48 * <p>A collection of prime number related utilities used in this library.</p>
53 // Debugging methods and variables
54 // -------------------------------------------------------------------------
56 private static final String NAME
= "prime";
58 private static final boolean DEBUG
= false;
60 private static final int debuglevel
= 5;
62 private static final PrintWriter err
= new PrintWriter(System
.out
, true);
64 private static void debug(String s
)
66 err
.println(">>> " + NAME
+ ": " + s
);
69 // Constants and variables
70 // -------------------------------------------------------------------------
72 private static final int DEFAULT_CERTAINTY
= 20; // XXX is this a good value?
74 private static final BigInteger ZERO
= BigInteger
.ZERO
;
76 private static final BigInteger ONE
= BigInteger
.ONE
;
78 private static final BigInteger TWO
= BigInteger
.valueOf(2L);
81 * The first SMALL_PRIME primes: Algorithm P, section 1.3.2, The Art of
82 * Computer Programming, Donald E. Knuth.
84 private static final int SMALL_PRIME_COUNT
= 1000;
86 private static final BigInteger
[] SMALL_PRIME
= new BigInteger
[SMALL_PRIME_COUNT
];
89 long time
= -System
.currentTimeMillis();
96 SMALL_PRIME
[++J
] = BigInteger
.valueOf(N
);
104 P6
: for (int K
= 1; true; K
++)
106 prime
= SMALL_PRIME
[K
].intValue();
107 if ((N
% prime
) == 0)
111 else if ((N
/ prime
) <= prime
)
118 time
+= System
.currentTimeMillis();
119 if (DEBUG
&& debuglevel
> 8)
122 for (int i
= 0; i
< (SMALL_PRIME_COUNT
/ 10); i
++)
124 sb
= new StringBuffer();
125 for (int j
= 0; j
< 10; j
++)
127 sb
.append(String
.valueOf(SMALL_PRIME
[i
* 10 + j
])).append(" ");
129 debug(sb
.toString());
132 if (DEBUG
&& debuglevel
> 4)
134 debug("Generating first " + String
.valueOf(SMALL_PRIME_COUNT
)
135 + " primes took: " + String
.valueOf(time
) + " ms.");
139 private static final Map knownPrimes
= new WeakHashMap();
142 // -------------------------------------------------------------------------
144 /** Trivial constructor to enforce Singleton pattern. */
151 // -------------------------------------------------------------------------
154 * <p>Trial division for the first 1000 small primes.</p>
156 * <p>Returns <code>true</code> if at least one small prime, among the first
157 * 1000 ones, was found to divide the designated number. Retuens <code>false</code>
160 * @param w the number to test.
161 * @return <code>true</code> if at least one small prime was found to divide
162 * the designated number.
164 public static boolean hasSmallPrimeDivisor(BigInteger w
)
167 for (int i
= 0; i
< SMALL_PRIME_COUNT
; i
++)
169 prime
= SMALL_PRIME
[i
];
170 if (w
.mod(prime
).equals(ZERO
))
172 if (DEBUG
&& debuglevel
> 4)
174 debug(prime
.toString(16) + " | " + w
.toString(16) + "...");
179 if (DEBUG
&& debuglevel
> 4)
181 debug(w
.toString(16) + " has no small prime divisors...");
187 * <p>Java port of Colin Plumb primality test (Euler Criterion)
188 * implementation for a base of 2 --from bnlib-1.1 release, function
189 * primeTest() in prime.c. this is his comments.</p>
191 * <p>"Now, check that bn is prime. If it passes to the base 2, it's prime
192 * beyond all reasonable doubt, and everything else is just gravy, but it
193 * gives people warm fuzzies to do it.</p>
195 * <p>This starts with verifying Euler's criterion for a base of 2. This is
196 * the fastest pseudoprimality test that I know of, saving a modular squaring
197 * over a Fermat test, as well as being stronger. 7/8 of the time, it's as
198 * strong as a strong pseudoprimality test, too. (The exception being when
199 * <code>bn == 1 mod 8</code> and <code>2</code> is a quartic residue, i.e.
200 * <code>bn</code> is of the form <code>a^2 + (8*b)^2</code>.) The precise
201 * series of tricks used here is not documented anywhere, so here's an
202 * explanation. Euler's criterion states that if <code>p</code> is prime
203 * then <code>a^((p-1)/2)</code> is congruent to <code>Jacobi(a,p)</code>,
204 * modulo <code>p</code>. <code>Jacobi(a, p)</code> is a function which is
205 * <code>+1</code> if a is a square modulo <code>p</code>, and <code>-1</code>
206 * if it is not. For <code>a = 2</code>, this is particularly simple. It's
207 * <code>+1</code> if <code>p == +/-1 (mod 8)</code>, and <code>-1</code> if
208 * <code>m == +/-3 (mod 8)</code>. If <code>p == 3 (mod 4)</code>, then all
209 * a strong test does is compute <code>2^((p-1)/2)</code>. and see if it's
210 * <code>+1</code> or <code>-1</code>. (Euler's criterion says <i>which</i>
211 * it should be.) If <code>p == 5 (mod 8)</code>, then <code>2^((p-1)/2)</code>
212 * is <code>-1</code>, so the initial step in a strong test, looking at
213 * <code>2^((p-1)/4)</code>, is wasted --you're not going to find a
214 * <code>+/-1</code> before then if it <b>is</b> prime, and it shouldn't
215 * have either of those values if it isn't. So don't bother.</p>
217 * <p>The remaining case is <code>p == 1 (mod 8)</code>. In this case, we
218 * expect <code>2^((p-1)/2) == 1 (mod p)</code>, so we expect that the
219 * square root of this, <code>2^((p-1)/4)</code>, will be <code>+/-1 (mod p)
220 * </code>. Evaluating this saves us a modular squaring 1/4 of the time. If
221 * it's <code>-1</code>, a strong pseudoprimality test would call <code>p</code>
222 * prime as well. Only if the result is <code>+1</code>, indicating that
223 * <code>2</code> is not only a quadratic residue, but a quartic one as well,
224 * does a strong pseudoprimality test verify more things than this test does.
227 * <p>We could back that down another step, looking at <code>2^((p-1)/8)</code>
228 * if there was a cheap way to determine if <code>2</code> were expected to
229 * be a quartic residue or not. Dirichlet proved that <code>2</code> is a
230 * quadratic residue iff <code>p</code> is of the form <code>a^2 + (8*b^2)</code>.
231 * All primes <code>== 1 (mod 4)</code> can be expressed as <code>a^2 +
232 * (2*b)^2</code>, but I see no cheap way to evaluate this condition."</p>
234 * @param bn the number to test.
235 * @return <code>true</code> iff the designated number passes Euler criterion
236 * as implemented by Colin Plumb in his <i>bnlib</i> version 1.1.
238 public static boolean passEulerCriterion(final BigInteger bn
)
240 BigInteger bn_minus_one
= bn
.subtract(ONE
);
241 BigInteger e
= bn_minus_one
;
242 // l is the 3 least-significant bits of e
243 int l
= e
.and(BigInteger
.valueOf(7L)).intValue();
244 int j
= 1; // Where to start in prime array for strong prime tests
251 a
= TWO
.modPow(e
, bn
);
252 if (l
== 6) // bn == 7 mod 8, expect +1
254 if (a
.bitLength() != 1)
256 debugBI("Fails Euler criterion #1", bn
);
257 return false; // Not prime
261 else // bn == 3 or 5 mod 8, expect -1 == bn-1
264 if (a
.compareTo(bn
) != 0)
266 debugBI("Fails Euler criterion #2", bn
);
267 return false; // Not prime
270 if ((l
& 4) != 0) // bn == 5 mod 8, make odd for strong tests
277 else // bn == 1 mod 8, expect 2^((bn-1)/4) == +/-1 mod bn
280 a
= TWO
.modPow(e
, bn
);
281 if (a
.bitLength() == 1)
282 j
= 0; // Re-do strong prime test to base 2
286 if (a
.compareTo(bn
) != 0)
288 debugBI("Fails Euler criterion #3", bn
);
289 return false; // Not prime
292 // bnMakeOdd(n) = d * 2^s. Replaces n with d and returns s.
293 k
= e
.getLowestSetBit();
297 // It's prime! Now go on to confirmation tests
299 // Now, e = (bn-1)/2^k is odd. k >= 1, and has a given value with
300 // probability 2^-k, so its expected value is 2. j = 1 in the usual case
301 // when the previous test was as good as a strong prime test, but 1/8 of
302 // the time, j = 0 because the strong prime test to the base 2 needs to
304 for (int i
= j
; i
< 7; i
++) // try only the first 7 primes
308 if (a
.bitLength() == 1)
309 continue; // Passed this test
315 // if (a.compareTo(w) == 0) { // Was result bn-1?
316 if (a
.compareTo(bn_minus_one
) == 0) // Was result bn-1?
319 if (--l
== 0) // Reached end, not -1? luck?
321 debugBI("Fails Euler criterion #4", bn
);
322 return false; // Failed, not prime
324 // This portion is executed, on average, once
325 // a = a.subtract(ONE); // Put a back where it was
326 a
= a
.modPow(TWO
, bn
);
327 if (a
.bitLength() == 1)
329 debugBI("Fails Euler criterion #5", bn
);
330 return false; // Failed, not prime
333 // It worked (to the base primes[i])
335 debugBI("Passes Euler criterion", bn
);
339 public static boolean isProbablePrime(BigInteger w
)
341 return isProbablePrime(w
, DEFAULT_CERTAINTY
);
345 * Wrapper around {@link BigInteger#isProbablePrime(int)} with few pre-checks.
347 * @param w the integer to test.
348 * @param certainty the certainty with which to compute the test.
350 public static boolean isProbablePrime(BigInteger w
, int certainty
)
352 // Nonnumbers are not prime.
356 // eliminate trivial cases when w == 0 or 1
357 if (w
.equals(ZERO
) || w
.equals(ONE
))
360 // Test if w is a known small prime.
361 for (int i
= 0; i
< SMALL_PRIME_COUNT
; i
++)
362 if (w
.equals(SMALL_PRIME
[i
]))
364 if (DEBUG
&& debuglevel
> 4)
365 debug(w
.toString(16) + " is a small prime");
369 // Check if it's already a known prime
370 WeakReference obj
= (WeakReference
) knownPrimes
.get(w
);
371 if (obj
!= null && w
.equals(obj
.get()))
373 if (DEBUG
&& debuglevel
> 4)
374 debug("found in known primes");
378 // trial division with first 1000 primes
379 if (hasSmallPrimeDivisor(w
))
381 if (DEBUG
&& debuglevel
> 4)
382 debug(w
.toString(16) + " has a small prime divisor. Rejected...");
386 // Euler's criterion.
387 // if (passEulerCriterion(w)) {
388 // if (DEBUG && debuglevel > 4) {
389 // debug(w.toString(16)+" passes Euler's criterion...");
392 // if (DEBUG && debuglevel > 4) {
393 // debug(w.toString(16)+" fails Euler's criterion. Rejected...");
398 // if (DEBUG && debuglevel > 4)
400 // debug(w.toString(16) + " is probable prime. Accepted...");
403 boolean result
= w
.isProbablePrime(certainty
);
404 if (result
&& certainty
> 0) // store it in the known primes weak hash-map
405 knownPrimes
.put(w
, new WeakReference(w
));
410 // helper methods -----------------------------------------------------------
412 private static final void debugBI(String msg
, BigInteger bn
)
414 if (DEBUG
&& debuglevel
> 4)
415 debug("*** " + msg
+ ": 0x" + bn
.toString(16));