Class Math

java.lang.Object
  |
  +--Math

public class Math

extends java.lang.Object

An implementation for operations on large integers.

Author:

E.Lemonnier & E.Nordenstam

Constructor Summary

Math()

Method Summary

static java.math.BigInteger	gcd(java.math.BigInteger a, java.math.BigInteger b) Compute the greatest common divisor (gcd) of two integers.
static boolean	isProbablePrime(java.math.BigInteger n, int certainty) Check if an integer is prime.
static java.math.BigInteger	makePrime(int bitLength, int certainty) Create a large prime integer.
static java.math.BigInteger	mod4Pow(java.math.BigInteger a, java.math.BigInteger e, java.math.BigInteger n) Same as modPow.
static java.math.BigInteger	modInverse(java.math.BigInteger a, java.math.BigInteger n) Compute the inverse of an integer a modulo n.
static java.math.BigInteger	modPow(java.math.BigInteger a, java.math.BigInteger e, java.math.BigInteger n) Compute a power e modulo n.
static java.math.BigInteger	polFactors(java.math.BigInteger n) Factorises a large integer.

Methods inherited from class java.lang.Object

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

Constructor Detail

Math

public Math()

Method Detail

gcd

public static java.math.BigInteger gcd(java.math.BigInteger a,
                                       java.math.BigInteger b)

Compute the greatest common divisor (gcd) of two integers. It uses the Euclidean algorithm.

Parameters:

a - large integer.

b - large integer.

Returns:

the gcd of a and b.

modInverse

public static java.math.BigInteger modInverse(java.math.BigInteger a,
                                              java.math.BigInteger n)
                                       throws java.lang.ArithmeticException

Compute the inverse of an integer a modulo n. It is assumed that a and n are relative primes, ie gcd(a,n)=1, otherwise an ArithmeticExpression is thrown. Uses the extended Euclidean algorithm.

Parameters:

a - integer to inverse.

n - modulo.

Returns:

the inverse of a modulo n.

modPow

public static java.math.BigInteger modPow(java.math.BigInteger a,
                                          java.math.BigInteger e,
                                          java.math.BigInteger n)

Compute a power e modulo n.

Parameters:

a - integer to exponentiate.

e - exponent.

n - modulo.

Returns:

a^e mod p.

mod4Pow

public static java.math.BigInteger mod4Pow(java.math.BigInteger a,
                                           java.math.BigInteger e,
                                           java.math.BigInteger n)

Same as modPow. In theory, it should be faster than modPow for large numbers, but somehow, java makes it slower...

Parameters:

a - integer to exponentiate.

e - exponent.

n - modulo.

Returns:

a^e mod p.

polFactors

public static java.math.BigInteger polFactors(java.math.BigInteger n)

Factorises a large integer. Uses Pollard's Rho algorithm.

Parameters:

n - an integer to factorise.

Returns:

a factor of this integer. It can be a composite number or the integer itself.

makePrime

public static java.math.BigInteger makePrime(int bitLength,
                                             int certainty)

Create a large prime integer. This integer has a length of bitLength bits, and its first and last bits are set to 1. isProbablePrime is used to check whether the generated integer is prime. The generated integer has a probability of being prime equal to: 1-1/2^certainty.

Parameters:

bitLength - the number of bits in the integer.

certainty - degree of probability of the integer of being prime.

Returns:

a prime integer.

isProbablePrime

public static boolean isProbablePrime(java.math.BigInteger n,
                                      int certainty)

Check if an integer is prime. It first test whether the integer is 1 or even. Then it uses an array of all the primes between 3 and 100, and check whether the integer is equal to or multiple of one of them. Finally, it uses the Miller-Rabin probabilistic algorithm to check if the integer is prime. The probability of the integer of being prime is then 1-1/2^certainty.

Parameters:

n - the integer to check.

certainty - degree of probability of the integer of being prime.

Returns:

true if it is prime, false otherwise.