modexp/
lib.rs

1// Copyright 2016 Cameron Higgins
2
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6
7// http://www.apache.org/licenses/LICENSE-2.0
8
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15
16extern crate num;
17
18use std::ops::Mul;
19use num::traits::{Zero, One};
20pub use num::bigint::{ToBigInt, BigInt};
21use num::iter::range_step;
22
23
24// Should this function really work like this, or maybe return an Option or
25// Result instead? Could be much better in the case that A.to_bigint() fails
26// for whatever reason.
27pub fn modexp<A>(b: A, e: A, m: A) -> BigInt
28    where A: ToBigInt
29{
30    modexp_fast_internal(b.to_bigint().expect("Could not create bigint from base."),
31                    e.to_bigint().expect("Could not create bigint from exponent."),
32                    m.to_bigint().expect("Could not create bigint from modulus."))
33}
34
35pub fn modexp_slow<A>(b: A, e: A, m: A) -> BigInt
36    where A: ToBigInt
37{
38    modexp_internal(b.to_bigint().expect("Could not create bigint from base."),
39                    e.to_bigint().expect("Could not create bigint from exponent."),
40                    m.to_bigint().expect("Could not create bigint from modulus."))
41}
42
43fn modexp_internal(b: BigInt, e: BigInt, m: BigInt) -> BigInt {
44    if m == BigInt::one() {
45        return BigInt::zero();
46    }
47
48    let mut c: BigInt = BigInt::one();
49
50    for _ in range_step(BigInt::one(), e + BigInt::one(), BigInt::one()) {
51        c = (c.mul(b.clone())) % m.clone();
52    }
53
54    c
55}
56
57fn modexp_fast_internal(mut b: BigInt, mut e: BigInt, m: BigInt) -> BigInt {
58    let mut res = BigInt::one();
59    let two = 2.to_bigint().unwrap();
60
61    while e > BigInt::zero() {
62        if e.clone() % two.clone() == BigInt::one() {
63            res = (res.clone() * b.clone()) % m.clone();
64        }
65
66        b = (b.clone() * b.clone()) % m.clone();
67        e = e.clone() / two.clone();
68    }
69
70    res % m
71}
72
73// Needs more testing. One function isn't adequate.
74
75#[test]
76fn test() {
77    assert!(modexp_slow(500, 2000, 50323) == 12847.to_bigint().unwrap());
78}
79
80#[test]
81fn test_fast() {
82    let a = modexp(500, 2000, 50323);
83    assert!(a == 12847.to_bigint().unwrap());
84}
modexp/lib.rs

modexp/
lib.rs
