mldsa_reduce
stdlib/milli/mldsa/mldsa_reduce.nbv only in the milli field
mldsa_reduce(x, static x_max, static canonical)
Reduce X = sum(x[t] * 2^(10 t)) modulo q = 8380417.
The caller guarantees each limb is an integer with 0 <= x[t] <= x_max[t] and x_max[t] <= 2^30. Returns the 23 little-endian bits of r where r = X mod q when canonical is 1, otherwise r < 2^23 and r = X mod q or r = X mod q + q.
The quotient k (as base 2^10 limbs) and remainder r are witness hints from mldsa_div_rem_q. X = k q + r is checked limb by limb in base 2^10 with range checked carries:
x[t] + carry[t - 1] - (k q + r)[t] = 1024 carry[t]
Each carry is range checked to [-2048, hi_t] where hi_t bounds (x_max[t] + hi_(t-1)) / 1024. With x_max <= 2^30 the carries fit in 21 bits, so 1024 carry and the left hand side are both well below p / 2 and the field equality implies the integer equality. k and r are only used through their bit decompositions, so they are integers below 2^k_bits and 2^23.
- Calls
bits/from_bits,mldsa/mldsa_assert_below_q,mldsa/mldsa_div_rem_q,mldsa/mldsa_limbs,bits/to_bits_exact- Precompiles
assert_eq!,assert_lte!,clone!,constrain_eq!,div_ceil!,div_floor!,if_eq!,if_lt!,len!,log2_ceil!,loop!,min!,static_eval!- Used by
milli/mldsa/mldsa_intt_sub,milli/mldsa/mldsa_ntt_z,milli/mldsa/mldsa_pointwise
Source
# Reduce X = sum(x[t] * 2^(10 t)) modulo q = 8380417.
#
# The caller guarantees each limb is an integer with 0 <= x[t] <= x_max[t]
# and x_max[t] <= 2^30. Returns the 23 little-endian bits of r where
# r = X mod q when `canonical` is 1, otherwise r < 2^23 and r = X mod q or
# r = X mod q + q.
#
# The quotient k (as base 2^10 limbs) and remainder r are witness hints from
# mldsa_div_rem_q. X = k q + r is checked
# limb by limb in base 2^10 with range checked carries:
#
# x[t] + carry[t - 1] - (k q + r)[t] = 1024 carry[t]
#
# Each carry is range checked to [-2048, hi_t] where hi_t bounds
# (x_max[t] + hi_(t-1)) / 1024. With x_max <= 2^30 the carries fit in 21 bits,
# so 1024 carry and the left hand side are both well below p / 2 and the field
# equality implies the integer equality. k and r are only used through their
# bit decompositions, so they are integers below 2^k_bits and 2^23.
(x, static x_max, static canonical)
static Q = 8380417
static Q_LIMBS = [1 1016 7]
static n = len! x
assert_eq! n, len! x_max
loop! n, t {
assert_lte! x_max[t], 1073741824
}
# exact bound on the quotient, computed at compile time
static k_max = static_eval! {
(let k, let r) = mldsa_div_rem_q(clone! x_max)
k
}
static mut k_bit_count = 1
loop! (len! k_max), t {
if_lt! 0, k_max[t] {
k_bit_count = 10 * t + (log2_ceil! k_max[t] + 1)
}
}
(let k_hint, let r_hint) = mldsa_div_rem_q(clone! x)
let mut k_bits[k_bit_count]
loop! (div_ceil! k_bit_count, 10), s {
static width = min! 10, k_bit_count - 10 * s
let b = to_bits_exact(k_hint[s], width)
loop! width, i {
k_bits[10 * s + i] = b[i]
}
}
let r_bits = to_bits_exact(r_hint, 23)
if_eq! canonical, 1 {
let _ = mldsa_assert_below_q(clone! r_bits)
}
let k_limbs = mldsa_limbs(k_bits)
let r_limbs = mldsa_limbs(clone! r_bits)
static k_limb_count = len! k_limbs
static mut limb_count = n
if_lt! limb_count, k_limb_count + 2 {
limb_count = k_limb_count + 2
}
# (k q + r) limbs
let mut rhs[limb_count]
loop! k_limb_count, s {
loop! 3, u {
rhs[s + u] = rhs[s + u] + k_limbs[s] * Q_LIMBS[u]
}
}
loop! 3, u {
rhs[u] = rhs[u] + r_limbs[u]
}
static INV_BASE = 1 / 1024
let mut x_ext[limb_count]
loop! n, t {
x_ext[t] = x[t]
}
let mut carry = 0
static mut hi = 0
loop! limb_count - 1, t {
# upper bound of x[t] + carry
static mut limb_max = 0
if_lt! t, n {
limb_max = x_max[t]
}
hi = div_floor! limb_max + hi, 1024
static width = log2_ceil! hi + 2049
assert_lte! width, 21
let d = x_ext[t] + carry - rhs[t]
carry = from_bits(to_bits_exact(d * INV_BASE + 2048, width)) - 2048
}
constrain_eq! x_ext[limb_count - 1] + carry, rhs[limb_count - 1]
r_bits