ntt
stdlib/polynomial/ntt.nbv
ntt(let input, root_powers)
apply a number theoretic transform to a vector of elements
- Calls
polynomial/bit_reverse_indices- Precompiles
assert_eq!,div_exact!,len!,log2_exact!,loop!- Used by
polynomial/intt_negacyclic,polynomial/ntt_negacyclic
Source
# apply a number theoretic transform to a vector of elements
(let input, root_powers)
static N = len! input
assert_eq! N, len! root_powers
let mut output = bit_reverse_indices(input)
static mut len = 1
loop! (log2_exact! N), i {
len = len * 2
static w_len = root_powers[div_exact! N, len]
loop! (div_exact! N, len), j {
static j = j * len
static mut w = 1
static len_half = div_exact! len, 2
loop! len_half, k {
let u = output[j + k]
let v = output[j + k + len_half] * w
output[j + k] = u + v
output[j + k + len_half] = u - v
w = w * w_len
}
}
}
output