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)

• ressol

  public static java.math.BigInteger ressol​(java.math.BigInteger a,
                                            java.math.BigInteger p)
                                     throws java.lang.IllegalArgumentException

  Computes the square root of a BigInteger 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:

  java.lang.IllegalArgumentException - 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 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)