power-mod 0.1.0

Fast mod for $a ^ b % p
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

mod errors;

pub use errors::{Error, Result};
use num::{
    bigint::BigInt,
    traits::{One, Zero},
    Bounded, Num,
};
use std::ops::Shr;

/// Fast modular exponentiation.
pub fn power_mod_fast<A>(a: A, e: A, m: A) -> A
where
    A: Copy + PartialOrd + Num + Bounded,
    A: Shr<A, Output = A>,
{
    let zero: A = Zero::zero();
    let one: A = One::one();
    let two: A = one + one;
    let max: A = Bounded::max_value();
    assert!(m != zero);
    assert!((m - one) < (max / (m - one)));

    let mut result = one;
    let mut base = a % m;
    let mut exponent = e;

    loop {
        if exponent <= zero {
            break;
        }
        if exponent % two == one {
            result = (result * base) % m;
        }
        exponent = exponent >> one;
        base = (base * base) % m;
    }

    result
}

pub fn power_mod<A, E, M>(a: &A, e: &E, m: &M) -> BigInt
where
    A: Into<BigInt> + Clone,
    E: Into<BigInt> + Clone,
    M: Into<BigInt> + Clone,
{
    let zero: BigInt = Zero::zero();
    let a: BigInt = a.clone().into();
    let e: BigInt = e.clone().into();
    let m: BigInt = m.clone().into();
    assert!(e >= zero);
    a.modpow(&e, &m)
}