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

primitives/algebra/field/
field_element.rs
