primitives/algebra/field/
field_element.rs

1use std::{
2    fmt::{Display, Formatter, Result as FmtResult},
3    iter::{Product, Sum},
4    ops::{Add, AddAssign, Div, Mul, MulAssign, Neg, Sub, SubAssign},
5};
6
7use ff::Field;
8use hybrid_array::Array;
9use num_traits::{One, Zero};
10use rand::{distributions::Standard, prelude::Distribution, RngCore};
11use serde::{Deserialize, Serialize};
12use subtle::{Choice, ConditionallySelectable, ConstantTimeEq, CtOption};
13
14use crate::{
15    algebra::{
16        field::{FieldExtension, PrimeFieldExtension, SubfieldElement},
17        ops::{AccReduce, DefaultDotProduct, IntoWide, MulAccReduce, ReduceWide},
18        uniform_bytes::FromUniformBytes,
19    },
20    errors::PrimitiveError,
21    sharing::unauthenticated::AdditiveShares,
22};
23
24/// A field element wrapper.
25#[derive(Copy, Clone, Debug, PartialOrd, PartialEq, Eq, Hash)]
26pub struct FieldElement<F: FieldExtension>(pub(crate) F);
27
28impl<F: FieldExtension> FieldElement<F> {
29    /// Construct a field element wrapper from an inner field element
30    #[inline]
31    pub fn new(inner: F) -> Self {
32        FieldElement(inner)
33    }
34
35    /// Get the inner value of the field element
36    #[inline]
37    pub fn inner(&self) -> F {
38        self.0
39    }
40
41    /// Compute the exponentiation of the given field element
42    #[inline]
43    pub fn pow(&self, exp: u64) -> Self {
44        FieldElement::new(self.0.pow([exp]))
45    }
46
47    /// Construct a field element from the given bytes
48    #[inline]
49    pub fn from_be_bytes(bytes: &[u8]) -> Result<FieldElement<F>, PrimitiveError> {
50        let mut bytes = bytes.to_vec();
51        bytes.reverse();
52        Ok(FieldElement(F::from_le_bytes(&bytes).ok_or_else(|| {
53            PrimitiveError::DeserializationFailed("Invalid field element encoding".to_string())
54        })?))
55    }
56
57    pub fn from_le_bytes(bytes: &[u8]) -> Result<FieldElement<F>, PrimitiveError> {
58        Ok(FieldElement(F::from_le_bytes(bytes).ok_or_else(|| {
59            PrimitiveError::DeserializationFailed("Invalid field element encoding".to_string())
60        })?))
61    }
62
63    /// Convert the field element to little-endian bytes
64    #[inline]
65    pub fn to_le_bytes(&self) -> impl IntoIterator<Item = u8> + '_ {
66        self.0.to_le_bytes()
67    }
68
69    /// Convert the field element to big-endian bytes
70    #[inline]
71    pub fn to_be_bytes(&self) -> impl IntoIterator<Item = u8> {
72        self.0
73            .to_le_bytes()
74            .into_iter()
75            .collect::<Vec<_>>()
76            .into_iter()
77            .rev()
78            .collect::<Vec<_>>()
79    }
80
81    pub fn to_biguint(&self) -> num_bigint::BigUint {
82        num_bigint::BigUint::from_bytes_le(
83            self.to_le_bytes().into_iter().collect::<Vec<_>>().as_ref(),
84        )
85    }
86}
87
88impl<F: FieldExtension> Distribution<FieldElement<F>> for Standard {
89    fn sample<R: RngCore + ?Sized>(&self, rng: &mut R) -> FieldElement<F> {
90        FieldElement(F::random(rng))
91    }
92}
93
94impl<F: FieldExtension> Default for FieldElement<F> {
95    fn default() -> Self {
96        Self::zero()
97    }
98}
99
100impl<F: FieldExtension> Serialize for FieldElement<F> {
101    fn serialize<S: serde::Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
102        let bytes = self
103            .to_le_bytes()
104            .into_iter()
105            .collect::<Array<u8, F::FieldBytesSize>>();
106        serde_bytes::serialize(AsRef::<[u8]>::as_ref(&bytes), serializer)
107    }
108}
109
110impl<'de, F: FieldExtension> Deserialize<'de> for FieldElement<F> {
111    fn deserialize<D: serde::Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
112        let bytes: &[u8] = serde_bytes::deserialize(deserializer)?;
113        let field_elem = FieldElement::from_le_bytes(bytes).map_err(|err| {
114            serde::de::Error::custom(format!("Failed to deserialize field element: {err:?}"))
115        })?;
116        Ok(field_elem)
117    }
118}
119
120impl<F: FieldExtension> Display for FieldElement<F> {
121    fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
122        write!(f, "{self:?}")
123    }
124}
125
126// --------------
127// | Arithmetic |
128// --------------
129
130// === Addition === //
131
132#[macros::op_variants(owned, borrowed, flipped_commutative)]
133impl<F: FieldExtension> Add<&FieldElement<F>> for FieldElement<F> {
134    type Output = FieldElement<F>;
135
136    #[inline]
137    fn add(self, rhs: &FieldElement<F>) -> Self::Output {
138        FieldElement(self.0 + rhs.0)
139    }
140}
141
142#[macros::op_variants(owned)]
143impl<'a, F: FieldExtension> AddAssign<&'a FieldElement<F>> for FieldElement<F> {
144    #[inline]
145    fn add_assign(&mut self, rhs: &'a FieldElement<F>) {
146        *self = *self + rhs;
147    }
148}
149
150// === Subtraction === //
151
152#[macros::op_variants(owned, borrowed, flipped)]
153impl<F: FieldExtension> Sub<&FieldElement<F>> for FieldElement<F> {
154    type Output = FieldElement<F>;
155
156    #[inline]
157    fn sub(self, rhs: &FieldElement<F>) -> Self::Output {
158        FieldElement(self.0 - rhs.0)
159    }
160}
161
162#[macros::op_variants(owned)]
163impl<'a, F: FieldExtension> SubAssign<&'a FieldElement<F>> for FieldElement<F> {
164    #[inline]
165    fn sub_assign(&mut self, rhs: &'a FieldElement<F>) {
166        *self = *self - rhs;
167    }
168}
169
170// === Multiplication === //
171
172#[macros::op_variants(owned, borrowed, flipped_commutative)]
173impl<F: FieldExtension> Mul<&FieldElement<F>> for FieldElement<F> {
174    type Output = FieldElement<F>;
175
176    #[inline]
177    fn mul(self, rhs: &FieldElement<F>) -> Self::Output {
178        FieldElement(self.0 * rhs.0)
179    }
180}
181
182#[macros::op_variants(owned, borrowed, flipped)]
183impl<F: FieldExtension> Mul<&SubfieldElement<F>> for FieldElement<F> {
184    type Output = FieldElement<F>;
185
186    #[inline]
187    fn mul(self, rhs: &SubfieldElement<F>) -> Self::Output {
188        FieldElement(self.0 * rhs.0)
189    }
190}
191
192#[macros::op_variants(owned)]
193impl<'a, F: FieldExtension> MulAssign<&'a FieldElement<F>> for FieldElement<F> {
194    #[inline]
195    fn mul_assign(&mut self, rhs: &'a FieldElement<F>) {
196        *self = *self * rhs;
197    }
198}
199
200#[macros::op_variants(owned)]
201impl<'a, F: FieldExtension> MulAssign<&'a SubfieldElement<F>> for FieldElement<F> {
202    #[inline]
203    fn mul_assign(&mut self, rhs: &'a SubfieldElement<F>) {
204        *self = *self * rhs;
205    }
206}
207
208// === Negation === //
209
210#[macros::op_variants(borrowed)]
211impl<F: FieldExtension> Neg for FieldElement<F> {
212    type Output = FieldElement<F>;
213
214    #[inline]
215    fn neg(self) -> Self::Output {
216        FieldElement(-self.0)
217    }
218}
219
220// === Division === //
221
222#[macros::op_variants(owned, borrowed, flipped)]
223impl<F: FieldExtension> Div<&FieldElement<F>> for FieldElement<F> {
224    type Output = CtOption<FieldElement<F>>;
225
226    #[inline]
227    fn div(self, rhs: &FieldElement<F>) -> Self::Output {
228        rhs.0.invert().map(|inv| FieldElement(self.0 * inv))
229    }
230}
231
232// === Equality === //
233
234impl<F: FieldExtension> ConstantTimeEq for FieldElement<F> {
235    #[inline]
236    fn ct_eq(&self, other: &Self) -> Choice {
237        self.0.ct_eq(&other.0)
238    }
239}
240
241impl<F: FieldExtension> ConditionallySelectable for FieldElement<F> {
242    #[inline]
243    fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self {
244        let selected = F::conditional_select(&a.0, &b.0, choice);
245        FieldElement(selected)
246    }
247}
248
249// === Other === //
250
251impl<F: FieldExtension> AdditiveShares for FieldElement<F> {}
252
253// ---------------
254// | Conversions |
255// ---------------
256
257impl<F: FieldExtension> From<bool> for FieldElement<F> {
258    #[inline]
259    fn from(value: bool) -> Self {
260        FieldElement(F::from(value as u64))
261    }
262}
263
264impl<F: FieldExtension> From<u8> for FieldElement<F> {
265    #[inline]
266    fn from(value: u8) -> Self {
267        FieldElement(F::from(value as u64))
268    }
269}
270
271impl<F: FieldExtension> From<u16> for FieldElement<F> {
272    #[inline]
273    fn from(value: u16) -> Self {
274        FieldElement(F::from(value as u64))
275    }
276}
277
278impl<F: FieldExtension> From<u32> for FieldElement<F> {
279    #[inline]
280    fn from(value: u32) -> Self {
281        FieldElement(F::from(value as u64))
282    }
283}
284
285impl<F: FieldExtension> From<u64> for FieldElement<F> {
286    #[inline]
287    fn from(value: u64) -> Self {
288        FieldElement(F::from(value))
289    }
290}
291
292impl<F: FieldExtension> From<u128> for FieldElement<F> {
293    #[inline]
294    fn from(value: u128) -> Self {
295        FieldElement(F::from(value))
296    }
297}
298
299impl<F: PrimeFieldExtension> From<SubfieldElement<F>> for FieldElement<F> {
300    #[inline]
301    fn from(value: SubfieldElement<F>) -> Self {
302        FieldElement(value.0)
303    }
304}
305
306// -------------------
307// | Iterator Traits |
308// -------------------
309impl<F: FieldExtension> Sum for FieldElement<F> {
310    #[inline]
311    fn sum<I: Iterator<Item = FieldElement<F>>>(iter: I) -> Self {
312        let tmp = iter.fold(<F as AccReduce>::zero_wide(), |mut acc, x| {
313            F::acc(&mut acc, x.0);
314            acc
315        });
316
317        FieldElement(F::reduce_mod_order(tmp))
318    }
319}
320
321impl<'a, F: FieldExtension> Sum<&'a FieldElement<F>> for FieldElement<F> {
322    #[inline]
323    fn sum<I: Iterator<Item = &'a FieldElement<F>>>(iter: I) -> Self {
324        let tmp = iter.fold(<F as AccReduce>::zero_wide(), |mut acc, x| {
325            F::acc(&mut acc, x.0);
326            acc
327        });
328
329        FieldElement(F::reduce_mod_order(tmp))
330    }
331}
332
333impl<F: FieldExtension> Product for FieldElement<F> {
334    #[inline]
335    fn product<I: Iterator<Item = FieldElement<F>>>(iter: I) -> Self {
336        iter.fold(FieldElement::one(), |acc, x| acc * x)
337    }
338}
339
340impl<'a, F: FieldExtension> Product<&'a FieldElement<F>> for FieldElement<F> {
341    #[inline]
342    fn product<I: Iterator<Item = &'a FieldElement<F>>>(iter: I) -> Self {
343        iter.fold(FieldElement::one(), |acc, x| acc * x)
344    }
345}
346
347impl<F: FieldExtension> FromUniformBytes for FieldElement<F> {
348    type UniformBytes = <F as FromUniformBytes>::UniformBytes;
349
350    fn from_uniform_bytes(bytes: &Array<u8, Self::UniformBytes>) -> Self {
351        Self(F::from_uniform_bytes(bytes))
352    }
353}
354
355// Dot product: FieldElement<F> x FieldElement<F>
356impl<F: FieldExtension> IntoWide<<F as MulAccReduce>::WideType> for FieldElement<F> {
357    #[inline]
358    fn to_wide(&self) -> <F as MulAccReduce>::WideType {
359        <F as MulAccReduce>::to_wide(&self.0)
360    }
361
362    #[inline]
363    fn zero_wide() -> <F as MulAccReduce>::WideType {
364        <F as MulAccReduce>::zero_wide()
365    }
366}
367
368impl<F: FieldExtension> ReduceWide<<F as MulAccReduce>::WideType> for FieldElement<F> {
369    #[inline]
370    fn reduce_mod_order(a: <F as MulAccReduce>::WideType) -> Self {
371        Self(F::reduce_mod_order(a))
372    }
373}
374
375impl<F: FieldExtension> MulAccReduce for FieldElement<F> {
376    type WideType = <F as MulAccReduce>::WideType;
377
378    #[inline]
379    fn mul_acc(acc: &mut Self::WideType, a: Self, b: Self) {
380        F::mul_acc(acc, a.0, b.0);
381    }
382}
383
384impl<F: FieldExtension> DefaultDotProduct for FieldElement<F> {}
385
386// Dot product: &FieldElement<F> x FieldElement<F>
387impl<'a, F: FieldExtension> MulAccReduce<&'a Self, Self> for FieldElement<F> {
388    type WideType = <F as MulAccReduce>::WideType;
389
390    #[inline]
391    fn mul_acc(acc: &mut Self::WideType, a: &'a Self, b: Self) {
392        F::mul_acc(acc, a.0, b.0);
393    }
394}
395
396impl<F: FieldExtension> DefaultDotProduct<&Self, Self> for FieldElement<F> {}
397
398// Dot product: FieldElement<F> x &FieldElement<F>
399impl<'a, F: FieldExtension> MulAccReduce<Self, &'a Self> for FieldElement<F> {
400    type WideType = <F as MulAccReduce>::WideType;
401
402    #[inline]
403    fn mul_acc(acc: &mut Self::WideType, a: Self, b: &'a Self) {
404        F::mul_acc(acc, a.0, b.0);
405    }
406}
407
408impl<F: FieldExtension> DefaultDotProduct<Self, &Self> for FieldElement<F> {}
409
410// Dot product: &FieldElement<F> x &FieldElement<F>
411impl<'a, 'b, F: FieldExtension> MulAccReduce<&'a Self, &'b Self> for FieldElement<F> {
412    type WideType = <F as MulAccReduce>::WideType;
413
414    #[inline]
415    fn mul_acc(acc: &mut Self::WideType, a: &'a Self, b: &'b Self) {
416        F::mul_acc(acc, a.0, b.0);
417    }
418}
419
420impl<F: FieldExtension> DefaultDotProduct<&Self, &Self> for FieldElement<F> {}
421
422// ----------------
423// | Zero and One |
424// ----------------
425
426impl<F: FieldExtension> Zero for FieldElement<F> {
427    /// The field's additive identity.
428    fn zero() -> Self {
429        FieldElement(F::ZERO)
430    }
431
432    fn is_zero(&self) -> bool {
433        self.0.is_zero().into()
434    }
435}
436
437impl<F: FieldExtension> One for FieldElement<F> {
438    /// The field's multiplicative identity.
439    fn one() -> Self {
440        FieldElement(F::ONE)
441    }
442}
443
444// ---------------
445// | Field trait |
446// ---------------
447
448impl<F: FieldExtension> Field for FieldElement<F> {
449    const ZERO: Self = FieldElement(F::ZERO);
450    const ONE: Self = FieldElement(F::ONE);
451
452    fn random(rng: impl RngCore) -> Self {
453        Self(F::random(rng))
454    }
455
456    fn square(&self) -> Self {
457        FieldElement(self.0.square())
458    }
459
460    fn double(&self) -> Self {
461        FieldElement(self.0.double())
462    }
463
464    fn invert(&self) -> CtOption<Self> {
465        self.0.invert().map(FieldElement)
466    }
467
468    fn sqrt_ratio(num: &Self, div: &Self) -> (Choice, Self) {
469        let (choice, sqrt) = F::sqrt_ratio(&num.0, &div.0);
470        (choice, FieldElement(sqrt))
471    }
472}
primitives/algebra/field/field_element.rs

primitives/algebra/field/
field_element.rs
