power_mod/
lib.rs

1mod errors;
2
3pub use errors::{Error, Result};
4use num::{
5    bigint::BigInt,
6    traits::{One, Zero},
7    Bounded, Num,
8};
9use std::ops::Shr;
10
11/// Fast modular exponentiation.
12pub fn power_mod_fast<A>(a: A, e: A, m: A) -> A
13where
14    A: Copy + PartialOrd + Num + Bounded,
15    A: Shr<A, Output = A>,
16{
17    let zero: A = Zero::zero();
18    let one: A = One::one();
19    let two: A = one + one;
20    let max: A = Bounded::max_value();
21    assert!(m != zero);
22    assert!((m - one) < (max / (m - one)));
23
24    let mut result = one;
25    let mut base = a % m;
26    let mut exponent = e;
27
28    loop {
29        if exponent <= zero {
30            break;
31        }
32        if exponent % two == one {
33            result = (result * base) % m;
34        }
35        exponent = exponent >> one;
36        base = (base * base) % m;
37    }
38
39    result
40}
41
42pub fn power_mod<A, E, M>(a: &A, e: &E, m: &M) -> BigInt
43where
44    A: Into<BigInt> + Clone,
45    E: Into<BigInt> + Clone,
46    M: Into<BigInt> + Clone,
47{
48    let zero: BigInt = Zero::zero();
49    let a: BigInt = a.clone().into();
50    let e: BigInt = e.clone().into();
51    let m: BigInt = m.clone().into();
52    assert!(e >= zero);
53    a.modpow(&e, &m)
54}
power_mod/lib.rs

power_mod/
lib.rs
