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 crate::integer::Integer;
32    use num_traits::FromPrimitive;
33
34    use crate::traits::ModInverse;
35
36    #[test]
37    fn test_mod_inverse() {
38        let tests = [
39            ["1234567", "458948883992"],
40	    ["239487239847", "2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919"],
41	    ["-10", "13"],
42            ["-6193420858199668535", "2881"],
43        ];
44
45        for test in &tests {
46            let element = BigInt::parse_bytes(test[0].as_bytes(), 10).unwrap();
47            let modulus = BigInt::parse_bytes(test[1].as_bytes(), 10).unwrap();
48
49            //println!("{} modinv {}", element, modulus);
50            let inverse = element.clone().mod_inverse(&modulus).unwrap();
51            //println!("inverse: {}", &inverse);
52            let cmp = (inverse * &element).mod_floor(&modulus);
53
54            assert_eq!(
55                cmp,
56                BigInt::one(),
57                "mod_inverse({}, {}) * {} % {} = {}, not 1",
58                &element,
59                &modulus,
60                &element,
61                &modulus,
62                &cmp
63            );
64        }
65
66        // exhaustive tests for small numbers
67        for n in 2..100 {
68            let modulus = BigInt::from_u64(n).unwrap();
69            for x in 1..n {
70                for sign in vec![1i64, -1i64] {
71                    let element = BigInt::from_i64(sign * x as i64).unwrap();
72                    let gcd = element.gcd(&modulus);
73
74                    if !gcd.is_one() {
75                        continue;
76                    }
77
78                    let inverse = element.clone().mod_inverse(&modulus).unwrap();
79                    let cmp = (&inverse * &element).mod_floor(&modulus);
80                    //println!("inverse: {}", &inverse);
81                    assert_eq!(
82                        cmp,
83                        BigInt::one(),
84                        "mod_inverse({}, {}) * {} % {} = {}, not 1",
85                        &element,
86                        &modulus,
87                        &element,
88                        &modulus,
89                        &cmp
90                    );
91                }
92            }
93        }
94    }
95}
num_bigint_dig/algorithms/mod_inverse.rs

num_bigint_dig/algorithms/
mod_inverse.rs
