Index Mathematics Conjectures nbv lettuce Widgets

mldsa_ntt_native

stdlib/dilithium/mldsa/mldsa_ntt_native.nbv only in the dilithium field

mldsa_ntt_native(u, static f)

NTT over Z_q (FIPS 204 Algorithm 41) of polynomials scaled by f, in the field Z_q itself, where it is a linear map.

u holds 256 * count coefficients, polynomial j at 256 j. Returns NTT(f u) laid out the same way, one witness variable per output.

NTT(f u)[k] = sum_m f zeta^((2 brv(k) + 1) m) u[m]

Calls
mldsa/mldsa_brv8, dilithium/mldsa/mldsa_zeta_table_native, slice, sum
Precompiles
clone!, div_exact!, len!, loop!, modulo!, wtns!
Used by
dilithium/mldsa/mldsa44_verify_static, dilithium/mldsa/mldsa44_w_approx, dilithium/mldsa/mldsa44_w_approx_static

Source

# NTT over Z_q (FIPS 204 Algorithm 41) of polynomials scaled by f, in the
# field Z_q itself, where it is a linear map.
#
# `u` holds 256 * count coefficients, polynomial j at 256 j. Returns NTT(f u)
# laid out the same way, one witness variable per output.
#
# NTT(f u)[k] = sum_m f zeta^((2 brv(k) + 1) m) u[m]
(u, static f)

static count = div_exact! (len! u), 256
static zetas = mldsa_zeta_table_native(f)

let mut out[256 * count]
loop! 256, k {
  static e = 2 * mldsa_brv8(k) + 1
  static mut row[256]
  loop! 256, m {
    static idx = modulo! e * m, 512
    row[m] = zetas[idx]
  }
  loop! count, j {
    out[256 * j + k] = wtns! sum((clone! row) * slice((clone! u), 256 * j, 256))
  }
}
out