Index Mathematics Conjectures nbv lettuce Widgets

mldsa_intt

stdlib/mersenne61/mldsa/mldsa_intt.nbv only in the mersenne61 field

mldsa_intt(y)

NTT^-1 over Z_q (FIPS 204 Algorithm 42) as a matrix product, in the 61 bit Mersenne field.

y holds 23 bits per coefficient (values below 2^23) of count polynomials. Returns 23 bits per coefficient of the canonical result.

NTT^-1(y)[k] = sum_m 256^-1 zeta^(-(2 brv(m) + 1) k) y[m] < 256 q 2^23 < 2^59.

Calls
bits/from_bits, mldsa/mldsa_brv8, mersenne61/mldsa/mldsa_reduce, mldsa/mldsa_zeta_table, slice, sum
Precompiles
clone!, div_exact!, len!, loop!, modulo!, wtns!
Used by
mersenne61/mldsa/mldsa44_w_approx

Source

# NTT^-1 over Z_q (FIPS 204 Algorithm 42) as a matrix product, in the 61 bit
# Mersenne field.
#
# `y` holds 23 bits per coefficient (values below 2^23) of `count`
# polynomials. Returns 23 bits per coefficient of the canonical result.
#
# NTT^-1(y)[k] = sum_m 256^-1 zeta^(-(2 brv(m) + 1) k) y[m] < 256 q 2^23 < 2^59.
(y)

static Q = 8380417
static count = div_exact! (len! y), 23 * 256
static zetas = mldsa_zeta_table(8347681)
static x_max = 256 * (Q - 1) * 8388607

let mut values[256 * count]
loop! 256 * count, i {
  values[i] = wtns! from_bits(slice((clone! y), 23 * i, 23))
}
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 row[256]
  loop! 256, m {
    row[m] = zetas[modulo! 512 - (modulo! col[m] * k, 512), 512]
  }
  loop! count, j {
    let x = sum((clone! row) * slice((clone! values), 256 * j, 256))
    let bits = mldsa_reduce(x, x_max, 1)
    loop! 23, b {
      out[23 * (256 * j + k) + b] = bits[b]
    }
  }
}
out