dashu_int/modular/
div.rs

1use crate::{
2    buffer::Buffer,
3    div_const::ConstLargeDivisor,
4    error::panic_divide_by_invalid_modulo,
5    gcd,
6    helper_macros::{debug_assert_zero, forward_modular_binop_to_ref_ref},
7    memory::MemoryAllocation,
8    primitive::{locate_top_word_plus_one, lowest_dword},
9    shift::{shl_in_place, shr_in_place},
10    Sign,
11};
12
13use core::ops::{Deref, Div, DivAssign};
14
15use super::{
16    add::negate_in_place,
17    repr::{Reduced, ReducedDword, ReducedLarge, ReducedRepr, ReducedWord},
18};
19use num_modular::Reducer;
20
21impl<'a> Reduced<'a> {
22    /// Multiplicative inverse.
23    ///
24    /// # Examples
25    ///
26    /// ```
27    /// # use dashu_int::{fast_div::ConstDivisor, UBig};
28    /// // A Mersenne prime.
29    /// let p = UBig::from(2u8).pow(127) - UBig::ONE;
30    /// let ring = ConstDivisor::new(p.clone());
31    /// // Fermat's little theorem: a^(p-2) = a^-1 (mod p)
32    /// let a = ring.reduce(123);
33    /// let ainv = a.clone().inv().unwrap();
34    /// assert_eq!(ainv, a.pow(&(p - UBig::from(2u8))));
35    /// assert_eq!((a * ainv).residue(), UBig::ONE);
36    /// ```
37    #[inline]
38    pub fn inv(&self) -> Option<Reduced<'a>> {
39        match self.repr() {
40            ReducedRepr::Single(raw, ring) => ring
41                .0
42                .inv(raw.0)
43                .map(|v| Reduced::from_single(ReducedWord(v), ring)),
44            ReducedRepr::Double(raw, ring) => ring
45                .0
46                .inv(raw.0)
47                .map(|v| Reduced::from_double(ReducedDword(v), ring)),
48            ReducedRepr::Large(raw, ring) => {
49                inv_large(ring, raw.clone()).map(|v| Reduced::from_large(v, ring))
50            }
51        }
52    }
53}
54
55fn inv_large(ring: &ConstLargeDivisor, mut raw: ReducedLarge) -> Option<ReducedLarge> {
56    // prepare modulus
57    let mut modulus = Buffer::from(ring.normalized_divisor.deref());
58    debug_assert_zero!(shr_in_place(&mut modulus, ring.shift));
59
60    // prepare modulo value
61    debug_assert_zero!(shr_in_place(&mut raw.0, ring.shift));
62    let raw_len = locate_top_word_plus_one(&raw.0);
63
64    // call extended gcd
65    let (is_g_one, b_sign) = match raw_len {
66        0 => return None,
67        1 => {
68            let (g, _, b_sign) = gcd::gcd_ext_word(&mut modulus, *raw.0.first().unwrap());
69            (g == 1, b_sign)
70        }
71        2 => {
72            let (g, _, b_sign) = gcd::gcd_ext_dword(&mut modulus, lowest_dword(&raw.0));
73            (g == 1, b_sign)
74        }
75        _ => {
76            let mut allocation =
77                MemoryAllocation::new(gcd::memory_requirement_ext_exact(modulus.len(), raw_len));
78            let (g_len, b_len, b_sign) = gcd::gcd_ext_in_place(
79                &mut modulus,
80                &mut raw.0[..raw_len],
81                &mut allocation.memory(),
82            );
83            modulus[b_len..].fill(0);
84
85            // check if inverse exists
86            (g_len == 1 && *raw.0.first().unwrap() == 1, b_sign)
87        }
88    };
89    if !is_g_one {
90        return None;
91    }
92
93    // return inverse
94    shl_in_place(&mut modulus, ring.shift);
95    let mut inv = ReducedLarge(modulus.into_boxed_slice());
96    debug_assert!(inv.is_valid(ring));
97    if b_sign == Sign::Negative {
98        negate_in_place(ring, &mut inv);
99    }
100    Some(inv)
101}
102
103forward_modular_binop_to_ref_ref!(impl Div, div, DivAssign, div_assign for Reduced);
104
105impl<'a> Div<&Reduced<'a>> for &Reduced<'a> {
106    type Output = Reduced<'a>;
107
108    #[inline]
109    fn div(self, rhs: &Reduced<'a>) -> Reduced<'a> {
110        // Clippy doesn't like that div is implemented using mul.
111        #[allow(clippy::suspicious_arithmetic_impl)]
112        match rhs.inv() {
113            None => panic_divide_by_invalid_modulo(),
114            Some(inv_rhs) => self * inv_rhs,
115        }
116    }
117}
dashu_int/modular/div.rs

dashu_int/modular/
div.rs
