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

primitives/algebra/field/
subfield_element.rs
