binius_field/
ghash.rs

1// Copyright 2023-2025 Irreducible Inc.
2// Copyright 2026 The Binius Developers
3
4//! Binary field implementation of GF(2^128) with a modulus of X^128 + X^7 + X^2 + X + 1.
5//! This is the GHASH field used in AES-GCM.
6
7use std::{
8	any::TypeId,
9	fmt::{Debug, Display, Formatter},
10	iter::{Product, Sum},
11	ops::{Add, AddAssign, Mul, MulAssign, Neg, Sub, SubAssign},
12};
13
14use binius_utils::{
15	DeserializeBytes, FixedSizeSerializeBytes, SerializationError, SerializeBytes,
16	bytes::{Buf, BufMut},
17};
18use bytemuck::{Pod, Zeroable};
19
20use super::{
21	binary_field::{BinaryField, BinaryField1b, TowerField, binary_field, impl_field_extension},
22	extension::ExtensionField,
23};
24use crate::{
25	AESTowerField8b, Field, PackedField, WideMul,
26	arch::packed_ghash_128::PackedBinaryGhash1x128b,
27	arithmetic_traits::InvertOrZero,
28	binary_field_arithmetic::{
29		TowerFieldArithmetic, invert_or_zero_using_packed, multiple_using_packed,
30		square_using_packed,
31	},
32	mul_by_binary_field_1b,
33	underlier::{U1, WithUnderlier},
34};
35
36binary_field!(pub BinaryField128bGhash(u128), 0x494ef99794d5244f9152df59d87a9186);
37
38// Deferred-reduction widening multiply, implemented by reusing the width-1 packed GHASH type. On
39// CLMUL backends `Output` is an unreduced `WideGhashProduct`, so accumulating products reduces
40// only once at the end; on portable backends it falls back to the trivial (eager) multiply.
41impl WideMul for BinaryField128bGhash {
42	type Output = <PackedBinaryGhash1x128b as WideMul>::Output;
43
44	#[inline]
45	fn wide_mul(a: Self, b: Self) -> Self::Output {
46		PackedBinaryGhash1x128b::wide_mul(
47			PackedBinaryGhash1x128b::set_single(a),
48			PackedBinaryGhash1x128b::set_single(b),
49		)
50	}
51
52	#[inline]
53	fn reduce(wide: Self::Output) -> Self {
54		PackedBinaryGhash1x128b::reduce(wide).get(0)
55	}
56}
57
58unsafe impl Pod for BinaryField128bGhash {}
59
60impl BinaryField128bGhash {
61	#[inline]
62	pub fn mul_x(self) -> Self {
63		let val = self.to_underlier();
64		let shifted = val << 1;
65
66		// GHASH irreducible polynomial: x^128 + x^7 + x^2 + x + 1
67		// When the high bit is set, we need to XOR with the reduction polynomial 0x87
68		// All 1s if the top bit is set, all 0s otherwise
69		let mask = (val >> 127).wrapping_neg();
70		let result = shifted ^ (0x87 & mask);
71
72		Self::from_underlier(result)
73	}
74
75	#[inline]
76	pub fn mul_inv_x(self) -> Self {
77		let val = self.to_underlier();
78		let shifted = val >> 1;
79
80		// If low bit was set, we need to add compensation for the remainder
81		// When dividing by x with remainder 1, we add x^(-1) = x^127 to the result
82		// Since x^128 ≡ x^7 + x^2 + x + 1, we have x^127 ≡ x^6 + x + 1
83		// So 0x43 = x^6 + x + 1 (bits 6, 1, 0) and we set bit 127 for the x^127 term
84		// All 1s if the bottom bit is set, all 0s otherwise
85		let mask = (val & 1).wrapping_neg();
86		let result = shifted ^ (((1u128 << 127) | 0x43) & mask);
87
88		Self::from_underlier(result)
89	}
90}
91
92impl TowerField for BinaryField128bGhash {
93	fn min_tower_level(self) -> usize {
94		match self {
95			Self::ZERO | Self::ONE => 0,
96			_ => 7,
97		}
98	}
99}
100
101// Cannot use `impl_arithmetic_using_packed!` because `PackedSubfield<Self, Self>` resolves
102// via `Underlier = u128`, but on SIMD targets `PackedBinaryGhash1x128b` uses `M128`.
103impl TowerFieldArithmetic for BinaryField128bGhash {
104	fn multiply(self, rhs: Self) -> Self {
105		multiple_using_packed::<PackedBinaryGhash1x128b>(self, rhs)
106	}
107
108	fn square(self) -> Self {
109		square_using_packed::<PackedBinaryGhash1x128b>(self)
110	}
111}
112
113impl InvertOrZero for BinaryField128bGhash {
114	#[inline]
115	fn invert_or_zero(self) -> Self {
116		invert_or_zero_using_packed::<PackedBinaryGhash1x128b>(self)
117	}
118}
119
120impl_field_extension!(BinaryField1b(U1) < @7 => BinaryField128bGhash(u128));
121
122mul_by_binary_field_1b!(BinaryField128bGhash);
123
124impl SerializeBytes for BinaryField128bGhash {
125	fn serialize(&self, write_buf: impl BufMut) -> Result<(), SerializationError> {
126		self.0.serialize(write_buf)
127	}
128}
129
130impl DeserializeBytes for BinaryField128bGhash {
131	fn deserialize(read_buf: impl Buf) -> Result<Self, SerializationError>
132	where
133		Self: Sized,
134	{
135		Ok(Self(DeserializeBytes::deserialize(read_buf)?))
136	}
137}
138
139impl FixedSizeSerializeBytes for BinaryField128bGhash {
140	const BYTE_SIZE: usize = 16;
141}
142
143impl From<AESTowerField8b> for BinaryField128bGhash {
144	#[inline]
145	fn from(value: AESTowerField8b) -> Self {
146		const LOOKUP_TABLE: [BinaryField128bGhash; 256] = [
147			BinaryField128bGhash(0x00000000000000000000000000000000),
148			BinaryField128bGhash(0x00000000000000000000000000000001),
149			BinaryField128bGhash(0x0dcb364640a222fe6b8330483c2e9849),
150			BinaryField128bGhash(0x0dcb364640a222fe6b8330483c2e9848),
151			BinaryField128bGhash(0x3d5bd35c94646a247573da4a5f7710ed),
152			BinaryField128bGhash(0x3d5bd35c94646a247573da4a5f7710ec),
153			BinaryField128bGhash(0x3090e51ad4c648da1ef0ea02635988a4),
154			BinaryField128bGhash(0x3090e51ad4c648da1ef0ea02635988a5),
155			BinaryField128bGhash(0x6d58c4e181f9199f41a12db1f974f3ac),
156			BinaryField128bGhash(0x6d58c4e181f9199f41a12db1f974f3ad),
157			BinaryField128bGhash(0x6093f2a7c15b3b612a221df9c55a6be5),
158			BinaryField128bGhash(0x6093f2a7c15b3b612a221df9c55a6be4),
159			BinaryField128bGhash(0x500317bd159d73bb34d2f7fba603e341),
160			BinaryField128bGhash(0x500317bd159d73bb34d2f7fba603e340),
161			BinaryField128bGhash(0x5dc821fb553f51455f51c7b39a2d7b08),
162			BinaryField128bGhash(0x5dc821fb553f51455f51c7b39a2d7b09),
163			BinaryField128bGhash(0xa72ec17764d7ced55e2f716f4ede412f),
164			BinaryField128bGhash(0xa72ec17764d7ced55e2f716f4ede412e),
165			BinaryField128bGhash(0xaae5f7312475ec2b35ac412772f0d966),
166			BinaryField128bGhash(0xaae5f7312475ec2b35ac412772f0d967),
167			BinaryField128bGhash(0x9a75122bf0b3a4f12b5cab2511a951c2),
168			BinaryField128bGhash(0x9a75122bf0b3a4f12b5cab2511a951c3),
169			BinaryField128bGhash(0x97be246db011860f40df9b6d2d87c98b),
170			BinaryField128bGhash(0x97be246db011860f40df9b6d2d87c98a),
171			BinaryField128bGhash(0xca760596e52ed74a1f8e5cdeb7aab283),
172			BinaryField128bGhash(0xca760596e52ed74a1f8e5cdeb7aab282),
173			BinaryField128bGhash(0xc7bd33d0a58cf5b4740d6c968b842aca),
174			BinaryField128bGhash(0xc7bd33d0a58cf5b4740d6c968b842acb),
175			BinaryField128bGhash(0xf72dd6ca714abd6e6afd8694e8dda26e),
176			BinaryField128bGhash(0xf72dd6ca714abd6e6afd8694e8dda26f),
177			BinaryField128bGhash(0xfae6e08c31e89f90017eb6dcd4f33a27),
178			BinaryField128bGhash(0xfae6e08c31e89f90017eb6dcd4f33a26),
179			BinaryField128bGhash(0x4d52354a3a3d8c865cb10fbabcf00118),
180			BinaryField128bGhash(0x4d52354a3a3d8c865cb10fbabcf00119),
181			BinaryField128bGhash(0x4099030c7a9fae7837323ff280de9951),
182			BinaryField128bGhash(0x4099030c7a9fae7837323ff280de9950),
183			BinaryField128bGhash(0x7009e616ae59e6a229c2d5f0e38711f5),
184			BinaryField128bGhash(0x7009e616ae59e6a229c2d5f0e38711f4),
185			BinaryField128bGhash(0x7dc2d050eefbc45c4241e5b8dfa989bc),
186			BinaryField128bGhash(0x7dc2d050eefbc45c4241e5b8dfa989bd),
187			BinaryField128bGhash(0x200af1abbbc495191d10220b4584f2b4),
188			BinaryField128bGhash(0x200af1abbbc495191d10220b4584f2b5),
189			BinaryField128bGhash(0x2dc1c7edfb66b7e77693124379aa6afd),
190			BinaryField128bGhash(0x2dc1c7edfb66b7e77693124379aa6afc),
191			BinaryField128bGhash(0x1d5122f72fa0ff3d6863f8411af3e259),
192			BinaryField128bGhash(0x1d5122f72fa0ff3d6863f8411af3e258),
193			BinaryField128bGhash(0x109a14b16f02ddc303e0c80926dd7a10),
194			BinaryField128bGhash(0x109a14b16f02ddc303e0c80926dd7a11),
195			BinaryField128bGhash(0xea7cf43d5eea4253029e7ed5f22e4037),
196			BinaryField128bGhash(0xea7cf43d5eea4253029e7ed5f22e4036),
197			BinaryField128bGhash(0xe7b7c27b1e4860ad691d4e9dce00d87e),
198			BinaryField128bGhash(0xe7b7c27b1e4860ad691d4e9dce00d87f),
199			BinaryField128bGhash(0xd7272761ca8e287777eda49fad5950da),
200			BinaryField128bGhash(0xd7272761ca8e287777eda49fad5950db),
201			BinaryField128bGhash(0xdaec11278a2c0a891c6e94d79177c893),
202			BinaryField128bGhash(0xdaec11278a2c0a891c6e94d79177c892),
203			BinaryField128bGhash(0x872430dcdf135bcc433f53640b5ab39b),
204			BinaryField128bGhash(0x872430dcdf135bcc433f53640b5ab39a),
205			BinaryField128bGhash(0x8aef069a9fb1793228bc632c37742bd2),
206			BinaryField128bGhash(0x8aef069a9fb1793228bc632c37742bd3),
207			BinaryField128bGhash(0xba7fe3804b7731e8364c892e542da376),
208			BinaryField128bGhash(0xba7fe3804b7731e8364c892e542da377),
209			BinaryField128bGhash(0xb7b4d5c60bd513165dcfb96668033b3f),
210			BinaryField128bGhash(0xb7b4d5c60bd513165dcfb96668033b3e),
211			BinaryField128bGhash(0x553e92e8bc0ae9a795ed1f57f3632d4d),
212			BinaryField128bGhash(0x553e92e8bc0ae9a795ed1f57f3632d4c),
213			BinaryField128bGhash(0x58f5a4aefca8cb59fe6e2f1fcf4db504),
214			BinaryField128bGhash(0x58f5a4aefca8cb59fe6e2f1fcf4db505),
215			BinaryField128bGhash(0x686541b4286e8383e09ec51dac143da0),
216			BinaryField128bGhash(0x686541b4286e8383e09ec51dac143da1),
217			BinaryField128bGhash(0x65ae77f268cca17d8b1df555903aa5e9),
218			BinaryField128bGhash(0x65ae77f268cca17d8b1df555903aa5e8),
219			BinaryField128bGhash(0x386656093df3f038d44c32e60a17dee1),
220			BinaryField128bGhash(0x386656093df3f038d44c32e60a17dee0),
221			BinaryField128bGhash(0x35ad604f7d51d2c6bfcf02ae363946a8),
222			BinaryField128bGhash(0x35ad604f7d51d2c6bfcf02ae363946a9),
223			BinaryField128bGhash(0x053d8555a9979a1ca13fe8ac5560ce0c),
224			BinaryField128bGhash(0x053d8555a9979a1ca13fe8ac5560ce0d),
225			BinaryField128bGhash(0x08f6b313e935b8e2cabcd8e4694e5645),
226			BinaryField128bGhash(0x08f6b313e935b8e2cabcd8e4694e5644),
227			BinaryField128bGhash(0xf210539fd8dd2772cbc26e38bdbd6c62),
228			BinaryField128bGhash(0xf210539fd8dd2772cbc26e38bdbd6c63),
229			BinaryField128bGhash(0xffdb65d9987f058ca0415e708193f42b),
230			BinaryField128bGhash(0xffdb65d9987f058ca0415e708193f42a),
231			BinaryField128bGhash(0xcf4b80c34cb94d56beb1b472e2ca7c8f),
232			BinaryField128bGhash(0xcf4b80c34cb94d56beb1b472e2ca7c8e),
233			BinaryField128bGhash(0xc280b6850c1b6fa8d532843adee4e4c6),
234			BinaryField128bGhash(0xc280b6850c1b6fa8d532843adee4e4c7),
235			BinaryField128bGhash(0x9f48977e59243eed8a63438944c99fce),
236			BinaryField128bGhash(0x9f48977e59243eed8a63438944c99fcf),
237			BinaryField128bGhash(0x9283a13819861c13e1e073c178e70787),
238			BinaryField128bGhash(0x9283a13819861c13e1e073c178e70786),
239			BinaryField128bGhash(0xa2134422cd4054c9ff1099c31bbe8f23),
240			BinaryField128bGhash(0xa2134422cd4054c9ff1099c31bbe8f22),
241			BinaryField128bGhash(0xafd872648de276379493a98b2790176a),
242			BinaryField128bGhash(0xafd872648de276379493a98b2790176b),
243			BinaryField128bGhash(0x186ca7a286376521c95c10ed4f932c55),
244			BinaryField128bGhash(0x186ca7a286376521c95c10ed4f932c54),
245			BinaryField128bGhash(0x15a791e4c69547dfa2df20a573bdb41c),
246			BinaryField128bGhash(0x15a791e4c69547dfa2df20a573bdb41d),
247			BinaryField128bGhash(0x253774fe12530f05bc2fcaa710e43cb8),
248			BinaryField128bGhash(0x253774fe12530f05bc2fcaa710e43cb9),
249			BinaryField128bGhash(0x28fc42b852f12dfbd7acfaef2ccaa4f1),
250			BinaryField128bGhash(0x28fc42b852f12dfbd7acfaef2ccaa4f0),
251			BinaryField128bGhash(0x7534634307ce7cbe88fd3d5cb6e7dff9),
252			BinaryField128bGhash(0x7534634307ce7cbe88fd3d5cb6e7dff8),
253			BinaryField128bGhash(0x78ff5505476c5e40e37e0d148ac947b0),
254			BinaryField128bGhash(0x78ff5505476c5e40e37e0d148ac947b1),
255			BinaryField128bGhash(0x486fb01f93aa169afd8ee716e990cf14),
256			BinaryField128bGhash(0x486fb01f93aa169afd8ee716e990cf15),
257			BinaryField128bGhash(0x45a48659d3083464960dd75ed5be575d),
258			BinaryField128bGhash(0x45a48659d3083464960dd75ed5be575c),
259			BinaryField128bGhash(0xbf4266d5e2e0abf497736182014d6d7a),
260			BinaryField128bGhash(0xbf4266d5e2e0abf497736182014d6d7b),
261			BinaryField128bGhash(0xb2895093a242890afcf051ca3d63f533),
262			BinaryField128bGhash(0xb2895093a242890afcf051ca3d63f532),
263			BinaryField128bGhash(0x8219b5897684c1d0e200bbc85e3a7d97),
264			BinaryField128bGhash(0x8219b5897684c1d0e200bbc85e3a7d96),
265			BinaryField128bGhash(0x8fd283cf3626e32e89838b806214e5de),
266			BinaryField128bGhash(0x8fd283cf3626e32e89838b806214e5df),
267			BinaryField128bGhash(0xd21aa2346319b26bd6d24c33f8399ed6),
268			BinaryField128bGhash(0xd21aa2346319b26bd6d24c33f8399ed7),
269			BinaryField128bGhash(0xdfd1947223bb9095bd517c7bc417069f),
270			BinaryField128bGhash(0xdfd1947223bb9095bd517c7bc417069e),
271			BinaryField128bGhash(0xef417168f77dd84fa3a19679a74e8e3b),
272			BinaryField128bGhash(0xef417168f77dd84fa3a19679a74e8e3a),
273			BinaryField128bGhash(0xe28a472eb7dffab1c822a6319b601672),
274			BinaryField128bGhash(0xe28a472eb7dffab1c822a6319b601673),
275			BinaryField128bGhash(0x93252331bf042b11512625b1f09fa87e),
276			BinaryField128bGhash(0x93252331bf042b11512625b1f09fa87f),
277			BinaryField128bGhash(0x9eee1577ffa609ef3aa515f9ccb13037),
278			BinaryField128bGhash(0x9eee1577ffa609ef3aa515f9ccb13036),
279			BinaryField128bGhash(0xae7ef06d2b6041352455fffbafe8b893),
280			BinaryField128bGhash(0xae7ef06d2b6041352455fffbafe8b892),
281			BinaryField128bGhash(0xa3b5c62b6bc263cb4fd6cfb393c620da),
282			BinaryField128bGhash(0xa3b5c62b6bc263cb4fd6cfb393c620db),
283			BinaryField128bGhash(0xfe7de7d03efd328e1087080009eb5bd2),
284			BinaryField128bGhash(0xfe7de7d03efd328e1087080009eb5bd3),
285			BinaryField128bGhash(0xf3b6d1967e5f10707b04384835c5c39b),
286			BinaryField128bGhash(0xf3b6d1967e5f10707b04384835c5c39a),
287			BinaryField128bGhash(0xc326348caa9958aa65f4d24a569c4b3f),
288			BinaryField128bGhash(0xc326348caa9958aa65f4d24a569c4b3e),
289			BinaryField128bGhash(0xceed02caea3b7a540e77e2026ab2d376),
290			BinaryField128bGhash(0xceed02caea3b7a540e77e2026ab2d377),
291			BinaryField128bGhash(0x340be246dbd3e5c40f0954debe41e951),
292			BinaryField128bGhash(0x340be246dbd3e5c40f0954debe41e950),
293			BinaryField128bGhash(0x39c0d4009b71c73a648a6496826f7118),
294			BinaryField128bGhash(0x39c0d4009b71c73a648a6496826f7119),
295			BinaryField128bGhash(0x0950311a4fb78fe07a7a8e94e136f9bc),
296			BinaryField128bGhash(0x0950311a4fb78fe07a7a8e94e136f9bd),
297			BinaryField128bGhash(0x049b075c0f15ad1e11f9bedcdd1861f5),
298			BinaryField128bGhash(0x049b075c0f15ad1e11f9bedcdd1861f4),
299			BinaryField128bGhash(0x595326a75a2afc5b4ea8796f47351afd),
300			BinaryField128bGhash(0x595326a75a2afc5b4ea8796f47351afc),
301			BinaryField128bGhash(0x549810e11a88dea5252b49277b1b82b4),
302			BinaryField128bGhash(0x549810e11a88dea5252b49277b1b82b5),
303			BinaryField128bGhash(0x6408f5fbce4e967f3bdba32518420a10),
304			BinaryField128bGhash(0x6408f5fbce4e967f3bdba32518420a11),
305			BinaryField128bGhash(0x69c3c3bd8eecb4815058936d246c9259),
306			BinaryField128bGhash(0x69c3c3bd8eecb4815058936d246c9258),
307			BinaryField128bGhash(0xde77167b8539a7970d972a0b4c6fa966),
308			BinaryField128bGhash(0xde77167b8539a7970d972a0b4c6fa967),
309			BinaryField128bGhash(0xd3bc203dc59b856966141a437041312f),
310			BinaryField128bGhash(0xd3bc203dc59b856966141a437041312e),
311			BinaryField128bGhash(0xe32cc527115dcdb378e4f0411318b98b),
312			BinaryField128bGhash(0xe32cc527115dcdb378e4f0411318b98a),
313			BinaryField128bGhash(0xeee7f36151ffef4d1367c0092f3621c2),
314			BinaryField128bGhash(0xeee7f36151ffef4d1367c0092f3621c3),
315			BinaryField128bGhash(0xb32fd29a04c0be084c3607bab51b5aca),
316			BinaryField128bGhash(0xb32fd29a04c0be084c3607bab51b5acb),
317			BinaryField128bGhash(0xbee4e4dc44629cf627b537f28935c283),
318			BinaryField128bGhash(0xbee4e4dc44629cf627b537f28935c282),
319			BinaryField128bGhash(0x8e7401c690a4d42c3945ddf0ea6c4a27),
320			BinaryField128bGhash(0x8e7401c690a4d42c3945ddf0ea6c4a26),
321			BinaryField128bGhash(0x83bf3780d006f6d252c6edb8d642d26e),
322			BinaryField128bGhash(0x83bf3780d006f6d252c6edb8d642d26f),
323			BinaryField128bGhash(0x7959d70ce1ee694253b85b6402b1e849),
324			BinaryField128bGhash(0x7959d70ce1ee694253b85b6402b1e848),
325			BinaryField128bGhash(0x7492e14aa14c4bbc383b6b2c3e9f7000),
326			BinaryField128bGhash(0x7492e14aa14c4bbc383b6b2c3e9f7001),
327			BinaryField128bGhash(0x44020450758a036626cb812e5dc6f8a4),
328			BinaryField128bGhash(0x44020450758a036626cb812e5dc6f8a5),
329			BinaryField128bGhash(0x49c93216352821984d48b16661e860ed),
330			BinaryField128bGhash(0x49c93216352821984d48b16661e860ec),
331			BinaryField128bGhash(0x140113ed601770dd121976d5fbc51be5),
332			BinaryField128bGhash(0x140113ed601770dd121976d5fbc51be4),
333			BinaryField128bGhash(0x19ca25ab20b55223799a469dc7eb83ac),
334			BinaryField128bGhash(0x19ca25ab20b55223799a469dc7eb83ad),
335			BinaryField128bGhash(0x295ac0b1f4731af9676aac9fa4b20b08),
336			BinaryField128bGhash(0x295ac0b1f4731af9676aac9fa4b20b09),
337			BinaryField128bGhash(0x2491f6f7b4d138070ce99cd7989c9341),
338			BinaryField128bGhash(0x2491f6f7b4d138070ce99cd7989c9340),
339			BinaryField128bGhash(0xc61bb1d9030ec2b6c4cb3ae603fc8533),
340			BinaryField128bGhash(0xc61bb1d9030ec2b6c4cb3ae603fc8532),
341			BinaryField128bGhash(0xcbd0879f43ace048af480aae3fd21d7a),
342			BinaryField128bGhash(0xcbd0879f43ace048af480aae3fd21d7b),
343			BinaryField128bGhash(0xfb406285976aa892b1b8e0ac5c8b95de),
344			BinaryField128bGhash(0xfb406285976aa892b1b8e0ac5c8b95df),
345			BinaryField128bGhash(0xf68b54c3d7c88a6cda3bd0e460a50d97),
346			BinaryField128bGhash(0xf68b54c3d7c88a6cda3bd0e460a50d96),
347			BinaryField128bGhash(0xab43753882f7db29856a1757fa88769f),
348			BinaryField128bGhash(0xab43753882f7db29856a1757fa88769e),
349			BinaryField128bGhash(0xa688437ec255f9d7eee9271fc6a6eed6),
350			BinaryField128bGhash(0xa688437ec255f9d7eee9271fc6a6eed7),
351			BinaryField128bGhash(0x9618a6641693b10df019cd1da5ff6672),
352			BinaryField128bGhash(0x9618a6641693b10df019cd1da5ff6673),
353			BinaryField128bGhash(0x9bd39022563193f39b9afd5599d1fe3b),
354			BinaryField128bGhash(0x9bd39022563193f39b9afd5599d1fe3a),
355			BinaryField128bGhash(0x613570ae67d90c639ae44b894d22c41c),
356			BinaryField128bGhash(0x613570ae67d90c639ae44b894d22c41d),
357			BinaryField128bGhash(0x6cfe46e8277b2e9df1677bc1710c5c55),
358			BinaryField128bGhash(0x6cfe46e8277b2e9df1677bc1710c5c54),
359			BinaryField128bGhash(0x5c6ea3f2f3bd6647ef9791c31255d4f1),
360			BinaryField128bGhash(0x5c6ea3f2f3bd6647ef9791c31255d4f0),
361			BinaryField128bGhash(0x51a595b4b31f44b98414a18b2e7b4cb8),
362			BinaryField128bGhash(0x51a595b4b31f44b98414a18b2e7b4cb9),
363			BinaryField128bGhash(0x0c6db44fe62015fcdb456638b45637b0),
364			BinaryField128bGhash(0x0c6db44fe62015fcdb456638b45637b1),
365			BinaryField128bGhash(0x01a68209a6823702b0c656708878aff9),
366			BinaryField128bGhash(0x01a68209a6823702b0c656708878aff8),
367			BinaryField128bGhash(0x3136671372447fd8ae36bc72eb21275d),
368			BinaryField128bGhash(0x3136671372447fd8ae36bc72eb21275c),
369			BinaryField128bGhash(0x3cfd515532e65d26c5b58c3ad70fbf14),
370			BinaryField128bGhash(0x3cfd515532e65d26c5b58c3ad70fbf15),
371			BinaryField128bGhash(0x8b49849339334e30987a355cbf0c842b),
372			BinaryField128bGhash(0x8b49849339334e30987a355cbf0c842a),
373			BinaryField128bGhash(0x8682b2d579916ccef3f9051483221c62),
374			BinaryField128bGhash(0x8682b2d579916ccef3f9051483221c63),
375			BinaryField128bGhash(0xb61257cfad572414ed09ef16e07b94c6),
376			BinaryField128bGhash(0xb61257cfad572414ed09ef16e07b94c7),
377			BinaryField128bGhash(0xbbd96189edf506ea868adf5edc550c8f),
378			BinaryField128bGhash(0xbbd96189edf506ea868adf5edc550c8e),
379			BinaryField128bGhash(0xe6114072b8ca57afd9db18ed46787787),
380			BinaryField128bGhash(0xe6114072b8ca57afd9db18ed46787786),
381			BinaryField128bGhash(0xebda7634f8687551b25828a57a56efce),
382			BinaryField128bGhash(0xebda7634f8687551b25828a57a56efcf),
383			BinaryField128bGhash(0xdb4a932e2cae3d8baca8c2a7190f676a),
384			BinaryField128bGhash(0xdb4a932e2cae3d8baca8c2a7190f676b),
385			BinaryField128bGhash(0xd681a5686c0c1f75c72bf2ef2521ff23),
386			BinaryField128bGhash(0xd681a5686c0c1f75c72bf2ef2521ff22),
387			BinaryField128bGhash(0x2c6745e45de480e5c6554433f1d2c504),
388			BinaryField128bGhash(0x2c6745e45de480e5c6554433f1d2c505),
389			BinaryField128bGhash(0x21ac73a21d46a21badd6747bcdfc5d4d),
390			BinaryField128bGhash(0x21ac73a21d46a21badd6747bcdfc5d4c),
391			BinaryField128bGhash(0x113c96b8c980eac1b3269e79aea5d5e9),
392			BinaryField128bGhash(0x113c96b8c980eac1b3269e79aea5d5e8),
393			BinaryField128bGhash(0x1cf7a0fe8922c83fd8a5ae31928b4da0),
394			BinaryField128bGhash(0x1cf7a0fe8922c83fd8a5ae31928b4da1),
395			BinaryField128bGhash(0x413f8105dc1d997a87f4698208a636a8),
396			BinaryField128bGhash(0x413f8105dc1d997a87f4698208a636a9),
397			BinaryField128bGhash(0x4cf4b7439cbfbb84ec7759ca3488aee1),
398			BinaryField128bGhash(0x4cf4b7439cbfbb84ec7759ca3488aee0),
399			BinaryField128bGhash(0x7c6452594879f35ef287b3c857d12645),
400			BinaryField128bGhash(0x7c6452594879f35ef287b3c857d12644),
401			BinaryField128bGhash(0x71af641f08dbd1a0990483806bffbe0c),
402			BinaryField128bGhash(0x71af641f08dbd1a0990483806bffbe0d),
403		];
404
405		LOOKUP_TABLE[value.0 as usize]
406	}
407}
408
409#[inline(always)]
410pub fn is_ghash_tower<F: TowerField>() -> bool {
411	TypeId::of::<F>() == TypeId::of::<BinaryField128bGhash>()
412		|| TypeId::of::<F>() == TypeId::of::<BinaryField1b>()
413}
414
415#[cfg(test)]
416mod tests {
417	use proptest::{prelude::any, proptest};
418
419	use super::*;
420	use crate::binary_field::tests::is_binary_field_valid_generator;
421
422	#[test]
423	fn test_ghash_mul() {
424		let a = BinaryField128bGhash(1u128);
425		let b = BinaryField128bGhash(1u128);
426		let c = a * b;
427
428		assert_eq!(c, BinaryField128bGhash::from(1u128));
429
430		let a = BinaryField128bGhash(1u128);
431		let b = BinaryField128bGhash(2u128);
432		let c = a * b;
433
434		assert_eq!(c, BinaryField128bGhash::from(2u128));
435
436		let a = BinaryField128bGhash(1u128);
437		let b = BinaryField128bGhash(1297182698762987u128);
438		let c = a * b;
439
440		assert_eq!(c, BinaryField128bGhash::from(1297182698762987u128));
441
442		let a = BinaryField128bGhash(2u128);
443		let b = BinaryField128bGhash(2u128);
444		let c = a * b;
445
446		assert_eq!(c, BinaryField128bGhash::from(4u128));
447
448		let a = BinaryField128bGhash(2u128);
449		let b = BinaryField128bGhash(3u128);
450		let c = a * b;
451
452		assert_eq!(c, BinaryField128bGhash::from(6u128));
453
454		let a = BinaryField128bGhash(3u128);
455		let b = BinaryField128bGhash(3u128);
456		let c = a * b;
457
458		assert_eq!(c, BinaryField128bGhash::from(5u128));
459
460		let a = BinaryField128bGhash(1u128 << 127);
461		let b = BinaryField128bGhash(2u128);
462		let c = a * b;
463
464		assert_eq!(c, BinaryField128bGhash::from(0b10000111));
465
466		let a = BinaryField128bGhash((1u128 << 127) + 1);
467		let b = BinaryField128bGhash(2u128);
468		let c = a * b;
469
470		assert_eq!(c, BinaryField128bGhash::from(0b10000101));
471
472		let a = BinaryField128bGhash(3u128 << 126);
473		let b = BinaryField128bGhash(2u128);
474		let c = a * b;
475
476		assert_eq!(c, BinaryField128bGhash::from(0b10000111 + (1u128 << 127)));
477
478		let a = BinaryField128bGhash(1u128 << 127);
479		let b = BinaryField128bGhash(4u128);
480		let c = a * b;
481
482		assert_eq!(c, BinaryField128bGhash::from(0b10000111 << 1));
483
484		let a = BinaryField128bGhash(1u128 << 127);
485		let b = BinaryField128bGhash(1u128 << 122);
486		let c = a * b;
487
488		assert_eq!(c, BinaryField128bGhash::from((0b00000111 << 121) + 0b10000111));
489	}
490
491	#[test]
492	fn test_multiplicative_generator() {
493		assert!(is_binary_field_valid_generator::<BinaryField128bGhash>());
494	}
495
496	#[test]
497	fn test_mul_x() {
498		let test_cases = [
499			0x0,                                    // Zero
500			0x1,                                    // One
501			0x2,                                    // Two
502			0x80000000000000000000000000000000u128, // High bit set
503			0x40000000000000000000000000000000u128, // Second highest bit
504			0xffffffffffffffffffffffffffffffffu128, // All bits set
505			0x87u128,                               // GHASH reduction polynomial
506			0x21ac73a21d46a21badd6747bcdfc5d4d,     // Random value
507		];
508
509		for &value in &test_cases {
510			let field_val = BinaryField128bGhash::new(value);
511			let mul_x_result = field_val.mul_x();
512			let regular_mul_result = field_val * BinaryField128bGhash::new(2u128);
513
514			assert_eq!(
515				mul_x_result, regular_mul_result,
516				"mul_x and regular multiplication by 2 differ for value {:#x}",
517				value
518			);
519		}
520	}
521
522	#[test]
523	fn test_mul_inv_x() {
524		let test_cases = [
525			0x0,                                    // Zero
526			0x1,                                    // One
527			0x2,                                    // Two
528			0x1u128,                                // Low bit set
529			0x3u128,                                // Two lowest bits set
530			0xffffffffffffffffffffffffffffffffu128, // All bits set
531			0x87u128,                               // GHASH reduction polynomial
532			0x21ac73a21d46a21badd6747bcdfc5d4d,     // Random value
533		];
534
535		for &value in &test_cases {
536			let field_val = BinaryField128bGhash::new(value);
537			let mul_inv_x_result = field_val.mul_inv_x();
538			let regular_mul_result = field_val
539				* BinaryField128bGhash::new(2u128)
540					.invert()
541					.expect("2 is invertible");
542
543			assert_eq!(
544				mul_inv_x_result, regular_mul_result,
545				"mul_inv_x and regular multiplication by 2 differ for value {:#x}",
546				value
547			);
548		}
549	}
550
551	proptest! {
552		#[test]
553		fn test_conversion_from_aes_consistency(a in any::<u8>(), b in any::<u8>()) {
554			let a_val = AESTowerField8b::new(a);
555			let b_val = AESTowerField8b::new(b);
556			let converted_a = BinaryField128bGhash::from(a_val);
557			let converted_b = BinaryField128bGhash::from(b_val);
558			assert_eq!(BinaryField128bGhash::from(a_val * b_val), converted_a * converted_b);
559		}
560
561		#[test]
562		fn test_wide_mul_correctness(a in any::<u128>(), b in any::<u128>()) {
563			let a = BinaryField128bGhash::new(a);
564			let b = BinaryField128bGhash::new(b);
565			let reduced = BinaryField128bGhash::reduce(BinaryField128bGhash::wide_mul(a, b));
566			assert_eq!(reduced, a * b);
567		}
568
569		// Exercises the point of the trait: accumulate two unreduced products, reduce once.
570		#[test]
571		fn test_wide_mul_deferred_accumulation(
572			a1 in any::<u128>(), b1 in any::<u128>(),
573			a2 in any::<u128>(), b2 in any::<u128>(),
574		) {
575			let (a1, b1) = (BinaryField128bGhash::new(a1), BinaryField128bGhash::new(b1));
576			let (a2, b2) = (BinaryField128bGhash::new(a2), BinaryField128bGhash::new(b2));
577			let wide =
578				BinaryField128bGhash::wide_mul(a1, b1) + BinaryField128bGhash::wide_mul(a2, b2);
579			assert_eq!(BinaryField128bGhash::reduce(wide), a1 * b1 + a2 * b2);
580		}
581	}
582}
binius_field/ghash.rs

binius_field/
ghash.rs
