airbender_crypto/secp256k1/scalars/
invert.rs

1use super::Scalar;
2
3impl Scalar {
4    // using addition chain from
5    // https://briansmith.org/ecc-inversion-addition-chains-01#secp256k1_scalar_inversion
6    pub fn invert_in_place(&mut self) {
7        let x_1 = *self;
8        self.pow2k_in_place(1);
9        let x_10 = *self;
10        let mut x_11 = x_10;
11        x_11 *= x_1;
12        let mut x_101 = x_10;
13        x_101 *= x_11;
14        let mut x_111 = x_10;
15        x_111 *= x_101;
16        let mut x_1001 = x_10;
17        x_1001 *= x_111;
18        let mut x_1011 = x_10;
19        x_1011 *= x_1001;
20        *self *= x_1011;
21        let x_1101 = *self;
22        self.pow2k_in_place(2);
23        *self *= x_1011;
24        let x6 = *self;
25        self.pow2k_in_place(2);
26        *self *= x_11;
27        let x8 = *self;
28        self.pow2k_in_place(6);
29        *self *= x6;
30        let x14 = *self;
31        self.pow2k_in_place(14);
32        *self *= x14;
33        let x28 = *self;
34        self.pow2k_in_place(28);
35        *self *= x28;
36        let x56 = *self;
37        self.pow2k_in_place(56);
38        *self *= x56;
39        self.pow2k_in_place(14);
40        *self *= x14;
41        self.pow2k_in_place(3);
42        *self *= x_101;
43        self.pow2k_in_place(4);
44        *self *= x_111;
45        self.pow2k_in_place(4);
46        *self *= x_101;
47        self.pow2k_in_place(5);
48        *self *= x_1011;
49        self.pow2k_in_place(4);
50        *self *= x_1011;
51        self.pow2k_in_place(4);
52        *self *= x_111;
53        self.pow2k_in_place(5);
54        *self *= x_111;
55        self.pow2k_in_place(6);
56        *self *= x_1101;
57        self.pow2k_in_place(4);
58        *self *= x_101;
59        self.pow2k_in_place(3);
60        *self *= x_111;
61        self.pow2k_in_place(5);
62        *self *= x_1001;
63        self.pow2k_in_place(6);
64        *self *= x_101;
65        self.pow2k_in_place(10);
66        *self *= x_111;
67        self.pow2k_in_place(4);
68        *self *= x_111;
69        self.pow2k_in_place(9);
70        *self *= x8;
71        self.pow2k_in_place(5);
72        *self *= x_1001;
73        self.pow2k_in_place(6);
74        *self *= x_1011;
75        self.pow2k_in_place(4);
76        *self *= x_1101;
77        self.pow2k_in_place(5);
78        *self *= x_11;
79        self.pow2k_in_place(6);
80        *self *= x_1101;
81        self.pow2k_in_place(10);
82        *self *= x_1101;
83        self.pow2k_in_place(4);
84        *self *= x_1001;
85        self.pow2k_in_place(6);
86        *self *= x_1;
87        self.pow2k_in_place(8);
88        *self *= x6;
89    }
90
91    #[inline(always)]
92    fn pow2k_in_place(&mut self, k: usize) {
93        for _ in 0..k {
94            self.0.square_in_place();
95        }
96    }
97}
98
99#[cfg(test)]
100mod tests {
101    use super::Scalar;
102    use proptest::{prop_assert_eq, proptest};
103    #[test]
104    fn test_invert() {
105        proptest!(|(x: Scalar)| {
106            let mut a = x;
107            a.invert_in_place();
108            a.invert_in_place();
109            prop_assert_eq!(a, x);
110
111            a = x;
112            a.invert_in_place();
113            a *= x;
114
115            if x.is_zero() {
116                prop_assert_eq!(a, Scalar::ZERO);
117            } else {
118                prop_assert_eq!(a, Scalar::ONE);
119            }
120        })
121    }
122}
airbender_crypto/secp256k1/scalars/invert.rs

airbender_crypto/secp256k1/scalars/
invert.rs
