Index Mathematics Conjectures nbv lettuce Widgets

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