mldsa_ntt_q
stdlib/mersenne61/mldsa/mldsa_ntt_q.nbv only in the mersenne61 field
mldsa_ntt_q(u, static u_max, static negate, static offset, static scale)
NTT over Z_q (FIPS 204 Algorithm 41) of polynomials w = s u + a, scaled by f, as a matrix product followed by one reduction per output.
u holds 256 * count non-negative integers below or equal to u_max, polynomial j at 256 j. negate selects s = -1 (1) or s = 1 (0), offset is a < q and scale is f. Returns 23 bits per output coefficient, laid out like the input, with values below 2^23 and congruent to NTT(f w) mod q.
NTT(f w)[k] = sum_m f zeta^((2 brv(k) + 1) m) (s u[m] + a). With s = -1 the coefficients are replaced by q - f zeta^(...), so every term is non-negative and the sum stays far below 2^59.
- Calls
mldsa/mldsa_brv8,mldsa/mldsa_mulmod_static,mersenne61/mldsa/mldsa_reduce,mldsa/mldsa_zeta_table,slice,sum- Precompiles
clone!,div_exact!,if_eq!,len!,loop!,modulo!- Used by
mersenne61/mldsa/mldsa44_w_approx
Source
# NTT over Z_q (FIPS 204 Algorithm 41) of polynomials w = s u + a, scaled by
# f, as a matrix product followed by one reduction per output.
#
# `u` holds 256 * count non-negative integers below or equal to `u_max`,
# polynomial j at 256 j. `negate` selects s = -1 (1) or s = 1 (0), `offset`
# is a < q and `scale` is f. Returns 23 bits per output coefficient, laid out
# like the input, with values below 2^23 and congruent to NTT(f w) mod q.
#
# NTT(f w)[k] = sum_m f zeta^((2 brv(k) + 1) m) (s u[m] + a). With s = -1 the
# coefficients are replaced by q - f zeta^(...), so every term is
# non-negative and the sum stays far below 2^59.
(u, static u_max, static negate, static offset, static scale)
static Q = 8380417
static count = div_exact! (len! u), 256
static zetas = mldsa_zeta_table(scale)
static mut entries[512]
loop! 512, e {
entries[e] = zetas[e]
if_eq! negate, 1 {
entries[e] = Q - zetas[e]
}
}
static x_max = Q + 256 * (Q - 1) * u_max
let mut out[23 * 256 * count]
loop! 256, k {
static e = 2 * mldsa_brv8(k) + 1
static mut row[256]
static mut row_sum = 0
loop! 256, m {
static idx = modulo! e * m, 512
row[m] = entries[idx]
row_sum = modulo! row_sum + zetas[idx], Q
}
static base = mldsa_mulmod_static(offset, row_sum)
loop! count, j {
let x = base + sum((clone! row) * slice((clone! u), 256 * j, 256))
let bits = mldsa_reduce(x, x_max, 0)
loop! 23, i {
out[23 * (256 * j + k) + i] = bits[i]
}
}
}
out