large_primes/operations/
pow.rs

1use num_bigint::BigUint;
2use num_traits::{ One, Zero };
3
4/// Computes the power of a `BigUint` base raised to a `BigUint` exponent.
5///
6/// This function calculates `base` raised to the power of `exp` using an efficient
7/// binary exponentiation algorithm.
8///
9/// # Arguments
10///
11/// * `base` - A reference to a `BigUint` representing the base.
12/// * `exp` - A reference to a `BigUint` representing the exponent.
13///
14/// # Returns
15///
16/// The result of `base` raised to the power of `exp`.
17///
18/// # Examples
19///
20/// ```
21/// use num_bigint::BigUint;
22/// use large_primes::pow;
23/// 
24/// let base = BigUint::from(2u32);
25/// let exponent = BigUint::from(3u32);
26/// let result = pow(&base, &exponent);
27/// assert_eq!(result, BigUint::from(8u32));
28/// ```
29pub fn pow(base: &BigUint, exp: &BigUint) -> BigUint {
30    // Modular exponentiation
31    let mut result = BigUint::one();
32    let mut current_base = base.clone();
33
34    let zero = BigUint::zero();
35    let one = BigUint::one();
36
37    let two = BigUint::from(2u32);
38
39    let mut power = exp.clone();
40
41    while &power > &zero {
42        if &power % &two == one {
43            result = &result * &current_base;
44        }
45
46        let shifted_power: BigUint = &power >> 1;
47        power = shifted_power.clone();
48        current_base = &current_base * &current_base;
49    }
50
51    result
52}
53
54/// Computes the modular exponentiation of a `BigUint` base raised to a `BigUint` exponent modulo another `BigUint`.
55///
56/// This function calculates `(base ^ exp) % modulus` using an efficient binary exponentiation algorithm,
57/// which is useful for large numbers in cryptographic applications.
58///
59/// # Arguments
60///
61/// * `base` - A reference to a `BigUint` representing the base.
62/// * `exp` - A reference to a `BigUint` representing the exponent.
63/// * `modulus` - A reference to a `BigUint` representing the modulus.
64///
65/// # Returns
66///
67/// The result of `(base ^ exp) % modulus`.
68///
69/// # Examples
70///
71/// ```
72/// use num_bigint::BigUint;
73/// use large_primes::pow_mod;
74/// 
75/// let base = BigUint::from(4u32);
76/// let exponent = BigUint::from(13u32);
77/// let modulus = BigUint::from(497u32);
78/// let result = pow_mod(&base, &exponent, &modulus);
79/// assert_eq!(result, BigUint::from(445u32));
80/// ```
81pub fn pow_mod(base: &BigUint, exp: &BigUint, modulus: &BigUint) -> BigUint {
82    // Modular exponentiation
83    let mut result = BigUint::one();
84    let mut base = base % modulus;
85
86    let zero = BigUint::zero();
87    let one = BigUint::one();
88
89    let two = BigUint::from(2u32);
90
91    let mut power = exp.clone();
92
93    while &power > &zero {
94        if &power % &two == one {
95            result = (&result * &base) % modulus;
96        }
97
98        let shifted_power: BigUint = &power >> 1;
99        power = shifted_power.clone();
100        base = (&base * &base) % modulus;
101    }
102
103    result
104}
105
106#[cfg(test)]
107mod tests {
108    use super::*;
109
110    #[test]
111    fn normal_power() {
112        let base = BigUint::from(2u32);
113        let exp = BigUint::zero();
114
115        assert_eq!(pow(&base, &exp), BigUint::from(1u32));
116
117        let base = BigUint::from(2u32);
118        let exp = BigUint::from(10u32);
119
120        assert_eq!(pow(&base, &exp), BigUint::from(1024u32));
121
122        let base = BigUint::from(2u32);
123        let exp = BigUint::from(100u32);
124
125        assert_eq!(
126            pow(&base, &exp),
127            BigUint::parse_bytes(b"1267650600228229401496703205376", 10).unwrap()
128        );
129    }
130
131    #[test]
132    fn base_cases() {
133        let base = BigUint::from(2u32);
134        let exp = BigUint::from(2u32);
135        let modulus = BigUint::from(3u32);
136
137        assert_eq!(pow_mod(&base, &exp, &modulus), BigUint::from(1u32));
138
139        let base = BigUint::from(2u32);
140        let exp = BigUint::zero();
141        let modulus = BigUint::from(3u32);
142
143        assert_eq!(pow_mod(&base, &exp, &modulus), BigUint::from(1u32));
144
145        let base = BigUint::from(2u32);
146        let exp = BigUint::from(1u32);
147        let modulus = BigUint::from(2u32);
148
149        assert_eq!(pow_mod(&base, &exp, &modulus), BigUint::from(0u32));
150    }
151
152    #[test]
153    fn big_cases() {
154        let base = BigUint::from(2u32);
155        let exp = BigUint::from(10u32);
156        let modulus = BigUint::from(100u32);
157
158        assert_eq!(pow_mod(&base, &exp, &modulus), BigUint::from(24u32));
159
160        let base = BigUint::from(2u32);
161        let exp = BigUint::from(100u32);
162        let modulus = BigUint::from(1000u32);
163
164        assert_eq!(pow_mod(&base, &exp, &modulus), BigUint::from(376u32));
165
166        let base = BigUint::from(2u32);
167        let exp = BigUint::from(1000u32);
168        let modulus = BigUint::from(10000u32);
169
170        assert_eq!(pow_mod(&base, &exp, &modulus), BigUint::from(9376u32));
171
172        let base = BigUint::from(2u32);
173        let exp = BigUint::from(10000u32);
174        let modulus = BigUint::from(100000u32);
175
176        assert_eq!(pow_mod(&base, &exp, &modulus), BigUint::from(9376u32));
177    }
178}
large_primes/operations/pow.rs

large_primes/operations/
pow.rs
