Index Mathematics Conjectures nbv lettuce Widgets

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)