ligerito_binary_fields/
lib.rs

1// src/lib.rs
2//! Binary extension fields GF(2^n) implementation
3//! Mirrors the Julia BinaryFields module
4
5#![cfg_attr(not(feature = "std"), no_std)]
6#![allow(clippy::all, unused_parens, unused_imports, dead_code)]
7
8mod elem;
9pub mod fast_inverse;
10mod poly;
11pub mod simd;
12
13pub use elem::{BinaryElem128, BinaryElem16, BinaryElem32, BinaryElem64};
14pub use fast_inverse::{batch_invert_gf128, batch_invert_gf128_in_place, invert_gf128};
15pub use poly::{BinaryPoly128, BinaryPoly16, BinaryPoly256, BinaryPoly32, BinaryPoly64};
16pub use simd::{batch_add_gf128, batch_mul_gf128};
17
18// Re-export traits with conditional Send + Sync
19#[cfg(feature = "std")]
20pub trait BinaryFieldElement:
21    Send + Sync + Sized + Copy + Clone + Default + PartialEq + Eq + core::fmt::Debug
22{
23    type Poly: BinaryPolynomial;
24
25    fn zero() -> Self;
26    fn one() -> Self;
27    fn from_poly(poly: Self::Poly) -> Self;
28    fn poly(&self) -> Self::Poly;
29    fn add(&self, other: &Self) -> Self;
30    fn mul(&self, other: &Self) -> Self;
31    fn inv(&self) -> Self;
32    fn pow(&self, exp: u64) -> Self;
33
34    fn from_bits(bits: u64) -> Self {
35        let mut result = Self::zero();
36        let mut power = Self::one();
37        let generator = Self::from_poly(Self::Poly::from_value(2));
38
39        for i in 0..64 {
40            if (bits >> i) & 1 == 1 {
41                result = result.add(&power);
42            }
43            if i < 63 {
44                power = power.mul(&generator);
45            }
46        }
47        result
48    }
49}
50
51#[cfg(not(feature = "std"))]
52pub trait BinaryFieldElement:
53    Sized + Copy + Clone + Default + PartialEq + Eq + core::fmt::Debug
54{
55    type Poly: BinaryPolynomial;
56
57    fn zero() -> Self;
58    fn one() -> Self;
59    fn from_poly(poly: Self::Poly) -> Self;
60    fn poly(&self) -> Self::Poly;
61    fn add(&self, other: &Self) -> Self;
62    fn mul(&self, other: &Self) -> Self;
63    fn inv(&self) -> Self;
64    fn pow(&self, exp: u64) -> Self;
65
66    fn from_bits(bits: u64) -> Self {
67        let mut result = Self::zero();
68        let mut power = Self::one();
69        let generator = Self::from_poly(Self::Poly::from_value(2));
70
71        for i in 0..64 {
72            if (bits >> i) & 1 == 1 {
73                result = result.add(&power);
74            }
75            if i < 63 {
76                power = power.mul(&generator);
77            }
78        }
79        result
80    }
81}
82
83pub trait BinaryPolynomial:
84    Sized + Copy + Clone + Default + PartialEq + Eq + core::fmt::Debug
85{
86    type Value: Copy + Clone + core::fmt::Debug;
87
88    fn zero() -> Self;
89    fn one() -> Self;
90    fn from_value(val: u64) -> Self;
91    fn value(&self) -> Self::Value;
92    fn add(&self, other: &Self) -> Self;
93    fn mul(&self, other: &Self) -> Self;
94    fn div_rem(&self, other: &Self) -> (Self, Self);
95}
96
97#[cfg(test)]
98mod tests {
99    use super::*;
100
101    #[test]
102    fn test_poly_operations() {
103        // polynomial addition
104        let a = BinaryPoly16::from_value(0x1234);
105        let b = BinaryPoly16::from_value(0x5678);
106        assert_eq!(a.add(&b).value(), 0x1234 ^ 0x5678);
107        assert_eq!(a.add(&a), BinaryPoly16::zero());
108
109        // polynomial multiplication
110        let a = BinaryPoly16::from_value(0x2);
111        let b = BinaryPoly16::from_value(0x3);
112        assert_eq!(a.mul(&b).value(), 0x6);
113        assert_eq!(a.mul(&BinaryPoly16::one()), a);
114
115        // polynomial division
116        let a = BinaryPoly16::from_value(0x15); // x^4 + x^2 + 1
117        let b = BinaryPoly16::from_value(0x3); // x + 1
118        let (q, r) = a.div_rem(&b);
119        assert_eq!(a, q.mul(&b).add(&r));
120    }
121
122    #[test]
123    fn test_field_axioms() {
124        // test for all field sizes
125        macro_rules! test_field {
126            ($elem:ty, $val1:expr, $val2:expr, $val3:expr) => {
127                let a = <$elem>::from_value($val1);
128                let b = <$elem>::from_value($val2);
129                let c = <$elem>::from_value($val3);
130
131                // associativity
132                assert_eq!(a.add(&b.add(&c)), a.add(&b).add(&c));
133                assert_eq!(a.mul(&b.mul(&c)), a.mul(&b).mul(&c));
134
135                // commutativity
136                assert_eq!(a.add(&b), b.add(&a));
137                assert_eq!(a.mul(&b), b.mul(&a));
138
139                // distributivity
140                assert_eq!(a.mul(&b.add(&c)), a.mul(&b).add(&a.mul(&c)));
141
142                // identities
143                assert_eq!(a.add(&<$elem>::zero()), a);
144                assert_eq!(a.mul(&<$elem>::one()), a);
145
146                // inverses
147                assert_eq!(a.add(&a), <$elem>::zero());
148                if a != <$elem>::zero() {
149                    assert_eq!(a.mul(&a.inv()), <$elem>::one());
150                }
151            };
152        }
153
154        test_field!(BinaryElem16, 0x1234, 0x5678, 0x9ABC);
155        test_field!(BinaryElem32, 0x12345678, 0x9ABCDEF0, 0x11111111);
156        test_field!(
157            BinaryElem128,
158            0x123456789ABCDEF0123456789ABCDEF0,
159            0xFEDCBA9876543210FEDCBA9876543210,
160            0x1111111111111111111111111111111
161        );
162    }
163
164    #[test]
165    fn test_fermat_little_theorem() {
166        // a^(2^n - 1) = 1 for all a != 0 in GF(2^n)
167        let a = BinaryElem16::from_value(0x1234);
168        assert_eq!(a.pow(65535), BinaryElem16::one()); // 2^16 - 1
169
170        // subfield property: a^(2^n) = a
171        assert_eq!(a.pow(65536), a);
172    }
173
174    #[test]
175    #[should_panic(expected = "Cannot invert zero")]
176    fn test_zero_inverse_panics() {
177        let _ = BinaryElem16::zero().inv();
178    }
179
180    #[test]
181    fn test_from_bits() {
182        // x + 1
183        let elem = BinaryElem16::from_bits(0b11);
184        let expected = BinaryElem16::from_value(1).add(&BinaryElem16::from_value(2));
185        assert_eq!(elem, expected);
186
187        // x^4 + x^2 + 1
188        let elem = BinaryElem16::from_bits(0b10101);
189        let x = BinaryElem16::from_value(2);
190        let expected = x.pow(4).add(&x.pow(2)).add(&BinaryElem16::one());
191        assert_eq!(elem, expected);
192    }
193}
194
195#[cfg(test)]
196mod julia_compatibility_tests {
197    use super::*;
198
199    #[test]
200    fn test_julia_sage_vectors() {
201        // verify we can construct the sage comparison vectors
202        let v_values: Vec<u128> = vec![
203            48843935073701397021918627474152975110,
204            257371465678647658219914792930422930533,
205            197874898248752057839214693713406247745,
206            86301329031543269357031453671330949739,
207            245592208151890074913079678553060805151,
208            191477208903117015546989222243599496680,
209            92830719409229016308089219817617750833,
210            264528954340572454088312978462893134650,
211            158998607558664949362678439274836957424,
212            187448928532932960560649099299315170550,
213            177534835847791156274472818404289166039,
214            307322189246381679156077507151623179879,
215            117208864575585467966316847685913785498,
216            332422437295611968587046799211069213610,
217            109428368893056851194159753059340120844,
218            197947890894953343492199130314470631788,
219        ];
220
221        let v: Vec<BinaryElem128> = v_values
222            .iter()
223            .map(|&val| BinaryElem128::from_value(val))
224            .collect();
225
226        for (i, &val) in v_values.iter().enumerate() {
227            assert_eq!(v[i].poly().value(), val);
228        }
229    }
230
231    #[test]
232    fn test_julia_betas() {
233        // beta values for field embeddings
234        let beta16 = BinaryElem128::from_value(44320122245670141922313918651005395719);
235        let _beta32 = BinaryElem128::from_value(23246355947528323030879441634950214446);
236
237        // verify beta^16 generates distinct elements
238        let mut bs16 = vec![BinaryElem128::one()];
239        for i in 1..16 {
240            bs16.push(bs16[i - 1].mul(&beta16));
241        }
242
243        for i in 0..16 {
244            for j in (i + 1)..16 {
245                assert_ne!(bs16[i], bs16[j]);
246            }
247        }
248    }
249
250    #[test]
251    fn test_large_multiplication() {
252        // test 128-bit multiplication edge cases
253        let cases = vec![
254            (
255                0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF0u128,
256                0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF0u128,
257            ),
258            (u128::MAX, u128::MAX),
259            (
260                0x8000000000000000_0000000000000000u128,
261                0x8000000000000000_0000000000000000u128,
262            ),
263        ];
264
265        for (a_val, b_val) in cases {
266            let a = BinaryElem128::from(a_val);
267            let b = BinaryElem128::from(b_val);
268
269            let _c = a.mul(&b);
270
271            // verify inverse works
272            if a != BinaryElem128::zero() {
273                let a_inv = a.inv();
274                assert_eq!(a.mul(&a_inv), BinaryElem128::one());
275            }
276        }
277    }
278
279    #[test]
280    fn test_field_embedding() {
281        // test embeddings for ligerito
282        let elem16 = BinaryElem16::from_value(0x1234);
283        let elem32: BinaryElem32 = elem16.into();
284        let elem64: BinaryElem64 = elem16.into();
285        let elem128: BinaryElem128 = elem16.into();
286
287        assert_eq!(elem32.poly().value() & 0xFFFF, 0x1234);
288        assert_eq!(elem64.poly().value() & 0xFFFF, 0x1234);
289        assert_eq!(elem128.poly().value() & 0xFFFF, 0x1234);
290    }
291}
ligerito_binary_fields/lib.rs

ligerito_binary_fields/
lib.rs
