iaik.utils

Class NumberTheory

java.lang.Object

iaik.utils.NumberTheory

public final class NumberTheory
extends java.lang.Object

Some useful number theoretic utility methods.

Version:

File Revision 23

Field Summary

Fields

Modifier and Type	Field and Description
static java.math.BigInteger	ONE BigInteger constant 1
static int	SMALLEST_PRIME_SIZE
static java.math.BigInteger	TWO BigInteger constant 2
static java.math.BigInteger	ZERO BigInteger constant 0

Method Summary

Methods

Modifier and Type	Method and Description
static int[]	extGcd(int a, int b) Extended Euclidean algorithm for computing the greatest common divisor of two integers.
static int	gcd(int a, int b) Euclidean algorithm for computing the greatest common divisor of two integers.
static java.math.BigInteger	getStrongPrime(int x, java.util.Random random) Returns a random strong prime.
static boolean	hasSmallFactors(java.math.BigInteger b) Test the given BigInteger b for small prime factors.
static boolean	isProbablePrime(java.math.BigInteger b) Perform a probabilistic primality test to determine if b is prime.
static boolean	millerRabin(java.math.BigInteger n) Performs the Miller-Rabin probabilistic primality test to determine if n is prime.
static java.math.BigInteger	nextPrime(java.math.BigInteger b) Return the smallest prime greater than or equal to b.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

SMALLEST_PRIME_SIZE

public static final int SMALLEST_PRIME_SIZE

See Also:

Constant Field Values

ZERO

public static final java.math.BigInteger ZERO

BigInteger constant 0

ONE

public static final java.math.BigInteger ONE

BigInteger constant 1

TWO

public static final java.math.BigInteger TWO

BigInteger constant 2

Method Detail

gcd

public static int gcd(int a,
      int b)

Euclidean algorithm for computing the greatest common divisor of two integers.

extGcd

public static int[] extGcd(int a,
           int b)

Extended Euclidean algorithm for computing the greatest common divisor of two integers.

Returns:

{d,x,y} satisfying ax + by = d

nextPrime

public static java.math.BigInteger nextPrime(java.math.BigInteger b)

Return the smallest prime greater than or equal to b.

getStrongPrime

public static java.math.BigInteger getStrongPrime(int x,
                                  java.util.Random random)

Returns a random strong prime.

This method implements an algorithm published in RSA LABORATORIES' CryptoBytes, Volume 3, Number 1 - Spring 1997, page 9.

Parameters:

x - the strength of the prime number

random - the random number generator to use

Returns:

the new generated random strong prime

isProbablePrime

public static boolean isProbablePrime(java.math.BigInteger b)

Perform a probabilistic primality test to determine if b is prime. This method returns true if b is probable prime and false if it is definitely composite. The probability of returning true if b is composite is fiexd to 2^-80 for this implementation.

This method only works for positive numbers.

See Also:

hasSmallFactors(java.math.BigInteger), millerRabin(java.math.BigInteger)

millerRabin

public static boolean millerRabin(java.math.BigInteger n)

Performs the Miller-Rabin probabilistic primality test to determine if n is prime. Implementation according to IEEE Specification 1363 with error probability less than 2^-100.

This method returns true if n is probable prime and false if it is definitely composite. The probability of returning true if n is composite is less than 2^-100 for this implementation.

Parameters:

n - the integer to be tested (bit length must be >= 160)

Returns:

true if n is probable prime and false if it is definitely composite.

Throws:

java.lang.IllegalArgumentException - if the bit length of the number to be tested is shorter than 160 bits

hasSmallFactors

public static boolean hasSmallFactors(java.math.BigInteger b)

Test the given BigInteger b for small prime factors. In other words, if this method returns true, the number is composite, if it returns false, it may be a prime. This method should not be used directly, use isProbablePrime() instead. Also note that it may not work for very small numbers.