Package org.bouncycastle.pqc.math.linearalgebra

## Class IntegerFunctions

- java.lang.Object
- - org.bouncycastle.pqc.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

    All Methods Static Methods Concrete Methods Deprecated Methods
    Modifier and Type | Method | Description
    --- | --- | ---
    `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​(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` | `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` | `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​(int a)` | Compute the integer part of the logarithm to the base 2 of the given integer.
    `static int` | `floorLog​(java.math.BigInteger 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 `ae 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 `ae`.
    `static long` | `pow​(long a, int e)` | Compute `ae`.
    `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` | `ressol​(java.math.BigInteger a, java.math.BigInteger p)` | Computes the square root of a BigInteger modulo a prime employing the Shanks-Tonelli algorithm.
    `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)

    - #### 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 b2 = 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 gk = 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 `ae`.
      Parameters:
        `a` - the base
        `e` - the exponent
      Returns:
        `ae`

    - #### pow

          public static long pow​(long a,
                                 int e)

      Compute `ae`.
      Parameters:
        `a` - the base
        `e` - the exponent
      Returns:
        `ae`

    - #### modPow

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

      Compute `ae mod n`.
      Parameters:
        `a` - the base
        `e` - the exponent
        `n` - the modulus
      Returns:
        `ae 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)