Index Mathematics Conjectures nbv lettuce Widgets

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