Index Mathematics Conjectures nbv lettuce Widgets

mldsa_intt_sub

stdlib/milli/mldsa/mldsa_intt_sub.nbv only in the milli field

mldsa_intt_sub(y, ct)

w = NTT^-1(y) - 2^13 ct mod q (FIPS 204 Algorithm 8, step 7).

y holds 23 bits per coefficient (values below 2^23) of count polynomials in the NTT domain. ct holds the exact signed integer coefficients of c * t1 (absolute value at most 39 * 1023). Returns 23 bits per coefficient of the canonical (below q) result.

NTT^-1(y)[k] = sum_m 256^-1 zeta^(-(2 brv(m) + 1) k) y[m]. The 2^13 ct term enters limb 1 (weight 2^10) as 2^19 - 8 ct, which is non-negative, and the added 2^29 is cancelled by adding q - (2^29 mod q) to limb 0.

Calls
mldsa/mldsa_brv8, mldsa/mldsa_limbs, 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

# w = NTT^-1(y) - 2^13 ct mod q (FIPS 204 Algorithm 8, step 7).
#
# `y` holds 23 bits per coefficient (values below 2^23) of `count`
# polynomials in the NTT domain. `ct` holds the exact signed integer
# coefficients of c * t1 (absolute value at most 39 * 1023). Returns 23 bits
# per coefficient of the canonical (below q) result.
#
# NTT^-1(y)[k] = sum_m 256^-1 zeta^(-(2 brv(m) + 1) k) y[m]. The 2^13 ct term
# enters limb 1 (weight 2^10) as 2^19 - 8 ct, which is non-negative, and the
# added 2^29 is cancelled by adding q - (2^29 mod q) to limb 0.
(y, ct)

static Q = 8380417
static count = div_exact! (len! y), 23 * 256
assert_eq! (len! ct), 256 * count

static zetas = mldsa_zeta_table(8347681)
static mut z0[512]
static mut z1[512]
static mut z2[512]
loop! 512, e {
  static c = mldsa_static_limbs(zetas[e])
  z0[e] = c[0]
  z1[e] = c[1]
  z2[e] = c[2]
}
static OFFSET = 524288
static CORRECTION = Q - (modulo! 536870912, Q)

# limb bounds: matrix entries and y have limbs <= (1023, 1023, 7)
static x_max = [
  256 * 1023 * 1023 + CORRECTION
  256 * 2 * 1023 * 1023 + 2 * OFFSET
  256 * (2 * 7 * 1023 + 1023 * 1023)
  256 * 2 * 7 * 1023
  256 * 7 * 7
]

# limbs of y, polynomial j coefficient m at 256 j + m
let mut y0[256 * count]
let mut y1[256 * count]
let mut y2[256 * count]
loop! 256 * count, i {
  let limbs = mldsa_limbs(slice((clone! y), 23 * i, 23))
  y0[i] = limbs[0]
  y1[i] = limbs[1]
  y2[i] = limbs[2]
}

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 m0[256]
  static mut m1[256]
  static mut m2[256]
  loop! 256, m {
    static idx = modulo! 512 - (modulo! col[m] * k, 512), 512
    m0[m] = z0[idx]
    m1[m] = z1[idx]
    m2[m] = z2[idx]
  }
  loop! count, j {
    let a0 = slice((clone! y0), 256 * j, 256)
    let a1 = slice((clone! y1), 256 * j, 256)
    let a2 = slice((clone! y2), 256 * j, 256)
    let x0 = CORRECTION + sum((clone! m0) * (clone! a0))
    let x1 = OFFSET - 8 * ct[256 * j + k] + sum((clone! m0) * (clone! a1)) + sum((clone! m1) * (clone! a0))
    let x2 = sum((clone! m0) * (clone! a2)) + sum((clone! m1) * (clone! a1)) + sum((clone! m2) * a0)
    let x3 = sum((clone! m1) * (clone! a2)) + sum((clone! m2) * a1)
    let x4 = sum((clone! m2) * a2)
    let bits = mldsa_reduce((concat! x0, x1, x2, x3, x4), (clone! x_max), 1)
    loop! 23, b {
      out[23 * (256 * j + k) + b] = bits[b]
    }
  }
}
out