dcrypt_common/
math_common.rs

1//! Common mathematical operations for cryptographic algorithms
2
3/// Perform modular exponentiation (a^b mod m)
4///
5/// Implements the square-and-multiply algorithm for efficient
6/// modular exponentiation.
7pub fn mod_exp(a: u64, b: u64, m: u64) -> u64 {
8    if m == 1 {
9        return 0;
10    }
11
12    let mut result = 1;
13    let mut base = a % m;
14    let mut exp = b;
15
16    while exp > 0 {
17        if exp % 2 == 1 {
18            result = (result * base) % m;
19        }
20
21        exp >>= 1;
22        base = (base * base) % m;
23    }
24
25    result
26}
27
28/// Compute the greatest common divisor of two numbers
29pub fn gcd(a: u64, b: u64) -> u64 {
30    if b == 0 {
31        return a;
32    }
33
34    gcd(b, a % b)
35}
36
37/// Extended Euclidean algorithm to compute a^(-1) mod m
38pub fn mod_inv(a: u64, m: u64) -> Option<u64> {
39    if m == 0 || m == 1 {
40        return None; // No modular inverse exists
41    }
42
43    // Ensure a is within the range [1, m-1]
44    let a = a % m;
45    if a == 0 {
46        return None; // No modular inverse exists for 0
47    }
48
49    // Initialize variables for the extended Euclidean algorithm
50    let mut a = a as i64;
51    let m_orig = m as i64;
52    let mut m = m_orig;
53
54    let mut x0: i64 = 1;
55    let mut x1: i64 = 0;
56
57    // Apply the extended Euclidean algorithm
58    while a > 1 {
59        if m == 0 {
60            return None; // No modular inverse exists (not coprime)
61        }
62
63        let q = a / m;
64        let temp = m;
65
66        m = a % m;
67        a = temp;
68
69        let temp = x1;
70        x1 = x0 - q * x1;
71        x0 = temp;
72    }
73
74    // Ensure the result is positive
75    if x0 < 0 {
76        x0 += m_orig;
77    }
78
79    if a == 1 {
80        Some(x0 as u64)
81    } else {
82        // No modular inverse exists
83        None
84    }
85}
86
87/// Perform modular addition: (a + b) mod m
88pub fn mod_add(a: u64, b: u64, m: u64) -> u64 {
89    (a + b) % m
90}
91
92/// Perform modular subtraction: (a - b) mod m
93pub fn mod_sub(a: u64, b: u64, m: u64) -> u64 {
94    (a + m - (b % m)) % m
95}
96
97/// Perform modular multiplication: (a * b) mod m
98pub fn mod_mul(a: u64, b: u64, m: u64) -> u64 {
99    (a * b) % m
100}
dcrypt_common/math_common.rs

dcrypt_common/
math_common.rs
