Module algebra 

Section 2.4. Interpreting the Pseudocode Section 4.2.2. Sampling algorithms Section 4.3. The Number-Theoretic Transform

Structs

BaseField

Finite field

Constants

GAMMA 🔒

ZETA_POW_BITREV 🔒

Since the powers of zeta used in the NTT and MultiplyNTTs are fixed, we use pre-computed tables to avoid the need to compute the exponentiations at runtime.

Traits

Ntt 🔒

The Number Theoretic Transform (NTT) is a variant of the Discrete Fourier Transform (DFT) defined over a finite field that turns costly polynomial multiplications into simple coefficient-wise multiplications modulo a fixed prime.

NttInverse 🔒

The inverse NTT is the reverse of the Number Theoretic Transform, converting coefficient-wise products back into standard polynomial form while preserving correctness modulo the same prime.

Functions

base_case_multiply 🔒

Algorithm 12: BaseCaseMultiply

matrix_sample_ntt 🔒

ntt_inverse_layer 🔒

One layer of the inverse NTT butterfly.

ntt_layer 🔒

One layer of the forward NTT butterfly.

sample_ntt 🔒

Algorithm 7: SampleNTT(B)

sample_poly_cbd 🔒

Algorithm 8: SamplePolyCBD_eta(B)

sample_poly_vec_cbd 🔒

Type Aliases

Elem 🔒

An element of GF(q).

Int 🔒

NttMatrix 🔒

A K x K matrix of NTT-domain polynomials. Each vector represents a row of the matrix, so that multiplying on the right just requires iteration.

NttPolynomial 🔒

An element of the ring T_q i.e. a tuple of 128 elements of the direct sum components of T_q.

NttVector 🔒

A vector of K NTT-domain polynomials.

Polynomial 🔒

An element of the ring R_q, i.e., a polynomial over Z_q of degree 255

Vector 🔒

A vector of polynomials of length K.