Prime (cryptix JavaDoc)

java.lang.Object
- cryptix.util.math.Prime

```
public final class Prime
extends java.lang.Object
```
A utility class to handle different algorithms for large prime number generation, factorisation and tests.
References:
1. [HAC] A. J. Menezes, P. C. van Oorschot, S. A. Vanstone, Handbook of Applied Cryptography CRC Press 1997, pp 145-154.
2. Bruce Schneier, "Section 19.6 ElGamal," and "Section 11.3 Number Theory" (heading "Generators," pages 253-254), Applied Cryptography, 2nd edition, John Wiley & Sons, 1996
3. S. C. Pohlig and M. E. Hellman, "An Improved Algorithm for Computing Logarithms in GF(p) and Its Cryptographic Significance," IEEE Transactions on Information Theory, v. 24 n. 1, Jan 1978, pages 106-111.
4. IEEE P1363 draft standard, http://stdsbbs.ieee.org/groups/1363/index.html
Copyright © 1997 Systemics Ltd on behalf of the Cryptix Development Team.
All rights reserved.
$Revision: 1.4 $
Author:

Raif S. Naffah, David Hopwood

Field Summary

Fields
Modifier and Type Field and Description

static int GERMAIN

static int PLAIN

static int STRONG

Fields
Modifier and Type	Field and Description
`static int`	`GERMAIN`
`static int`	`PLAIN`
`static int`	`STRONG`

Method Summary

All Methods Static Methods Concrete Methods
Modifier and Type	Method and Description
`static java.lang.Object[]`	`getElGamal(int bitlength, int certainty, java.util.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 java.math.BigInteger`	`getGermain(int bitlength, int certainty, java.util.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 java.math.BigInteger[]`	`getGordon(int bitlength, int certainty, java.util.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 java.math.BigInteger[]`	`getSmallFactors(java.math.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 java.math.BigInteger[]`	`getSmallFactors(java.math.BigInteger r, int certainty, java.math.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(java.math.BigInteger g, java.math.BigInteger p, java.math.BigInteger[] z)`
`static boolean`	`isGermain(java.math.BigInteger p, int certainty)`
`static boolean`	`isProbablePrimeFast(java.math.BigInteger r, int certainty)` Implements a faster (on average) primality check than `BigInteger.isProbablePrime(r, certainty)`.

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- Field Detail
  - PLAIN
```
public static final int PLAIN
```
    See Also:
    
    Constant Field Values
  - STRONG
```
public static final int STRONG
```
    See Also:
    
    Constant Field Values
  - GERMAIN
```
public static final int GERMAIN
```
    See Also:
    
    Constant Field Values
- Method Detail
  - getGordon
```
public static java.math.BigInteger[] getGordon(int bitlength,
                                               int certainty,
                                               java.util.Random random)
```
    Returns a Gordon strong probable-prime with an approximate specified bitlength, that is prime with a probability exceeding 1 - (1/2)^certainty.
    A prime is said to be strong iff integers r, s, and t exist such that the following three conditions are satisfied:
    1. p - 1 has a large prime factor, denoted r,
    2. p + 1 has a large prime factor, denoted s, and
    3. r - 1 has a large prime factor, denoted t.
    GORDON's algorithm is described in [HAC] p.150 as follows:
    1. generate 2 random primes s and t of roughly equal bit-length.
    2. select an integer i0. Find the first prime in the sequence 2it + 1, for i = i0, i0+1, i0+2,... Denote this prime by r = 2it + 1.
    3. compute p0 = 2(s^(r-2) mod r)s - 1 --See errata on [HAC] web site.
    4. select an integer j0. Find the first prime in the sequence p0 + 2jrs, for j = j0, j0 + 1, j0 + 2, ... Denote this prime by p = p0 + 2jrs.
    5. return p.
    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.
  - getGermain
```
public static java.math.BigInteger getGermain(int bitlength,
                                              int certainty,
                                              java.util.Random random)
```
    Returns a Germain (Sophie) probable-prime with an approximate specified bitlength, that is prime with a probability exceeding 1 - (1/2)^certainty.
    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.
  - getElGamal
```
public static java.lang.Object[] getElGamal(int bitlength,
                                            int certainty,
                                            java.util.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.
    
    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).
  - getSmallFactors
```
public static java.math.BigInteger[] getSmallFactors(java.math.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.
    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.
  - getSmallFactors
```
public static java.math.BigInteger[] getSmallFactors(java.math.BigInteger r,
                                                     int certainty,
                                                     java.math.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.
    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.
  - isGermain
```
public static boolean isGermain(java.math.BigInteger p,
                                int certainty)
```
    Returns:
    
    true iff p is a probable prime and (p-1)/2 is also a probable prime.
  - isGeneratorModP
```
public static boolean isGeneratorModP(java.math.BigInteger g,
                                      java.math.BigInteger p,
                                      java.math.BigInteger[] z)
```
    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.
  - isProbablePrimeFast
```
public static boolean isProbablePrimeFast(java.math.BigInteger r,
                                          int certainty)
```
    Implements a faster (on average) primality check than BigInteger.isProbablePrime(r, certainty).

Class Prime

Field Summary

Method Summary

Methods inherited from class java.lang.Object

Field Detail

PLAIN

STRONG

GERMAIN

Method Detail

getGordon

getGermain

getElGamal

getSmallFactors

getSmallFactors

isGermain

isGeneratorModP

isProbablePrimeFast