ibig 0.3.6

A big integer library with good performance
Documentation 
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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123

use crate::{
    arch::word::Word,
    ibig::IBig,
    modular::modulo::{Modulo, ModuloLarge, ModuloRepr, ModuloSmall, ModuloSmallRaw},
    ops::RemEuclid,
    ubig::UBig,
};
use core::{
    convert::TryInto,
    ops::{Div, DivAssign},
};

impl<'a> Modulo<'a> {
    /// Inverse.
    ///
    /// Returns `None` if there is no unique inverse.
    ///
    /// # Examples
    ///
    /// ```
    /// # use ibig::{modular::ModuloRing, ubig};
    /// let ring = ModuloRing::new(&ubig!(10));
    /// assert_eq!(ring.from(7).inverse(), Some(ring.from(3)));
    /// assert_eq!(ring.from(2).inverse(), None);
    /// ```
    pub fn inverse(&self) -> Option<Modulo<'a>> {
        match self.repr() {
            ModuloRepr::Small(self_small) => self_small.inverse().map(Into::into),
            ModuloRepr::Large(self_large) => self_large.inverse().map(Into::into),
        }
    }
}

impl<'a> Div<Modulo<'a>> for Modulo<'a> {
    type Output = Modulo<'a>;

    #[inline]
    fn div(self, rhs: Modulo<'a>) -> Modulo<'a> {
        (&self).div(&rhs)
    }
}

impl<'a> Div<&Modulo<'a>> for Modulo<'a> {
    type Output = Modulo<'a>;

    #[inline]
    fn div(self, rhs: &Modulo<'a>) -> Modulo<'a> {
        (&self).div(rhs)
    }
}

impl<'a> Div<Modulo<'a>> for &Modulo<'a> {
    type Output = Modulo<'a>;

    #[inline]
    fn div(self, rhs: Modulo<'a>) -> Modulo<'a> {
        self.div(&rhs)
    }
}

impl<'a> Div<&Modulo<'a>> for &Modulo<'a> {
    type Output = Modulo<'a>;

    #[inline]
    fn div(self, rhs: &Modulo<'a>) -> Modulo<'a> {
        // Clippy doesn't like that division is implemented using multiplication.
        #[allow(clippy::suspicious_arithmetic_impl)]
        match rhs.inverse() {
            None => panic!("Division by a non-invertible Modulo"),
            Some(inv_rhs) => self * inv_rhs,
        }
    }
}

impl<'a> DivAssign<Modulo<'a>> for Modulo<'a> {
    #[inline]
    fn div_assign(&mut self, rhs: Modulo<'a>) {
        self.div_assign(&rhs)
    }
}

impl<'a> DivAssign<&Modulo<'a>> for Modulo<'a> {
    #[inline]
    fn div_assign(&mut self, rhs: &Modulo<'a>) {
        *self = (&*self).div(rhs)
    }
}

impl<'a> ModuloSmall<'a> {
    /// Inverse.
    fn inverse(&self) -> Option<ModuloSmall<'a>> {
        let a = self.residue();
        let b = self.ring().modulus();
        // TODO: Optimized `extended_gcd` for `Word`s.
        // x * a + _ * b == gcd
        let (gcd, x, _) = UBig::from(a).extended_gcd(&UBig::from(b));
        if gcd == UBig::from_word(1) {
            let res: Word = x.rem_euclid(IBig::from(b)).try_into().unwrap();
            Some(ModuloSmall::new(
                ModuloSmallRaw::from_word(res, self.ring()),
                self.ring(),
            ))
        } else {
            None
        }
    }
}

impl<'a> ModuloLarge<'a> {
    /// Inverse.
    fn inverse(&self) -> Option<ModuloLarge<'a>> {
        let a = self.residue();
        let b = self.ring().modulus();
        let (gcd, x, _) = a.extended_gcd(&b);
        if gcd == UBig::from_word(1) {
            // TODO: Get rid of redundant remainder computations.
            let res: UBig = x.rem_euclid(IBig::from(b)).try_into().unwrap();
            Some(ModuloLarge::from_ubig(res, self.ring()))
        } else {
            None
        }
    }
}