1extern crate num;
 2extern crate num_bigint;
 3extern crate num_traits;
 4
 5use num_bigint::BigInt;
 6use num_traits::{One, Zero};
 7
 8pub fn modulus(a: &BigInt, m: &BigInt) -> BigInt {
 9    ((a % m) + m) % m
10}
11
12pub fn mod_inverse0(a: &BigInt, q: &BigInt) -> BigInt {
13    let mut mn = (q.clone(), a.clone());
14    let mut xy: (BigInt, BigInt) = (Zero::zero(), One::one());
15
16    let big_zero: BigInt = Zero::zero();
17    while mn.1 != big_zero {
18        xy = (xy.1.clone(), xy.0 - (mn.0.clone() / mn.1.clone()) * xy.1);
19        mn = (mn.1.clone(), modulus(&mn.0, &mn.1));
20    }
21
22    while xy.0 < Zero::zero() {
23        xy.0 = modulus(&xy.0, q);
24    }
25    xy.0
26}
27
28/*
29pub fn mod_inverse1(a0: BigInt, m0: BigInt) -> BigInt {
30    if m0 == One::one() {
31        return One::one();
32    }
33
34    let (mut a, mut m, mut x0, mut inv): (BigInt, BigInt, BigInt, BigInt) =
35        (a0, m0.clone(), Zero::zero(), One::one());
36
37    while a > One::one() {
38        inv = inv - (&a / m.clone()) * x0.clone();
39        a = a % m.clone();
40        std::mem::swap(&mut a, &mut m);
41        std::mem::swap(&mut x0, &mut inv);
42    }
43
44    if inv < Zero::zero() {
45        inv += m0.clone()
46    }
47    inv
48}
49
50pub fn mod_inverse2(a: BigInt, q: BigInt) -> BigInt {
51    let mut aa: BigInt = a;
52    let mut qq: BigInt = q;
53    if qq < Zero::zero() {
54        qq = -qq;
55    }
56    if aa < Zero::zero() {
57        aa = -aa;
58    }
59    let d = num::Integer::gcd(&aa, &qq);
60    if d != One::one() {
61        println!("ERR no mod_inv");
62    }
63    let res: BigInt;
64    if d < Zero::zero() {
65        res = d + qq;
66    } else {
67        res = d;
68    }
69    res
70}
71*/
72
73pub fn concatenate_arrays<T: Clone>(x: &[T], y: &[T]) -> Vec<T> {
74    x.iter().chain(y).cloned().collect()
75}
76
77#[cfg(test)]
78mod tests {
79    use super::*;
80
81    #[test]
82    fn test_mod_inverse() {
83        let a = BigInt::parse_bytes(b"123456789123456789123456789123456789123456789", 10).unwrap();
84        let b = BigInt::parse_bytes(b"12345678", 10).unwrap();
85        assert_eq!(
86            mod_inverse0(&a, &b),
87            BigInt::parse_bytes(b"641883", 10).unwrap()
88        );
89    }
90}