binius_field/
extension.rs

1// Copyright 2023-2025 Irreducible Inc.
2
3use std::{
4	iter,
5	ops::{Add, AddAssign, Mul, MulAssign, Sub, SubAssign},
6};
7
8use super::Field;
9
10pub trait ExtensionField<F: Field>:
11	Field
12	+ From<F>
13	+ TryInto<F>
14	+ Add<F, Output = Self>
15	+ Sub<F, Output = Self>
16	+ Mul<F, Output = Self>
17	+ AddAssign<F>
18	+ SubAssign<F>
19	+ MulAssign<F>
20{
21	/// Base-2 logarithm of the extension degree.
22	const LOG_DEGREE: usize;
23
24	/// Extension degree.
25	///
26	/// `DEGREE` is guaranteed to equal `2^LOG_DEGREE`.
27	const DEGREE: usize = 1 << Self::LOG_DEGREE;
28
29	/// For `0 <= i < DEGREE`, returns `i`-th basis field element.
30	///
31	/// # Preconditions
32	///
33	/// * `i` must be in the range [0, `Self::DEGREE`).
34	fn basis(i: usize) -> Self;
35
36	/// Create an extension field element from a slice of base field elements in order
37	/// consistent with `basis(i)` return values.
38	/// Potentially faster than taking an inner product with a vector of basis elements.
39	///
40	/// # Preconditions
41	///
42	/// * `base_elems` must have at most `DEGREE` elements.
43	#[inline]
44	fn from_bases(base_elems: impl IntoIterator<Item = F>) -> Self {
45		Self::from_bases_sparse(base_elems, 0)
46	}
47
48	/// A specialized version of `from_bases` which assumes that only base field
49	/// elements with indices dividing `2^log_stride` can be nonzero.
50	///
51	/// `base_elems` should have length at most `ceil(DEGREE / 2^LOG_STRIDE)`. Note that
52	/// [`ExtensionField::from_bases`] is a special case of `from_bases_sparse` with `log_stride =
53	/// 0`.
54	///
55	/// # Preconditions
56	///
57	/// * `log_stride` must be at most `LOG_DEGREE`.
58	/// * `base_elems` must have at most `ceil(DEGREE / 2^log_stride)` elements.
59	fn from_bases_sparse(base_elems: impl IntoIterator<Item = F>, log_stride: usize) -> Self;
60
61	/// Iterator over base field elements.
62	fn iter_bases(&self) -> impl Iterator<Item = F>;
63
64	/// Convert into an iterator over base field elements.
65	fn into_iter_bases(self) -> impl Iterator<Item = F>;
66
67	/// Returns the i-th base field element.
68	#[inline]
69	fn get_base(&self, i: usize) -> F {
70		assert!(i < Self::DEGREE, "index out of bounds");
71		unsafe { self.get_base_unchecked(i) }
72	}
73
74	/// Returns the i-th base field element without bounds checking.
75	///
76	/// # Safety
77	/// `i` must be less than `DEGREE`.
78	unsafe fn get_base_unchecked(&self, i: usize) -> F;
79
80	/// Transpose square block of subfield elements within `values` in place.
81	///
82	/// # Preconditions
83	///
84	/// * `values.len()` must equal `DEGREE`.
85	fn square_transpose(values: &mut [Self]);
86}
87
88impl<F: Field> ExtensionField<F> for F {
89	const LOG_DEGREE: usize = 0;
90
91	#[inline(always)]
92	fn basis(i: usize) -> Self {
93		assert!(i == 0, "index {i} out of range for degree 1");
94		Self::ONE
95	}
96
97	#[inline(always)]
98	fn from_bases_sparse(base_elems: impl IntoIterator<Item = F>, log_stride: usize) -> Self {
99		assert!(log_stride == 0, "log_stride must be 0 for degree-1 extension");
100		let mut base_elems = base_elems.into_iter();
101		base_elems.next().unwrap_or(Self::ZERO)
102	}
103
104	#[inline(always)]
105	fn iter_bases(&self) -> impl Iterator<Item = F> {
106		iter::once(*self)
107	}
108
109	#[inline(always)]
110	fn into_iter_bases(self) -> impl Iterator<Item = F> {
111		iter::once(self)
112	}
113
114	#[inline(always)]
115	unsafe fn get_base_unchecked(&self, i: usize) -> F {
116		debug_assert_eq!(i, 0);
117		*self
118	}
119
120	#[inline]
121	fn square_transpose(values: &mut [Self]) {
122		assert!(values.len() == 1, "values.len() must be 1 for degree-1 extension");
123	}
124}
binius_field/extension.rs

binius_field/
extension.rs
