modulo!
Element-wise integer remainder, static or as an unconstrained witness hint. Integer and field arithmetic
modulo! lhs, rhs
Computes lhs mod rhs element-wise with each field element taken as its canonical integer in [0, p).
With a static lhs the result is computed at compile time. With a witness lhs the remainders become new witness entries that are unconstrained hints. The caller must constrain them, e.g. with div_floor! as lhs = rhs * quotient + remainder and range checks on both parts, or with a relation that pins the value down directly (xor_bits_vec_wtns takes (a + b) mod 2 as a hint and constrains it with one multiplication).
Arguments
lhs- Static or witness vector.
rhs- Static vector of nonzero moduli, the same length as
lhs.
Returns
A vector of remainders the length of lhs: static for a static lhs, fresh witness entries otherwise. Expression form only.
Constraints
None. A witness lhs adds one witness entry per element and no rows.
Example
(let x) static r = modulo! [7 8 9], [4 4 4] x + r
The parity of a sum of two bits, constrained as in xor_bits_vec_wtns:
(let a, let b) let x = modulo! a + b, [2] # a * b = (a + b - x) / 2 forces x = a xor b for bits a and b constrain_mul! a, b, (a + b - x) * (1 / 2) x
Notes
Errors: divisor must be static, division by zero, arguments are of mismatched dimension. Precompile arguments run to the next comma, so modulo! a + b, [2] takes the remainder of the whole sum; write (modulo! x, 2) in parentheses when it is itself an argument.
Used in the standard library
bits/add32_bits, bits/u32_bits_static, bits/xor_bits_vec_wtns, chacha/chacha_block, dilithium/mldsa/mldsa_intt_native, dilithium/mldsa/mldsa_ntt_native, ext/ext_sum, keccak/keccak_f1600, keccak/keccak_sponge_shake, mersenne61/mldsa/mldsa_intt, mersenne61/mldsa/mldsa_ntt_q, mersenne61/mldsa/mldsa_reduce, milli/mldsa/mldsa_intt_sub, milli/mldsa/mldsa_ntt_z, mldsa/mldsa_div_rem_q, mldsa/mldsa_use_hint, shift, size_cyclic, slip/slip_placements, typed/typed_varint_static