de.flexiprovider.common.math
Class IntegerFunctions

java.lang.Object
  |
  +--de.flexiprovider.common.math.IntegerFunctions

public final class IntegerFunctions

extends java.lang.Object

Class of number-theory related functions for use with integers represented as int's or FlexiBigInt objects.

Author:

Ralf-P. Weinmann, Martin Döring

Method Summary

static FlexiBigInt	binomial(int n, int t) Computes the binomial coefficient (n|t) ("n over t").
static int	bitCount(int a)
static int	ceilLog(FlexiBigInt a) Compute the smallest integer that is greater than or equal to the logarithm to the base 2 of the given FlexiBigInt.
static int	ceilLog(int a) Compute the smallest integer that is greater than or equal to the logarithm to the base 2 of the given integer.
static int	ceilLog256(int n) Compute ceil(log_256 n), the number of bytes needed to encode the integer n.
static int	ceilLog256(long n) Compute ceil(log_256 n), the number of bytes needed to encode the long integer n.
static FlexiBigInt[]	divideAndRound(FlexiBigInt[] a, FlexiBigInt b)
static FlexiBigInt	divideAndRound(FlexiBigInt a, FlexiBigInt b)
static FlexiBigInt[]	extgcd(FlexiBigInt a, FlexiBigInt b) Extended euclidian algorithm (computes gcd and representation).
static int[]	extGCD(int a, int b) Extended euclidian algorithm (computes gcd and representation).
static float	floatLog(float param) Calculation of a logarithmus of a float param
static float	floatPow(float f, int i) int power of a base float, only use for small ints
static int	floorLog(FlexiBigInt a) Compute the integer part of the logarithm to the base 2 of the given integer.
static int	floorLog(int a) Compute the integer part of the logarithm to the base 2 of the given integer.
static int	gcd(int u, int v) Computes the greatest common divisor of the two specified integers
static byte[]	integerToOctets(FlexiBigInt val)
static float	intRoot(int base, int root) Takes an approximation of the root from an integer base, using newton's algorithm
static boolean	isIncreasing(int[] a)
static int	isPower(int a, int p) Tests whether an integer a is power of another integer p.
static boolean	isPrime(int n) Miller-Rabin-Test, determines wether the given integer is probably prime or composite.
static int	jacobi(FlexiBigInt A, FlexiBigInt B) Computes the value of the Jacobi symbol (A|B).
static FlexiBigInt	leastCommonMultiple(FlexiBigInt[] numbers) Computation of the least common multiple of a set of FlexiBigInts.
static int	leastDiv(int a) Find and return the least non-trivial divisor of an integer a.
static double	log(double x) Deprecated. use MathFunctions.log(double) instead
static double	log(long x) Deprecated. use MathFunctions.log(long) instead
static void	main(java.lang.String[] args)
static int	maxPower(int a) Compute the largest h with 2^h | a if a!=0.
static long	mod(long a, long m) Returns a long integer whose value is (a mod m).
static int	modInverse(int a, int mod) Computes the modular inverse of an integer a
static long	modInverse(long a, long mod) Computes the modular inverse of an integer a
static int	modPow(int a, int e, int n) Compute ae mod n.
static FlexiBigInt	nextPrime(long n) Computes the next prime greater than n.
static FlexiBigInt	nextProbablePrime(FlexiBigInt n) Compute the next probable prime greater than n with the default certainty (20).
static FlexiBigInt	nextProbablePrime(FlexiBigInt n, int certainty) Compute the next probable prime greater than n with the specified certainty.
static int	nextSmallerPrime(int n) Returns the largest prime smaller than the given integer
static FlexiBigInt	octetsToInteger(byte[] data)
static FlexiBigInt	octetsToInteger(byte[] data, int offset, int length)
static int	order(int g, int p) determines the order of g modulo p, p prime and 1 < g < p.
static boolean	passesSmallPrimeTest(FlexiBigInt candidate) Short trial-division test to find out whether a number is not prime.
static int	pow(int a, int e) Compute ae.
static long	pow(long a, int e) Compute ae.
static FlexiBigInt	randomize(FlexiBigInt upperBound)
static FlexiBigInt	randomize(FlexiBigInt upperBound, SecureRandom prng)
static FlexiBigInt	reduceInto(FlexiBigInt n, FlexiBigInt begin, FlexiBigInt end) Reduces an integer into a given interval
static FlexiBigInt	ressol(FlexiBigInt a, FlexiBigInt p) Computes the square root of a FlexiBigInt modulo a prime employing the Shanks-Tonelli algorithm.
static FlexiBigInt	squareRoot(FlexiBigInt a) Extract the truncated square root of a FlexiBigInt.

Methods inherited from class java.lang.Object

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

Method Detail

jacobi

public static int jacobi(FlexiBigInt A,
                         FlexiBigInt B)

Computes the value of the Jacobi symbol (A|B). The following properties hold for the Jacobi symbol which makes it a very efficient way to evaluate the Legendre symbol

(A|B) = 0 IF gcd(A,B) > 1
(-1|B) = 1 IF n = 1 (mod 1)
(-1|B) = -1 IF n = 3 (mod 4)
(A|B) (C|B) = (AC|B)
(A|B) (A|C) = (A|CB)
(A|B) = (C|B) IF A = C (mod B)
(2|B) = 1 IF N = 1 OR 7 (mod 8)
(2|B) = 1 IF N = 3 OR 5 (mod 8)

Parameters:

A - integer value

B - integer value

Returns:

value of the jacobi symbol (A|B)

ressol

public static FlexiBigInt ressol(FlexiBigInt a,
                                 FlexiBigInt p)
                          throws NoQuadraticResidueException

Computes the square root of a FlexiBigInt modulo a prime employing the Shanks-Tonelli algorithm.

Parameters:

a - value out of which we extract the square root

p - prime modulus that determines the underlying field

Returns:

a number b such that b² = a (mod p) if a is a quadratic residue modulo p.

Throws:

NoQuadraticResidueException - if a is a quadratic non-residue modulo p

gcd

public static int gcd(int u,
                      int v)

Computes the greatest common divisor of the two specified integers

Parameters:

u - - first integer

v - - second integer

Returns:

gcd(a, b)

extGCD

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

Extended euclidian algorithm (computes gcd and representation).

Parameters:

a - the first integer

b - the second integer

Returns:

(g,u,v), where g = gcd(abs(a),abs(b)) = ua + vb

divideAndRound

public static FlexiBigInt divideAndRound(FlexiBigInt a,
                                         FlexiBigInt b)

divideAndRound

public static FlexiBigInt[] divideAndRound(FlexiBigInt[] a,
                                           FlexiBigInt b)

ceilLog

public static int ceilLog(FlexiBigInt a)

Compute the smallest integer that is greater than or equal to the logarithm to the base 2 of the given FlexiBigInt.

Parameters:

a - the integer

Returns:

ceil[log(a)]

ceilLog

public static int ceilLog(int a)

Compute the smallest integer that is greater than or equal to the logarithm to the base 2 of the given integer.

Parameters:

a - the integer

Returns:

ceil[log(a)]

ceilLog256

public static int ceilLog256(int n)

Compute ceil(log_256 n), the number of bytes needed to encode the integer n.

Parameters:

n - the integer

Returns:

the number of bytes needed to encode n

ceilLog256

public static int ceilLog256(long n)

Compute ceil(log_256 n), the number of bytes needed to encode the long integer n.

Parameters:

n - the long integer

Returns:

the number of bytes needed to encode n

floorLog

public static int floorLog(FlexiBigInt a)

Compute the integer part of the logarithm to the base 2 of the given integer.

Parameters:

a - the integer

Returns:

floor[log(a)]

floorLog

public static int floorLog(int a)

Compute the integer part of the logarithm to the base 2 of the given integer.

Parameters:

a - the integer

Returns:

floor[log(a)]

maxPower

public static int maxPower(int a)

Compute the largest h with 2^h | a if a!=0.

Parameters:

a - an integer

Returns:

the largest h with 2^h | a if a!=0, 0 otherwise

bitCount

public static int bitCount(int a)

Parameters:

a - an integer

Returns:

the number of ones in the binary representation of an integer a

order

public static int order(int g,
                        int p)

determines the order of g modulo p, p prime and 1 < g < p. This algorithm is only efficient for small p (see X9.62-1998, p. 68).

Parameters:

g - an integer with 1 < g < p

p - a prime

Returns:

the order k of g (that is k is the smallest integer with g^k = 1 mod p

reduceInto

public static FlexiBigInt reduceInto(FlexiBigInt n,
                                     FlexiBigInt begin,
                                     FlexiBigInt end)

Reduces an integer into a given interval

Parameters:

n - - the integer

begin - - left bound of the interval

end - - right bound of the interval

Returns:

n reduced into [begin,end]

pow

public static int pow(int a,
                      int e)

Compute a^e.

Parameters:

a - the base

e - the exponent

Returns:

a^e

pow

public static long pow(long a,
                       int e)

Compute a^e.

Parameters:

a - the base

e - the exponent

Returns:

a^e

modPow

public static int modPow(int a,
                         int e,
                         int n)

Compute a^e mod n.

Parameters:

a - the base

e - the exponent

n - the modulus

Returns:

a^e mod n

extgcd

public static FlexiBigInt[] extgcd(FlexiBigInt a,
                                   FlexiBigInt b)

Extended euclidian algorithm (computes gcd and representation).

Parameters:

a - - the first integer

b - - the second integer

Returns:

(d,u,v), where d = gcd(a,b) = ua + vb

leastCommonMultiple

public static FlexiBigInt leastCommonMultiple(FlexiBigInt[] numbers)

Computation of the least common multiple of a set of FlexiBigInts.

Parameters:

numbers - - the set of numbers

Returns:

the lcm(numbers)

mod

public static long mod(long a,
                       long m)

Returns a long integer whose value is (a mod m). This method differs from % in that it always returns a non-negative integer.

Parameters:

a - value on which the modulo operation has to be performed.

m - the modulus.

Returns:

a mod m

modInverse

public static int modInverse(int a,
                             int mod)

Computes the modular inverse of an integer a

Parameters:

a - - the integer to invert

mod - - the modulus

Returns:

a^-1 mod n

modInverse

public static long modInverse(long a,
                              long mod)

Computes the modular inverse of an integer a

Parameters:

a - - the integer to invert

mod - - the modulus

Returns:

a^-1 mod n

isPower

public static int isPower(int a,
                          int p)

Tests whether an integer a is power of another integer p.

Parameters:

a - - the first integer

p - - the second integer

Returns:

n if a = p^n or -1 otherwise

leastDiv

public static int leastDiv(int a)

Find and return the least non-trivial divisor of an integer a.

Parameters:

a - - the integer

Returns:

divisor p >1 or 1 if a = -1,0,1

isPrime

public static boolean isPrime(int n)

Miller-Rabin-Test, determines wether the given integer is probably prime or composite. This method returns true if the given integer is prime with probability 1 - 2^-20.

Parameters:

n - the integer to test for primality

Returns:

true if the given integer is prime with probability 2^-100, false otherwise

passesSmallPrimeTest

public static boolean passesSmallPrimeTest(FlexiBigInt candidate)

Short trial-division test to find out whether a number is not prime. This test is usually used before a Miller-Rabin primality test.

Parameters:

candidate - the number to test

Returns:

true if the number has no factor of the tested primes, false if the number is definitely composite

nextSmallerPrime

public static int nextSmallerPrime(int n)

Returns the largest prime smaller than the given integer

Parameters:

n - - upper bound

Returns:

the largest prime smaller than n, or 1 if n <= 2

nextProbablePrime

public static FlexiBigInt nextProbablePrime(FlexiBigInt n,
                                            int certainty)

Compute the next probable prime greater than n with the specified certainty.

Parameters:

n - a integer number

certainty - the certainty that the generated number is prime

Returns:

the next prime greater than n

nextProbablePrime

public static FlexiBigInt nextProbablePrime(FlexiBigInt n)

Compute the next probable prime greater than n with the default certainty (20).

Parameters:

n - a integer number

Returns:

the next prime greater than n

nextPrime

public static FlexiBigInt nextPrime(long n)

Computes the next prime greater than n.

Parameters:

n - a integer number

Returns:

the next prime greater than n

binomial

public static FlexiBigInt binomial(int n,
                                   int t)

Computes the binomial coefficient (n|t) ("n over t"). Formula:

• if n !=0 and t != 0 then (n|t) = Mult(i=1, t): (n-(i-1))/i
• if t = 0 then (n|t) = 1
• if n = 0 and t > 0 then (n|t) = 0

Parameters:

n - - the "upper" integer

t - - the "lower" integer

Returns:

the binomialcoefficient "n over t" as FlexiBigInt

randomize

public static FlexiBigInt randomize(FlexiBigInt upperBound)

randomize

public static FlexiBigInt randomize(FlexiBigInt upperBound,
                                    SecureRandom prng)

squareRoot

public static FlexiBigInt squareRoot(FlexiBigInt a)

Extract the truncated square root of a FlexiBigInt.

Parameters:

a - - value out of which we extract the square root

Returns:

the truncated square root of a

intRoot

public static float intRoot(int base,
                            int root)

Takes an approximation of the root from an integer base, using newton's algorithm

Parameters:

base - the base to take the root from

root - the root, for example 2 for a square root

floatLog

public static float floatLog(float param)

Calculation of a logarithmus of a float param

Parameters:

param -

Returns:

floatPow

public static float floatPow(float f,
                             int i)

int power of a base float, only use for small ints

Parameters:

f -

i -

Returns:

log

public static double log(double x)

Deprecated. use MathFunctions.log(double) instead

calculate the logarithm to the base 2.

Parameters:

x - any double value

Returns:

log_2(x)

log

public static double log(long x)

Deprecated. use MathFunctions.log(long) instead

calculate the logarithm to the base 2.

Parameters:

x - any long value >=1

Returns:

log_2(x)

isIncreasing

public static boolean isIncreasing(int[] a)

integerToOctets

public static byte[] integerToOctets(FlexiBigInt val)

octetsToInteger

public static FlexiBigInt octetsToInteger(byte[] data,
                                          int offset,
                                          int length)

octetsToInteger

public static FlexiBigInt octetsToInteger(byte[] data)

main

public static void main(java.lang.String[] args)