crypto_bigint/uint/
inv_mod.rs

Help
1use super::UInt;
2use crate::Limb;
3
4impl<const LIMBS: usize> UInt<LIMBS> {
5    /// Computes 1/`self` mod 2^k as specified in Algorithm 4 from
6    /// A Secure Algorithm for Inversion Modulo 2k by
7    /// Sadiel de la Fe and Carles Ferrer. See
8    /// <https://www.mdpi.com/2410-387X/2/3/23>.
9    ///
10    /// Conditions: `self` < 2^k and `self` must be odd
11    pub const fn inv_mod2k(&self, k: usize) -> Self {
12        let mut x = Self::ZERO;
13        let mut b = Self::ONE;
14        let mut i = 0;
15
16        while i < k {
17            let mut x_i = Self::ZERO;
18            let j = b.limbs[0].0 & 1;
19            x_i.limbs[0] = Limb(j);
20            x = x.bitor(&x_i.shl_vartime(i));
21
22            let t = b.wrapping_sub(self);
23            b = Self::ct_select(b, t, j.wrapping_neg()).shr_vartime(1);
24            i += 1;
25        }
26        x
27    }
28}
29
30#[cfg(test)]
31mod tests {
32    use crate::U256;
33
34    #[test]
35    fn inv_mod2k() {
36        let v = U256::from_be_slice(&[
37            0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
38            0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe,
39            0xff, 0xff, 0xfc, 0x2f,
40        ]);
41        let e = U256::from_be_slice(&[
42            0x36, 0x42, 0xe6, 0xfa, 0xea, 0xac, 0x7c, 0x66, 0x63, 0xb9, 0x3d, 0x3d, 0x6a, 0x0d,
43            0x48, 0x9e, 0x43, 0x4d, 0xdc, 0x01, 0x23, 0xdb, 0x5f, 0xa6, 0x27, 0xc7, 0xf6, 0xe2,
44            0x2d, 0xda, 0xca, 0xcf,
45        ]);
46        let a = v.inv_mod2k(256);
47        assert_eq!(e, a);
48
49        let v = U256::from_be_slice(&[
50            0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
51            0xff, 0xfe, 0xba, 0xae, 0xdc, 0xe6, 0xaf, 0x48, 0xa0, 0x3b, 0xbf, 0xd2, 0x5e, 0x8c,
52            0xd0, 0x36, 0x41, 0x41,
53        ]);
54        let e = U256::from_be_slice(&[
55            0x26, 0x17, 0x76, 0xf2, 0x9b, 0x6b, 0x10, 0x6c, 0x76, 0x80, 0xcf, 0x3e, 0xd8, 0x30,
56            0x54, 0xa1, 0xaf, 0x5a, 0xe5, 0x37, 0xcb, 0x46, 0x13, 0xdb, 0xb4, 0xf2, 0x00, 0x99,
57            0xaa, 0x77, 0x4e, 0xc1,
58        ]);
59        let a = v.inv_mod2k(256);
60        assert_eq!(e, a);
61    }
62}
crypto_bigint/uint/inv_mod.rs

crypto_bigint/uint/
inv_mod.rs
