pqc_kyber/reference/
reduce.rs

1use crate::params::*;
2
3const QINV: i32 = 62209; // q^(-1) mod 2^16
4
5/// Name:  montgomery_reduce
6///
7/// Description: Montgomery reduction; given a 32-bit integer a, computes
8///  16-bit integer congruent to a * R^-1 mod q,
9///  where R=2^16
10///
11/// Arguments:   - i32 a: input integer to be reduced; has to be in {-q2^15,...,q2^15-1}
12///
13/// Returns:   integer in {-q+1,...,q-1} congruent to a * R^-1 modulo q.
14pub fn montgomery_reduce(a: i32) -> i16 {
15    let ua = a.wrapping_mul(QINV) as i16;
16    let u = ua as i32;
17    let mut t = u * KYBER_Q as i32;
18    t = a - t;
19    t >>= 16;
20    t as i16
21}
22
23/// Name:  barrett_reduce
24///
25/// Description: Barrett reduction; given a 16-bit integer a, computes
26///  centered representative congruent to a mod q in {-(q-1)/2,...,(q-1)/2}
27///
28/// Arguments:   - i16 a: input integer to be reduced
29///
30/// Returns:   i16 in {-(q-1)/2,...,(q-1)/2} congruent to a modulo q.
31pub fn barrett_reduce(a: i16) -> i16 {
32    let v = ((1u32 << 26) / KYBER_Q as u32 + 1) as i32;
33    let mut t = v * a as i32 + (1 << 25);
34    t >>= 26;
35    t *= KYBER_Q as i32;
36    a - t as i16
37}
pqc_kyber/reference/reduce.rs

pqc_kyber/reference/
reduce.rs
