yui_core/conc/num/
f2.rs

1//! The finite field 𝔽₂ = ℤ/2ℤ with two elements `0` and `1`.
2//!
3//! Specialized over [`FF<2>`](super::FF) — stores a single `bool` and
4//! implements addition/multiplication as direct `^` (XOR) / `&` (AND).
5//!
6//! See: <https://en.wikipedia.org/wiki/GF(2)>
7
8use std::fmt::{Debug, Display};
9use std::ops::{Add, Neg, Sub, Mul, Div, Rem, AddAssign, SubAssign, MulAssign, DivAssign, RemAssign};
10use std::str::FromStr;
11use num_integer::Integer;
12use num_traits::{One, Pow, Zero};
13use auto_impl_ops::auto_ops;
14
15use crate::abst::{MathType, AddMonOps, AddGrpOps, MonOps, RingOps, FieldOps, EucRingOps, AddMon, AddGrp, Mon, Ring, EucRing, Field};
16use crate::util::parse_err::ParseErr;
17
18/// An element of the finite field 𝔽₂.
19#[derive(Clone, Copy, PartialEq, Eq, Default)]
20pub struct FF2(bool);
21
22impl<I> From<I> for FF2
23where I: Integer {
24    fn from(a: I) -> Self {
25        Self(a.is_odd())
26    }
27}
28
29impl FromStr for FF2 {
30    type Err = ParseErr;
31    fn from_str(s: &str) -> Result<Self, Self::Err> {
32        let a = s.parse::<i64>().map_err(|_| ParseErr::invalid(s, &Self::math_symbol()))?;
33        Ok(Self::from(a))
34    }
35}
36
37impl Display for FF2 {
38    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
39        if self.0 {
40            write!(f, "1")
41        } else {
42            write!(f, "0")
43        }
44    }
45}
46
47impl Debug for FF2 {
48    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
49        Display::fmt(self, f)
50    }
51}
52
53impl Zero for FF2 {
54    fn zero() -> Self {
55        Self(false)
56    }
57
58    fn is_zero(&self) -> bool {
59        !self.0
60    }
61}
62
63impl One for FF2 {
64    fn one() -> Self {
65        Self(true)
66    }
67
68    fn is_one(&self) -> bool {
69        self.0
70    }
71}
72
73impl Neg for FF2 {
74    type Output = Self;
75    fn neg(self) -> Self::Output {
76        self
77    }
78}
79
80impl Neg for &FF2 {
81    type Output = FF2;
82    fn neg(self) -> Self::Output {
83        *self
84    }
85}
86
87#[auto_ops]
88impl Add<&FF2> for &FF2 {
89    type Output = FF2;
90    fn add(self, rhs: &FF2) -> Self::Output {
91        FF2(self.0 != rhs.0)
92    }
93}
94
95#[auto_ops]
96impl Sub<&FF2> for &FF2 {
97    type Output = FF2;
98    fn sub(self, rhs: &FF2) -> Self::Output {
99        Add::add(self, rhs)
100    }
101}
102
103#[auto_ops]
104impl Mul<&FF2> for &FF2 {
105    type Output = FF2;
106    fn mul(self, rhs: &FF2) -> Self::Output {
107        FF2(self.0 && rhs.0)
108    }
109}
110
111#[auto_ops]
112impl Div<&FF2> for &FF2 {
113    type Output = FF2;
114    fn div(self, rhs: &FF2) -> Self::Output {
115        assert!(!rhs.is_zero());
116        *self
117    }
118}
119
120#[auto_ops]
121impl Rem<&FF2> for &FF2 {
122    type Output = FF2;
123    fn rem(self, rhs: &FF2) -> Self::Output {
124        assert!(!rhs.is_zero());
125        FF2::zero()
126    }
127}
128
129impl Pow<usize> for &FF2 {
130    type Output = FF2;
131    fn pow(self, rhs: usize) -> Self::Output {
132        if rhs == 0 { FF2::one() } else { *self }
133    }
134}
135
136macro_rules! impl_alg_ops {
137    ($trait:ident) => {
138        impl $trait for FF2 {}
139        impl $trait<FF2> for &FF2 {}
140    };
141}
142
143impl_alg_ops!(AddMonOps);
144impl_alg_ops!(AddGrpOps);
145impl_alg_ops!(MonOps);
146impl_alg_ops!(RingOps);
147impl_alg_ops!(EucRingOps);
148impl_alg_ops!(FieldOps);
149
150impl MathType for FF2 {
151    fn math_symbol() -> String {
152        String::from("F₂")
153    }
154}
155
156impl AddMon for FF2 {}
157impl AddGrp for FF2 {}
158impl Mon for FF2 {}
159
160impl Ring for FF2 {
161    fn inv(&self) -> Option<Self> {
162        self.is_one().then_some(*self)
163    }
164
165    fn is_unit(&self) -> bool {
166        !self.is_zero()
167    }
168
169    fn normalizing_unit(&self) -> Self {
170        Self::one()
171    }
172
173    fn c_weight(&self) -> f64 {
174        if self.is_zero() {
175            0f64
176        } else {
177            1f64
178        }
179    }
180}
181
182impl EucRing for FF2 {}
183impl Field for FF2 {}
184
185mod tex {
186    use crate::util::tex::TeX;
187    use super::*;
188
189    impl TeX for FF2 {
190        fn tex_math_symbol() -> String {
191            String::from("\\mathbb{F}_2")
192        }
193        fn tex_string(&self) -> String {
194            self.to_string()
195        }
196    }
197}
198
199#[cfg(test)]
200mod tests {
201    use super::*;
202
203    #[test]
204    fn init() {
205        let a = FF2::from(0);
206        assert_eq!(a.0, false);
207
208        let a = FF2::from(1);
209        assert_eq!(a.0, true);
210
211        let a = FF2::from(2);
212        assert_eq!(a.0, false);
213    }
214
215    #[test]
216    fn display() {
217        let a = FF2::zero();
218        assert_eq!(a.to_string(), "0");
219
220        let a = FF2::one();
221        assert_eq!(a.to_string(), "1");
222
223        let a = FF2::from(2);
224        assert_eq!(a.to_string(), "0");
225    }
226
227    #[test]
228    fn from_big() {
229        // parity is read directly, so a value past `i64` still converts.
230        use num_bigint::BigInt;
231        assert_eq!(FF2::from(BigInt::from(2).pow(100u32) + BigInt::from(1)), FF2::one());
232        assert_eq!(FF2::from(BigInt::from(2).pow(100u32)), FF2::zero());
233    }
234
235    #[test]
236    fn add() {
237        let a = FF2::from(2);
238        let b = FF2::from(4);
239
240        assert_eq!(a + b, FF2::from(0));
241
242        let a = FF2::from(3);
243        let b = FF2::from(4);
244
245        assert_eq!(a + b, FF2::from(1));
246
247        let a = FF2::from(3);
248        let b = FF2::from(5);
249
250        assert_eq!(a + b, FF2::from(0));
251    }
252
253    #[test]
254    fn add_assign() {
255        let mut a = FF2::from(3);
256        a += FF2::from(4);
257        assert_eq!(a, FF2::from(1));
258    }
259
260    #[test]
261    fn neg() {
262        let a = FF2::from(3);
263        assert_eq!(-a, FF2::from(1));
264    }
265
266    #[test]
267    fn sub() {
268        let a = FF2::from(3);
269        let b = FF2::from(5);
270
271        assert_eq!(a - b, FF2::from(0));
272    }
273
274    #[test]
275    fn sub_assign() {
276        let mut a = FF2::from(3);
277        a -= FF2::from(4);
278        assert_eq!(a, FF2::from(1));
279    }
280
281    #[test]
282    fn mul() {
283        let a = FF2::from(3);
284        let b = FF2::from(4);
285        assert_eq!(a * b, FF2::from(0));
286
287        let a = FF2::from(1);
288        let b = FF2::from(5);
289        assert_eq!(a * b, FF2::from(1));
290    }
291
292    #[test]
293    fn mul_assign() {
294        let mut a = FF2::from(3);
295        a *= FF2::from(4);
296        assert_eq!(a, FF2::from(0));
297    }
298
299    #[test]
300    fn div() {
301        let a = FF2::from(5);
302        let b = FF2::from(3);
303        assert_eq!(a / b, FF2::from(1));
304    }
305
306    #[test]
307    fn div_assign() {
308        let mut a = FF2::from(4);
309        a /= FF2::from(3);
310        assert_eq!(a, FF2::from(0));
311    }
312
313    #[test]
314    fn rem() {
315        let a = FF2::from(5);
316        let b = FF2::from(3);
317        assert_eq!(a % b, FF2::zero());
318    }
319
320    #[test]
321    fn rem_assign() {
322        let mut a = FF2::from(5);
323        a %= FF2::from(3);
324        assert_eq!(a, FF2::zero());
325    }
326
327    #[test]
328    fn tex() {
329        use crate::util::tex::TeX;
330        assert_eq!(FF2::tex_math_symbol(), "\\mathbb{F}_2");
331        assert_eq!(FF2::from(5).tex_string(), "1");
332    }
333}
yui_core/conc/num/f2.rs

yui_core/conc/num/
f2.rs
