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 rand::RngCore;
12
13use crate::{
14	arithmetic_traits::{InvertOrZero, Square},
15	as_packed_field::PackScalar,
16	underlier::WithUnderlier,
17};
18
19/// This trait is based on `ff::Field` with some unused functionality removed.
20pub trait Field:
21	Sized
22	+ Eq
23	+ Copy
24	+ Clone
25	+ Default
26	+ Send
27	+ Sync
28	+ Debug
29	+ Display
30	+ Hash
31	+ 'static
32	+ Neg<Output = Self>
33	+ Add<Output = Self>
34	+ Sub<Output = Self>
35	+ Mul<Output = Self>
36	+ Sum
37	+ Product
38	+ for<'a> Add<&'a Self, Output = Self>
39	+ for<'a> Sub<&'a Self, Output = Self>
40	+ for<'a> Mul<&'a Self, Output = Self>
41	+ for<'a> Sum<&'a Self>
42	+ for<'a> Product<&'a Self>
43	+ AddAssign
44	+ SubAssign
45	+ MulAssign
46	+ for<'a> AddAssign<&'a Self>
47	+ for<'a> SubAssign<&'a Self>
48	+ for<'a> MulAssign<&'a Self>
49	+ Square
50	+ InvertOrZero
51	// `Underlier: PackScalar<Self>` is an obvious property but it can't be deduced by the compiler so we are id here.
52	+ WithUnderlier<Underlier: PackScalar<Self>>
53	+ SerializeBytes
54	+ DeserializeBytes
55{
56	/// The zero element of the field, the additive identity.
57	const ZERO: Self;
58
59	/// The one element of the field, the multiplicative identity.
60	const ONE: Self;
61
62	/// The characteristic of the field.
63	const CHARACTERISTIC: usize;
64
65	/// Returns an element chosen uniformly at random using a user-provided RNG.
66	fn random(rng: impl RngCore) -> Self;
67
68	/// Returns true iff this element is zero.
69	fn is_zero(&self) -> bool {
70		*self == Self::ZERO
71	}
72
73	/// Doubles this element.
74	#[must_use]
75	fn double(&self) -> Self;
76
77	/// Computes the multiplicative inverse of this element,
78	/// failing if the element is zero.
79	fn invert(&self) -> Option<Self> {
80		let inv = self.invert_or_zero();
81		(!inv.is_zero()).then_some(inv)
82	}
83
84	/// Exponentiates `self` by `exp`, where `exp` is a little-endian order integer
85	/// exponent.
86	///
87	/// # Guarantees
88	///
89	/// This operation is constant time with respect to `self`, for all exponents with the
90	/// same number of digits (`exp.as_ref().len()`). It is variable time with respect to
91	/// the number of digits in the exponent.
92	fn pow<S: AsRef<[u64]>>(&self, exp: S) -> Self {
93		let mut res = Self::ONE;
94		for e in exp.as_ref().iter().rev() {
95			for i in (0..64).rev() {
96				res = res.square();
97				let mut tmp = res;
98				tmp *= self;
99				if ((*e >> i) & 1) != 0 {
100					res = tmp;
101				}
102			}
103		}
104		res
105	}
106
107	/// Exponentiates `self` by `exp`, where `exp` is a little-endian order integer
108	/// exponent.
109	///
110	/// # Guarantees
111	///
112	/// **This operation is variable time with respect to `self`, for all exponent.** If
113	/// the exponent is fixed, this operation is effectively constant time. However, for
114	/// stronger constant-time guarantees, [`Field::pow`] should be used.
115	fn pow_vartime<S: AsRef<[u64]>>(&self, exp: S) -> Self {
116		let mut res = Self::ONE;
117		for e in exp.as_ref().iter().rev() {
118			for i in (0..64).rev() {
119				res = res.square();
120
121				if ((*e >> i) & 1) == 1 {
122					res.mul_assign(self);
123				}
124			}
125		}
126
127		res
128	}
129}
binius_field/field.rs

binius_field/
field.rs
