iaik.utils
Class NumberTheory

java.lang.Object
  |
  +--iaik.utils.NumberTheory

public final class NumberTheory

extends java.lang.Object

Some useful number theoretic utility methods.

Field Summary

static java.math.BigInteger	ONE BigInteger constant 1
static java.math.BigInteger	TWO BigInteger constant 2
static java.math.BigInteger	ZERO BigInteger constant 0

Method Summary

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) Perform the Miller-Rabin probabilistic primality test to determine if b 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

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 fixed at 2^-80 for this implementation. This bound is a reasonable choice for most cryptographic operations.

This method can be used as drop-in replacement for the BigInteger.isProbablePrime() method offering much better performance. This is achieved by first filtering out number divisable by small primes and then using the Miller-Rabin test with tighter bounds.

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)

Perform the Miller-Rabin 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 fixed at 2^-80 for this implementation. This bound is a reasonable choice for most cryptographic operations.

This is basically the same algorithm as BigInteger.isProbablePrime() but uses tighter bounds for 2^-80 based on the length of the number to achieve significantly better average performance.

As implemented here the algorithm was adapted from the Handbook of Applied Cryptography by Menezes, van Oorscho, and Vanstone. This method should only be used to test large positive numbers.

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. Trial division using the 2048 smallest primes is performed.