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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

// Copyright 2016 Cameron Higgins

// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at

// http://www.apache.org/licenses/LICENSE-2.0

// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.


extern crate num;

use std::ops::Mul;
use num::traits::{Zero, One};
pub use num::bigint::{ToBigInt, BigInt};
use num::iter::range_step;


// Should this function really work like this, or maybe return an Option or
// Result instead? Could be much better in the case that A.to_bigint() fails
// for whatever reason.
pub fn modexp<A>(b: A, e: A, m: A) -> BigInt
    where A: ToBigInt
{
    modexp_fast_internal(b.to_bigint().expect("Could not create bigint from base."),
                    e.to_bigint().expect("Could not create bigint from exponent."),
                    m.to_bigint().expect("Could not create bigint from modulus."))
}

pub fn modexp_slow<A>(b: A, e: A, m: A) -> BigInt
    where A: ToBigInt
{
    modexp_internal(b.to_bigint().expect("Could not create bigint from base."),
                    e.to_bigint().expect("Could not create bigint from exponent."),
                    m.to_bigint().expect("Could not create bigint from modulus."))
}

fn modexp_internal(b: BigInt, e: BigInt, m: BigInt) -> BigInt {
    if m == BigInt::one() {
        return BigInt::zero();
    }

    let mut c: BigInt = BigInt::one();

    for _ in range_step(BigInt::one(), e + BigInt::one(), BigInt::one()) {
        c = (c.mul(b.clone())) % m.clone();
    }

    c
}

fn modexp_fast_internal(mut b: BigInt, mut e: BigInt, m: BigInt) -> BigInt {
    let mut res = BigInt::one();
    let two = 2.to_bigint().unwrap();

    while e > BigInt::zero() {
        if e.clone() % two.clone() == BigInt::one() {
            res = (res.clone() * b.clone()) % m.clone();
        }

        b = (b.clone() * b.clone()) % m.clone();
        e = e.clone() / two.clone();
    }

    res % m
}

// Needs more testing. One function isn't adequate.

#[test]
fn test() {
    assert!(modexp_slow(500, 2000, 50323) == 12847.to_bigint().unwrap());
}

#[test]
fn test_fast() {
    let a = modexp(500, 2000, 50323);
    assert!(a == 12847.to_bigint().unwrap());
}