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	+ Neg<Output = Self>
32	+ Add<Output = Self>
33	+ Sub<Output = Self>
34	+ Mul<Output = Self>
35	+ Sum
36	+ Product
37	+ for<'a> Add<&'a Self, Output = Self>
38	+ for<'a> Sub<&'a Self, Output = Self>
39	+ for<'a> Mul<&'a Self, Output = Self>
40	+ for<'a> Sum<&'a Self>
41	+ for<'a> Product<&'a Self>
42	+ AddAssign
43	+ SubAssign
44	+ MulAssign
45	+ for<'a> AddAssign<&'a Self>
46	+ for<'a> SubAssign<&'a Self>
47	+ for<'a> MulAssign<&'a Self>
48	+ Square
49	+ InvertOrZero
50	+ Random
51	+ Zeroable
52	+ SerializeBytes
53	+ DeserializeBytes
54{
55	/// The zero element of the field, the additive identity.
56	const ZERO: Self;
57
58	/// The one element of the field, the multiplicative identity.
59	const ONE: Self;
60
61	/// The characteristic of the field.
62	const CHARACTERISTIC: usize;
63
64	/// Fixed generator of the multiplicative group.
65	const MULTIPLICATIVE_GENERATOR: Self;
66
67	/// Returns true iff this element is zero.
68	fn is_zero(&self) -> bool {
69		*self == Self::ZERO
70	}
71
72	/// Doubles this element.
73	#[must_use]
74	fn double(&self) -> Self;
75
76	/// Computes the multiplicative inverse of this element,
77	/// failing if the element is zero.
78	fn invert(&self) -> Option<Self> {
79		let inv = self.invert_or_zero();
80		(!inv.is_zero()).then_some(inv)
81	}
82
83	/// Exponentiates `self` by `exp`, where `exp` is a little-endian order integer
84	/// exponent.
85	///
86	/// # Guarantees
87	///
88	/// This operation is constant time with respect to `self`, for all exponents with the
89	/// same number of digits (`exp.as_ref().len()`). It is variable time with respect to
90	/// the number of digits in the exponent.
91	fn pow<S: AsRef<[u64]>>(&self, exp: S) -> Self {
92		let mut res = Self::ONE;
93		for e in exp.as_ref().iter().rev() {
94			for i in (0..64).rev() {
95				res = res.square();
96				let mut tmp = res;
97				tmp *= self;
98				if ((*e >> i) & 1) != 0 {
99					res = tmp;
100				}
101			}
102		}
103		res
104	}
105
106	/// Exponentiates `self` by `exp`, where `exp` is a little-endian order integer
107	/// exponent.
108	///
109	/// # Guarantees
110	///
111	/// **This operation is variable time with respect to `self`, for all exponent.** If
112	/// the exponent is fixed, this operation is effectively constant time. However, for
113	/// stronger constant-time guarantees, [`Field::pow`] should be used.
114	fn pow_vartime<S: AsRef<[u64]>>(&self, exp: S) -> Self {
115		let mut res = Self::ONE;
116		for e in exp.as_ref().iter().rev() {
117			for i in (0..64).rev() {
118				res = res.square();
119
120				if ((*e >> i) & 1) == 1 {
121					res.mul_assign(self);
122				}
123			}
124		}
125
126		res
127	}
128}
binius_field/field.rs

binius_field/
field.rs
