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 crate::{
14	Random,
15	arithmetic_traits::{InvertOrZero, Square},
16};
17
18/// This trait is based on `ff::Field` with some unused functionality removed.
19pub trait Field:
20	Sized
21	+ Eq
22	+ Copy
23	+ Clone
24	+ Default
25	+ Send
26	+ Sync
27	+ Debug
28	+ Display
29	+ Hash
30	+ 'static
31	+ FieldOps<Self>
32	+ Random
33	+ Zeroable
34	+ SerializeBytes
35	+ DeserializeBytes
36{
37	/// The zero element of the field, the additive identity.
38	const ZERO: Self;
39
40	/// The one element of the field, the multiplicative identity.
41	const ONE: Self;
42
43	/// The characteristic of the field.
44	const CHARACTERISTIC: usize;
45
46	/// Fixed generator of the multiplicative group.
47	const MULTIPLICATIVE_GENERATOR: Self;
48
49	/// Returns true iff this element is zero.
50	fn is_zero(&self) -> bool {
51		*self == Self::ZERO
52	}
53
54	/// Doubles this element.
55	#[must_use]
56	fn double(&self) -> Self;
57
58	/// Computes the multiplicative inverse of this element,
59	/// failing if the element is zero.
60	fn invert(&self) -> Option<Self> {
61		let inv = self.invert_or_zero();
62		(!inv.is_zero()).then_some(inv)
63	}
64
65	/// Exponentiates `self` by `exp`, where `exp` is a little-endian order integer
66	/// exponent.
67	///
68	/// # Guarantees
69	///
70	/// This operation is constant time with respect to `self`, for all exponents with the
71	/// same number of digits (`exp.as_ref().len()`). It is variable time with respect to
72	/// the number of digits in the exponent.
73	fn pow<S: AsRef<[u64]>>(&self, exp: S) -> Self {
74		let mut res = Self::ONE;
75		for e in exp.as_ref().iter().rev() {
76			for i in (0..64).rev() {
77				res = res.square();
78				let mut tmp = res;
79				tmp *= self;
80				if ((*e >> i) & 1) != 0 {
81					res = tmp;
82				}
83			}
84		}
85		res
86	}
87
88	/// Exponentiates `self` by `exp`, where `exp` is a little-endian order integer
89	/// exponent.
90	///
91	/// # Guarantees
92	///
93	/// **This operation is variable time with respect to `self`, for all exponent.** If
94	/// the exponent is fixed, this operation is effectively constant time. However, for
95	/// stronger constant-time guarantees, [`Field::pow`] should be used.
96	fn pow_vartime<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/// # Type Parameter
125///
126/// The type parameter `F` represents the scalar field type. For a `Field` implementation,
127/// `F` is `Self`. For a `PackedField` implementation, `F` is the scalar type being packed.
128///
129/// # Required Methods
130///
131/// - [`zero()`](Self::zero) - Returns the additive identity (all elements are zero)
132/// - [`one()`](Self::one) - Returns the multiplicative identity (all elements are one)
133pub trait FieldOps<F>:
134	Neg<Output = Self>
135	+ Add<Output = Self>
136	+ Sub<Output = Self>
137	+ Mul<Output = Self>
138	+ Sum
139	+ Product
140	+ for<'a> Add<&'a Self, Output = Self>
141	+ for<'a> Sub<&'a Self, Output = Self>
142	+ for<'a> Mul<&'a Self, Output = Self>
143	+ for<'a> Sum<&'a Self>
144	+ for<'a> Product<&'a Self>
145	+ AddAssign
146	+ SubAssign
147	+ MulAssign
148	+ for<'a> AddAssign<&'a Self>
149	+ for<'a> SubAssign<&'a Self>
150	+ for<'a> MulAssign<&'a Self>
151	+ Mul<F, Output = Self>
152	+ MulAssign<F>
153	+ Square
154	+ InvertOrZero
155{
156	/// Returns the zero element (additive identity).
157	fn zero() -> Self;
158
159	/// Returns the one element (multiplicative identity).
160	fn one() -> Self;
161}
binius_field/field.rs

binius_field/
field.rs
