Package org.bouncycastle.pqc.math.ntru.polynomial

## Class IntegerPolynomial

- java.lang.Object
- - org.bouncycastle.pqc.math.ntru.polynomial.IntegerPolynomial

- All Implemented Interfaces:
    `Polynomial`
  Direct Known Subclasses:
    `DenseTernaryPolynomial`

      public class IntegerPolynomial
      extends java.lang.Object
      implements Polynomial

  A polynomial with `int` coefficients.
  Some methods (like `add`) change the polynomial, others (like `mult`) do not but return the result as a new polynomial.

- - ### Field Summary

    Fields
    Modifier and Type | Field | Description
    --- | --- | ---
    `int[]` | `coeffs` |

  - ### Constructor Summary

    Constructors
    Constructor | Description
    --- | ---
    `IntegerPolynomial​(int N)` | Constructs a new polynomial with `N` coefficients initialized to 0.
    `IntegerPolynomial​(int[] coeffs)` | Constructs a new polynomial with a given set of coefficients.
    `IntegerPolynomial​(BigIntPolynomial p)` | Constructs a `IntegerPolynomial` from a `BigIntPolynomial`.

  - ### Method Summary

    All Methods Static Methods Instance Methods Concrete Methods
    Modifier and Type | Method | Description
    --- | --- | ---
    `void` | `add​(IntegerPolynomial b)` | Adds another polynomial which can have a different number of coefficients.
    `void` | `add​(IntegerPolynomial b, int modulus)` | Adds another polynomial which can have a different number of coefficients, and takes the coefficient values mod `modulus`.
    `void` | `center0​(int q)` | Shifts the values of all coefficients to the interval `[-q/2, q/2]`.
    `long` | `centeredNormSq​(int q)` | Computes the centered euclidean norm of the polynomial.
    `void` | `clear()` |
    `java.lang.Object` | `clone()` |
    `int` | `count​(int value)` | Counts the number of coefficients equal to an integer
    `void` | `div​(int k)` | Divides each coefficient by `k` and rounds to the nearest integer.
    `void` | `ensurePositive​(int modulus)` | Adds `modulus` until all coefficients are above 0.
    `boolean` | `equals​(java.lang.Object obj)` |
    `boolean` | `equalsOne()` | Tests if `p(x) = 1`.
    `static IntegerPolynomial` | `fromBinary​(byte[] data, int N, int q)` | Returns a polynomial with N coefficients between `0` and `q-1`. `q` must be a power of 2. Ignores any excess bytes.
    `static IntegerPolynomial` | `fromBinary​(java.io.InputStream is, int N, int q)` | Returns a polynomial with N coefficients between `0` and `q-1`. `q` must be a power of 2. Ignores any excess bytes.
    `static IntegerPolynomial` | `fromBinary3Sves​(byte[] data, int N)` | Decodes a byte array to a polynomial with `N` ternary coefficients Ignores any excess bytes.
    `static IntegerPolynomial` | `fromBinary3Tight​(byte[] b, int N)` | Converts a byte array produced by `toBinary3Tight()` to a polynomial.
    `static IntegerPolynomial` | `fromBinary3Tight​(java.io.InputStream is, int N)` | Reads data produced by `toBinary3Tight()` from an input stream and converts it to a polynomial.
    `IntegerPolynomial` | `invertF3()` | Computes the inverse mod 3.
    `IntegerPolynomial` | `invertFq​(int q)` | Computes the inverse mod `q; q` must be a power of 2. Returns `null` if the polynomial is not invertible.
    `void` | `mod​(int modulus)` | Takes each coefficient modulo `modulus`.
    `void` | `mod3()` | Takes each coefficient modulo 3 such that all coefficients are ternary.
    `void` | `modPositive​(int modulus)` | Ensures all coefficients are between 0 and `modulus-1`
    `void` | `mult​(int factor)` | Multiplies each coefficient by a `int`.
    `BigIntPolynomial` | `mult​(BigIntPolynomial poly2)` | Multiplies the polynomial by a `BigIntPolynomial`, taking the indices mod N.
    `IntegerPolynomial` | `mult​(IntegerPolynomial poly2)` | Multiplies the polynomial with another, taking the indices mod N
    `IntegerPolynomial` | `mult​(IntegerPolynomial poly2, int modulus)` | Multiplies the polynomial with another, taking the values mod modulus and the indices mod N
    `void` | `mult3​(int modulus)` | Multiplies each coefficient by a 2 and applies a modulus.
    `Resultant` | `resultant()` | Resultant of this polynomial with `x^n-1` using a probabilistic algorithm.
    `ModularResultant` | `resultant​(int p)` | Resultant of this polynomial with `x^n-1 mod p`.
    `Resultant` | `resultantMultiThread()` | Multithreaded version of `resultant()`.
    `void` | `rotate1()` | Multiplication by `X` in `Z[X]/Z[X^n-1]`.
    `void` | `sub​(IntegerPolynomial b)` | Subtracts another polynomial which can have a different number of coefficients.
    `void` | `sub​(IntegerPolynomial b, int modulus)` | Subtracts another polynomial which can have a different number of coefficients, and takes the coefficient values mod `modulus`.
    `int` | `sumCoeffs()` | Returns the sum of all coefficients, i.e. evaluates the polynomial at 0.
    `byte[]` | `toBinary​(int q)` | Encodes a polynomial whose coefficients are between 0 and q, to binary. q must be a power of 2.
    `byte[]` | `toBinary3Sves()` | Encodes a polynomial with ternary coefficients to binary.
    `byte[]` | `toBinary3Tight()` | Converts a polynomial with ternary coefficients to binary.
    `IntegerPolynomial` | `toIntegerPolynomial()` | Returns a polynomial that is equal to this polynomial (in the sense that `Polynomial.mult(IntegerPolynomial, int)` returns equal `IntegerPolynomial`s).

    - ### Methods inherited from class java.lang.Object

      `finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

- - ### Field Detail

    - #### coeffs

          public int[] coeffs

  - ### Constructor Detail

    - #### IntegerPolynomial

          public IntegerPolynomial​(int N)

      Constructs a new polynomial with `N` coefficients initialized to 0.
      Parameters:
        `N` - the number of coefficients

    - #### IntegerPolynomial

          public IntegerPolynomial​(int[] coeffs)

      Constructs a new polynomial with a given set of coefficients.
      Parameters:
        `coeffs` - the coefficients

    - #### IntegerPolynomial

          public IntegerPolynomial​(BigIntPolynomial p)

      Constructs a `IntegerPolynomial` from a `BigIntPolynomial`. The two polynomials are independent of each other.
      Parameters:
        `p` - the original polynomial

  - ### Method Detail

    - #### fromBinary3Sves

          public static IntegerPolynomial fromBinary3Sves​(byte[] data,
                                                          int N)

      Decodes a byte array to a polynomial with `N` ternary coefficients
      Ignores any excess bytes.
      Parameters:
        `data` - an encoded ternary polynomial
        `N` - number of coefficients
      Returns:
        the decoded polynomial

    - #### fromBinary3Tight

          public static IntegerPolynomial fromBinary3Tight​(byte[] b,
                                                           int N)

      Converts a byte array produced by `toBinary3Tight()` to a polynomial.
      Parameters:
        `b` - a byte array
        `N` - number of coefficients
      Returns:
        the decoded polynomial

    - #### fromBinary3Tight

          public static IntegerPolynomial fromBinary3Tight​(java.io.InputStream is,
                                                           int N)
                                                    throws java.io.IOException

      Reads data produced by `toBinary3Tight()` from an input stream and converts it to a polynomial.
      Parameters:
        `is` - an input stream
        `N` - number of coefficients
      Returns:
        the decoded polynomial
      Throws:
        `java.io.IOException`

    - #### fromBinary

          public static IntegerPolynomial fromBinary​(byte[] data,
                                                     int N,
                                                     int q)

      Returns a polynomial with N coefficients between `0` and `q-1`.
      `q` must be a power of 2.
      Ignores any excess bytes.
      Parameters:
        `data` - an encoded ternary polynomial
        `N` - number of coefficients
        `q` -
      Returns:
        the decoded polynomial

    - #### fromBinary

          public static IntegerPolynomial fromBinary​(java.io.InputStream is,
                                                     int N,
                                                     int q)
                                              throws java.io.IOException

      Returns a polynomial with N coefficients between `0` and `q-1`.
      `q` must be a power of 2.
      Ignores any excess bytes.
      Parameters:
        `is` - an encoded ternary polynomial
        `N` - number of coefficients
        `q` -
      Returns:
        the decoded polynomial
      Throws:
        `java.io.IOException`

    - #### toBinary3Sves

          public byte[] toBinary3Sves()

      Encodes a polynomial with ternary coefficients to binary. `coeffs[2*i]` and `coeffs[2*i+1]` must not both equal -1 for any integer `i`, so this method is only safe to use with polynomials produced by `fromBinary3Sves()`.
      Returns:
        the encoded polynomial

    - #### toBinary3Tight

          public byte[] toBinary3Tight()

      Converts a polynomial with ternary coefficients to binary.
      Returns:
        the encoded polynomial

    - #### toBinary

          public byte[] toBinary​(int q)

      Encodes a polynomial whose coefficients are between 0 and q, to binary. q must be a power of 2.
      Parameters:
        `q` -
      Returns:
        the encoded polynomial

    - #### mult

          public IntegerPolynomial mult​(IntegerPolynomial poly2,
                                        int modulus)

      Multiplies the polynomial with another, taking the values mod modulus and the indices mod N
      Specified by:
        `mult` in interface `Polynomial`
      Parameters:
        `poly2` - a polynomial
        `modulus` - a modulus to apply
      Returns:
        the product of the two polynomials

    - #### mult

          public IntegerPolynomial mult​(IntegerPolynomial poly2)

      Multiplies the polynomial with another, taking the indices mod N
      Specified by:
        `mult` in interface `Polynomial`
      Parameters:
        `poly2` - a polynomial
      Returns:
        the product of the two polynomials

    - #### mult

          public BigIntPolynomial mult​(BigIntPolynomial poly2)

      Description copied from interface: `Polynomial`
      Multiplies the polynomial by a `BigIntPolynomial`, taking the indices mod N. Does not change this polynomial but returns the result as a new polynomial.
      Both polynomials must have the same number of coefficients.
      Specified by:
        `mult` in interface `Polynomial`
      Parameters:
        `poly2` - the polynomial to multiply by
      Returns:
        a new polynomial

    - #### invertFq

          public IntegerPolynomial invertFq​(int q)

      Computes the inverse mod `q; q` must be a power of 2.
      Returns `null` if the polynomial is not invertible.
      Parameters:
        `q` - the modulus
      Returns:
        a new polynomial

    - #### invertF3

          public IntegerPolynomial invertF3()

      Computes the inverse mod 3. Returns `null` if the polynomial is not invertible.
      Returns:
        a new polynomial

    - #### resultant

          public Resultant resultant()

      Resultant of this polynomial with `x^n-1` using a probabilistic algorithm.

      Unlike EESS, this implementation does not compute all resultants modulo primes such that their product exceeds the maximum possible resultant, but rather stops when `NUM_EQUAL_RESULTANTS` consecutive modular resultants are equal.
      This means the return value may be incorrect. Experiments show this happens in about 1 out of 100 cases when `N=439` and `NUM_EQUAL_RESULTANTS=2`, so the likelyhood of leaving the loop too early is `(1/100)^(NUM_EQUAL_RESULTANTS-1)`.

      Because of the above, callers must verify the output and try a different polynomial if necessary.

      Returns:
        `(rho, res)` satisfying `res = rho*this + t*(x^n-1)` for some integer `t`.

    - #### resultantMultiThread

          public Resultant resultantMultiThread()

      Multithreaded version of `resultant()`.
      Returns:
        `(rho, res)` satisfying `res = rho*this + t*(x^n-1)` for some integer `t`.

    - #### resultant

          public ModularResultant resultant​(int p)

      Resultant of this polynomial with `x^n-1 mod p`.
      Returns:
        `(rho, res)` satisfying `res = rho*this + t*(x^n-1) mod p` for some integer `t`.

    - #### add

          public void add​(IntegerPolynomial b,
                          int modulus)

      Adds another polynomial which can have a different number of coefficients, and takes the coefficient values mod `modulus`.
      Parameters:
        `b` - another polynomial

    - #### add

          public void add​(IntegerPolynomial b)

      Adds another polynomial which can have a different number of coefficients.
      Parameters:
        `b` - another polynomial

    - #### sub

          public void sub​(IntegerPolynomial b,
                          int modulus)

      Subtracts another polynomial which can have a different number of coefficients, and takes the coefficient values mod `modulus`.
      Parameters:
        `b` - another polynomial

    - #### sub

          public void sub​(IntegerPolynomial b)

      Subtracts another polynomial which can have a different number of coefficients.
      Parameters:
        `b` - another polynomial

    - #### mult

          public void mult​(int factor)

      Multiplies each coefficient by a `int`. Does not return a new polynomial but modifies this polynomial.
      Parameters:
        `factor` -

    - #### mult3

          public void mult3​(int modulus)

      Multiplies each coefficient by a 2 and applies a modulus. Does not return a new polynomial but modifies this polynomial.
      Parameters:
        `modulus` - a modulus

    - #### div

          public void div​(int k)

      Divides each coefficient by `k` and rounds to the nearest integer. Does not return a new polynomial but modifies this polynomial.
      Parameters:
        `k` - the divisor

    - #### mod3

          public void mod3()

      Takes each coefficient modulo 3 such that all coefficients are ternary.

    - #### modPositive

          public void modPositive​(int modulus)

      Ensures all coefficients are between 0 and `modulus-1`
      Parameters:
        `modulus` - a modulus

    - #### mod

          public void mod​(int modulus)

      Takes each coefficient modulo `modulus`.

    - #### ensurePositive

          public void ensurePositive​(int modulus)

      Adds `modulus` until all coefficients are above 0.
      Parameters:
        `modulus` - a modulus

    - #### centeredNormSq

          public long centeredNormSq​(int q)

      Computes the centered euclidean norm of the polynomial.
      Parameters:
        `q` - a modulus
      Returns:
        the centered norm

    - #### center0

          public void center0​(int q)

      Shifts the values of all coefficients to the interval `[-q/2, q/2]`.
      Parameters:
        `q` - a modulus

    - #### sumCoeffs

          public int sumCoeffs()

      Returns the sum of all coefficients, i.e. evaluates the polynomial at 0.
      Returns:
        the sum of all coefficients

    - #### equalsOne

          public boolean equalsOne()

      Tests if `p(x) = 1`.
      Returns:
        true iff all coefficients are equal to zero, except for the lowest coefficient which must equal 1

    - #### count

          public int count​(int value)

      Counts the number of coefficients equal to an integer
      Parameters:
        `value` - an integer
      Returns:
        the number of coefficients equal to `value`

    - #### rotate1

          public void rotate1()

      Multiplication by `X` in `Z[X]/Z[X^n-1]`.

    - #### clear

          public void clear()

    - #### toIntegerPolynomial

          public IntegerPolynomial toIntegerPolynomial()

      Description copied from interface: `Polynomial`
      Returns a polynomial that is equal to this polynomial (in the sense that `Polynomial.mult(IntegerPolynomial, int)` returns equal `IntegerPolynomial`s). The new polynomial is guaranteed to be independent of the original.
      Specified by:
        `toIntegerPolynomial` in interface `Polynomial`
      Returns:
        a new `IntegerPolynomial`.

    - #### clone

          public java.lang.Object clone()

      Overrides:
        `clone` in class `java.lang.Object`

    - #### equals

          public boolean equals​(java.lang.Object obj)

      Overrides:
        `equals` in class `java.lang.Object`