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

primitives/algebra/field/
subfield_element.rs
