ec_generic/
finite_fields.rs

1use num_bigint::BigUint;
2
3///
4/// A struct which implements the bottom layer finite field group needed to
5/// operate with the coordinates of the elliptic curve group.
6///
7pub struct FiniteField {}
8
9#[derive(Debug, PartialEq)]
10pub enum FiniteFieldError {
11    InvalidArgument(String),
12    InvalidResult(String),
13}
14
15impl FiniteField {
16    ///
17    /// Adds to elements in the set
18    ///
19    /// `a + b = a mod p`
20    ///
21    pub fn add(a: &BigUint, b: &BigUint, p: &BigUint) -> Result<BigUint, FiniteFieldError> {
22        FiniteField::check_less_than(a, p)?;
23        FiniteField::check_less_than(b, p)?;
24
25        Ok((a + b).modpow(&BigUint::from(1u32), p))
26    }
27
28    ///
29    /// Multiplies to elements in the set
30    ///
31    /// `a * b = a mod p`
32    ///
33    pub fn mult(a: &BigUint, b: &BigUint, p: &BigUint) -> Result<BigUint, FiniteFieldError> {
34        FiniteField::check_less_than(a, p)?;
35        FiniteField::check_less_than(b, p)?;
36
37        Ok((a * b).modpow(&BigUint::from(1u32), p))
38    }
39
40    ///
41    /// Finds the additive inverse of an element in the set:
42    ///
43    /// `a + (-a) = 0 mod p`
44    ///
45    pub fn inv_add(a: &BigUint, p: &BigUint) -> Result<BigUint, FiniteFieldError> {
46        FiniteField::check_less_than(a, p)?;
47
48        if *a == BigUint::from(0u32) {
49            return Ok(a.clone());
50        }
51
52        Ok(p - a)
53    }
54
55    ///
56    /// Subtract two elements in the set:
57    ///
58    /// `a - b = a + (-b) = a mod p`
59    ///
60    pub fn subtract(a: &BigUint, b: &BigUint, p: &BigUint) -> Result<BigUint, FiniteFieldError> {
61        FiniteField::check_less_than(a, p)?;
62        FiniteField::check_less_than(b, p)?;
63
64        let b_inv = FiniteField::inv_add(b, p)?;
65
66        FiniteField::add(a, &b_inv, p)
67    }
68
69    ///
70    /// Finds the multiplicative inverse of an element in the set if p is a
71    /// prime number using Fermat's Little Theorem:
72    ///
73    /// `a^(-1) mod p = a^(p-2) mod p`
74    ///
75    /// Such that:
76    /// `a * a^(-1) = 1 mod p`
77    ///
78    pub fn inv_mult_prime(a: &BigUint, p: &BigUint) -> Result<BigUint, FiniteFieldError> {
79        FiniteField::check_less_than(a, p)?;
80
81        Ok(a.modpow(&(p - BigUint::from(2u32)), p))
82    }
83
84    ///
85    /// Divides two elements in the set:
86    ///
87    /// `a / b = a * b^(-1) = a mod p`
88    ///
89    pub fn divide(a: &BigUint, b: &BigUint, p: &BigUint) -> Result<BigUint, FiniteFieldError> {
90        FiniteField::check_less_than(a, p)?;
91        FiniteField::check_less_than(b, p)?;
92
93        let d_inv = FiniteField::inv_mult_prime(b, p)?;
94
95        FiniteField::mult(a, &d_inv, p)
96    }
97
98    pub fn check_less_than(a: &BigUint, b: &BigUint) -> Result<(), FiniteFieldError> {
99        if a >= b {
100            return Err(FiniteFieldError::InvalidArgument(format!("{} >= {}", a, b)));
101        }
102        Ok(())
103    }
104}
105
106#[cfg(test)]
107mod test {
108    use super::*;
109
110    #[test]
111    fn test_add() {
112        let a = BigUint::from(4u32);
113        let b = BigUint::from(10u32);
114        let p = BigUint::from(11u32);
115
116        let res = FiniteField::add(&a, &b, &p).unwrap();
117        assert_eq!(res, BigUint::from(3u32));
118
119        let a = BigUint::from(10u32);
120        let b = BigUint::from(1u32);
121        let p = BigUint::from(11u32);
122
123        let res = FiniteField::add(&a, &b, &p).unwrap();
124        assert_eq!(res, BigUint::from(0u32));
125
126        let a = BigUint::from(4u32);
127        let b = BigUint::from(10u32);
128        let p = BigUint::from(31u32);
129
130        let res = FiniteField::add(&a, &b, &p).unwrap();
131        assert_eq!(res, BigUint::from(14u32));
132    }
133
134    #[test]
135    fn test_multiply() {
136        let a = BigUint::from(4u32);
137        let b = BigUint::from(10u32);
138        let p = BigUint::from(11u32);
139
140        let res = FiniteField::mult(&a, &b, &p).unwrap();
141        assert_eq!(res, BigUint::from(7u32));
142
143        let p = BigUint::from(51u32);
144
145        let res = FiniteField::mult(&a, &b, &p).unwrap();
146        assert_eq!(res, BigUint::from(40u32));
147    }
148
149    #[test]
150    fn test_inv_add() {
151        let a = BigUint::from(4u32);
152        let p = BigUint::from(51u32);
153
154        let res = FiniteField::inv_add(&a, &p).unwrap();
155        assert_eq!(res, BigUint::from(47u32));
156
157        let a = BigUint::from(0u32);
158        let p = BigUint::from(51u32);
159
160        let res = FiniteField::inv_add(&a, &p).unwrap();
161        assert_eq!(res, BigUint::from(0u32));
162
163        let a = BigUint::from(52u32);
164        let p = BigUint::from(51u32);
165
166        assert_eq!(
167            FiniteField::inv_add(&a, &p),
168            Err(FiniteFieldError::InvalidArgument(format!("{} >= {}", a, p)))
169        );
170
171        let a = BigUint::from(4u32);
172        let p = BigUint::from(51u32);
173
174        let c_inv = FiniteField::inv_add(&a, &p);
175
176        assert_eq!(c_inv, Ok(BigUint::from(47u32)));
177        assert_eq!(
178            FiniteField::add(&a, &c_inv.unwrap(), &p),
179            Ok(BigUint::from(0u32))
180        );
181    }
182
183    #[test]
184    fn test_subtract() {
185        // a - a = 0 mod p
186        let a = BigUint::from(4u32);
187        let p = BigUint::from(51u32);
188
189        assert_eq!(FiniteField::subtract(&a, &a, &p), Ok(BigUint::from(0u32)));
190    }
191
192    #[test]
193    fn test_inv_mult() {
194        // 4 * 3 mod 11 = 12 mod 11 = 1
195        let a = BigUint::from(4u32);
196        let p = BigUint::from(11u32);
197
198        let c_inv = FiniteField::inv_mult_prime(&a, &p);
199
200        assert_eq!(c_inv, Ok(BigUint::from(3u32)));
201        assert_eq!(
202            FiniteField::mult(&a, &c_inv.unwrap(), &p),
203            Ok(BigUint::from(1u32))
204        );
205    }
206
207    #[test]
208    fn test_divide() {
209        // a / a = 1 mod p
210        let a = BigUint::from(4u32);
211        let p = BigUint::from(11u32);
212
213        assert_eq!(FiniteField::divide(&a, &a, &p), Ok(BigUint::from(1u32)));
214    }
215}
ec_generic/finite_fields.rs

ec_generic/
finite_fields.rs
