barrettreduce function

int barrettreduce(
  1. int a
)

Barrett reduce reduces the value 'a' modulo q using the Barrett approximation. This ensures the result is in 0, q-1.

Implementation

int barrettreduce(int a) {
  // Barrett reduction according to PQClean:
  // Given q=3329, the derived constants are used for the reduction.
  //
  // Formula: a' = a - floor(a * v / 2^26) * q
  // where v = floor((2^26 + q/2)/q)

  const int v = ((1 << 26) + (KYBER_Q >> 1)) ~/ KYBER_Q;
  int t = (v * a) >> 26;
  t *= KYBER_Q;
  return a - t;
}