Module mq 

Computations with polynomials modulo X^n+1 and modulo q = 12289.

Computations modulo q = 12289

External callers should only see polynomials modulo X^n+1 and modulo q. Such polynomials use slices of u16. There are three distinct representations:

• External representation: plain coefficients, in the [0,q-1] range.

• Internal representation: plain coefficients, but with a storage convention that may differ from the external representation.

• NTT representation: NTT format, coefficients may also have an internal range that differs from the external representation.

Appropriate functions are provided to convert between these representations.

Constants

SQBETA

Maximum squared norm for “small” vectors (floor(beta^2)).

Functions

mqpoly_NTT_to_int

Convert a polynomial from NTT to internal representation (in-place).

mqpoly_div_ntt

Divide polynomial a by polynomial b; both must be in NTT representation.

mqpoly_div_small

Compute h = g/f mod X^n+1 mod q.

mqpoly_ext_to_int

Given a polynomial in external representation, convert it to internal representation (in-place).

mqpoly_int_to_NTT

Convert a polynomial from internal representation to NTT (in-place).

mqpoly_int_to_ext

Given a polynomial in internal representation, convert it to external representation (in-place).

mqpoly_int_to_small

Given a polynomial in internal representation, convert it to small coefficients.

mqpoly_mul_ntt

Multiply polynomial a by polynomial b; both must be in NTT representation.

mqpoly_signed_to_ext

Convert a polynomial with signed coefficients into a polynomial modulo q (external representation).

mqpoly_small_is_invertible

Check whether the provided polynomial with small coefficient is invertible modulo X^n+1 and modulo q.

mqpoly_small_to_int

Given a polynomial with small coefficients, convert it to internal representation.

mqpoly_sqnorm

Get the squared norm of a polynomial modulo q (assuming normalization of coefficients in [-q/2,+q/2]).

mqpoly_sub_int

Subtract polynomial b from polynomial a; both must be in internal representation, or both must be in NTT representation.

signed_poly_sqnorm

Get the square norm of a polynomial with signed integer coefficients.