1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

use crate::BigInt;

/// Generic trait to implement modular inverse.
pub trait ModInverse<R: Sized>: Sized {
    type Output: Sized;

    /// Function to calculate the [modular multiplicative
    /// inverse](https://en.wikipedia.org/wiki/Modular_multiplicative_inverse) of an integer *a* modulo *m*.
    ///
    /// TODO: references
    /// Returns the modular inverse of `self`.
    /// If none exists it returns `None`.
    fn mod_inverse(self, m: R) -> Option<Self::Output>;
}

/// Generic trait to implement extended GCD.
/// Calculates the extended eucledian algorithm.
/// See https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm for details.
/// The returned values are
/// - greatest common divisor (1)
/// - Bezout coefficients (2)
pub trait ExtendedGcd<R: Sized>: Sized {
    fn extended_gcd(self, other: R) -> (BigInt, BigInt, BigInt);
}