div_floor!
Element-wise integer division rounding down, static or as an unconstrained witness hint. Integer and field arithmetic
div_floor! lhs, rhs
Divides lhs by rhs element-wise, rounding down, 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 quotients become new witness entries that are unconstrained hints: nothing ties them to lhs, and a dishonest prover can put any value there. The caller must constrain them, usually together with modulo! as lhs = rhs * quotient + remainder plus range checks on the quotient and remainder (for example with to_bits_exact) small enough that the equation cannot wrap around the field.
Arguments
lhs- Static or witness vector of dividends.
rhs- Static vector of nonzero divisors, the same length as
lhs.
Returns
A vector of quotients 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
A quotient and remainder by 4, constrained so they are sound for inputs below 2^10:
(let x) let q = div_floor! x, [4] let r = modulo! x, [4] # r < 4 and q < 2^8, so q * 4 + r cannot wrap around the field let _ = to_bits_exact(r, 2) let _ = to_bits_exact(q, 8) constrain_eq! x, q * 4 + r q
(let x) static q = div_floor! [7 9], [2 2] x + q
Notes
Errors: divisor must be static, division by zero, arguments are of mismatched dimension. The stdlib uses the hint form in keccak_f1600 (theta parities, each bit-checked) and mldsa_use_hint (a quotient decomposed with to_bits_exact).
Used in the standard library
bits/u32_bits_static, blake3/blake3_core, keccak/keccak_f1600, lattice/lattice_digest, mersenne61/mldsa/mldsa_reduce, mersenne61/poseidon/poseidon_mersenne61_state, milli/mldsa/mldsa_reduce, milli/poseidon/poseidon_milli_state, mldsa/mldsa_div_rem_q, mldsa/mldsa_use_hint, polynomial/poly_norm_l1, slip/slip_placements, slip/slip_r1cs_arg_verify, typed/typed_lattice_digest_bits, typed/typed_varint_len, typed/typed_varint_static