mldsa_intt_sub
stdlib/milli/mldsa/mldsa_intt_sub.nbv only in the milli field
mldsa_intt_sub(y, ct)
w = NTT^-1(y) - 2^13 ct mod q (FIPS 204 Algorithm 8, step 7).
y holds 23 bits per coefficient (values below 2^23) of count polynomials in the NTT domain. ct holds the exact signed integer coefficients of c * t1 (absolute value at most 39 * 1023). Returns 23 bits per coefficient of the canonical (below q) result.
NTT^-1(y)[k] = sum_m 256^-1 zeta^(-(2 brv(m) + 1) k) y[m]. The 2^13 ct term enters limb 1 (weight 2^10) as 2^19 - 8 ct, which is non-negative, and the added 2^29 is cancelled by adding q - (2^29 mod q) to limb 0.
- Calls
mldsa/mldsa_brv8,mldsa/mldsa_limbs,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
# w = NTT^-1(y) - 2^13 ct mod q (FIPS 204 Algorithm 8, step 7).
#
# `y` holds 23 bits per coefficient (values below 2^23) of `count`
# polynomials in the NTT domain. `ct` holds the exact signed integer
# coefficients of c * t1 (absolute value at most 39 * 1023). Returns 23 bits
# per coefficient of the canonical (below q) result.
#
# NTT^-1(y)[k] = sum_m 256^-1 zeta^(-(2 brv(m) + 1) k) y[m]. The 2^13 ct term
# enters limb 1 (weight 2^10) as 2^19 - 8 ct, which is non-negative, and the
# added 2^29 is cancelled by adding q - (2^29 mod q) to limb 0.
(y, ct)
static Q = 8380417
static count = div_exact! (len! y), 23 * 256
assert_eq! (len! ct), 256 * count
static zetas = mldsa_zeta_table(8347681)
static mut z0[512]
static mut z1[512]
static mut z2[512]
loop! 512, e {
static c = mldsa_static_limbs(zetas[e])
z0[e] = c[0]
z1[e] = c[1]
z2[e] = c[2]
}
static OFFSET = 524288
static CORRECTION = Q - (modulo! 536870912, Q)
# limb bounds: matrix entries and y have limbs <= (1023, 1023, 7)
static x_max = [
256 * 1023 * 1023 + CORRECTION
256 * 2 * 1023 * 1023 + 2 * OFFSET
256 * (2 * 7 * 1023 + 1023 * 1023)
256 * 2 * 7 * 1023
256 * 7 * 7
]
# limbs of y, polynomial j coefficient m at 256 j + m
let mut y0[256 * count]
let mut y1[256 * count]
let mut y2[256 * count]
loop! 256 * count, i {
let limbs = mldsa_limbs(slice((clone! y), 23 * i, 23))
y0[i] = limbs[0]
y1[i] = limbs[1]
y2[i] = limbs[2]
}
static mut col[256]
loop! 256, m {
col[m] = 2 * mldsa_brv8(m) + 1
}
let mut out[23 * 256 * count]
loop! 256, k {
static mut m0[256]
static mut m1[256]
static mut m2[256]
loop! 256, m {
static idx = modulo! 512 - (modulo! col[m] * k, 512), 512
m0[m] = z0[idx]
m1[m] = z1[idx]
m2[m] = z2[idx]
}
loop! count, j {
let a0 = slice((clone! y0), 256 * j, 256)
let a1 = slice((clone! y1), 256 * j, 256)
let a2 = slice((clone! y2), 256 * j, 256)
let x0 = CORRECTION + sum((clone! m0) * (clone! a0))
let x1 = OFFSET - 8 * ct[256 * j + k] + sum((clone! m0) * (clone! a1)) + sum((clone! m1) * (clone! a0))
let x2 = sum((clone! m0) * (clone! a2)) + sum((clone! m1) * (clone! a1)) + sum((clone! m2) * a0)
let x3 = sum((clone! m1) * (clone! a2)) + sum((clone! m2) * a1)
let x4 = sum((clone! m2) * a2)
let bits = mldsa_reduce((concat! x0, x1, x2, x3, x4), (clone! x_max), 1)
loop! 23, b {
out[23 * (256 * j + k) + b] = bits[b]
}
}
}
out