euc_lib/
traits.rs

1use crate::EucRes;
2extern crate num;
3use num::{ One, Zero, Signed};
4
5pub trait EucExt<T>
6where
7    T: One
8        + Zero
9        + Copy
10        + std::ops::Mul<Output = T>
11        + std::ops::Div<Output = T>
12        + std::ops::Rem<Output = T>
13        + std::ops::Sub<Output = T>
14        + std::cmp::Ord,
15{
16    
17    /// Returns extended euclidean algorithm result.
18    fn euc_ext(mut d1: T, mut d2: T) -> EucRes<T> {
19        let (mut spp, mut sp) = (T::one(), T::zero());
20        let (mut tpp, mut tp) = (T::zero(), T::one());
21        let mut q = d1 / d2;
22
23        loop {
24            (d1, d2) = (d2, d1 % d2);
25            if d2 == T::zero() {
26                break;
27            }
28            (spp, sp, tpp, tp) = (sp, spp - (q * sp), tp, tpp - (q * tp));
29            q = d1 / d2;
30        }
31
32        return EucRes {
33            d: d1,
34            s: sp,
35            t: tp,
36        };
37    }
38}
39
40pub trait Euc<T>
41where
42    T: std::ops::Rem<Output = T> + Zero + std::cmp::Ord + Copy,
43{
44    /// Returns normal euclidean algorithm result.
45    fn euc(mut d1: T, mut d2: T) -> T {
46        while d2 != T::zero() {
47            (d1, d2) = (d2, d1 % d2);
48        }
49        return d1;
50    }
51
52    /// Returns normal euclidean algorithm result from 2 or more numbers.
53    fn euc_from_vec(mut d: Vec<T>) -> Result<T, String> {
54        if d.len() == 2 {
55            return Ok(Self::euc(d[0], d[1]));
56        } else if d.len() < 2 {
57            return Err(
58                "critical error occured, length of vector smaller than 2, unable to calculate euc"
59                    .to_owned(),
60            );
61        }
62        Ok(Self::euc(
63            d.pop().expect("error occured calculating euc"),
64            match Self::euc_from_vec(d.clone()) {
65                Ok(res) => res,
66                Err(err) => return Err(err),
67            },
68        ))
69    }
70
71    /// Returns normal euclidean algorithm result but uses recursion insted of loop.
72    fn euc_recursive(mut d1: T, mut d2: T) -> T {
73        if d1 > d2 {
74            (d1, d2) = (d2, d1)
75        }
76        if d1 % d2 == T::zero() {
77            return d2;
78        } else {
79            Self::euc_recursive(d2, d1 % d2)
80        }
81    }
82}
83
84pub trait Lcm<T>: self::Euc<T> + self::Euc<T>
85where
86    T: std::ops::Mul<Output = T> + std::ops::Rem<Output = T> + Zero + std::cmp::Ord + Copy + Signed,
87{
88
89    /// Returns least common multiple.
90    fn lcm(d1: T, d2: T) -> T {
91        T::abs(&(d1 * d2)) / Self::euc(d1, d2)
92    }
93
94    /// Returns least common multiple but uses recursive euclides.
95    fn lcm_recursive(d1: T, d2: T) -> T {
96        T::abs(&(d1 * d2)) / Self::euc_recursive(d1, d2)
97    }
98
99    /// Returns least common multiple from 2 or more numbers.
100    fn lcm_from_vec(mut d: Vec<T>) -> Result<T, String> {
101        if d.len() == 2 {
102            return Ok(Self::lcm(d[0], d[1]));
103        } else if d.len() < 2 {
104            return Err(
105                "critical error occured, length of vector smaller than 2, unable to calculate lcm"
106                    .to_owned(),
107            );
108        }
109        Ok(Self::lcm(
110            d.pop().expect("error occured calculating lcm"),
111            match Self::lcm_from_vec(d.clone()) {
112                Ok(res) => res,
113                Err(err) => return Err(err),
114            },
115        ))
116    }
117}
118
119pub trait Congruence<T>: self::EucExt<T>
120where
121    T: One
122        + Zero
123        + Copy
124        + std::ops::Mul<Output = T>
125        + std::ops::Div<Output = T>
126        + std::ops::Rem<Output = T>
127        + std::ops::Sub<Output = T>
128        + std::cmp::Ord,
129{
130    /// Returns congruence result 
131    /// 8x = 2 (mod 17)
132    /// ax = b (mod n)
133    fn congruence(mut a: T, mut b: T, n: T) -> Result<T, String> {
134        a = a % n;
135        b = b % n;
136        let ecr = Self::euc_ext(a, n);
137
138        if b % ecr.d != T::zero() {
139            return Err("Error occured b%euc_ext(a,n) != 0".to_owned());
140        }
141        let x = (ecr.s * (b / ecr.d)) % n;
142        if x > T::zero() {
143            return Ok(x);
144        }
145        return Ok(x + n);
146    }
147}
euc_lib/traits.rs

euc_lib/
traits.rs
