crypto_bigint/int/
invert_mod.rs

1//! Operations related to computing the inverse of an [`Int`] modulo a [`Uint`].
2
3use crate::{CtOption, Int, InvertMod, NonZero, Odd, Uint};
4
5impl<const LIMBS: usize> Int<LIMBS> {
6    /// Computes the multiplicative inverse of `self` mod `modulus`, where `modulus` is odd.
7    #[must_use]
8    pub fn invert_odd_mod(&self, modulus: &Odd<Uint<LIMBS>>) -> CtOption<Uint<LIMBS>> {
9        let (abs, sgn) = self.abs_sign();
10        let maybe_inv = abs.invert_odd_mod(modulus);
11        let abs_inv = maybe_inv.as_inner_unchecked();
12        let neg_inv = modulus.wrapping_sub(abs_inv);
13        let neg_inv = Uint::select(&neg_inv, abs_inv, abs_inv.is_nonzero().not());
14
15        // Note: when `self` is negative and modulus is non-zero, then
16        // self^{-1} % modulus = modulus - |self|^{-1} % modulus
17        CtOption::new(Uint::select(abs_inv, &neg_inv, sgn), maybe_inv.is_some())
18    }
19
20    /// Computes the multiplicative inverse of `self` mod `modulus`.
21    ///
22    /// Returns some if an inverse exists, otherwise none.
23    #[must_use]
24    pub const fn invert_mod(&self, modulus: &NonZero<Uint<LIMBS>>) -> CtOption<Uint<LIMBS>> {
25        let (abs, sgn) = self.abs_sign();
26        let maybe_inv = abs.invert_mod(modulus);
27        let abs_inv = maybe_inv.as_inner_unchecked();
28        let neg_inv = modulus.as_ref().wrapping_sub(abs_inv);
29        let neg_inv = Uint::select(&neg_inv, abs_inv, abs_inv.is_nonzero().not());
30
31        // Note: when `self` is negative and modulus is non-zero, then
32        // self^{-1} % modulus = modulus - |self|^{-1} % modulus
33        CtOption::new(Uint::select(abs_inv, &neg_inv, sgn), maybe_inv.is_some())
34    }
35}
36
37impl<const LIMBS: usize> InvertMod<NonZero<Uint<LIMBS>>> for Int<LIMBS>
38where
39    Uint<LIMBS>: InvertMod<Output = Uint<LIMBS>>,
40{
41    type Output = Uint<LIMBS>;
42
43    fn invert_mod(&self, modulus: &NonZero<Uint<LIMBS>>) -> CtOption<Self::Output> {
44        Self::invert_mod(self, modulus)
45    }
46}
47
48#[cfg(test)]
49mod tests {
50    use crate::{I256, I1024, U256, U1024};
51
52    #[test]
53    fn negative_inverse_modulus_one_is_canonical_zero() {
54        let odd_modulus = U256::ONE.to_odd().unwrap();
55        let modulus = U256::ONE.to_nz().unwrap();
56
57        assert_eq!(
58            Option::<U256>::from(I256::MINUS_ONE.invert_odd_mod(&odd_modulus)),
59            Some(U256::ZERO)
60        );
61        assert_eq!(
62            Option::<U256>::from(I256::MINUS_ONE.invert_mod(&modulus)),
63            Some(U256::ZERO)
64        );
65        assert_eq!(Option::<U256>::from(I256::ZERO.invert_mod(&modulus)), None);
66    }
67
68    #[test]
69    fn test_invert_odd() {
70        let a = I1024::from_be_hex(concat![
71            "FFFDDA166EAC4B985A4BAE6865C0BAE2510C4072939ADE2D05DB444E80D6ABB1",
72            "CB85BED4F9A48A5CAE1568E61DBCF2DB884EE3363063E5291211D934EA0B9C07",
73            "4338D107815CFD7716A5B75586DDD93136A6234F98D270627F5AB344157A3527",
74            "C7D13DDB214D0A87B19D2F33D07E3D1952EB145419B92989B4CF3CD47897767B"
75        ]);
76        let m = U1024::from_be_hex(concat![
77            "D509E7854ABDC81921F669F1DC6F61359523F3949803E58ED4EA8BC16483DC6F",
78            "37BFE27A9AC9EEA2969B357ABC5C0EE214BE16A7D4C58FC620D5B5A20AFF001A",
79            "D198D3155E5799DC4EA76652D64983A7E130B5EACEBAC768D28D589C36EC749C",
80            "558D0B64E37CD0775C0D0104AE7D98BA23C815185DD43CD8B16292FD94156767"
81        ])
82        .to_odd()
83        .unwrap();
84        let expected = U1024::from_be_hex(concat![
85            "24D3C45CFFAF0D5C7620A469C3DC2F3313DDE78A0987F0CEF7EABFF4A5407219",
86            "645BBF1E19580A3619798AAA545597FCA2496DAA2DF4685D313F98F52DD151C3",
87            "48BF956F72C8BDA32FC3F3E5F955226B8D9138C6E64AA568075BA2AEDBE58ED2",
88            "173B01FCA9E1905F9C74589FB3C36D55A4CBCB7FA86CC803BE979091D3F0C431"
89        ]);
90
91        let res = a.invert_odd_mod(&m).unwrap();
92        assert_eq!(res, expected);
93
94        // Even though it is less efficient, it still works
95        let res = a.invert_mod(&m.to_nz().unwrap()).unwrap();
96        assert_eq!(res, expected);
97    }
98
99    #[test]
100    fn test_invert_even() {
101        let a = I1024::from_be_hex(concat![
102            "FFFDDA166EAC4B985A4BAE6865C0BAE2510C4072939ADE2D05DB444E80D6ABB1",
103            "CB85BED4F9A48A5CAE1568E61DBCF2DB884EE3363063E5291211D934EA0B9C07",
104            "4338D107815CFD7716A5B75586DDD93136A6234F98D270627F5AB344157A3527",
105            "C7D13DDB214D0A87B19D2F33D07E3D1952EB145419B92989B4CF3CD47897767B",
106        ]);
107        let m = U1024::from_be_hex(concat![
108            "D509E7854ABDC81921F669F1DC6F61359523F3949803E58ED4EA8BC16483DC6F",
109            "37BFE27A9AC9EEA2969B357ABC5C0EE214BE16A7D4C58FC620D5B5A20AFF001A",
110            "D198D3155E5799DC4EA76652D64983A7E130B5EACEBAC768D28D589C36EC749C",
111            "558D0B64E37CD0775C0D0104AE7D98BA23C815185DD43CD8B16292FD94156000"
112        ])
113        .to_nz()
114        .unwrap();
115        let expected = U1024::from_be_hex(concat![
116            "B64AAE72443C49FD5BE587DDE82A265E8C1226D73E5AE3DC3081E6C5471EE917",
117            "5BC37EF8AE73B8D7F0365652BC335F9BC375EA303381B08D4A15E0CBBF92FDF4",
118            "D58AB97A48B1507553808DC84F9C6F656F39F81D9157AE2E1FD98C487D4D52F8",
119            "F9F1107F0F4064B074637B983CB6672DAD75067A02F0E455DBB6E2CE7D7ED8B3",
120        ]);
121
122        let res = a.invert_mod(&m).unwrap();
123        assert_eq!(res, expected);
124    }
125}
crypto_bigint/int/invert_mod.rs

crypto_bigint/int/
invert_mod.rs
