malachite_base/num/arithmetic/
mod_inverse.rs

1// Copyright © 2026 Mikhail Hogrefe
2//
3// This file is part of Malachite.
4//
5// Malachite is free software: you can redistribute it and/or modify it under the terms of the GNU
6// Lesser General Public License (LGPL) as published by the Free Software Foundation; either version
7// 3 of the License, or (at your option) any later version. See <https://www.gnu.org/licenses/>.
8
9use crate::num::arithmetic::mod_div::gcdinv;
10use crate::num::arithmetic::traits::ModInverse;
11use crate::num::basic::signeds::PrimitiveSigned;
12use crate::num::basic::unsigneds::PrimitiveUnsigned;
13use crate::num::conversion::traits::WrappingFrom;
14
15// The modular inverse is unique, so filtering the cofactor from `gcdinv` on the GCD being 1
16// produces the same value as any other algorithm.
17private_test_fn! {mod_inverse_binary<
18    U: WrappingFrom<S> + PrimitiveUnsigned,
19    S: PrimitiveSigned + WrappingFrom<U>,
20>(
21    x: U,
22    m: U,
23) -> Option<U> {
24    assert_ne!(x, U::ZERO);
25    assert!(x < m, "x must be reduced mod m, but {x} >= {m}");
26    let (gcd, inverse) = gcdinv::<U, S>(x, m);
27    if gcd == U::ONE {
28        Some(inverse)
29    } else {
30        None
31    }
32}}
33
34macro_rules! impl_mod_inverse {
35    ($u:ident, $s:ident) => {
36        impl ModInverse<$u> for $u {
37            type Output = $u;
38
39            /// Computes the multiplicative inverse of a number modulo another number $m$. The input
40            /// must be already reduced modulo $m$.
41            ///
42            /// Returns `None` if $x$ and $m$ are not coprime.
43            ///
44            /// $f(x, m) = y$, where $x, y < m$, $\gcd(x, y) = 1$, and $xy \equiv 1 \mod m$.
45            ///
46            /// # Worst-case complexity
47            /// $T(n) = O(n)$
48            ///
49            /// $M(n) = O(1)$
50            ///
51            /// where $T$ is time, $M$ is additional memory, and $n$ is
52            /// `max(self.significant_bits(), m.significant_bits())`: the extended Euclidean
53            /// algorithm on words performs $O(n)$ iterations of constant-cost word operations, with
54            /// no allocation.
55            ///
56            /// # Panics
57            /// Panics if `self` is greater than or equal to `m`.
58            ///
59            /// # Examples
60            /// See [here](super::mod_inverse#mod_inverse).
61            #[inline]
62            fn mod_inverse(self, m: $u) -> Option<$u> {
63                mod_inverse_binary::<$u, $s>(self, m)
64            }
65        }
66    };
67}
68apply_to_unsigned_signed_pairs!(impl_mod_inverse);
malachite_base/num/arithmetic/mod_inverse.rs

malachite_base/num/arithmetic/
mod_inverse.rs
