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	/// Exponentiates `self` by `exp`, where `exp` is a little-endian order integer
95	/// exponent.
96	fn pow<S: AsRef<[u64]>>(&self, exp: S) -> Self {
97		let mut res = Self::ONE;
98		for e in exp.as_ref().iter().rev() {
99			for i in (0..64).rev() {
100				res = res.square();
101
102				if ((*e >> i) & 1) == 1 {
103					res.mul_assign(self);
104				}
105			}
106		}
107
108		res
109	}
110}
111
112/// Operations for types that represent vectors of field elements.
113///
114/// This trait abstracts over:
115/// - [`Field`] types (single field elements, which are trivially vectors of length 1)
116/// - [`PackedField`](crate::PackedField) types (SIMD-accelerated vectors of field elements)
117/// - Symbolic field types (for constraint system representations)
118///
119/// Mathematically, instances of this trait represent vectors of field elements where
120/// arithmetic operations like addition, subtraction, multiplication, squaring, and
121/// inversion are defined element-wise. For a packed field with width N, multiplying
122/// two values performs N independent field multiplications in parallel.
123///
124/// # Required Methods
125///
126/// - [`zero()`](Self::zero) - Returns the additive identity (all elements are zero)
127/// - [`one()`](Self::one) - Returns the multiplicative identity (all elements are one)
128pub trait FieldOps:
129	Clone
130	+ Neg<Output = Self>
131	+ Add<Output = Self>
132	+ Sub<Output = Self>
133	+ Mul<Output = Self>
134	+ Sum
135	+ Product
136	+ for<'a> Add<&'a Self, Output = Self>
137	+ for<'a> Sub<&'a Self, Output = Self>
138	+ for<'a> Mul<&'a Self, Output = Self>
139	+ for<'a> Sum<&'a Self>
140	+ for<'a> Product<&'a Self>
141	+ AddAssign
142	+ SubAssign
143	+ MulAssign
144	+ for<'a> AddAssign<&'a Self>
145	+ for<'a> SubAssign<&'a Self>
146	+ for<'a> MulAssign<&'a Self>
147	+ Square
148	+ InvertOrZero
149{
150	type Scalar: Field;
151
152	/// Returns the zero element (additive identity).
153	fn zero() -> Self;
154
155	/// Returns the one element (multiplicative identity).
156	fn one() -> Self;
157
158	/// Transpose the subfield elements in a slice of field elements.
159	///
160	/// ## Arguments
161	///
162	/// * `elems` - a slice of $n$ elements, where $n$ is the degee of the extension of
163	///   `Self::Scalar` over `FSub`. They are overwritten with the result elements.
164	///
165	/// ## Preconditions
166	///
167	/// * `elems.len()` must equal `<Self::Scalar as ExtensionField<FSub>>::DEGREE`
168	fn square_transpose<FSub: Field>(elems: &mut [Self])
169	where
170		Self::Scalar: ExtensionField<FSub>;
171}
172
173impl<F: Field> FieldOps for F {
174	type Scalar = F;
175
176	fn zero() -> Self {
177		Self::ZERO
178	}
179
180	fn one() -> Self {
181		Self::ONE
182	}
183
184	fn square_transpose<FSub: Field>(elems: &mut [Self])
185	where
186		F: ExtensionField<FSub>,
187	{
188		<F as ExtensionField<FSub>>::square_transpose(elems)
189	}
190}
binius_field/field.rs

binius_field/
field.rs
