plat_core/
modular.rs

1//! Modular arithmetic utilities for lattice-based cryptography.
2
3/// Reduce `a` into [0, modulus).
4#[inline]
5pub fn mod_reduce(a: i64, modulus: u64) -> u64 {
6    let m = modulus as i64;
7    let r = a % m;
8    if r < 0 { (r + m) as u64 } else { r as u64 }
9}
10
11/// Centered representative: maps value in [0, q) to (-q/2, q/2].
12#[inline]
13pub fn center(a: u64, modulus: u64) -> i64 {
14    let a = a % modulus;
15    if a > modulus / 2 {
16        a as i64 - modulus as i64
17    } else {
18        a as i64
19    }
20}
21
22/// Modular addition: (a + b) mod q.
23#[inline]
24pub fn mod_add(a: u64, b: u64, modulus: u64) -> u64 {
25    ((a as u128 + b as u128) % modulus as u128) as u64
26}
27
28/// Modular subtraction: (a - b) mod q.
29#[inline]
30pub fn mod_sub(a: u64, b: u64, modulus: u64) -> u64 {
31    if a >= b {
32        (a - b) % modulus
33    } else {
34        modulus - ((b - a) % modulus)
35    }
36}
37
38/// Modular multiplication: (a * b) mod q.
39#[inline]
40pub fn mod_mul(a: u64, b: u64, modulus: u64) -> u64 {
41    ((a as u128 * b as u128) % modulus as u128) as u64
42}
43
44/// Modular negation: (-a) mod q.
45#[inline]
46pub fn mod_neg(a: u64, modulus: u64) -> u64 {
47    if a == 0 { 0 } else { modulus - (a % modulus) }
48}
49
50/// Modular exponentiation: a^exp mod q (for NTT root computation).
51pub fn mod_pow(mut base: u64, mut exp: u64, modulus: u64) -> u64 {
52    let mut result: u128 = 1;
53    let m = modulus as u128;
54    base %= modulus;
55    let mut b = base as u128;
56    while exp > 0 {
57        if exp & 1 == 1 {
58            result = (result * b) % m;
59        }
60        exp >>= 1;
61        b = (b * b) % m;
62    }
63    result as u64
64}
65
66/// Modular inverse via Fermat's little theorem (modulus must be prime).
67pub fn mod_inv(a: u64, modulus: u64) -> u64 {
68    mod_pow(a, modulus - 2, modulus)
69}
70
71#[cfg(test)]
72mod tests {
73    use super::*;
74
75    #[test]
76    fn test_mod_reduce_positive() {
77        assert_eq!(mod_reduce(7, 5), 2);
78    }
79
80    #[test]
81    fn test_mod_reduce_negative() {
82        assert_eq!(mod_reduce(-3, 5), 2);
83    }
84
85    #[test]
86    fn test_center() {
87        assert_eq!(center(1, 7), 1);
88        assert_eq!(center(6, 7), -1);
89        assert_eq!(center(3, 7), 3); // 3 == 7/2 = 3, not > 3
90        assert_eq!(center(4, 7), -3); // 4 > 3 → 4 - 7 = -3
91    }
92
93    #[test]
94    fn test_mod_arithmetic() {
95        let q = 97;
96        assert_eq!(mod_add(50, 60, q), 13);
97        assert_eq!(mod_sub(10, 30, q), 77);
98        assert_eq!(mod_mul(50, 50, q), (2500 % 97));
99        assert_eq!(mod_neg(10, q), 87);
100    }
101
102    #[test]
103    fn test_mod_pow() {
104        assert_eq!(mod_pow(2, 10, 1024), 0); // 1024 mod 1024 = 0
105        assert_eq!(mod_pow(3, 4, 97), 81 % 97);
106    }
107
108    #[test]
109    fn test_mod_inv() {
110        let q = 97u64;
111        for a in 1..q {
112            let inv = mod_inv(a, q);
113            assert_eq!(mod_mul(a, inv, q), 1, "inverse failed for {a}");
114        }
115    }
116}
plat_core/modular.rs

plat_core/
modular.rs
