binius_field/
field.rs

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

binius_field/
field.rs
