Index Mathematics Conjectures nbv lettuce Widgets

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