p3_binary_field/
poly_basis.rs

1//! `GF(2^128)` in the polynomial basis of `x^128 + x^7 + x^2 + x + 1`.
2//!
3//! [`BinaryField128`] stores its elements in the tower basis, and a product there is a change of
4//! basis on each operand, a carryless multiply, and a change of basis back — three table-driven
5//! conversions of sixteen dependent lookups each, which dominate the multiply. Code that
6//! performs many products on the same data can pay the conversion once at each end instead, and
7//! multiply through [`mul`] in between.
8//!
9//! Addition is `XOR` in either basis, so a sum needs no conversion at all: only products and
10//! squares do, which is what this module supplies. An element is carried as the `u128` of its
11//! coordinates, deliberately not as a field type — the two bases are indistinguishable once
12//! wrapped, and a value that reaches ordinary [`BinaryField128`] arithmetic in the wrong one is
13//! silently wrong rather than ill-typed.
14
15use crate::tower::TowerLevel;
16use crate::{BinaryField128, clmul};
17
18/// Whether [`mul`] and [`square`] compile down to a hardware carryless multiply.
19///
20/// Where they do not, the carryless product is the bit-serial fallback, which is far slower than
21/// the recursive tower arithmetic `BinaryField128` uses on such a target. Working in this basis
22/// is a loss there, so a caller choosing between the two representations should branch on this.
23pub const HAS_HARDWARE_CLMUL: bool = clmul::HAS_HARDWARE_CLMUL;
24
25/// The polynomial-basis coordinates of a tower element.
26#[must_use]
27#[inline]
28pub fn from_tower(x: BinaryField128) -> u128 {
29    clmul::tower_to_poly_128(x.to_repr())
30}
31
32/// The tower element with the given polynomial-basis coordinates.
33#[inline]
34pub fn to_tower(v: u128) -> BinaryField128 {
35    BinaryField128::from_repr(clmul::poly_to_tower_128(v))
36}
37
38/// The product of two elements, both given and returned in the polynomial basis.
39#[must_use]
40#[inline]
41pub fn mul(a: u128, b: u128) -> u128 {
42    clmul::poly_mul_128(a, b)
43}
44
45/// The square of an element, given and returned in the polynomial basis.
46#[must_use]
47#[inline]
48pub fn square(a: u128) -> u128 {
49    clmul::poly_square_128(a)
50}
51
52#[cfg(test)]
53mod tests {
54    use p3_field::PrimeCharacteristicRing;
55    use proptest::prelude::*;
56
57    use super::{from_tower, mul, square, to_tower};
58    use crate::BinaryField128;
59
60    /// Building an element from a 128-bit pattern, which every pattern is a valid one of.
61    fn element(bits: u128) -> BinaryField128 {
62        BinaryField128::from_le_bytes(bits.to_le_bytes())
63    }
64
65    proptest! {
66        #[test]
67        fn the_change_of_basis_round_trips(bits in any::<u128>()) {
68            let x = element(bits);
69            prop_assert_eq!(to_tower(from_tower(x)), x);
70        }
71
72        /// Addition is `XOR` in both bases, so the conversion commutes with it.
73        #[test]
74        fn the_change_of_basis_is_additive(a in any::<u128>(), b in any::<u128>()) {
75            let (x, y) = (element(a), element(b));
76            prop_assert_eq!(from_tower(x + y), from_tower(x) ^ from_tower(y));
77        }
78
79        /// The polynomial-basis product is the tower product, seen in the other basis.
80        #[test]
81        fn the_product_agrees_with_the_tower_product(a in any::<u128>(), b in any::<u128>()) {
82            let (x, y) = (element(a), element(b));
83            prop_assert_eq!(to_tower(mul(from_tower(x), from_tower(y))), x * y);
84        }
85
86        #[test]
87        fn the_square_agrees_with_the_tower_square(a in any::<u128>()) {
88            let x = element(a);
89            prop_assert_eq!(to_tower(square(from_tower(x))), x.square());
90        }
91    }
92
93    /// The basis change fixes zero and one, as any field isomorphism must.
94    #[test]
95    fn the_change_of_basis_fixes_the_constants() {
96        assert_eq!(from_tower(BinaryField128::ZERO), 0);
97        assert_eq!(from_tower(BinaryField128::ONE), 1);
98        assert_eq!(to_tower(0), BinaryField128::ZERO);
99        assert_eq!(to_tower(1), BinaryField128::ONE);
100    }
101}
p3_binary_field/poly_basis.rs

p3_binary_field/
poly_basis.rs
