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

primitives/algebra/field/
subfield_element.rs
