public final class IntegerFunctions extends Object
Modifier and Type | Method and Description |
---|---|
static BigInteger |
binomial(int n,
int t)
Computes the binomial coefficient (n|t) ("n over t").
|
static int |
bitCount(int a) |
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.
|
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 BigInteger[] |
divideAndRound(BigInteger[] a,
BigInteger b) |
static BigInteger |
divideAndRound(BigInteger a,
BigInteger b) |
static BigInteger[] |
extgcd(BigInteger a,
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 |
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(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(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(BigInteger A,
BigInteger B)
Computes the value of the Jacobi symbol (A|B).
|
static BigInteger |
leastCommonMultiple(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 void |
main(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 BigInteger |
nextPrime(long n)
Computes the next prime greater than n.
|
static BigInteger |
nextProbablePrime(BigInteger n)
Compute the next probable prime greater than n with the default
certainty (20).
|
static BigInteger |
nextProbablePrime(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 BigInteger |
octetsToInteger(byte[] data) |
static 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(BigInteger 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 BigInteger |
randomize(BigInteger upperBound) |
static BigInteger |
randomize(BigInteger upperBound,
SecureRandom prng) |
static BigInteger |
reduceInto(BigInteger n,
BigInteger begin,
BigInteger end)
Reduces an integer into a given interval
|
static BigInteger |
ressol(BigInteger a,
BigInteger p)
Computes the square root of a BigInteger modulo a prime employing the
Shanks-Tonelli algorithm.
|
static BigInteger |
squareRoot(BigInteger a)
Extract the truncated square root of a BigInteger.
|
public static int jacobi(BigInteger A, BigInteger B)
(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)
A
- integer valueB
- integer valuepublic static BigInteger ressol(BigInteger a, BigInteger p) throws IllegalArgumentException
a
- value out of which we extract the square rootp
- prime modulus that determines the underlying fieldNoQuadraticResidueException
- if a is a quadratic non-residue modulo pIllegalArgumentException
public static int gcd(int u, int v)
u
- - first integerv
- - second integerpublic static int[] extGCD(int a, int b)
a
- the first integerb
- the second integerpublic static BigInteger divideAndRound(BigInteger a, BigInteger b)
public static BigInteger[] divideAndRound(BigInteger[] a, BigInteger b)
public static int ceilLog(BigInteger a)
a
- the integerpublic static int ceilLog(int a)
a
- the integerpublic static int ceilLog256(int n)
n
- the integerpublic static int ceilLog256(long n)
n
- the long integerpublic static int floorLog(BigInteger a)
a
- the integerpublic static int floorLog(int a)
a
- the integerpublic static int maxPower(int a)
a
- an integerpublic static int bitCount(int a)
a
- an integerpublic static int order(int g, int p)
g
- an integer with 1 < g < pp
- a primepublic static BigInteger reduceInto(BigInteger n, BigInteger begin, BigInteger end)
n
- - the integerbegin
- - left bound of the intervalend
- - right bound of the intervalpublic static int pow(int a, int e)
a
- the basee
- the exponentpublic static long pow(long a, int e)
a
- the basee
- the exponentpublic static int modPow(int a, int e, int n)
a
- the basee
- the exponentn
- the moduluspublic static BigInteger[] extgcd(BigInteger a, BigInteger b)
a
- - the first integerb
- - the second integerpublic static BigInteger leastCommonMultiple(BigInteger[] numbers)
numbers
- - the set of numberspublic static long mod(long a, long m)
a
- value on which the modulo operation has to be performed.m
- the modulus.public static int modInverse(int a, int mod)
a
- - the integer to invertmod
- - the moduluspublic static long modInverse(long a, long mod)
a
- - the integer to invertmod
- - the moduluspublic static int isPower(int a, int p)
a
- - the first integerp
- - the second integerpublic static int leastDiv(int a)
a
- - the integerpublic static boolean isPrime(int n)
n
- the integer to test for primalitypublic static boolean passesSmallPrimeTest(BigInteger candidate)
candidate
- the number to testpublic static int nextSmallerPrime(int n)
n
- - upper boundpublic static BigInteger nextProbablePrime(BigInteger n, int certainty)
n
- a integer numbercertainty
- the certainty that the generated number is primepublic static BigInteger nextProbablePrime(BigInteger n)
n
- a integer numberpublic static BigInteger nextPrime(long n)
n
- a integer numberpublic static BigInteger binomial(int n, int t)
n
- - the "upper" integert
- - the "lower" integerpublic static BigInteger randomize(BigInteger upperBound)
public static BigInteger randomize(BigInteger upperBound, SecureRandom prng)
public static BigInteger squareRoot(BigInteger a)
a
- - value out of which we extract the square rootpublic static float intRoot(int base, int root)
base
- the base to take the root fromroot
- the root, for example 2 for a square rootpublic static float floatLog(float param)
param
- public static float floatPow(float f, int i)
f
- i
- public static double log(double x)
x
- any double valuepublic static double log(long x)
x
- any long value >=1public static boolean isIncreasing(int[] a)
public static byte[] integerToOctets(BigInteger val)
public static BigInteger octetsToInteger(byte[] data, int offset, int length)
public static BigInteger octetsToInteger(byte[] data)
public static void main(String[] args)
Copyright © 2016 BouncyCastle.org. All rights reserved.