cryptix.util.math
public final class Prime extends Object
References:
Copyright © 1997
Systemics Ltd on behalf of the
Cryptix Development Team.
All rights reserved.
$Revision: 1.4 $
Field Summary | |
---|---|
static int | GERMAIN |
static int | PLAIN |
static int | STRONG |
Method Summary | |
---|---|
static Object[] | getElGamal(int bitlength, int certainty, Random random, int prime_type)
Generates a random probable-prime, p, of the given length, such that all
the factors of p - 1 are known.
|
static BigInteger | getGermain(int bitlength, int certainty, Random random)
Returns a Germain (Sophie) probable-prime with an approximate
specified bitlength, that is prime with a probability exceeding
1 - (1/2)certainty.
|
static BigInteger[] | getGordon(int bitlength, int certainty, Random random)
Returns a Gordon strong probable-prime with an approximate
specified bitlength, that is prime with a probability exceeding
1 - (1/2)certainty.
|
static BigInteger[] | getSmallFactors(BigInteger r, int certainty)
Returns a BigInteger array whose elements are the prime factors of a
designated BigInteger value, or null if the value could not easily be
factorised.
|
static BigInteger[] | getSmallFactors(BigInteger r, int certainty, BigInteger q)
Return a BigInteger array whose elements are the prime factors of a
designated BigInteger value, for which we already have one large prime
factor.
|
static boolean | isGeneratorModP(BigInteger g, BigInteger p, BigInteger[] z) |
static boolean | isGermain(BigInteger p, int certainty) |
static boolean | isProbablePrimeFast(BigInteger r, int certainty)
Implements a faster (on average) primality check than
BigInteger.isProbablePrime(r, certainty) . |
Parameters: bitlength An approximate number of bits that the returned prime integer must have. certainty A measure of the probability that the returned integer p, and the largest factor of p - 1 are primes. The Miller-Rabin test used ensures that these values are prime with a probability that exceeds 1 - (1/2)certainty. random A source of randomness for the bits to use in building the prime. prime_type what type of prime to build: PLAIN, STRONG or GERMAIN.
Returns: An array of two Objects: the first being the found prime itself, say p, and the second Object is an array of the known distinct prime factors of the value (p - 1).
An integer p is a GERMAIN prime iff it is a prime, and p = 2q + 1 where q is also a prime.
Parameters: bitlength An approximate number of bits that the returned prime integer must have. certainty A measure of the probability that the returned integer is a prime. The Miller-Rabin test used ensures that the returned value is a prime with a probability that exceeds 1 - (1/2)certainty. random A source of randomness for the bits to use in building the prime.
Returns: A Germain prime: a prime of the form 2q + 1 where q is also a prime.
A prime is said to be strong iff integers r, s, and t exist such that the following three conditions are satisfied:
GORDON's algorithm is described in [HAC] p.150 as follows:
Parameters: bitlength An approximate number of bits that the returned prime integer must have. certainty A measure of the probability that the returned integer is a prime. The Miller-Rabin test used ensures that the returned value is a prime with a probability that exceeds 1 - (1/2)certainty. random A source of randomness for the bits to use in building the prime.
Returns: An array whose elements are respectively p, r, s and t.
Parameters: r A BigInteger to factor. certainty A measure of the probability that the largest returned factor is a prime. The Miller-Rabin test used ensures that this factor is a prime with a probability that exceeds 1 - (1/2)certainty.
Returns: A BigInteger array whose elements are the distinct prime
factors of p when the latter can be written as:
S_1 * S_2 * ... * S_n * L
Where S_i are small prime factors found in SMALL_PRIMES and L is a
large prime factor. Return null otherwise.
The returned array conatins all the distinct factors including the one we gave on input. The returned array is not guaranteed to be in any specific order.
Parameters: r A BigInteger to factor. certainty A measure of the probability that the returned integers are primes. The Miller-Rabin test used ensures that each array element is a prime with a probability that exceeds 1 - (1/2)certainty. q A known prime factor of r.
Returns: If all the prime factors, except two (one of which is q), can be found in the list of pre-computed small primes the method returns an array whose elements are the distinct prime factors of r. On the other hand if not all the prime factors, except two, can be found in the list of pre-computed small primes the method returns null.
Returns: true iff g is a generator mod p. z is an array containing (p-1)/q, for each unique prime factor q of p-1.
Returns: true iff p is a probable prime and (p-1)/2 is also a probable prime.
BigInteger.isProbablePrime(r, certainty)
.