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

binius_field/
ghash.rs
