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::{error::Error, 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	fn basis(i: usize) -> Result<Self, Error>;
31
32	/// Create an extension field element from a slice of base field elements in order
33	/// consistent with `basis(i)` return values.
34	/// Potentially faster than taking an inner product with a vector of basis elements.
35	fn from_bases(base_elems: &[F]) -> Result<Self, Error> {
36		Self::from_bases_sparse(base_elems, 0)
37	}
38
39	/// A specialized version of `from_bases` which assumes that only base field
40	/// elements with indices dividing `2^log_stride` can be nonzero.
41	///
42	/// `base_elems` should have length at most `ceil(DEGREE / 2^LOG_STRIDE)`. Note that
43	/// [`ExtensionField::from_bases`] is a special case of `from_bases_sparse` with `log_stride = 0`.
44	fn from_bases_sparse(base_elems: &[F], log_stride: usize) -> Result<Self, Error>;
45
46	/// Iterator over base field elements.
47	fn iter_bases(&self) -> impl Iterator<Item = F>;
48
49	/// Convert into an iterator over base field elements.
50	fn into_iter_bases(self) -> impl Iterator<Item = F>;
51
52	/// Returns the i-th base field element.
53	#[inline]
54	fn get_base(&self, i: usize) -> F {
55		assert!(i < Self::DEGREE, "index out of bounds");
56		unsafe { self.get_base_unchecked(i) }
57	}
58
59	/// Returns the i-th base field element without bounds checking.
60	///
61	/// # Safety
62	/// `i` must be less than `DEGREE`.
63	unsafe fn get_base_unchecked(&self, i: usize) -> F;
64}
65
66impl<F: Field> ExtensionField<F> for F {
67	const LOG_DEGREE: usize = 0;
68
69	#[inline(always)]
70	fn basis(i: usize) -> Result<Self, Error> {
71		if i != 0 {
72			return Err(Error::ExtensionDegreeMismatch);
73		}
74		Ok(Self::ONE)
75	}
76
77	#[inline(always)]
78	fn from_bases_sparse(base_elems: &[F], log_stride: usize) -> Result<Self, Error> {
79		if log_stride != 0 {
80			return Err(Error::ExtensionDegreeMismatch);
81		}
82
83		match base_elems.len() {
84			0 => Ok(F::ZERO),
85			1 => Ok(base_elems[0]),
86			_ => Err(Error::ExtensionDegreeMismatch),
87		}
88	}
89
90	#[inline(always)]
91	fn iter_bases(&self) -> impl Iterator<Item = F> {
92		iter::once(*self)
93	}
94
95	#[inline(always)]
96	fn into_iter_bases(self) -> impl Iterator<Item = F> {
97		iter::once(self)
98	}
99
100	#[inline(always)]
101	unsafe fn get_base_unchecked(&self, i: usize) -> F {
102		debug_assert_eq!(i, 0);
103		*self
104	}
105}
binius_field/extension.rs

binius_field/
extension.rs
