use crate*;
const QINV: i32 = 62209; // q^(-1) mod 2^16
// Name: montgomery_reduce
//
// Description: Montgomery reduction; given a 32-bit integer a, computes
// 16-bit integer congruent to a * R^-1 mod q,
// where R=2^16
//
// Arguments: - i32 a: input integer to be reduced; has to be in {-q2^15,...,q2^15-1}
//
// Returns: integer in {-q+1,...,q-1} congruent to a * R^-1 modulo q.
// Name: barrett_reduce
//
// Description: Barrett reduction; given a 16-bit integer a, computes
// centered representative congruent to a mod q in {-(q-1)/2,...,(q-1)/2}
//
// Arguments: - i16 a: input integer to be reduced
//
// Returns: i16 in {-(q-1)/2,...,(q-1)/2} congruent to a modulo q.