binius_math/
binary_subspace.rs

1// Copyright 2024-2025 Irreducible Inc.
2
3use binius_field::BinaryField;
4use binius_utils::{bail, iter::IterExtensions};
5
6use super::error::Error;
7
8/// An $F_2$-linear subspace of a binary field.
9///
10/// The subspace is defined by a basis of elements from a binary field. The basis elements are
11/// ordered, which implies an ordering on the subspace elements.
12#[derive(Debug, Clone)]
13pub struct BinarySubspace<F: BinaryField> {
14	basis: Vec<F>,
15}
16
17impl<F: BinaryField> BinarySubspace<F> {
18	/// Creates a new subspace from a vector of ordered basis elements.
19	///
20	/// This constructor does not check that the basis elements are linearly independent.
21	pub const fn new_unchecked(basis: Vec<F>) -> Self {
22		Self { basis }
23	}
24
25	/// Creates a new subspace of this binary subspace with the given dimension.
26	///
27	/// This creates a new sub-subspace using a prefix of the default $\mathbb{F}_2$ basis elements
28	/// of the field.
29	///
30	/// ## Throws
31	///
32	/// * `Error::DomainSizeTooLarge` if `dim` is greater than this subspace's dimension.
33	pub fn with_dim(dim: usize) -> Result<Self, Error> {
34		let basis = (0..dim)
35			.map(|i| F::basis_checked(i).map_err(|_| Error::DomainSizeTooLarge))
36			.collect::<Result<_, _>>()?;
37		Ok(Self { basis })
38	}
39
40	/// Creates a new subspace of this binary subspace with reduced dimension.
41	///
42	/// This creates a new sub-subspace using a prefix of the ordered basis elements.
43	///
44	/// ## Throws
45	///
46	/// * `Error::DomainSizeTooLarge` if `dim` is greater than this subspace's dimension.
47	pub fn reduce_dim(&self, dim: usize) -> Result<Self, Error> {
48		if dim > self.dim() {
49			bail!(Error::DomainSizeTooLarge);
50		}
51		Ok(Self {
52			basis: self.basis[..dim].to_vec(),
53		})
54	}
55
56	/// Creates a new subspace isomorphic to the given one.
57	pub fn isomorphic<FIso>(&self) -> BinarySubspace<FIso>
58	where
59		FIso: BinaryField + From<F>,
60	{
61		BinarySubspace {
62			basis: self.basis.iter().copied().map(Into::into).collect(),
63		}
64	}
65
66	/// Returns the dimension of the subspace.
67	pub fn dim(&self) -> usize {
68		self.basis.len()
69	}
70
71	/// Returns the slice of ordered basis elements.
72	pub fn basis(&self) -> &[F] {
73		&self.basis
74	}
75
76	pub fn get(&self, index: usize) -> F {
77		self.basis
78			.iter()
79			.take(usize::BITS as usize)
80			.enumerate()
81			.fold(F::ZERO, |acc, (i, basis_i)| {
82				if (index >> i) & 1 != 0 {
83					acc + basis_i
84				} else {
85					acc
86				}
87			})
88	}
89
90	pub fn get_checked(&self, index: usize) -> Result<F, Error> {
91		if index >= 1 << self.basis.len() {
92			bail!(Error::ArgumentRangeError {
93				arg: "index".to_string(),
94				range: 0..1 << self.basis.len(),
95			});
96		}
97		Ok(self.get(index))
98	}
99
100	/// Returns an iterator over all elements of the subspace in order.
101	///
102	/// This has a limitation that the iterator only yields the first `2^usize::BITS` elements.
103	pub fn iter(&self) -> impl Iterator<Item = F> + '_ {
104		let last = if self.basis.len() < usize::BITS as usize {
105			(1 << self.basis.len()) - 1
106		} else {
107			usize::MAX
108		};
109		(0..=last).map_skippable(|i| self.get(i))
110	}
111}
112
113impl<F: BinaryField> Default for BinarySubspace<F> {
114	fn default() -> Self {
115		let basis = (0..F::DEGREE).map(|i| F::basis(i)).collect();
116		Self { basis }
117	}
118}
119
120#[cfg(test)]
121mod tests {
122	use assert_matches::assert_matches;
123	use binius_field::{BinaryField128b, BinaryField8b};
124
125	use super::*;
126
127	#[test]
128	fn test_default_binary_subspace_iterates_elements() {
129		let subspace = BinarySubspace::<BinaryField8b>::default();
130		for i in 0..=255 {
131			assert_eq!(subspace.get(i), BinaryField8b::new(i as u8));
132		}
133	}
134
135	#[test]
136	fn test_binary_subspace_range_error() {
137		let subspace = BinarySubspace::<BinaryField8b>::default();
138		assert_matches!(subspace.get_checked(256), Err(Error::ArgumentRangeError { .. }));
139	}
140
141	#[test]
142	fn test_default_large_binary_subspace_iterates_elements() {
143		let subspace = BinarySubspace::<BinaryField128b>::default();
144		for i in 0..=255 {
145			assert_eq!(subspace.get(i), BinaryField128b::new(i as u128));
146		}
147	}
148
149	#[test]
150	fn test_default_binary_subspace() {
151		let subspace = BinarySubspace::<BinaryField8b>::default();
152		assert_eq!(subspace.dim(), 8);
153		assert_eq!(subspace.basis().len(), 8);
154
155		assert_eq!(
156			subspace.basis(),
157			[
158				BinaryField8b::new(0b00000001),
159				BinaryField8b::new(0b00000010),
160				BinaryField8b::new(0b00000100),
161				BinaryField8b::new(0b00001000),
162				BinaryField8b::new(0b00010000),
163				BinaryField8b::new(0b00100000),
164				BinaryField8b::new(0b01000000),
165				BinaryField8b::new(0b10000000)
166			]
167		);
168
169		let expected_elements: [u8; 256] = (0..=255).collect::<Vec<_>>().try_into().unwrap();
170
171		for (i, &expected) in expected_elements.iter().enumerate() {
172			assert_eq!(subspace.get(i), BinaryField8b::new(expected));
173		}
174	}
175
176	#[test]
177	fn test_with_dim_valid() {
178		let subspace = BinarySubspace::<BinaryField8b>::with_dim(3).unwrap();
179		assert_eq!(subspace.dim(), 3);
180		assert_eq!(subspace.basis().len(), 3);
181
182		assert_eq!(
183			subspace.basis(),
184			[
185				BinaryField8b::new(0b001),
186				BinaryField8b::new(0b010),
187				BinaryField8b::new(0b100)
188			]
189		);
190
191		let expected_elements: [u8; 8] = [0b000, 0b001, 0b010, 0b011, 0b100, 0b101, 0b110, 0b111];
192
193		for (i, &expected) in expected_elements.iter().enumerate() {
194			assert_eq!(subspace.get(i), BinaryField8b::new(expected));
195		}
196	}
197
198	#[test]
199	fn test_with_dim_invalid() {
200		let result = BinarySubspace::<BinaryField8b>::with_dim(10);
201		assert_matches!(result, Err(Error::DomainSizeTooLarge));
202	}
203
204	#[test]
205	fn test_reduce_dim_valid() {
206		let subspace = BinarySubspace::<BinaryField8b>::with_dim(6).unwrap();
207		let reduced = subspace.reduce_dim(4).unwrap();
208		assert_eq!(reduced.dim(), 4);
209		assert_eq!(reduced.basis().len(), 4);
210
211		assert_eq!(
212			reduced.basis(),
213			[
214				BinaryField8b::new(0b0001),
215				BinaryField8b::new(0b0010),
216				BinaryField8b::new(0b0100),
217				BinaryField8b::new(0b1000)
218			]
219		);
220
221		let expected_elements: [u8; 16] = (0..16).collect::<Vec<_>>().try_into().unwrap();
222
223		for (i, &expected) in expected_elements.iter().enumerate() {
224			assert_eq!(reduced.get(i), BinaryField8b::new(expected));
225		}
226	}
227
228	#[test]
229	fn test_reduce_dim_invalid() {
230		let subspace = BinarySubspace::<BinaryField8b>::with_dim(4).unwrap();
231		let result = subspace.reduce_dim(6);
232		assert_matches!(result, Err(Error::DomainSizeTooLarge));
233	}
234
235	#[test]
236	fn test_isomorphic_conversion() {
237		let subspace = BinarySubspace::<BinaryField8b>::with_dim(3).unwrap();
238		let iso_subspace: BinarySubspace<BinaryField128b> = subspace.isomorphic();
239		assert_eq!(iso_subspace.dim(), 3);
240		assert_eq!(iso_subspace.basis().len(), 3);
241
242		assert_eq!(
243			iso_subspace.basis(),
244			[
245				BinaryField128b::from(BinaryField8b::new(0b001)),
246				BinaryField128b::from(BinaryField8b::new(0b010)),
247				BinaryField128b::from(BinaryField8b::new(0b100))
248			]
249		);
250	}
251
252	#[test]
253	fn test_get_checked_valid() {
254		let subspace = BinarySubspace::<BinaryField8b>::default();
255		for i in 0..256 {
256			assert!(subspace.get_checked(i).is_ok());
257		}
258	}
259
260	#[test]
261	fn test_get_checked_invalid() {
262		let subspace = BinarySubspace::<BinaryField8b>::default();
263		assert_matches!(subspace.get_checked(256), Err(Error::ArgumentRangeError { .. }));
264	}
265
266	#[test]
267	fn test_iterate_subspace() {
268		let subspace = BinarySubspace::<BinaryField8b>::with_dim(3).unwrap();
269		let elements: Vec<_> = subspace.iter().collect();
270		assert_eq!(elements.len(), 8);
271
272		let expected_elements: [u8; 8] = [0b000, 0b001, 0b010, 0b011, 0b100, 0b101, 0b110, 0b111];
273
274		for (i, &expected) in expected_elements.iter().enumerate() {
275			assert_eq!(elements[i], BinaryField8b::new(expected));
276		}
277	}
278}