mldsa_ntt_z
stdlib/milli/mldsa/mldsa_ntt_z.nbv only in the milli field
mldsa_ntt_z(v0, v1)
NTT over Z_q of the polynomials z_j = gamma1 - v_j (FIPS 204 Algorithm 41 applied to the signature response).
v0 and v1 hold the base 2^10 limbs (10 and 8 bits) of the unsigned 18 bit values v for 256 * count coefficients, polynomial j at 256 j .. 256 (j + 1). Returns 23 bits per output coefficient, laid out the same way, with values below 2^23 and congruent to NTT(z) mod q.
NTT(z)[k] = sum_m zeta^((2 brv(k) + 1) m) z[m]. With c[k][m] = q - zeta^(...) this is gamma1 sum_m zeta^(...) + sum_m c[k][m] v[m] mod q, a non-negative integer combination that is reduced once per output.
- Calls
mldsa/mldsa_brv8,mldsa/mldsa_mulmod_static,milli/mldsa/mldsa_reduce,mldsa/mldsa_static_limbs,mldsa/mldsa_zeta_table,slice,sum- Precompiles
assert_eq!,clone!,concat!,div_exact!,len!,loop!,modulo!- Used by
milli/mldsa/mldsa44_w_approx
Source
# NTT over Z_q of the polynomials z_j = gamma1 - v_j (FIPS 204 Algorithm 41
# applied to the signature response).
#
# `v0` and `v1` hold the base 2^10 limbs (10 and 8 bits) of the unsigned
# 18 bit values v for 256 * count coefficients, polynomial j at
# 256 j .. 256 (j + 1). Returns 23 bits per output coefficient, laid out the
# same way, with values below 2^23 and congruent to NTT(z) mod q.
#
# NTT(z)[k] = sum_m zeta^((2 brv(k) + 1) m) z[m]. With c[k][m] = q - zeta^(...)
# this is gamma1 sum_m zeta^(...) + sum_m c[k][m] v[m] mod q, a non-negative
# integer combination that is reduced once per output.
(v0, v1)
static Q = 8380417
static GAMMA1 = 131072
static count = div_exact! (len! v0), 256
assert_eq! (len! v0), len! v1
static zetas = mldsa_zeta_table(1)
# limbs of q - zeta^e
static mut neg0[512]
static mut neg1[512]
static mut neg2[512]
loop! 512, e {
static c = mldsa_static_limbs(Q - zetas[e])
neg0[e] = c[0]
neg1[e] = c[1]
neg2[e] = c[2]
}
# limb bounds: c limbs <= (1023, 1023, 7), v limbs <= (1023, 255)
static x_max = [
1023 + 256 * 1023 * 1023
1023 + 256 * (1023 * 255 + 1023 * 1023)
7 + 256 * (1023 * 255 + 7 * 1023)
256 * 7 * 255
]
let mut out[23 * 256 * count]
loop! 256, k {
static e = 2 * mldsa_brv8(k) + 1
static mut c0[256]
static mut c1[256]
static mut c2[256]
static mut row_sum = 0
loop! 256, m {
static idx = modulo! e * m, 512
c0[m] = neg0[idx]
c1[m] = neg1[idx]
c2[m] = neg2[idx]
row_sum = modulo! row_sum + zetas[idx], Q
}
static base = mldsa_static_limbs(mldsa_mulmod_static(row_sum, GAMMA1))
loop! count, j {
let a = slice((clone! v0), 256 * j, 256)
let b = slice((clone! v1), 256 * j, 256)
let x0 = base[0] + sum((clone! c0) * (clone! a))
let x1 = base[1] + sum((clone! c0) * (clone! b)) + sum((clone! c1) * (clone! a))
let x2 = base[2] + sum((clone! c1) * (clone! b)) + sum((clone! c2) * a)
let x3 = sum((clone! c2) * b)
let bits = mldsa_reduce((concat! x0, x1, x2, x3), (clone! x_max), 0)
loop! 23, i {
out[23 * (256 * j + k) + i] = bits[i]
}
}
}
out