org.bouncycastle.pqc.legacy.math.linearalgebra
Class IntegerFunctions

java.lang.Object
  org.bouncycastle.pqc.legacy.math.linearalgebra.IntegerFunctions

public final class IntegerFunctions

extends java.lang.Object

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

Method Summary

static java.math.BigInteger	binomial(int n, int t) Computes the binomial coefficient (n|t) ("n over t").
static int	bitCount(int a)
static int	ceilLog(java.math.BigInteger a) Compute the smallest integer that is greater than or equal to the logarithm to the base 2 of the given BigInteger.
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 java.math.BigInteger[]	divideAndRound(java.math.BigInteger[] a, java.math.BigInteger b)
static java.math.BigInteger	divideAndRound(java.math.BigInteger a, java.math.BigInteger b)
static java.math.BigInteger[]	extgcd(java.math.BigInteger a, java.math.BigInteger b) Extended euclidian algorithm (computes gcd and representation).
static int[]	extGCD(int a, int b) Extended euclidian algorithm (computes gcd and representation).
static float	floatPow(float f, int i) int power of a base float, only use for small ints
static int	floorLog(java.math.BigInteger 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(java.math.BigInteger 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(java.math.BigInteger A, java.math.BigInteger B) Computes the value of the Jacobi symbol (A|B).
static java.math.BigInteger	leastCommonMultiple(java.math.BigInteger[] numbers) Computation of the least common multiple of a set of BigIntegers.
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 int	maxPower(int a) Compute the largest h with 2^h | a if a!
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 a e mod n.
static java.math.BigInteger	nextPrime(long n) Computes the next prime greater than n.
static java.math.BigInteger	nextProbablePrime(java.math.BigInteger n) Compute the next probable prime greater than n with the default certainty (20).
static java.math.BigInteger	nextProbablePrime(java.math.BigInteger 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 java.math.BigInteger	octetsToInteger(byte[] data)
static java.math.BigInteger	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(java.math.BigInteger candidate) Short trial-division test to find out whether a number is not prime.
static int	pow(int a, int e) Compute a e.
static long	pow(long a, int e) Compute a e.
static java.math.BigInteger	randomize(java.math.BigInteger upperBound)
static java.math.BigInteger	randomize(java.math.BigInteger upperBound, java.security.SecureRandom prng)
static java.math.BigInteger	reduceInto(java.math.BigInteger n, java.math.BigInteger begin, java.math.BigInteger end) Reduces an integer into a given interval
static java.math.BigInteger	squareRoot(java.math.BigInteger a) Extract the truncated square root of a BigInteger.

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(java.math.BigInteger A,
                         java.math.BigInteger 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)

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 java.math.BigInteger divideAndRound(java.math.BigInteger a,
                                                  java.math.BigInteger b)

divideAndRound

public static java.math.BigInteger[] divideAndRound(java.math.BigInteger[] a,
                                                    java.math.BigInteger b)

ceilLog

public static int ceilLog(java.math.BigInteger a)

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

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(java.math.BigInteger 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 java.math.BigInteger reduceInto(java.math.BigInteger n,
                                              java.math.BigInteger begin,
                                              java.math.BigInteger 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 java.math.BigInteger[] extgcd(java.math.BigInteger a,
                                            java.math.BigInteger 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 java.math.BigInteger leastCommonMultiple(java.math.BigInteger[] numbers)

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

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(java.math.BigInteger 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 java.math.BigInteger nextProbablePrime(java.math.BigInteger 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 java.math.BigInteger nextProbablePrime(java.math.BigInteger 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 java.math.BigInteger 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 java.math.BigInteger 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 BigInteger

randomize

public static java.math.BigInteger randomize(java.math.BigInteger upperBound)

randomize

public static java.math.BigInteger randomize(java.math.BigInteger upperBound,
                                             java.security.SecureRandom prng)

squareRoot

public static java.math.BigInteger squareRoot(java.math.BigInteger a)

Extract the truncated square root of a BigInteger.

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

floatPow

public static float floatPow(float f,
                             int i)

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

Parameters:

f - base float

i - power to be raised to.

Returns:

int power i of f

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(java.math.BigInteger val)

octetsToInteger

public static java.math.BigInteger octetsToInteger(byte[] data,
                                                   int offset,
                                                   int length)

octetsToInteger

public static java.math.BigInteger octetsToInteger(byte[] data)