Top Description Fields Constructors Methods
org.bouncycastle.pqc.legacy.math.linearalgebra

public final Class IntegerFunctions

extends Object
Class Inheritance
Imports
java.math.BigInteger, java.security.SecureRandom, org.bouncycastle.crypto.CryptoServicesRegistrar, org.bouncycastle.util.BigIntegers
Class of number-theory related functions for use with integers represented as int's or BigInteger objects.

Field Summary

Modifier and TypeField and Description
private static final BigInteger
FOUR

private static final int[]
jacobiTable

private static final BigInteger
ONE

private static final long
SMALL_PRIME_PRODUCT

private static final int[]
SMALL_PRIMES

private static SecureRandom
sr

private static final BigInteger
TWO

private static final BigInteger
ZERO

Constructor Summary

AccessConstructor and Description
private
IntegerFunctions()

Method Summary

Modifier and TypeMethod and Description
public static BigInteger

Returns:

the binomialcoefficient "n over t" as BigInteger
binomial(int
- the "upper" integer
n, int
- the "lower" integer
t)

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

public static int

Returns:

the number of ones in the binary representation of an integer a
bitCount(int
an integer
a)

public static int

Returns:

ceil[log(a)]
ceilLog(BigInteger
the integer
a)

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

public static int

Returns:

ceil[log(a)]
ceilLog(int
the integer
a)

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

public static int

Returns:

the number of bytes needed to encode n
ceilLog256(int
the integer
n)

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

public static int

Returns:

the number of bytes needed to encode n
ceilLog256(long
the long integer
n)

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

public static BigInteger
divideAndRound(BigInteger a, BigInteger b)

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

public static int[]

Returns:

(g,u,v), where g = gcd(abs(a),abs(b)) = ua + vb
extGCD(int
the first integer
a, int
the second integer
b)

Extended euclidian algorithm (computes gcd and representation).

public static BigInteger[]

Returns:

(d,u,v), where d = gcd(a,b) = ua + vb
extgcd(BigInteger
- the first integer
a, BigInteger
- the second integer
b)

Extended euclidian algorithm (computes gcd and representation).

public static float

Returns:

int power i of f
floatPow(float
base float
f, int
power to be raised to.
i)

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

public static int

Returns:

floor[log(a)]
floorLog(BigInteger
the integer
a)

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

public static int

Returns:

floor[log(a)]
floorLog(int
the integer
a)

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

public static int

Returns:

gcd(a, b)
gcd(int
- first integer
u, int
- second integer
v)

Computes the greatest common divisor of the two specified integers

public static byte[]
integerToOctets(BigInteger val)

public static float
intRoot(int
the base to take the root from
base, int
the root, for example 2 for a square root
root)

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

public static boolean
isIncreasing(int[] a)

public static int

Returns:

n if a = p^n or -1 otherwise
isPower(int
- the first integer
a, int
- the second integer
p)

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

public static boolean

Returns:

true if the given integer is prime with probability 2-100, false otherwise
isPrime(int
the integer to test for primality
n)

Miller-Rabin-Test, determines wether the given integer is probably prime or composite.

public static int

Returns:

value of the jacobi symbol (A|B)
jacobi(BigInteger
integer value
A, BigInteger
integer value
B)

Computes the value of the Jacobi symbol (A|B).

public static BigInteger

Returns:

the lcm(numbers)
leastCommonMultiple(BigInteger[]
- the set of numbers
numbers)

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

public static int

Returns:

divisor p >1 or 1 if a = -1,0,1
leastDiv(int
- the integer
a)

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

public static double

Returns:

log_2(x)
log(double
any double value
x)

Deprecated use MathFunctions.log(double) instead
calculate the logarithm to the base 2.
public static double

Returns:

log_2(x)
log(long
any long value >=1
x)

Deprecated use MathFunctions.log(long) instead
calculate the logarithm to the base 2.
private static double

Returns:

log_2(arg)
logBKM(double
a double value with 1<= arg<= 4.768462058
arg)

Deprecated use MathFunctions.logBKM(double) instead
BKM Algorithm to calculate logarithms to the base 2.
public static int

Returns:

the largest h with 2^h | a if a!=0, 0 otherwise
maxPower(int
an integer
a)

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

public static long

Returns:

a mod m
mod(long
value on which the modulo operation has to be performed.
a, long
the modulus.
m)

Returns a long integer whose value is (a mod m).

public static int

Returns:

a-1 mod n
modInverse(int
- the integer to invert
a, int
- the modulus
mod)

Computes the modular inverse of an integer a

public static long

Returns:

a-1 mod n
modInverse(long
- the integer to invert
a, long
- the modulus
mod)

Computes the modular inverse of an integer a

public static int

Returns:

ae mod n
modPow(int
the base
a, int
the exponent
e, int
the modulus
n)

Compute ae mod n.

public static BigInteger

Returns:

the next prime greater than n
nextPrime(long
a integer number
n)

Computes the next prime greater than n.

public static BigInteger

Returns:

the next prime greater than n
nextProbablePrime(BigInteger
a integer number
n, int
the certainty that the generated number is prime
certainty)

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

public static BigInteger

Returns:

the next prime greater than n
nextProbablePrime(BigInteger
a integer number
n)

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

public static int

Returns:

the largest prime smaller than n, or 1 if n <= 2
nextSmallerPrime(int
- upper bound
n)

Returns the largest prime smaller than the given integer

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

public static BigInteger
octetsToInteger(byte[] data)

public static int

Returns:

the order k of g (that is k is the smallest integer with gk = 1 mod p
order(int
an integer with 1 < g < p
g, int
a prime
p)

determines the order of g modulo p, p prime and 1 < g < p.

public static boolean

Returns:

true if the number has no factor of the tested primes, false if the number is definitely composite
passesSmallPrimeTest(BigInteger
the number to test
candidate)

Short trial-division test to find out whether a number is not prime.

public static int

Returns:

ae
pow(int
the base
a, int
the exponent
e)

Compute ae.

public static long

Returns:

ae
pow(long
the base
a, int
the exponent
e)

Compute ae.

public static BigInteger
randomize(BigInteger upperBound)

public static BigInteger
randomize(BigInteger upperBound, SecureRandom prng)

public static BigInteger

Returns:

n reduced into [begin,end]
reduceInto(BigInteger
- the integer
n, BigInteger
- left bound of the interval
begin, BigInteger
- right bound of the interval
end)

Reduces an integer into a given interval

public static BigInteger

Returns:

the truncated square root of a
squareRoot(BigInteger
- value out of which we extract the square root
a)

Extract the truncated square root of a BigInteger.

Inherited from java.lang.Object:
cloneequalsfinalizegetClasshashCodenotifynotifyAlltoStringwaitwaitwait

Field Detail

FOURback to summary
private static final BigInteger FOUR
jacobiTableback to summary
private static final int[] jacobiTable
ONEback to summary
private static final BigInteger ONE
SMALL_PRIME_PRODUCTback to summary
private static final long SMALL_PRIME_PRODUCT
SMALL_PRIMESback to summary
private static final int[] SMALL_PRIMES
srback to summary
private static SecureRandom sr
TWOback to summary
private static final BigInteger TWO
ZEROback to summary
private static final BigInteger ZERO

Constructor Detail

IntegerFunctionsback to summary
private IntegerFunctions()

Method Detail

binomialback to summary
public static 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:int

- the "upper" integer

t:int

- the "lower" integer

Returns:BigInteger

the binomialcoefficient "n over t" as BigInteger

bitCountback to summary
public static int bitCount(int a)
Parameters
a:int

an integer

Returns:int

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

ceilLogback to summary
public static int ceilLog(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:BigInteger

the integer

Returns:int

ceil[log(a)]

ceilLogback to summary
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:int

the integer

Returns:int

ceil[log(a)]

ceilLog256back to summary
public static int ceilLog256(int n)

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

Parameters
n:int

the integer

Returns:int

the number of bytes needed to encode n

ceilLog256back to summary
public static int ceilLog256(long n)

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

Parameters
n:long

the long integer

Returns:int

the number of bytes needed to encode n

divideAndRoundback to summary
public static BigInteger divideAndRound(BigInteger a, BigInteger b)
divideAndRoundback to summary
public static BigInteger[] divideAndRound(BigInteger[] a, BigInteger b)
extGCDback to summary
public static int[] extGCD(int a, int b)

Extended euclidian algorithm (computes gcd and representation).

Parameters
a:int

the first integer

b:int

the second integer

Returns:int[]

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

extgcdback to summary
public static BigInteger[] extgcd(BigInteger a, BigInteger b)

Extended euclidian algorithm (computes gcd and representation).

Parameters
a:BigInteger

- the first integer

b:BigInteger

- the second integer

Returns:BigInteger[]

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

floatPowback to summary
public static float floatPow(float f, int i)

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

Parameters
f:float

base float

i:int

power to be raised to.

Returns:float

int power i of f

floorLogback to summary
public static int floorLog(BigInteger a)

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

Parameters
a:BigInteger

the integer

Returns:int

floor[log(a)]

floorLogback to summary
public static int floorLog(int a)

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

Parameters
a:int

the integer

Returns:int

floor[log(a)]

gcdback to summary
public static int gcd(int u, int v)

Computes the greatest common divisor of the two specified integers

Parameters
u:int

- first integer

v:int

- second integer

Returns:int

gcd(a, b)

integerToOctetsback to summary
public static byte[] integerToOctets(BigInteger val)
intRootback to summary
public static float intRoot(int base, int root)

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

Parameters
base:int

the base to take the root from

root:int

the root, for example 2 for a square root

isIncreasingback to summary
public static boolean isIncreasing(int[] a)
isPowerback to summary
public static int isPower(int a, int p)

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

Parameters
a:int

- the first integer

p:int

- the second integer

Returns:int

n if a = p^n or -1 otherwise

isPrimeback to summary
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:int

the integer to test for primality

Returns:boolean

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

jacobiback to summary
public static int jacobi(BigInteger A, 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:BigInteger

integer value

B:BigInteger

integer value

Returns:int

value of the jacobi symbol (A|B)

leastCommonMultipleback to summary
public static BigInteger leastCommonMultiple(BigInteger[] numbers)

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

Parameters
numbers:BigInteger[]

- the set of numbers

Returns:BigInteger

the lcm(numbers)

leastDivback to summary
public static int leastDiv(int a)

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

Parameters
a:int

- the integer

Returns:int

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

logback to summary
public static double log(double x)

Deprecated

use MathFunctions.log(double) instead

calculate the logarithm to the base 2.

Parameters
x:double

any double value

Returns:double

log_2(x)

logback to summary
public static double log(long x)

Deprecated

use MathFunctions.log(long) instead

calculate the logarithm to the base 2.

Parameters
x:long

any long value >=1

Returns:double

log_2(x)

logBKMback to summary
private static double logBKM(double arg)

Deprecated

use MathFunctions.logBKM(double) instead

BKM Algorithm to calculate logarithms to the base 2.

Parameters
arg:double

a double value with 1<= arg<= 4.768462058

Returns:double

log_2(arg)

maxPowerback to summary
public static int maxPower(int a)

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

Parameters
a:int

an integer

Returns:int

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

modback to summary
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:long

value on which the modulo operation has to be performed.

m:long

the modulus.

Returns:long

a mod m

modInverseback to summary
public static int modInverse(int a, int mod)

Computes the modular inverse of an integer a

Parameters
a:int

- the integer to invert

mod:int

- the modulus

Returns:int

a-1 mod n

modInverseback to summary
public static long modInverse(long a, long mod)

Computes the modular inverse of an integer a

Parameters
a:long

- the integer to invert

mod:long

- the modulus

Returns:long

a-1 mod n

modPowback to summary
public static int modPow(int a, int e, int n)

Compute ae mod n.

Parameters
a:int

the base

e:int

the exponent

n:int

the modulus

Returns:int

ae mod n

nextPrimeback to summary
public static BigInteger nextPrime(long n)

Computes the next prime greater than n.

Parameters
n:long

a integer number

Returns:BigInteger

the next prime greater than n

nextProbablePrimeback to summary
public static BigInteger nextProbablePrime(BigInteger n, int certainty)

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

Parameters
n:BigInteger

a integer number

certainty:int

the certainty that the generated number is prime

Returns:BigInteger

the next prime greater than n

nextProbablePrimeback to summary
public static BigInteger nextProbablePrime(BigInteger n)

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

Parameters
n:BigInteger

a integer number

Returns:BigInteger

the next prime greater than n

nextSmallerPrimeback to summary
public static int nextSmallerPrime(int n)

Returns the largest prime smaller than the given integer

Parameters
n:int

- upper bound

Returns:int

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

octetsToIntegerback to summary
public static BigInteger octetsToInteger(byte[] data, int offset, int length)
octetsToIntegerback to summary
public static BigInteger octetsToInteger(byte[] data)
orderback to summary
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:int

an integer with 1 < g < p

p:int

a prime

Returns:int

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

passesSmallPrimeTestback to summary
public static boolean passesSmallPrimeTest(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:BigInteger

the number to test

Returns:boolean

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

powback to summary
public static int pow(int a, int e)

Compute ae.

Parameters
a:int

the base

e:int

the exponent

Returns:int

ae

powback to summary
public static long pow(long a, int e)

Compute ae.

Parameters
a:long

the base

e:int

the exponent

Returns:long

ae

randomizeback to summary
public static BigInteger randomize(BigInteger upperBound)
randomizeback to summary
public static BigInteger randomize(BigInteger upperBound, SecureRandom prng)
reduceIntoback to summary
public static BigInteger reduceInto(BigInteger n, BigInteger begin, BigInteger end)

Reduces an integer into a given interval

Parameters
n:BigInteger

- the integer

begin:BigInteger

- left bound of the interval

end:BigInteger

- right bound of the interval

Returns:BigInteger

n reduced into [begin,end]

squareRootback to summary
public static BigInteger squareRoot(BigInteger a)

Extract the truncated square root of a BigInteger.

Parameters
a:BigInteger

- value out of which we extract the square root

Returns:BigInteger

the truncated square root of a