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

binius_field/
ghash.rs
