
For the latest news and information visit The GNU Crypto project 

PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 
java.lang.Object gnu.crypto.util.Prime
A collection of prime number related utilities used in this library.
Method Summary  
static boolean 
hasSmallPrimeDivisor(java.math.BigInteger w)
Trial division for the first 1000 small primes. 
static boolean 
isProbablePrime(java.math.BigInteger w)
Calls the method with same name and two arguments using the preconfigured value for DO_MILLER_RABIN . 
static boolean 
isProbablePrime(java.math.BigInteger w,
boolean doMillerRabin)
This implementation does not rely solely on the MillerRabin strong probabilistic primality test to claim the primality of the designated number. 
static boolean 
passEulerCriterion(java.math.BigInteger w)
Java port of Colin Plumb primality test (Euler Criterion) implementation for a base of 2 from bnlib1.1 release, function primeTest() in prime.c. this is his comments; (bn is our w). 
static boolean 
passFermatLittleTheorem(java.math.BigInteger w)
Checks Fermat's Little Theorem for base 2; i.e. 
static boolean 
passMillerRabin(java.math.BigInteger w)
Applies the MillerRabin strong probabilistic primality test. 
Methods inherited from class java.lang.Object 
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait 
Method Detail 
public static boolean hasSmallPrimeDivisor(java.math.BigInteger w)
Trial division for the first 1000 small primes.
Returns true
if at least one small prime, among the first
1000 ones, was found to divide the designated number. Retuens false
otherwise.
w
 the number to test.
true
if at least one small prime was found to divide
the designated number.public static boolean passEulerCriterion(java.math.BigInteger w)
Java port of Colin Plumb primality test (Euler Criterion) implementation for a base of 2 from bnlib1.1 release, function primeTest() in prime.c. this is his comments; (bn is our w).
"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 gives people warm fuzzies to do it.
This starts with verifying Euler's criterion for a base of 2. This is
the fastest pseudoprimality test that I know of, saving a modular squaring
over a Fermat test, as well as being stronger. 7/8 of the time, it's as
strong as a strong pseudoprimality test, too. (The exception being when
bn == 1 mod 8
and 2
is a quartic residue, i.e.
bn
is of the form a^2 + (8*b)^2
.) The precise
series of tricks used here is not documented anywhere, so here's an
explanation. Euler's criterion states that if p
is prime
then a^((p1)/2)
is congruent to Jacobi(a,p)
,
modulo p
. Jacobi(a, p)
is a function which is
+1
if a is a square modulo p
, and 1
if it is not. For a = 2
, this is particularly simple. It's
+1
if p == +/1 (mod 8)
, and 1
if
m == +/3 (mod 8)
. If p == 3 (mod 4)
, then all
a strong test does is compute 2^((p1)/2)
. and see if it's
+1
or 1
. (Euler's criterion says which
it should be.) If p == 5 (mod 8)
, then 2^((p1)/2)
is 1
, so the initial step in a strong test, looking at
2^((p1)/4)
, is wasted you're not going to find a
+/1
before then if it is prime, and it shouldn't
have either of those values if it isn't. So don't bother.
The remaining case is p == 1 (mod 8)
. In this case, we
expect 2^((p1)/2) == 1 (mod p)
, so we expect that the
square root of this, 2^((p1)/4)
, will be +/1 (mod p)
. Evaluating this saves us a modular squaring 1/4 of the time. If
it's 1
, a strong pseudoprimality test would call p
prime as well. Only if the result is +1
, indicating that
2
is not only a quadratic residue, but a quartic one as well,
does a strong pseudoprimality test verify more things than this test does.
Good enough.
We could back that down another step, looking at 2^((p1)/8)
if there was a cheap way to determine if 2
were expected to
be a quartic residue or not. Dirichlet proved that 2
is a
quadratic residue iff p
is of the form a^2 + (8*b^2)
.
All primes == 1 (mod 4)
can be expressed as a^2 +
(2*b)^2
, but I see no cheap way to evaluate this condition."
w
 the number to test.
true
iff the designated number passes Euler criterion
as implemented by Colin Plumb in his bnlib version 1.1.public static boolean passFermatLittleTheorem(java.math.BigInteger w)
Checks Fermat's Little Theorem for base 2; i.e. 2**(w1) == 1
(mod w)
.
w
 the number to test.
true
iff 2**(w1) == 1 (mod w)
.public static boolean passMillerRabin(java.math.BigInteger w)
Applies the MillerRabin strong probabilistic primality test.
The HAC (Handbook of Applied Cryptography), Alfred Menezes & al. Note
4.57 states that for q
, n=18
is enough while
for p
, n=6
(512 bits) or n=3 (1024
bits) are enough to yield robust primality tests. The values used
are from table 4.4 given in Note 4.49.
 Parameters:
w
 the number to test.
 Returns:
true
iff the designated number passes the Miller
Rabin probabilistic primality test for a computed number of rounds.
isProbablePrime
public static boolean isProbablePrime(java.math.BigInteger w)
Calls the method with same name and two arguments using the
preconfigured value for DO_MILLER_RABIN
.
 Parameters:
w
 the integer to test.
 Returns:
true
iff the designated number has no small prime
divisor passes the Euler criterion, and optionally a MillerRabin test.
isProbablePrime
public static boolean isProbablePrime(java.math.BigInteger w,
boolean doMillerRabin)
This implementation does not rely solely on the MillerRabin 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, with the option passed as one of
its arguments to follow with the MillerRabin test.
 Parameters:
w
 the integer to test.doMillerRabin
 if true
and the designated integer was
already found to be a probable prime, then also do a MillerRabin test.
 Returns:
true
iff the designated number has no small prime
divisor passes the Euler criterion, and optionally a MillerRabin test.
Overview
Package
Class
Use
Tree
Deprecated
Index
Help
For the latest news and information visit
The GNU Crypto
project
PREV CLASS
NEXT CLASS
FRAMES
NO FRAMES
SUMMARY: NESTED  FIELD  CONSTR  METHOD
DETAIL: FIELD  CONSTR  METHOD
Copyright © 2001, 2002, 2003
Free Software Foundation,
Inc. All Rights Reserved.