Index Mathematics Conjectures nbv lettuce Widgets

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