Index Mathematics Conjectures nbv lettuce Widgets

intt_negacyclic

stdlib/polynomial/intt_negacyclic.nbv

intt_negacyclic(input)

apply an inverse negacyclic number theoretic transform to a vector of coefficients. Polynomial ring degree is assumed to be equal to the length of the input

Calls
polynomial/ntt, valloc
Precompiles
len!, root_of_unity!
Used by
milli/mldsa/mldsa_ct1, polynomial/intt_negacyclic_vec, polynomial/polynomial_coef_mul

Source

# apply an inverse negacyclic number theoretic transform to a
# vector of coefficients. Polynomial ring degree is assumed
# to be equal to the length of the input
(input)

static N = len! input
static N_inv = 1 / N
(static _, static negacyclic_root_inv_powers) = root_of_unity! 2 * N, N
(static _, static root_inv_powers) = root_of_unity! N, N

let output = ntt(input, root_inv_powers)

output * negacyclic_root_inv_powers * valloc(N, N_inv)