mldsa_div_rem_q
stdlib/mldsa/mldsa_div_rem_q.nbv
mldsa_div_rem_q(x)
Long division of X = sum(x[t] * 1024^t) by q = 8380417, using only values below 2^31 so it works in fields of 32 bits or more even when X is larger than the field.
Limbs must be non-negative integers below 2^30. Returns (k, r) with X = q sum(k[t] * 1024^t) + r, k[t] < 1024 and r < q. With witness limbs the results are unconstrained hints. Evaluate inside static_eval! for static limbs.
- Precompiles
div_floor!,if_lt!,len!,loop!,modulo!- Used by
milli/mldsa/mldsa_reduce,mldsa/mldsa_mulmod_static
Source
# Long division of X = sum(x[t] * 1024^t) by q = 8380417, using only values
# below 2^31 so it works in fields of 32 bits or more even when X is larger
# than the field.
#
# Limbs must be non-negative integers below 2^30. Returns (k, r) with
# X = q sum(k[t] * 1024^t) + r, k[t] < 1024 and r < q. With witness limbs the
# results are unconstrained hints. Evaluate inside static_eval! for static
# limbs.
(x)
static Q = 8380417
static n = len! x
# the final carry of the normalization is below 2^21, three more digits
static digits = n + 3
# normalize into base 1024 digits
let mut d[digits]
let mut carry = 0
loop! digits, t {
let mut s = carry
if_lt! t, n {
s = s + x[t]
}
d[t] = modulo! s, 1024
carry = div_floor! s, 1024
}
# divide from the most significant digit, 5 bits at a time: rem < q < 2^23
# so rem * 32 + 31 < 2^28
let mut k[digits]
let mut rem = 0
loop! digits, i {
static t = digits - 1 - i
let cur = rem * 32 + (div_floor! d[t], 32)
let high = div_floor! cur, Q
rem = modulo! cur, Q
let cur = rem * 32 + (modulo! d[t], 32)
let low = div_floor! cur, Q
rem = modulo! cur, Q
k[t] = high * 32 + low
}
(k, rem)