mldsa_reduce
stdlib/mersenne61/mldsa/mldsa_reduce.nbv only in the mersenne61 field
mldsa_reduce(x, static x_max, static canonical)
Reduce x modulo q = 8380417 in the 61 bit Mersenne field.
The caller guarantees x is an integer with 0 <= x <= x_max < 2^59. 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 x mod q + q.
The quotient k and remainder r are witness hints, range checked through their bits, and x = k q + r is a single field equation. k < 2^k_bits <= 2 (x_max / q + 2), so k q + r < 2^60 + 2^24 < p and the field equation implies the integer equation.
- Calls
bits/from_bits,mldsa/mldsa_assert_below_q,bits/to_bits_exact- Precompiles
assert_lt!,clone!,constrain_eq!,div_floor!,if_eq!,log2_ceil!,modulo!- Used by
mersenne61/mldsa/mldsa_intt,mersenne61/mldsa/mldsa_ntt_q,mersenne61/mldsa/mldsa_pointwise
Source
# Reduce x modulo q = 8380417 in the 61 bit Mersenne field.
#
# The caller guarantees x is an integer with 0 <= x <= x_max < 2^59. 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 x mod q + q.
#
# The quotient k and remainder r are witness hints, range checked through
# their bits, and x = k q + r is a single field equation. k < 2^k_bits <=
# 2 (x_max / q + 2), so k q + r < 2^60 + 2^24 < p and the field equation
# implies the integer equation.
(x, static x_max, static canonical)
static Q = 8380417
assert_lt! x_max, 576460752303423488, "x_max must be below 2^59"
static k_max = div_floor! x_max, Q
static k_bit_count = log2_ceil! k_max + 2
let k_bits = to_bits_exact((div_floor! x, Q), k_bit_count)
let r_bits = to_bits_exact((modulo! x, Q), 23)
constrain_eq! x, Q * from_bits(k_bits) + from_bits(clone! r_bits)
if_eq! canonical, 1 {
let _ = mldsa_assert_below_q(clone! r_bits)
}
r_bits