binius_field/
field.rs

1// Copyright 2024-2025 Irreducible Inc.
2// Copyright 2026 The Binius Developers
3
4use std::{
5	fmt::Display,
6	hash::Hash,
7	iter::{self, Product, Sum},
8	ops::{Add, AddAssign, Mul, MulAssign, Neg, Sub, SubAssign},
9};
10
11use binius_utils::{DeserializeBytes, FixedSizeSerializeBytes, SerializeBytes};
12
13use crate::{
14	PackedField,
15	arithmetic_traits::{InvertOrZero, Square},
16};
17
18/// An element of a finite field.
19///
20/// A finite field (also called a Galois field) has order `p^k` where `p` is the
21/// [`CHARACTERISTIC`](Self::CHARACTERISTIC) and `k` is the
22/// [`ORDER_EXPONENT`](Self::ORDER_EXPONENT).
23pub trait Field:
24	PackedField<Scalar = Self>
25	+ Display
26	+ Hash
27	+ SerializeBytes
28	+ DeserializeBytes
29	+ FixedSizeSerializeBytes
30{
31	/// The zero element of the field, the additive identity.
32	const ZERO: Self;
33
34	/// The one element of the field, the multiplicative identity.
35	const ONE: Self;
36
37	/// The characteristic `p` of the field. The field order is `p^k` where `k` is
38	/// [`ORDER_EXPONENT`](Self::ORDER_EXPONENT).
39	const CHARACTERISTIC: usize;
40
41	/// The exponent `k` such that the field order equals `CHARACTERISTIC^k`.
42	const ORDER_EXPONENT: usize;
43
44	/// Fixed generator of the multiplicative group.
45	const MULTIPLICATIVE_GENERATOR: Self;
46
47	/// Returns true iff this element is zero.
48	fn is_zero(&self) -> bool {
49		*self == Self::ZERO
50	}
51
52	/// Doubles this element.
53	#[must_use]
54	fn double(&self) -> Self;
55
56	/// Exponentiates `self` by `exp`, where `exp` is a little-endian order integer
57	/// exponent.
58	fn pow<S: AsRef<[u64]>>(&self, exp: S) -> Self {
59		let mut res = Self::ONE;
60		for e in exp.as_ref().iter().rev() {
61			for i in (0..64).rev() {
62				res = res.square();
63
64				if ((*e >> i) & 1) == 1 {
65					res.mul_assign(self);
66				}
67			}
68		}
69
70		res
71	}
72}
73
74/// Operations for types that represent vectors of field elements.
75///
76/// This trait abstracts over:
77/// - [`Field`] types (single field elements, which are trivially vectors of length 1)
78/// - [`PackedField`] types (SIMD-accelerated vectors of field elements)
79/// - Symbolic field types (for constraint system representations)
80///
81/// Mathematically, instances of this trait represent vectors of field elements where
82/// arithmetic operations like addition, subtraction, multiplication, squaring, and
83/// inversion are defined element-wise. For a packed field with width N, multiplying
84/// two values performs N independent field multiplications in parallel.
85///
86/// # Required Methods
87///
88/// - [`zero()`](Self::zero) - Returns the additive identity (all elements are zero)
89/// - [`one()`](Self::one) - Returns the multiplicative identity (all elements are one)
90pub trait FieldOps:
91	Clone
92	+ Neg<Output = Self>
93	+ Add<Output = Self>
94	+ Sub<Output = Self>
95	+ Mul<Output = Self>
96	+ Sum
97	+ Product
98	+ for<'a> Add<&'a Self, Output = Self>
99	+ for<'a> Sub<&'a Self, Output = Self>
100	+ for<'a> Mul<&'a Self, Output = Self>
101	+ for<'a> Sum<&'a Self>
102	+ for<'a> Product<&'a Self>
103	+ AddAssign
104	+ SubAssign
105	+ MulAssign
106	+ for<'a> AddAssign<&'a Self>
107	+ for<'a> SubAssign<&'a Self>
108	+ for<'a> MulAssign<&'a Self>
109	+ Square
110	+ InvertOrZero
111{
112	type Scalar: Field;
113
114	/// Returns the zero element (additive identity).
115	fn zero() -> Self;
116
117	/// Returns the one element (multiplicative identity).
118	fn one() -> Self;
119
120	/// Transpose the subfield elements in a slice of field elements.
121	///
122	/// ## Arguments
123	///
124	/// * `elems` - a slice of $n$ elements, where $n$ is the degee of the extension of
125	///   `Self::Scalar` over `FSub`. They are overwritten with the result elements.
126	///
127	/// ## Preconditions
128	///
129	/// * `elems.len()` must equal `Self::Scalar::DEGREE`
130	fn square_transpose<FSub: Field>(elems: &mut [Self])
131	where
132		Self::Scalar: ExtensionField<FSub>;
133}
134
135impl<F: Field> FieldOps for F {
136	type Scalar = F;
137
138	fn zero() -> Self {
139		Self::ZERO
140	}
141
142	fn one() -> Self {
143		Self::ONE
144	}
145
146	fn square_transpose<FSub: Field>(elems: &mut [Self])
147	where
148		F: ExtensionField<FSub>,
149	{
150		<F as ExtensionField<FSub>>::square_transpose(elems);
151	}
152}
153
154pub trait ExtensionField<F: Field>:
155	Field
156	+ From<F>
157	+ TryInto<F>
158	+ Add<F, Output = Self>
159	+ Sub<F, Output = Self>
160	+ Mul<F, Output = Self>
161	+ AddAssign<F>
162	+ SubAssign<F>
163	+ MulAssign<F>
164{
165	/// Base-2 logarithm of the extension degree.
166	const LOG_DEGREE: usize;
167
168	/// Extension degree.
169	///
170	/// `DEGREE` is guaranteed to equal `2^LOG_DEGREE`.
171	const DEGREE: usize = 1 << Self::LOG_DEGREE;
172
173	/// For `0 <= i < DEGREE`, returns `i`-th basis field element.
174	///
175	/// # Preconditions
176	///
177	/// * `i` must be in the range [0, `Self::DEGREE`).
178	fn basis(i: usize) -> Self;
179
180	/// Create an extension field element from a slice of base field elements in order
181	/// consistent with `basis(i)` return values.
182	/// Potentially faster than taking an inner product with a vector of basis elements.
183	///
184	/// # Preconditions
185	///
186	/// * `base_elems` must have at most `DEGREE` elements.
187	#[inline]
188	fn from_bases(base_elems: impl IntoIterator<Item = F>) -> Self {
189		Self::from_bases_sparse(base_elems, 0)
190	}
191
192	/// A specialized version of `from_bases` which assumes that only base field
193	/// elements with indices dividing `2^log_stride` can be nonzero.
194	///
195	/// `base_elems` should have length at most `ceil(DEGREE / 2^LOG_STRIDE)`. Note that
196	/// [`ExtensionField::from_bases`] is a special case of `from_bases_sparse` with `log_stride =
197	/// 0`.
198	///
199	/// # Preconditions
200	///
201	/// * `log_stride` must be at most `LOG_DEGREE`.
202	/// * `base_elems` must have at most `ceil(DEGREE / 2^log_stride)` elements.
203	fn from_bases_sparse(base_elems: impl IntoIterator<Item = F>, log_stride: usize) -> Self;
204
205	/// Iterator over base field elements.
206	fn iter_bases(&self) -> impl Iterator<Item = F>;
207
208	/// Returns the i-th base field element.
209	#[inline]
210	fn get_base(&self, i: usize) -> F {
211		assert!(i < Self::DEGREE, "index out of bounds");
212		unsafe { self.get_base_unchecked(i) }
213	}
214
215	/// Returns the i-th base field element without bounds checking.
216	///
217	/// # Safety
218	/// `i` must be less than `DEGREE`.
219	unsafe fn get_base_unchecked(&self, i: usize) -> F;
220
221	/// Transpose square block of subfield elements within `values` in place.
222	///
223	/// # Preconditions
224	///
225	/// * `values.len()` must equal `DEGREE`.
226	fn square_transpose(values: &mut [Self]);
227}
228
229impl<F: Field> ExtensionField<F> for F {
230	const LOG_DEGREE: usize = 0;
231
232	#[inline(always)]
233	fn basis(i: usize) -> Self {
234		assert!(i == 0, "index {i} out of range for degree 1");
235		Self::ONE
236	}
237
238	#[inline(always)]
239	fn from_bases_sparse(base_elems: impl IntoIterator<Item = F>, log_stride: usize) -> Self {
240		assert!(log_stride == 0, "log_stride must be 0 for degree-1 extension");
241		let mut base_elems = base_elems.into_iter();
242		base_elems.next().unwrap_or(Self::ZERO)
243	}
244
245	#[inline(always)]
246	fn iter_bases(&self) -> impl Iterator<Item = F> {
247		iter::once(*self)
248	}
249
250	#[inline(always)]
251	unsafe fn get_base_unchecked(&self, i: usize) -> F {
252		debug_assert_eq!(i, 0);
253		*self
254	}
255
256	#[inline]
257	fn square_transpose(values: &mut [Self]) {
258		assert!(values.len() == 1, "values.len() must be 1 for degree-1 extension");
259	}
260}
binius_field/field.rs

binius_field/
field.rs
