num_bigint_dig/algorithms/
mod_inverse.rs

1use alloc::borrow::Cow;
2
3use num_traits::{One, Signed};
4
5use crate::algorithms::extended_gcd;
6use crate::{BigInt, BigUint};
7
8/// Calculate the modular inverse of `g`.
9/// Implementation is based on the naive version from wikipedia.
10#[inline]
11pub fn mod_inverse(g: Cow<BigUint>, n: Cow<BigUint>) -> Option<BigInt> {
12    let (d, x, _) = extended_gcd(g, n.clone(), true);
13
14    if !d.is_one() {
15        return None;
16    }
17
18    let x = x.unwrap();
19
20    if x.is_negative() {
21        Some(x + n.as_ref())
22    } else {
23        Some(x)
24    }
25}
26
27#[cfg(test)]
28mod tests {
29    use super::*;
30
31    use alloc::vec;
32
33    use num_traits::FromPrimitive;
34
35    use crate::integer::Integer;
36    use crate::traits::ModInverse;
37
38    #[test]
39    fn test_mod_inverse() {
40        let tests = [
41            ["1234567", "458948883992"],
42            [
43                "239487239847",
44                "2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919",
45            ],
46            ["-10", "13"],
47            ["-6193420858199668535", "2881"],
48        ];
49
50        for test in &tests {
51            let element = BigInt::parse_bytes(test[0].as_bytes(), 10).unwrap();
52            let modulus = BigInt::parse_bytes(test[1].as_bytes(), 10).unwrap();
53
54            //println!("{} modinv {}", element, modulus);
55            let inverse = element.clone().mod_inverse(&modulus).unwrap();
56            //println!("inverse: {}", &inverse);
57            let cmp = (inverse * &element).mod_floor(&modulus);
58
59            assert_eq!(
60                cmp,
61                BigInt::one(),
62                "mod_inverse({}, {}) * {} % {} = {}, not 1",
63                &element,
64                &modulus,
65                &element,
66                &modulus,
67                &cmp
68            );
69        }
70
71        // exhaustive tests for small numbers
72        for n in 2..100 {
73            let modulus = BigInt::from_u64(n).unwrap();
74            for x in 1..n {
75                for sign in vec![1i64, -1i64] {
76                    let element = BigInt::from_i64(sign * x as i64).unwrap();
77                    let gcd = element.gcd(&modulus);
78
79                    if !gcd.is_one() {
80                        continue;
81                    }
82
83                    let inverse = element.clone().mod_inverse(&modulus).unwrap();
84                    let cmp = (&inverse * &element).mod_floor(&modulus);
85                    //println!("inverse: {}", &inverse);
86                    assert_eq!(
87                        cmp,
88                        BigInt::one(),
89                        "mod_inverse({}, {}) * {} % {} = {}, not 1",
90                        &element,
91                        &modulus,
92                        &element,
93                        &modulus,
94                        &cmp
95                    );
96                }
97            }
98        }
99    }
100}
num_bigint_dig/algorithms/mod_inverse.rs

num_bigint_dig/algorithms/
mod_inverse.rs
