binius_field/
field.rs

1// Copyright 2024-2025 Irreducible Inc.
2// Copyright 2026 The Binius Developers
3
4use std::{
5	fmt::{Debug, Display},
6	hash::Hash,
7	iter::{Product, Sum},
8	ops::{Add, AddAssign, Mul, MulAssign, Neg, Sub, SubAssign},
9};
10
11use binius_utils::{DeserializeBytes, FixedSizeSerializeBytes, SerializeBytes};
12use bytemuck::Zeroable;
13
14use super::extension::ExtensionField;
15use crate::{
16	Random, WideMul,
17	arithmetic_traits::{InvertOrZero, Square},
18};
19
20/// An element of a finite field.
21///
22/// A finite field (also called a Galois field) has order `p^k` where `p` is the
23/// [`CHARACTERISTIC`](Self::CHARACTERISTIC) and `k` is the
24/// [`ORDER_EXPONENT`](Self::ORDER_EXPONENT).
25pub trait Field:
26	Sized
27	+ Eq
28	+ Copy
29	+ Clone
30	+ Default
31	+ Send
32	+ Sync
33	+ Debug
34	+ Display
35	+ Hash
36	+ 'static
37	+ Neg<Output = Self>
38	+ Add<Output = Self>
39	+ Sub<Output = Self>
40	+ Mul<Output = Self>
41	+ for<'a> Add<&'a Self, Output = Self>
42	+ for<'a> Sub<&'a Self, Output = Self>
43	+ for<'a> Mul<&'a Self, Output = Self>
44	+ Sum
45	+ Product
46	+ for<'a> Sum<&'a Self>
47	+ for<'a> Product<&'a Self>
48	+ AddAssign
49	+ SubAssign
50	+ MulAssign
51	+ for<'a> AddAssign<&'a Self>
52	+ for<'a> SubAssign<&'a Self>
53	+ for<'a> MulAssign<&'a Self>
54	+ Square
55	+ InvertOrZero
56	+ Random
57	+ Zeroable
58	+ SerializeBytes
59	+ DeserializeBytes
60	+ FixedSizeSerializeBytes
61	+ WideMul<Output: Debug + Send + Sync + 'static>
62{
63	/// The zero element of the field, the additive identity.
64	const ZERO: Self;
65
66	/// The one element of the field, the multiplicative identity.
67	const ONE: Self;
68
69	/// The characteristic `p` of the field. The field order is `p^k` where `k` is
70	/// [`ORDER_EXPONENT`](Self::ORDER_EXPONENT).
71	const CHARACTERISTIC: usize;
72
73	/// The exponent `k` such that the field order equals `CHARACTERISTIC^k`.
74	const ORDER_EXPONENT: usize;
75
76	/// Fixed generator of the multiplicative group.
77	const MULTIPLICATIVE_GENERATOR: Self;
78
79	/// Returns true iff this element is zero.
80	fn is_zero(&self) -> bool {
81		*self == Self::ZERO
82	}
83
84	/// Doubles this element.
85	#[must_use]
86	fn double(&self) -> Self;
87
88	/// Computes the multiplicative inverse of this element,
89	/// failing if the element is zero.
90	fn invert(&self) -> Option<Self> {
91		let inv = self.invert_or_zero();
92		(!inv.is_zero()).then_some(inv)
93	}
94
95	/// Exponentiates `self` by `exp`, where `exp` is a little-endian order integer
96	/// exponent.
97	fn pow<S: AsRef<[u64]>>(&self, exp: S) -> Self {
98		let mut res = Self::ONE;
99		for e in exp.as_ref().iter().rev() {
100			for i in (0..64).rev() {
101				res = res.square();
102
103				if ((*e >> i) & 1) == 1 {
104					res.mul_assign(self);
105				}
106			}
107		}
108
109		res
110	}
111}
112
113/// Operations for types that represent vectors of field elements.
114///
115/// This trait abstracts over:
116/// - [`Field`] types (single field elements, which are trivially vectors of length 1)
117/// - [`PackedField`](crate::PackedField) types (SIMD-accelerated vectors of field elements)
118/// - Symbolic field types (for constraint system representations)
119///
120/// Mathematically, instances of this trait represent vectors of field elements where
121/// arithmetic operations like addition, subtraction, multiplication, squaring, and
122/// inversion are defined element-wise. For a packed field with width N, multiplying
123/// two values performs N independent field multiplications in parallel.
124///
125/// # Required Methods
126///
127/// - [`zero()`](Self::zero) - Returns the additive identity (all elements are zero)
128/// - [`one()`](Self::one) - Returns the multiplicative identity (all elements are one)
129pub trait FieldOps:
130	Clone
131	+ Neg<Output = Self>
132	+ Add<Output = Self>
133	+ Sub<Output = Self>
134	+ Mul<Output = Self>
135	+ Sum
136	+ Product
137	+ for<'a> Add<&'a Self, Output = Self>
138	+ for<'a> Sub<&'a Self, Output = Self>
139	+ for<'a> Mul<&'a Self, Output = Self>
140	+ for<'a> Sum<&'a Self>
141	+ for<'a> Product<&'a Self>
142	+ AddAssign
143	+ SubAssign
144	+ MulAssign
145	+ for<'a> AddAssign<&'a Self>
146	+ for<'a> SubAssign<&'a Self>
147	+ for<'a> MulAssign<&'a Self>
148	+ Square
149	+ InvertOrZero
150{
151	type Scalar: Field;
152
153	/// Returns the zero element (additive identity).
154	fn zero() -> Self;
155
156	/// Returns the one element (multiplicative identity).
157	fn one() -> Self;
158
159	/// Transpose the subfield elements in a slice of field elements.
160	///
161	/// ## Arguments
162	///
163	/// * `elems` - a slice of $n$ elements, where $n$ is the degee of the extension of
164	///   `Self::Scalar` over `FSub`. They are overwritten with the result elements.
165	///
166	/// ## Preconditions
167	///
168	/// * `elems.len()` must equal `<Self::Scalar as ExtensionField<FSub>>::DEGREE`
169	fn square_transpose<FSub: Field>(elems: &mut [Self])
170	where
171		Self::Scalar: ExtensionField<FSub>;
172}
173
174impl<F: Field> FieldOps for F {
175	type Scalar = F;
176
177	fn zero() -> Self {
178		Self::ZERO
179	}
180
181	fn one() -> Self {
182		Self::ONE
183	}
184
185	fn square_transpose<FSub: Field>(elems: &mut [Self])
186	where
187		F: ExtensionField<FSub>,
188	{
189		<F as ExtensionField<FSub>>::square_transpose(elems)
190	}
191}
binius_field/field.rs

binius_field/
field.rs
