Struct Ntt32Context 

pub struct Ntt32Context {
    pub n: usize,
    pub log_n: u32,
    pub q: u32,
    pub two_q: u32,
    pub root_powers: Vec<u32>,
    pub root_powers_shoup: Vec<u32>,
    pub inv_root_powers: Vec<u32>,
    pub inv_root_powers_shoup: Vec<u32>,
    pub n_inv: u32,
    pub n_inv_shoup: u32,
}

Pre-computed NTT context for a single 28-bit prime.

Stores twiddle factors (root powers) in Longa-Naehrig ordering along with their Shoup precomputed quotients for division-free multiplication.

Usage

use vaea_ntt::ntt32::{Ntt32Context, generate_primes_28};

let primes = generate_primes_28(1024, 1);
let ctx = Ntt32Context::new(1024, primes[0]);

let mut data = vec![0u32; 1024];
data[0] = 42;
ctx.forward(&mut data);   // NTT forward
ctx.inverse(&mut data);   // NTT inverse (data restored)
assert_eq!(data[0], 42);

Fields

n: usize

Polynomial size (power of 2)

log_n: u32

log2(n)

q: u32

Prime < 2^28

two_q: u32

2 · q — precomputed for Harvey lazy butterfly

root_powers: Vec<u32>

Forward root powers (Longa-Naehrig ordering)

root_powers_shoup: Vec<u32>

Shoup quotients for forward root powers: floor(root_powers[i] · 2^32 / q)

inv_root_powers: Vec<u32>

Inverse root powers for INTT

inv_root_powers_shoup: Vec<u32>

Shoup quotients for inverse root powers

n_inv: u32

N^{-1} mod q — normalization factor for INTT

n_inv_shoup: u32

Shoup quotient for n_inv

Implementations

impl Ntt32Context

pub fn try_new(n: usize, q: u32) -> Result<Self, NttError>

Fallible constructor for an NTT context for a 28-bit prime.

Validates all preconditions and returns an error instead of panicking.

Arguments

• n — polynomial size, must be a power of 2 ≥ 2
• q — prime < 2^28, must satisfy q ≡ 1 (mod 2N)

Errors

• crate::NttError::InvalidSize if n is not a power of 2 ≥ 2
• crate::NttError::PrimeTooLarge if q ≥ 2^28
• crate::NttError::NotPrime if q is not prime
• crate::NttError::NotNttFriendly if (q - 1) is not divisible by 2N

pub fn new(n: usize, q: u32) -> Self

Creates a new NTT context for a 28-bit prime.

Computes primitive roots, twiddle factors (Longa-Naehrig ordering), and precomputes all Shoup quotients.

Arguments

• n — polynomial size, must be a power of 2 ≥ 2
• q — prime < 2^28, must satisfy q ≡ 1 (mod 2N)

Panics

• If n is not a power of 2 ≥ 2
• If q ≥ 2^28
• If q is not prime
• If (q - 1) is not divisible by 2N

pub fn forward(&self, data: &mut [u32])

Applies the NTT forward transform in-place.

On aarch64, dispatches to the fully-vectorized NEON implementation. On other architectures, uses the scalar Shoup NTT.

pub fn inverse(&self, data: &mut [u32])

Applies the NTT inverse transform in-place (with N⁻¹ normalization).

Output coefficients are fully normalized to [0, q). On aarch64, dispatches to the NEON implementation. On other architectures, uses the scalar Shoup NTT.

pub fn inverse_lazy(&self, data: &mut [u32])

Applies the NTT inverse transform without N⁻¹ normalization.

Output coefficients are scaled by N relative to the true INTT. Use this when chaining operations where normalization can be deferred, or when matching libraries that don’t normalize (e.g., concrete-ntt).

pub fn n_inv(&self) -> u32

Returns N⁻¹ mod q — useful for manual normalization after inverse_lazy().

pub fn n_inv_shoup(&self) -> u32

Returns the Shoup quotient for N⁻¹ — for manual Shoup normalization.

pub fn pointwise_mul(&self, a: &[u32], b: &[u32], result: &mut [u32])

Pointwise multiplication of two vectors in the NTT domain.

Computes result[i] = a[i] · b[i] mod q for each coefficient.

pub fn negacyclic_mul(&self, a: &[u32], b: &[u32]) -> Vec<u32>

Negacyclic polynomial multiplication in Z_q[X]/(X^N + 1).

Computes result = a · b mod (X^N + 1) using forward NTT, pointwise multiplication, and inverse NTT.

Returns

A new vector of length N containing the product.

pub fn negacyclic_mul_into( &self, a_buf: &mut [u32], b_buf: &mut [u32], result: &mut [u32], )

Zero-allocation negacyclic multiplication.

The caller provides pre-allocated buffers:

• a_buf / b_buf: input polynomials (overwritten with NTT-domain values)
• result: output buffer for the product

All buffers must have length N. After the call, a_buf and b_buf contain NTT-domain data (destroyed); result contains the product in coefficient domain.

Example

use vaea_ntt::ntt32::{Ntt32Context, generate_primes_28};

let primes = generate_primes_28(256, 1);
let ctx = Ntt32Context::new(256, primes[0]);

let mut a = vec![1u32; 256];
let mut b = vec![2u32; 256];
let mut result = vec![0u32; 256];

ctx.negacyclic_mul_into(&mut a, &mut b, &mut result);
// result now contains a·b mod (X^256 + 1)
// a and b are now in NTT domain (overwritten)

Trait Implementations

impl Clone for Ntt32Context

fn clone(&self) -> Ntt32Context

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for Ntt32Context

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.