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

Class 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 IntegerPolynomials).

      • 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()

      • 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