Index Mathematics Conjectures nbv lettuce Widgets

mldsa_assert_below_q

stdlib/mldsa/mldsa_assert_below_q.nbv

mldsa_assert_below_q(r_bits)

Constrain the value of 23 little-endian bits to be at most q - 1 = 0x7FE000: if bits 13..22 are all set, bits 0..12 must be clear.

Calls
bits/and_bits, slice, sum
Precompiles
assert_eq!, clone!, constrain_eq!, len!, loop!
Used by
dilithium/mldsa/mldsa44_w_approx, dilithium/mldsa/mldsa44_w_approx_static, mersenne61/mldsa/mldsa_reduce, milli/mldsa/mldsa_reduce

Source

# Constrain the value of 23 little-endian bits to be at most q - 1 = 0x7FE000:
# if bits 13..22 are all set, bits 0..12 must be clear.
(r_bits)

assert_eq! 23, len! r_bits
let mut top_set = r_bits[13]
loop! 9, i {
  top_set = and_bits(top_set, r_bits[14 + i])
}
constrain_eq! 0, top_set * sum(slice((clone! r_bits), 0, 13))
r_bits