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::{Product, Sum},
8	ops::{Add, AddAssign, Mul, MulAssign, Neg, Sub, SubAssign},
9};
10
11use binius_utils::{DeserializeBytes, FixedSizeSerializeBytes, SerializeBytes};
12
13use super::extension::ExtensionField;
14use crate::{
15	PackedField,
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	PackedField<Scalar = Self>
26	+ Display
27	+ Hash
28	+ SerializeBytes
29	+ DeserializeBytes
30	+ FixedSizeSerializeBytes
31{
32	/// The zero element of the field, the additive identity.
33	const ZERO: Self;
34
35	/// The one element of the field, the multiplicative identity.
36	const ONE: Self;
37
38	/// The characteristic `p` of the field. The field order is `p^k` where `k` is
39	/// [`ORDER_EXPONENT`](Self::ORDER_EXPONENT).
40	const CHARACTERISTIC: usize;
41
42	/// The exponent `k` such that the field order equals `CHARACTERISTIC^k`.
43	const ORDER_EXPONENT: usize;
44
45	/// Fixed generator of the multiplicative group.
46	const MULTIPLICATIVE_GENERATOR: Self;
47
48	/// Returns true iff this element is zero.
49	fn is_zero(&self) -> bool {
50		*self == Self::ZERO
51	}
52
53	/// Doubles this element.
54	#[must_use]
55	fn double(&self) -> Self;
56
57	/// Exponentiates `self` by `exp`, where `exp` is a little-endian order integer
58	/// exponent.
59	fn pow<S: AsRef<[u64]>>(&self, exp: S) -> Self {
60		let mut res = Self::ONE;
61		for e in exp.as_ref().iter().rev() {
62			for i in (0..64).rev() {
63				res = res.square();
64
65				if ((*e >> i) & 1) == 1 {
66					res.mul_assign(self);
67				}
68			}
69		}
70
71		res
72	}
73}
74
75/// Operations for types that represent vectors of field elements.
76///
77/// This trait abstracts over:
78/// - [`Field`] types (single field elements, which are trivially vectors of length 1)
79/// - [`PackedField`] types (SIMD-accelerated vectors of field elements)
80/// - Symbolic field types (for constraint system representations)
81///
82/// Mathematically, instances of this trait represent vectors of field elements where
83/// arithmetic operations like addition, subtraction, multiplication, squaring, and
84/// inversion are defined element-wise. For a packed field with width N, multiplying
85/// two values performs N independent field multiplications in parallel.
86///
87/// # Required Methods
88///
89/// - [`zero()`](Self::zero) - Returns the additive identity (all elements are zero)
90/// - [`one()`](Self::one) - Returns the multiplicative identity (all elements are one)
91pub trait FieldOps:
92	Clone
93	+ Neg<Output = Self>
94	+ Add<Output = Self>
95	+ Sub<Output = Self>
96	+ Mul<Output = Self>
97	+ Sum
98	+ Product
99	+ for<'a> Add<&'a Self, Output = Self>
100	+ for<'a> Sub<&'a Self, Output = Self>
101	+ for<'a> Mul<&'a Self, Output = Self>
102	+ for<'a> Sum<&'a Self>
103	+ for<'a> Product<&'a Self>
104	+ AddAssign
105	+ SubAssign
106	+ MulAssign
107	+ for<'a> AddAssign<&'a Self>
108	+ for<'a> SubAssign<&'a Self>
109	+ for<'a> MulAssign<&'a Self>
110	+ Square
111	+ InvertOrZero
112{
113	type Scalar: Field;
114
115	/// Returns the zero element (additive identity).
116	fn zero() -> Self;
117
118	/// Returns the one element (multiplicative identity).
119	fn one() -> Self;
120
121	/// Transpose the subfield elements in a slice of field elements.
122	///
123	/// ## Arguments
124	///
125	/// * `elems` - a slice of $n$ elements, where $n$ is the degee of the extension of
126	///   `Self::Scalar` over `FSub`. They are overwritten with the result elements.
127	///
128	/// ## Preconditions
129	///
130	/// * `elems.len()` must equal `<Self::Scalar as ExtensionField<FSub>>::DEGREE`
131	fn square_transpose<FSub: Field>(elems: &mut [Self])
132	where
133		Self::Scalar: ExtensionField<FSub>;
134}
135
136impl<F: Field> FieldOps for F {
137	type Scalar = F;
138
139	fn zero() -> Self {
140		Self::ZERO
141	}
142
143	fn one() -> Self {
144		Self::ONE
145	}
146
147	fn square_transpose<FSub: Field>(elems: &mut [Self])
148	where
149		F: ExtensionField<FSub>,
150	{
151		<F as ExtensionField<FSub>>::square_transpose(elems)
152	}
153}
binius_field/field.rs

binius_field/
field.rs
