Class IntegerPolynomial

  • All Implemented Interfaces:
    Polynomial
    Direct Known Subclasses:
    DenseTernaryPolynomial

    public class IntegerPolynomial
    extends 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 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
      • 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​(InputStream is,
                                                   int N,
                                                   int q)
                                            throws 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:
        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()