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, error::Error};
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	/// ## Pre-conditions
32	///
33	/// * `i` must be in the range [0, `Self::DEGREE`).
34	#[inline]
35	fn basis(i: usize) -> Self {
36		Self::basis_checked(i).expect("pre-condition: 0 <= i < DEGREE")
37	}
38
39	/// For `0 <= i < DEGREE`, returns `i`-th basis field element.
40	///
41	/// This is the same operation as [`Self::basis`], but it returns an error result instead of
42	/// panicking if the index is out of range.
43	///
44	/// ## Throws
45	///
46	/// * `Error::ExtensionDegreeMismatch` unless `i` is in the range [0, `Self::DEGREE`).
47	fn basis_checked(i: usize) -> Result<Self, Error>;
48
49	/// Create an extension field element from a slice of base field elements in order
50	/// consistent with `basis(i)` return values.
51	/// Potentially faster than taking an inner product with a vector of basis elements.
52	#[inline]
53	fn from_bases(base_elems: impl IntoIterator<Item = F>) -> Result<Self, Error> {
54		Self::from_bases_sparse(base_elems, 0)
55	}
56
57	/// A specialized version of `from_bases` which assumes that only base field
58	/// elements with indices dividing `2^log_stride` can be nonzero.
59	///
60	/// `base_elems` should have length at most `ceil(DEGREE / 2^LOG_STRIDE)`. Note that
61	/// [`ExtensionField::from_bases`] is a special case of `from_bases_sparse` with `log_stride =
62	/// 0`.
63	fn from_bases_sparse(
64		base_elems: impl IntoIterator<Item = F>,
65		log_stride: usize,
66	) -> Result<Self, Error>;
67
68	/// Iterator over base field elements.
69	fn iter_bases(&self) -> impl Iterator<Item = F>;
70
71	/// Convert into an iterator over base field elements.
72	fn into_iter_bases(self) -> impl Iterator<Item = F>;
73
74	/// Returns the i-th base field element.
75	#[inline]
76	fn get_base(&self, i: usize) -> F {
77		assert!(i < Self::DEGREE, "index out of bounds");
78		unsafe { self.get_base_unchecked(i) }
79	}
80
81	/// Returns the i-th base field element without bounds checking.
82	///
83	/// # Safety
84	/// `i` must be less than `DEGREE`.
85	unsafe fn get_base_unchecked(&self, i: usize) -> F;
86
87	/// Transpose square block of subfield elements within `values` in place.
88	fn square_transpose(values: &mut [Self]) -> Result<(), Error>;
89}
90
91impl<F: Field> ExtensionField<F> for F {
92	const LOG_DEGREE: usize = 0;
93
94	#[inline(always)]
95	fn basis_checked(i: usize) -> Result<Self, Error> {
96		if i != 0 {
97			return Err(Error::ExtensionDegreeMismatch);
98		}
99		Ok(Self::ONE)
100	}
101
102	#[inline(always)]
103	fn from_bases_sparse(
104		base_elems: impl IntoIterator<Item = F>,
105		log_stride: usize,
106	) -> Result<Self, Error> {
107		let mut base_elems = base_elems.into_iter();
108		if log_stride != 0 {
109			return Err(Error::ExtensionDegreeMismatch);
110		}
111
112		match base_elems.next() {
113			Some(elem) => Ok(elem),
114			None => Ok(Self::ZERO),
115		}
116	}
117
118	#[inline(always)]
119	fn iter_bases(&self) -> impl Iterator<Item = F> {
120		iter::once(*self)
121	}
122
123	#[inline(always)]
124	fn into_iter_bases(self) -> impl Iterator<Item = F> {
125		iter::once(self)
126	}
127
128	#[inline(always)]
129	unsafe fn get_base_unchecked(&self, i: usize) -> F {
130		debug_assert_eq!(i, 0);
131		*self
132	}
133
134	#[inline]
135	fn square_transpose(values: &mut [Self]) -> Result<(), Error> {
136		if values.len() != 1 {
137			return Err(Error::MismatchedLengths);
138		}
139
140		Ok(())
141	}
142}
binius_field/extension.rs

binius_field/
extension.rs
