/rust/registry/src/index.crates.io-6f17d22bba15001f/num-bigint-0.4.6/src/biguint/power.rs

Source (jump to first uncovered line)
use super::monty::monty_modpow;
use super::BigUint;

use crate::big_digit::{self, BigDigit};

use num_integer::Integer;
use num_traits::{One, Pow, ToPrimitive, Zero};

impl Pow<&BigUint> for BigUint {
    type Output = BigUint;

    #[inline]
    fn pow(self, exp: &BigUint) -> BigUint {
        if self.is_one() || exp.is_zero() {
            BigUint::one()
        } else if self.is_zero() {
            Self::ZERO
        } else if let Some(exp) = exp.to_u64() {
            self.pow(exp)
        } else if let Some(exp) = exp.to_u128() {
            self.pow(exp)
        } else {
            // At this point, `self >= 2` and `exp >= 2¹²⁸`. The smallest possible result given
            // `2.pow(2¹²⁸)` would require far more memory than 64-bit targets can address!
            panic!("memory overflow")
        }
    }
}

impl Pow<BigUint> for BigUint {
    type Output = BigUint;

    #[inline]
    fn pow(self, exp: BigUint) -> BigUint {
        Pow::pow(self, &exp)
    }
}

impl Pow<&BigUint> for &BigUint {
    type Output = BigUint;

    #[inline]
    fn pow(self, exp: &BigUint) -> BigUint {
        if self.is_one() || exp.is_zero() {
            BigUint::one()
        } else if self.is_zero() {
            BigUint::ZERO
        } else {
            self.clone().pow(exp)
        }
    }
}

impl Pow<BigUint> for &BigUint {
    type Output = BigUint;

    #[inline]
    fn pow(self, exp: BigUint) -> BigUint {
        Pow::pow(self, &exp)
    }
}

macro_rules! pow_impl {
    ($T:ty) => {
        impl Pow<$T> for BigUint {
            type Output = BigUint;

            fn pow(self, mut exp: $T) -> BigUint {
                if exp == 0 {
                    return BigUint::one();
                }
                let mut base = self;

                while exp & 1 == 0 {
                    base = &base * &base;
                    exp >>= 1;
                }

                if exp == 1 {
                    return base;
                }

                let mut acc = base.clone();
                while exp > 1 {
                    exp >>= 1;
                    base = &base * &base;
                    if exp & 1 == 1 {
                        acc *= &base;
                    }
                }
                acc
            }
        }

        impl Pow<&$T> for BigUint {
            type Output = BigUint;

            #[inline]
            fn pow(self, exp: &$T) -> BigUint {
                Pow::pow(self, *exp)
            }
        }

        impl Pow<$T> for &BigUint {
            type Output = BigUint;

            #[inline]
            fn pow(self, exp: $T) -> BigUint {
                if exp == 0 {
                    return BigUint::one();
                }
                Pow::pow(self.clone(), exp)
            }
        }

        impl Pow<&$T> for &BigUint {
            type Output = BigUint;

            #[inline]
            fn pow(self, exp: &$T) -> BigUint {
                Pow::pow(self, *exp)
            }
        }
    };
}

pow_impl!(u8);
pow_impl!(u16);
pow_impl!(u32);
pow_impl!(u64);
pow_impl!(usize);
pow_impl!(u128);

pub(super) fn modpow(x: &BigUint, exponent: &BigUint, modulus: &BigUint) -> BigUint {
    assert!(
        !modulus.is_zero(),
        "attempt to calculate with zero modulus!"
    );

    if modulus.is_odd() {
        // For an odd modulus, we can use Montgomery multiplication in base 2^32.
        monty_modpow(x, exponent, modulus)
    } else {
        // Otherwise do basically the same as `num::pow`, but with a modulus.
        plain_modpow(x, &exponent.data, modulus)
    }
}

fn plain_modpow(base: &BigUint, exp_data: &[BigDigit], modulus: &BigUint) -> BigUint {
    assert!(
        !modulus.is_zero(),
        "attempt to calculate with zero modulus!"
    );

    let i = match exp_data.iter().position(|&r| r != 0) {
        None => return BigUint::one(),
        Some(i) => i,
    };

    let mut base = base % modulus;
    for _ in 0..i {
        for _ in 0..big_digit::BITS {
            base = &base * &base % modulus;
        }
    }

    let mut r = exp_data[i];
    let mut b = 0u8;
    while r.is_even() {
        base = &base * &base % modulus;
        r >>= 1;
        b += 1;
    }

    let mut exp_iter = exp_data[i + 1..].iter();
    if exp_iter.len() == 0 && r.is_one() {
        return base;
    }

    let mut acc = base.clone();
    r >>= 1;
    b += 1;

    {
        let mut unit = |exp_is_odd| {
            base = &base * &base % modulus;
            if exp_is_odd {
                acc *= &base;
                acc %= modulus;
            }
        };

        if let Some(&last) = exp_iter.next_back() {
            // consume exp_data[i]
            for _ in b..big_digit::BITS {
                unit(r.is_odd());
                r >>= 1;
            }

            // consume all other digits before the last
            for &r in exp_iter {
                let mut r = r;
                for _ in 0..big_digit::BITS {
                    unit(r.is_odd());
                    r >>= 1;
                }
            }
            r = last;
        }

        debug_assert_ne!(r, 0);
        while !r.is_zero() {
            unit(r.is_odd());
            r >>= 1;
        }
    }
    acc
}

#[test]
fn test_plain_modpow() {
    let two = &BigUint::from(2u32);
    let modulus = BigUint::from(0x1100u32);

    let exp = vec![0, 0b1];
    assert_eq!(
        two.pow(0b1_00000000_u32) % &modulus,
        plain_modpow(two, &exp, &modulus)
    );
    let exp = vec![0, 0b10];
    assert_eq!(
        two.pow(0b10_00000000_u32) % &modulus,
        plain_modpow(two, &exp, &modulus)
    );
    let exp = vec![0, 0b110010];
    assert_eq!(
        two.pow(0b110010_00000000_u32) % &modulus,
        plain_modpow(two, &exp, &modulus)
    );
    let exp = vec![0b1, 0b1];
    assert_eq!(
        two.pow(0b1_00000001_u32) % &modulus,
        plain_modpow(two, &exp, &modulus)
    );
    let exp = vec![0b1100, 0, 0b1];
    assert_eq!(
        two.pow(0b1_00000000_00001100_u32) % &modulus,
        plain_modpow(two, &exp, &modulus)
    );
}

#[test]
fn test_pow_biguint() {
    let base = BigUint::from(5u8);
    let exponent = BigUint::from(3u8);

    assert_eq!(BigUint::from(125u8), base.pow(exponent));
}

Coverage Report

Created: 2025-07-23 07:29

Line	Count	Source (jump to first uncovered line)
1		use super::monty::monty_modpow;
2		use super::BigUint;
3
4		use crate::big_digit::{self, BigDigit};
5
6		use num_integer::Integer;
7		use num_traits::{One, Pow, ToPrimitive, Zero};
8
9		impl Pow<&BigUint> for BigUint {
10		type Output = BigUint;
11
12		#[inline]
13	0	fn pow(self, exp: &BigUint) -> BigUint {
14	0	if self.is_one() \|\| exp.is_zero() {
15	0	BigUint::one()
16	0	} else if self.is_zero() {
17	0	Self::ZERO
18	0	} else if let Some(exp) = exp.to_u64() {
19	0	self.pow(exp)
20	0	} else if let Some(exp) = exp.to_u128() {
21	0	self.pow(exp)
22		} else {
23		// At this point, `self >= 2` and `exp >= 2¹²⁸`. The smallest possible result given
24		// `2.pow(2¹²⁸)` would require far more memory than 64-bit targets can address!
25	0	panic!("memory overflow")
26		}
27	0	}
28		}
29
30		impl Pow<BigUint> for BigUint {
31		type Output = BigUint;
32
33		#[inline]
34	0	fn pow(self, exp: BigUint) -> BigUint {
35	0	Pow::pow(self, &exp)
36	0	}
37		}
38
39		impl Pow<&BigUint> for &BigUint {
40		type Output = BigUint;
41
42		#[inline]
43	0	fn pow(self, exp: &BigUint) -> BigUint {
44	0	if self.is_one() \|\| exp.is_zero() {
45	0	BigUint::one()
46	0	} else if self.is_zero() {
47	0	BigUint::ZERO
48		} else {
49	0	self.clone().pow(exp)
50		}
51	0	}
52		}
53
54		impl Pow<BigUint> for &BigUint {
55		type Output = BigUint;
56
57		#[inline]
58	0	fn pow(self, exp: BigUint) -> BigUint {
59	0	Pow::pow(self, &exp)
60	0	}
61		}
62
63		macro_rules! pow_impl {
64		($T:ty) => {
65		impl Pow<$T> for BigUint {
66		type Output = BigUint;
67
68	0	fn pow(self, mut exp: $T) -> BigUint {
69	0	if exp == 0 {
70	0	return BigUint::one();
71	0	}
72	0	let mut base = self;
73
74	0	while exp & 1 == 0 {
75	0	base = &base * &base;
76	0	exp >>= 1;
77	0	}
78
79	0	if exp == 1 {
80	0	return base;
81	0	}
82	0
83	0	let mut acc = base.clone();
84	0	while exp > 1 {
85	0	exp >>= 1;
86	0	base = &base * &base;
87	0	if exp & 1 == 1 {
88	0	acc *= &base;
89	0	}
90		}
91	0	acc
92	0	} Unexecuted instantiation: <num_bigint::biguint::BigUint as num_traits::pow::Pow<u8>>::pow Unexecuted instantiation: <num_bigint::biguint::BigUint as num_traits::pow::Pow<u16>>::pow Unexecuted instantiation: <num_bigint::biguint::BigUint as num_traits::pow::Pow<u32>>::pow Unexecuted instantiation: <num_bigint::biguint::BigUint as num_traits::pow::Pow<u64>>::pow Unexecuted instantiation: <num_bigint::biguint::BigUint as num_traits::pow::Pow<usize>>::pow Unexecuted instantiation: <num_bigint::biguint::BigUint as num_traits::pow::Pow<u128>>::pow
93		}
94
95		impl Pow<&$T> for BigUint {
96		type Output = BigUint;
97
98		#[inline]
99	0	fn pow(self, exp: &$T) -> BigUint {
100	0	Pow::pow(self, *exp)
101	0	} Unexecuted instantiation: <num_bigint::biguint::BigUint as num_traits::pow::Pow<&u8>>::pow Unexecuted instantiation: <num_bigint::biguint::BigUint as num_traits::pow::Pow<&u16>>::pow Unexecuted instantiation: <num_bigint::biguint::BigUint as num_traits::pow::Pow<&u32>>::pow Unexecuted instantiation: <num_bigint::biguint::BigUint as num_traits::pow::Pow<&u64>>::pow Unexecuted instantiation: <num_bigint::biguint::BigUint as num_traits::pow::Pow<&usize>>::pow Unexecuted instantiation: <num_bigint::biguint::BigUint as num_traits::pow::Pow<&u128>>::pow
102		}
103
104		impl Pow<$T> for &BigUint {
105		type Output = BigUint;
106
107		#[inline]
108	0	fn pow(self, exp: $T) -> BigUint {
109	0	if exp == 0 {
110	0	return BigUint::one();
111	0	}
112	0	Pow::pow(self.clone(), exp)
113	0	} Unexecuted instantiation: <&num_bigint::biguint::BigUint as num_traits::pow::Pow<u8>>::pow Unexecuted instantiation: <&num_bigint::biguint::BigUint as num_traits::pow::Pow<u16>>::pow Unexecuted instantiation: <&num_bigint::biguint::BigUint as num_traits::pow::Pow<u64>>::pow Unexecuted instantiation: <&num_bigint::biguint::BigUint as num_traits::pow::Pow<usize>>::pow Unexecuted instantiation: <&num_bigint::biguint::BigUint as num_traits::pow::Pow<u128>>::pow Unexecuted instantiation: <&num_bigint::biguint::BigUint as num_traits::pow::Pow<u32>>::pow
114		}
115
116		impl Pow<&$T> for &BigUint {
117		type Output = BigUint;
118
119		#[inline]
120	0	fn pow(self, exp: &$T) -> BigUint {
121	0	Pow::pow(self, *exp)
122	0	} Unexecuted instantiation: <&num_bigint::biguint::BigUint as num_traits::pow::Pow<&u8>>::pow Unexecuted instantiation: <&num_bigint::biguint::BigUint as num_traits::pow::Pow<&u16>>::pow Unexecuted instantiation: <&num_bigint::biguint::BigUint as num_traits::pow::Pow<&u32>>::pow Unexecuted instantiation: <&num_bigint::biguint::BigUint as num_traits::pow::Pow<&u64>>::pow Unexecuted instantiation: <&num_bigint::biguint::BigUint as num_traits::pow::Pow<&usize>>::pow Unexecuted instantiation: <&num_bigint::biguint::BigUint as num_traits::pow::Pow<&u128>>::pow
123		}
124		};
125		}
126
127		pow_impl!(u8);
128		pow_impl!(u16);
129		pow_impl!(u32);
130		pow_impl!(u64);
131		pow_impl!(usize);
132		pow_impl!(u128);
133
134	0	pub(super) fn modpow(x: &BigUint, exponent: &BigUint, modulus: &BigUint) -> BigUint {
135	0	assert!(
136	0	!modulus.is_zero(),
137	0	"attempt to calculate with zero modulus!"
138		);
139
140	0	if modulus.is_odd() {
141		// For an odd modulus, we can use Montgomery multiplication in base 2^32.
142	0	monty_modpow(x, exponent, modulus)
143		} else {
144		// Otherwise do basically the same as `num::pow`, but with a modulus.
145	0	plain_modpow(x, &exponent.data, modulus)
146		}
147	0	}
148
149	0	fn plain_modpow(base: &BigUint, exp_data: &[BigDigit], modulus: &BigUint) -> BigUint {
150	0	assert!(
151	0	!modulus.is_zero(),
152	0	"attempt to calculate with zero modulus!"
153		);
154
155	0	let i = match exp_data.iter().position(\|&r\| r != 0) {
156	0	None => return BigUint::one(),
157	0	Some(i) => i,
158	0	};
159	0
160	0	let mut base = base % modulus;
161	0	for _ in 0..i {
162	0	for _ in 0..big_digit::BITS {
163	0	base = &base * &base % modulus;
164	0	}
165		}
166
167	0	let mut r = exp_data[i];
168	0	let mut b = 0u8;
169	0	while r.is_even() {
170	0	base = &base * &base % modulus;
171	0	r >>= 1;
172	0	b += 1;
173	0	}
174
175	0	let mut exp_iter = exp_data[i + 1..].iter();
176	0	if exp_iter.len() == 0 && r.is_one() {
177	0	return base;
178	0	}
179	0
180	0	let mut acc = base.clone();
181	0	r >>= 1;
182	0	b += 1;
183	0
184	0	{
185	0	let mut unit = \|exp_is_odd\| {
186	0	base = &base * &base % modulus;
187	0	if exp_is_odd {
188	0	acc *= &base;
189	0	acc %= modulus;
190	0	}
191	0	};
192
193	0	if let Some(&last) = exp_iter.next_back() {
194		// consume exp_data[i]
195	0	for _ in b..big_digit::BITS {
196	0	unit(r.is_odd());
197	0	r >>= 1;
198	0	}
199
200		// consume all other digits before the last
201	0	for &r in exp_iter {
202	0	let mut r = r;
203	0	for _ in 0..big_digit::BITS {
204	0	unit(r.is_odd());
205	0	r >>= 1;
206	0	}
207		}
208	0	r = last;
209	0	}
210
211	0	debug_assert_ne!(r, 0);
212	0	while !r.is_zero() {
213	0	unit(r.is_odd());
214	0	r >>= 1;
215	0	}
216		}
217	0	acc
218	0	}
219
220		#[test]
221		fn test_plain_modpow() {
222		let two = &BigUint::from(2u32);
223		let modulus = BigUint::from(0x1100u32);
224
225		let exp = vec![0, 0b1];
226		assert_eq!(
227		two.pow(0b1_00000000_u32) % &modulus,
228		plain_modpow(two, &exp, &modulus)
229		);
230		let exp = vec![0, 0b10];
231		assert_eq!(
232		two.pow(0b10_00000000_u32) % &modulus,
233		plain_modpow(two, &exp, &modulus)
234		);
235		let exp = vec![0, 0b110010];
236		assert_eq!(
237		two.pow(0b110010_00000000_u32) % &modulus,
238		plain_modpow(two, &exp, &modulus)
239		);
240		let exp = vec![0b1, 0b1];
241		assert_eq!(
242		two.pow(0b1_00000001_u32) % &modulus,
243		plain_modpow(two, &exp, &modulus)
244		);
245		let exp = vec![0b1100, 0, 0b1];
246		assert_eq!(
247		two.pow(0b1_00000000_00001100_u32) % &modulus,
248		plain_modpow(two, &exp, &modulus)
249		);
250		}
251
252		#[test]
253		fn test_pow_biguint() {
254		let base = BigUint::from(5u8);
255		let exponent = BigUint::from(3u8);
256
257		assert_eq!(BigUint::from(125u8), base.pow(exponent));
258		}