fgf/field/binary/
poly.rs

1//! Polynomial-basis binary presentations at degrees 1, 2, 4, and 8.
2//!
3//! [`Polynomial`] is the construction `GF(2)[x] / p(x)` for an irreducible
4//! degree-`N` `p`. The representation, its descriptor, and its generator
5//! derive from the polynomial at compile time, so each polynomial is a
6//! distinct representation with fully `const` scalar arithmetic.
7//!
8//! | Constant | Polynomial | Convention |
9//! | --- | --- | --- |
10//! | [`AES`] | `0x11B` | AES/Rijndael; the field `GF2P8MULB` multiplies natively |
11//! | [`RS`] | `0x11D` | Intel ISA-L, `klauspost/reedsolomon`, QR codes |
12//!
13//! Any other degree-8 irreducible polynomial is spelled directly, such as
14//! `Polynomial<0x12D>` for Data Matrix or `Polynomial<0x187>` for the CCSDS Reed–Solomon
15//! field. Distinct polynomials are unrelated encodings: a byte has different
16//! products under each, so a buffer carries one convention and never two.
17//!
18//! ```
19//! use fgf::{AES, Elem, FiniteField, Polynomial, RS};
20//!
21//! // The same bytes multiply differently under the two conventions.
22//! let (a, b) = (0x53, 0xca);
23//! assert_eq!(
24//!     Elem::<FiniteField<2, 8, Polynomial<AES>>>::from_raw(a)
25//!         .mul(Elem::<FiniteField<2, 8, Polynomial<AES>>>::from_raw(b))
26//!         .to_raw(),
27//!     0x01
28//! );
29//! assert_eq!(
30//!     Elem::<FiniteField<2, 8, Polynomial<RS>>>::from_raw(a)
31//!         .mul(Elem::<FiniteField<2, 8, Polynomial<RS>>>::from_raw(b))
32//!         .to_raw(),
33//!     0x8f
34//! );
35//!
36//! // Any irreducible polynomial is a field; its generator is derived.
37//! assert_eq!(
38//!     Elem::<FiniteField<2, 8, Polynomial<0x12D>>>::GENERATOR.pow(255),
39//!     Elem::<FiniteField<2, 8, Polynomial<0x12D>>>::ONE
40//! );
41//! ```
42//!
43//! ```compile_fail,E0080
44//! // x^8 + 1 = (x + 1)^8 is reducible, so this field does not exist.
45//! let _ = fgf::Elem::<fgf::FiniteField<2, 8, fgf::Polynomial<0x101>>>::from_raw(1);
46//! ```
47//!
48//! ```compile_fail,E0080
49//! // The degree-eight polynomial does not match a degree-four field.
50//! let _ = fgf::Elem::<fgf::FiniteField<2, 4, fgf::Polynomial<0x11B>>>::from_raw(1);
51//! ```
52
53use super::BinaryRepr;
54use super::description::{BinaryDescription, ByteLogExp};
55use crate::field::FiniteFieldRepr;
56
57/// The AES/Rijndael polynomial `x^8 + x^4 + x^3 + x + 1`.
58///
59/// It is the field the x86 `GF2P8MULB` instruction implements, so
60/// `FiniteField<2, 8, Polynomial<AES>>` multiplies with one instruction per vector
61/// on GFNI hosts. Its derived generator is `0x03`.
62pub const AES: u128 = 0x11B;
63
64/// The `0x11D` Reed–Solomon convention, `x^8 + x^4 + x^3 + x^2 + 1`.
65///
66/// Intel ISA-L, `klauspost/reedsolomon`, and QR codes use this polynomial;
67/// `FiniteField<2, 8, Polynomial<RS>>` shards are byte-identical to those ecosystems.
68/// Reed–Solomon codes also use other polynomials. Its derived generator is
69/// `0x02`.
70pub const RS: u128 = 0x11D;
71
72/// The polynomial-basis representation of GF(2^N) under the reduction
73/// polynomial `P`.
74///
75/// `P` is the full polynomial including the leading term, and must be
76/// irreducible of the field's degree; the check runs when the
77/// representation's constants are evaluated. The same type spells GF(2) as
78/// [`Polynomial<3>`](Polynomial), the polynomial `x + 1`.
79#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, Default, PartialOrd, Ord)]
80pub struct Polynomial<const P: u128>;
81
82impl<const P: u128> crate::field::private::Sealed for Polynomial<P> {}
83
84impl<const P: u128> Polynomial<P> {
85    /// The full reduction polynomial including the leading term.
86    pub const POLY: u128 = P;
87
88    /// The low byte `XORed` in when a shift overflows the field.
89    ///
90    /// Read by the kernel differential tests as their independent oracle;
91    /// non-`simd` builds have no other user.
92    #[allow(dead_code)]
93    pub(crate) const REDUCTION_LOW: u8 = (P & 0xFF) as u8;
94
95    /// The bytes of the degree-eight field name, `"GF(2^8)/0x1XY"`.
96    const NAME_BYTES8: [u8; 13] = name_bytes8(P);
97    /// The bytes of the degree-four field name, `"GF(2^4)/0x1X"`.
98    const NAME_BYTES4: [u8; 12] = name_bytes4(P);
99    /// The bytes of the degree-two field name, `"GF(2^2)/0xX"`.
100    const NAME_BYTES2: [u8; 11] = name_bytes2(P);
101
102    /// The smallest primitive element of the described field.
103    ///
104    /// An element generates the group exactly when no proper cofactor power
105    /// returns it to one. The search starts at two, so the AES field finds
106    /// `0x03` and the Reed–Solomon field `0x02`, matching the frozen
107    /// conventions.
108    pub(crate) const fn smallest_generator(description: &BinaryDescription) -> u64 {
109        let limit = 1u64 << description.degree();
110        let mut candidate = 2u64;
111        loop {
112            assert!(candidate < limit, "Polynomial P has no primitive element");
113            if description.is_generator(candidate) {
114                break candidate;
115            }
116            candidate += 1;
117        }
118    }
119}
120
121/// The bytes of the degree-eight field name: `"GF(2^8)/0x1XY"`.
122const fn name_bytes8(poly: u128) -> [u8; 13] {
123    const HEX: &[u8; 16] = b"0123456789ABCDEF";
124    let mut name = *b"GF(2^8)/0x000";
125    name[10] = HEX[((poly >> 8) & 0xf) as usize];
126    name[11] = HEX[((poly >> 4) & 0xf) as usize];
127    name[12] = HEX[(poly & 0xf) as usize];
128    name
129}
130
131/// The bytes of the degree-four field name: `"GF(2^4)/0x1X"`.
132const fn name_bytes4(poly: u128) -> [u8; 12] {
133    const HEX: &[u8; 16] = b"0123456789ABCDEF";
134    let mut name = *b"GF(2^4)/0x00";
135    name[10] = HEX[((poly >> 4) & 0xf) as usize];
136    name[11] = HEX[(poly & 0xf) as usize];
137    name
138}
139
140/// The bytes of the degree-two field name: `"GF(2^2)/0xX"`.
141const fn name_bytes2(poly: u128) -> [u8; 11] {
142    const HEX: &[u8; 16] = b"0123456789ABCDEF";
143    let mut name = *b"GF(2^2)/0x0";
144    name[10] = HEX[(poly & 0xf) as usize];
145    name
146}
147
148macro_rules! poly_degree8 {
149    () => {
150        impl<const P: u128> FiniteFieldRepr<2, 8> for Polynomial<P> {
151            const NAME: &'static str = match core::str::from_utf8(&Polynomial::<P>::NAME_BYTES8) {
152                Ok(name) => name,
153                Err(_) => panic!("Polynomial field names are ASCII"),
154            };
155            const VALID: () = {
156                assert!(
157                    super::description::poly_degree(P) == 8,
158                    "polynomial degree does not match field degree"
159                );
160                <Self as BinaryRepr<8>>::DESCRIPTION.validate();
161                assert!(
162                    <Self as BinaryRepr<8>>::DESCRIPTION.is_generator(
163                        Polynomial::<P>::smallest_generator(<Self as BinaryRepr<8>>::DESCRIPTION)
164                    ),
165                    "byte representation generator does not have full order"
166                );
167            };
168        }
169        impl<const P: u128> BinaryRepr<8> for Polynomial<P> {
170            const DESCRIPTION: &'static BinaryDescription = &BinaryDescription::polynomial(8, P);
171            const LOG_EXP: Option<&'static ByteLogExp> = Some(&ByteLogExp::build(
172                &BinaryDescription::polynomial(8, P),
173                Polynomial::<P>::smallest_generator(&BinaryDescription::polynomial(8, P)),
174            ));
175        }
176    };
177}
178
179poly_degree8!();
180
181impl<const P: u128> FiniteFieldRepr<2, 4> for Polynomial<P> {
182    const NAME: &'static str = match core::str::from_utf8(&Polynomial::<P>::NAME_BYTES4) {
183        Ok(name) => name,
184        Err(_) => panic!("Polynomial field names are ASCII"),
185    };
186    const VALID: () = {
187        assert!(
188            super::description::poly_degree(P) == 4,
189            "polynomial degree does not match field degree"
190        );
191        <Self as BinaryRepr<4>>::DESCRIPTION.validate();
192    };
193}
194
195impl<const P: u128> BinaryRepr<4> for Polynomial<P> {
196    const DESCRIPTION: &'static BinaryDescription = &BinaryDescription::polynomial(4, P);
197    const LOG_EXP: Option<&'static ByteLogExp> = None;
198}
199
200impl<const P: u128> FiniteFieldRepr<2, 2> for Polynomial<P> {
201    const NAME: &'static str = match core::str::from_utf8(&Polynomial::<P>::NAME_BYTES2) {
202        Ok(name) => name,
203        Err(_) => panic!("Polynomial field names are ASCII"),
204    };
205    const VALID: () = {
206        assert!(
207            super::description::poly_degree(P) == 2,
208            "polynomial degree does not match field degree"
209        );
210        <Self as BinaryRepr<2>>::DESCRIPTION.validate();
211    };
212}
213
214impl<const P: u128> BinaryRepr<2> for Polynomial<P> {
215    const DESCRIPTION: &'static BinaryDescription = &BinaryDescription::polynomial(2, P);
216    const LOG_EXP: Option<&'static ByteLogExp> = None;
217}
218
219impl<const P: u128> FiniteFieldRepr<2, 1> for Polynomial<P> {
220    const NAME: &'static str = "GF(2)";
221    const VALID: () = {
222        assert!(P == 3, "Polynomial<3> is the only degree-one form");
223        <Self as BinaryRepr<1>>::DESCRIPTION.validate();
224    };
225}
226
227impl<const P: u128> BinaryRepr<1> for Polynomial<P> {
228    const DESCRIPTION: &'static BinaryDescription = &BinaryDescription::polynomial(1, P);
229    const LOG_EXP: Option<&'static ByteLogExp> = None;
230}
231
232use super::super::HasGenerator;
233use crate::field::FiniteField;
234
235impl<const P: u128> HasGenerator for FiniteField<2, 8, Polynomial<P>> {
236    const GENERATOR_RAW: u8 = {
237        let g = Polynomial::<P>::smallest_generator(<Polynomial<P> as BinaryRepr<8>>::DESCRIPTION);
238        assert!(
239            <Polynomial<P> as BinaryRepr<8>>::DESCRIPTION.is_generator(g),
240            "byte representation generator does not have full order"
241        );
242        #[allow(clippy::cast_possible_truncation)]
243        let generator = g as u8;
244        generator
245    };
246}
247
248impl<const P: u128> HasGenerator for FiniteField<2, 4, Polynomial<P>> {
249    const GENERATOR_RAW: u8 = {
250        let g = Polynomial::<P>::smallest_generator(<Polynomial<P> as BinaryRepr<4>>::DESCRIPTION);
251        assert!(
252            <Polynomial<P> as BinaryRepr<4>>::DESCRIPTION.is_generator(g),
253            "representation generator does not have full order"
254        );
255        #[allow(clippy::cast_possible_truncation)]
256        let generator = g as u8;
257        generator
258    };
259}
260
261impl<const P: u128> HasGenerator for FiniteField<2, 2, Polynomial<P>> {
262    const GENERATOR_RAW: u8 = {
263        let g = Polynomial::<P>::smallest_generator(<Polynomial<P> as BinaryRepr<2>>::DESCRIPTION);
264        assert!(
265            <Polynomial<P> as BinaryRepr<2>>::DESCRIPTION.is_generator(g),
266            "representation generator does not have full order"
267        );
268        #[allow(clippy::cast_possible_truncation)]
269        let generator = g as u8;
270        generator
271    };
272}
273
274impl<const P: u128> HasGenerator for FiniteField<2, 1, Polynomial<P>> {
275    const GENERATOR_RAW: u8 = 1;
276}
277
278#[cfg(test)]
279pub(super) mod tests {
280    extern crate std;
281
282    use core::hint::black_box;
283
284    use super::super::description::poly_irreducible;
285    use super::*;
286
287    /// Independent shift-reduce product in `GF(2)[x] / poly`, degree `n`.
288    pub(in crate::field::binary) fn oracle_mul(poly: u128, n: u32, x: u64, y: u64) -> u64 {
289        let mut acc: u128 = 0;
290        for k in 0..n {
291            if (y >> k) & 1 == 1 {
292                acc ^= u128::from(x) << k;
293            }
294        }
295        for k in (n..2 * n).rev() {
296            if (acc >> k) & 1 == 1 {
297                acc ^= poly << (k - n);
298            }
299        }
300        #[allow(clippy::cast_possible_truncation)]
301        let product = acc as u64;
302        product
303    }
304
305    /// The smallest element of `GF(2)[x] / poly` from two upward whose
306    /// powers first return to one after exactly `2^n - 1` steps.
307    pub(in crate::field::binary) fn oracle_smallest_generator(poly: u128, n: u32) -> u64 {
308        let order = (1u64 << n) - 1;
309        (2..=order)
310            .find(|&candidate| {
311                let mut power = candidate;
312                let mut steps = 1;
313                while power != 1 && steps <= order {
314                    power = oracle_mul(poly, n, power, candidate);
315                    steps += 1;
316                }
317                steps == order
318            })
319            .expect("a field has a primitive element")
320    }
321
322    /// Apply coordinate columns: bit `i` of `word` selects `columns[i]`.
323    pub(in crate::field::binary) fn apply_columns(columns: [u8; 8], word: u64) -> u64 {
324        (0..8)
325            .filter(|&i| (word >> i) & 1 == 1)
326            .fold(0, |image, i| image ^ u64::from(columns[i]))
327    }
328
329    /// Every irreducible polynomial of degree `n`.
330    fn irreducibles(n: u32) -> impl Iterator<Item = u128> {
331        (1u128 << n..2u128 << n).filter(move |&p| poly_irreducible(p, n))
332    }
333
334    /// The generator search, evaluated at runtime over every irreducible
335    /// polynomial of degrees 2, 4, and 8, finds the brute-force smallest
336    /// element of full multiplicative order.
337    #[test]
338    fn smallest_generator_matches_brute_force_order() {
339        for n in [2u8, 4, 8] {
340            for poly in irreducibles(u32::from(n)) {
341                let description = BinaryDescription::polynomial(black_box(n), black_box(poly));
342                assert_eq!(
343                    Polynomial::<AES>::smallest_generator(&description),
344                    oracle_smallest_generator(poly, u32::from(n)),
345                    "degree {n}, polynomial {poly:#x}"
346                );
347            }
348        }
349    }
350
351    /// Field names carry the polynomial: the hexadecimal digits after
352    /// `0x` parse back to every irreducible polynomial of the degree.
353    #[test]
354    fn field_names_round_trip_their_polynomial() {
355        fn parsed(name: &[u8]) -> u128 {
356            let name = core::str::from_utf8(name).expect("ASCII name");
357            let (_, digits) = name.rsplit_once("0x").expect("hexadecimal suffix");
358            u128::from_str_radix(digits, 16).expect("hexadecimal digits")
359        }
360        for poly in irreducibles(8) {
361            assert_eq!(parsed(&name_bytes8(black_box(poly))), poly);
362        }
363        for poly in irreducibles(4) {
364            assert_eq!(parsed(&name_bytes4(black_box(poly))), poly);
365        }
366        for poly in irreducibles(2) {
367            assert_eq!(parsed(&name_bytes2(black_box(poly))), poly);
368        }
369    }
370
371    /// Every degree-8 polynomial, against an independent irreducibility
372    /// count: GF(2) has exactly 30 irreducible polynomials of degree 8.
373    #[test]
374    fn irreducibility_check_admits_exactly_the_thirty_fields() {
375        let count = (0x100..=0x1FFu128)
376            .filter(|&p| super::super::description::poly_irreducible(p, 8))
377            .count();
378        assert_eq!(count, 30);
379        assert!(super::super::description::poly_irreducible(AES, 8));
380        assert!(super::super::description::poly_irreducible(RS, 8));
381        assert!(super::super::description::poly_irreducible(0x12D, 8));
382        assert!(super::super::description::poly_irreducible(0x187, 8));
383        assert!(!super::super::description::poly_irreducible(0x101, 8));
384        assert!(!super::super::description::poly_irreducible(0x0FF, 8));
385        assert!(!super::super::description::poly_irreducible(0x200, 8));
386    }
387}
fgf/field/binary/poly.rs

fgf/field/binary/
poly.rs
