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

ligerito_binary_fields/
lib.rs
