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	Divisible, Maskable, 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	// A field is a degenerate packed field of width one, so it divides into a single copy of
63	// itself. This mirrors `PackedField: Divisible<Self::Scalar>` for the blanket packed impl.
64	+ Divisible<Self>
65	// A field is maskable as a width-one packed field, mirroring
66	// `PackedField: Maskable<Self::Scalar>`.
67	+ Maskable<Self>
68{
69	/// The zero element of the field, the additive identity.
70	const ZERO: Self;
71
72	/// The one element of the field, the multiplicative identity.
73	const ONE: Self;
74
75	/// The characteristic `p` of the field. The field order is `p^k` where `k` is
76	/// [`ORDER_EXPONENT`](Self::ORDER_EXPONENT).
77	const CHARACTERISTIC: usize;
78
79	/// The exponent `k` such that the field order equals `CHARACTERISTIC^k`.
80	const ORDER_EXPONENT: usize;
81
82	/// Fixed generator of the multiplicative group.
83	const MULTIPLICATIVE_GENERATOR: Self;
84
85	/// Returns true iff this element is zero.
86	fn is_zero(&self) -> bool {
87		*self == Self::ZERO
88	}
89
90	/// Doubles this element.
91	#[must_use]
92	fn double(&self) -> Self;
93
94	/// Computes the multiplicative inverse of this element,
95	/// failing if the element is zero.
96	fn invert(&self) -> Option<Self> {
97		let inv = self.invert_or_zero();
98		(!inv.is_zero()).then_some(inv)
99	}
100
101	/// Exponentiates `self` by `exp`, where `exp` is a little-endian order integer
102	/// exponent.
103	fn pow<S: AsRef<[u64]>>(&self, exp: S) -> Self {
104		let mut res = Self::ONE;
105		for e in exp.as_ref().iter().rev() {
106			for i in (0..64).rev() {
107				res = res.square();
108
109				if ((*e >> i) & 1) == 1 {
110					res.mul_assign(self);
111				}
112			}
113		}
114
115		res
116	}
117}
118
119/// Operations for types that represent vectors of field elements.
120///
121/// This trait abstracts over:
122/// - [`Field`] types (single field elements, which are trivially vectors of length 1)
123/// - [`PackedField`](crate::PackedField) types (SIMD-accelerated vectors of field elements)
124/// - Symbolic field types (for constraint system representations)
125///
126/// Mathematically, instances of this trait represent vectors of field elements where
127/// arithmetic operations like addition, subtraction, multiplication, squaring, and
128/// inversion are defined element-wise. For a packed field with width N, multiplying
129/// two values performs N independent field multiplications in parallel.
130///
131/// # Required Methods
132///
133/// - [`zero()`](Self::zero) - Returns the additive identity (all elements are zero)
134/// - [`one()`](Self::one) - Returns the multiplicative identity (all elements are one)
135pub trait FieldOps:
136	Clone
137	+ Neg<Output = Self>
138	+ Add<Output = Self>
139	+ Sub<Output = Self>
140	+ Mul<Output = Self>
141	+ Sum
142	+ Product
143	+ for<'a> Add<&'a Self, Output = Self>
144	+ for<'a> Sub<&'a Self, Output = Self>
145	+ for<'a> Mul<&'a Self, Output = Self>
146	+ for<'a> Sum<&'a Self>
147	+ for<'a> Product<&'a Self>
148	+ AddAssign
149	+ SubAssign
150	+ MulAssign
151	+ for<'a> AddAssign<&'a Self>
152	+ for<'a> SubAssign<&'a Self>
153	+ for<'a> MulAssign<&'a Self>
154	+ Square
155	+ InvertOrZero
156{
157	type Scalar: Field;
158
159	/// Returns the zero element (additive identity).
160	fn zero() -> Self;
161
162	/// Returns the one element (multiplicative identity).
163	fn one() -> Self;
164
165	/// Transpose the subfield elements in a slice of field elements.
166	///
167	/// ## Arguments
168	///
169	/// * `elems` - a slice of $n$ elements, where $n$ is the degee of the extension of
170	///   `Self::Scalar` over `FSub`. They are overwritten with the result elements.
171	///
172	/// ## Preconditions
173	///
174	/// * `elems.len()` must equal `<Self::Scalar as ExtensionField<FSub>>::DEGREE`
175	fn square_transpose<FSub: Field>(elems: &mut [Self])
176	where
177		Self::Scalar: ExtensionField<FSub>;
178}
179
180impl<F: Field> FieldOps for F {
181	type Scalar = F;
182
183	fn zero() -> Self {
184		Self::ZERO
185	}
186
187	fn one() -> Self {
188		Self::ONE
189	}
190
191	fn square_transpose<FSub: Field>(elems: &mut [Self])
192	where
193		F: ExtensionField<FSub>,
194	{
195		<F as ExtensionField<FSub>>::square_transpose(elems)
196	}
197}
binius_field/field.rs

binius_field/
field.rs
