Index Mathematics Conjectures nbv lettuce Widgets

mldsa_pointwise

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

mldsa_pointwise(a, z_hat, c_hat, t_hat, static k)

y = A_hat z_hat - c_hat t_hat in the NTT domain (FIPS 204 Algorithm 8, step 7), in the 61 bit Mersenne field.

a holds base 2^10 limbs of A_hat (k x l polynomials, polynomial (i, s) coefficient m at 3 (256 (l i + s) + m)). z_hat (l polynomials), c_hat (one polynomial) and t_hat (k polynomials) hold 23 bits per coefficient. Returns 23 bits per coefficient of the k results, below 2^23 and congruent mod q.

Products of values below 2^23 are below 2^46. q 2^24 > 2^46 keeps the subtracted product non-negative and the sum stays below 2^49.

Calls
bits/from_bits, mersenne61/mldsa/mldsa_reduce, slice
Precompiles
assert_eq!, clone!, div_exact!, len!, loop!
Used by
mersenne61/mldsa/mldsa44_w_approx

Source

# y = A_hat z_hat - c_hat t_hat in the NTT domain (FIPS 204 Algorithm 8,
# step 7), in the 61 bit Mersenne field.
#
# `a` holds base 2^10 limbs of A_hat (k x l polynomials, polynomial (i, s)
# coefficient m at 3 (256 (l i + s) + m)). `z_hat` (l polynomials), `c_hat`
# (one polynomial) and `t_hat` (k polynomials) hold 23 bits per coefficient.
# Returns 23 bits per coefficient of the k results, below 2^23 and congruent
# mod q.
#
# Products of values below 2^23 are below 2^46. q 2^24 > 2^46 keeps the
# subtracted product non-negative and the sum stays below 2^49.
(a, z_hat, c_hat, t_hat, static k)

static Q = 8380417
static l = div_exact! (len! z_hat), 23 * 256
assert_eq! (len! a), 3 * 256 * k * l
assert_eq! (len! t_hat), 23 * 256 * k
static OFFSET = Q * 16777216
static x_max = l * (Q - 1) * 8388607 + OFFSET

let mut out[23 * 256 * k]
loop! 256, m {
  let mut z[l]
  loop! l, s {
    z[s] = from_bits(slice((clone! z_hat), 23 * (256 * s + m), 23))
  }
  let c = from_bits(slice((clone! c_hat), 23 * m, 23))
  loop! k, i {
    let mut x = OFFSET - c * from_bits(slice((clone! t_hat), 23 * (256 * i + m), 23))
    loop! l, s {
      static base = 3 * (256 * (l * i + s) + m)
      x = x + (a[base] + 1024 * a[base + 1] + 1048576 * a[base + 2]) * z[s]
    }
    let bits = mldsa_reduce(x, x_max, 0)
    loop! 23, b {
      out[23 * (256 * i + m) + b] = bits[b]
    }
  }
}
out