crypto_bigint/uint/ref_type/
invert_mod.rs

1use super::UintRef;
2use crate::Odd;
3
4impl Odd<UintRef> {
5    /// Returns the multiplicative inverse of the argument modulo 2^64. The implementation is based
6    /// on the Hurchalla's method for computing the multiplicative inverse modulo a power of two.
7    ///
8    /// For better understanding the implementation, the following paper is recommended:
9    /// J. Hurchalla, "An Improved Integer Multiplicative Inverse (modulo 2^w)",
10    /// <https://arxiv.org/pdf/2204.limbs4342.pdf>
11    ///
12    /// Variable time with respect to the number of words in `value`, however that number will be
13    /// fixed for a given integer size.
14    #[must_use]
15    pub const fn invert_mod_u64(&self) -> u64 {
16        let value = self.as_ref().lowest_u64();
17        let x = value.wrapping_mul(3) ^ 2;
18        let y = 1u64.wrapping_sub(x.wrapping_mul(value));
19        let (x, y) = (x.wrapping_mul(y.wrapping_add(1)), y.wrapping_mul(y));
20        let (x, y) = (x.wrapping_mul(y.wrapping_add(1)), y.wrapping_mul(y));
21        let (x, y) = (x.wrapping_mul(y.wrapping_add(1)), y.wrapping_mul(y));
22        x.wrapping_mul(y.wrapping_add(1))
23    }
24}
25
26#[cfg(test)]
27mod tests {
28    use crate::U128;
29
30    #[test]
31    fn invert_mod_u64() {
32        let q = U128::ONE.to_odd().unwrap();
33        let inv = q.as_uint_ref().invert_mod_u64();
34        assert_eq!(inv, 0x1);
35
36        let q = U128::from(3u64).to_odd().unwrap();
37        let inv = q.as_uint_ref().invert_mod_u64();
38        assert_eq!(inv, 0xaaaaaaaaaaaaaaab);
39
40        let q = U128::from_be_hex("AAAAAAAABBBBBBBBCCCCCCCCDDDDDDDD")
41            .to_odd()
42            .unwrap();
43        let inv = q.as_uint_ref().invert_mod_u64();
44        assert_eq!(inv, 0xa6a0916b76276275);
45    }
46}
crypto_bigint/uint/ref_type/invert_mod.rs

crypto_bigint/uint/ref_type/
invert_mod.rs
