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

primitives/algebra/field/
field_element.rs
