primitives/algebra/field/
field_extension.rs

1use std::{
2    fmt::Debug,
3    hash::Hash,
4    ops::{Mul, MulAssign},
5};
6
7use ff::Field;
8use hybrid_array::ArraySize;
9use rand::RngCore;
10use serde::{Deserialize, Serialize};
11
12use crate::{
13    algebra::{
14        ops::{AccReduce, DotProduct, MulAccReduce},
15        uniform_bytes::FromUniformBytes,
16    },
17    types::{HeapArray, Positive},
18};
19
20pub type ByteSize<F> = <F as FieldExtension>::FieldBytesSize;
21pub type BitSize<F> = <F as FieldExtension>::FieldBitSize;
22pub type FieldDegree<F> = <F as FieldExtension>::Degree;
23pub type Subfield<F> = <F as FieldExtension>::Subfield;
24
25/// A generic trait for field extensions
26pub trait FieldExtension:
27    Field
28    + Ord
29    + Debug
30    + PartialEq
31    + Hash
32    + Mul<Self::Subfield, Output = Self>
33    + MulAssign<Self::Subfield>
34    + Serialize
35    + for<'de> Deserialize<'de>
36    + FromUniformBytes
37    + From<u64>
38    + From<u128>
39    + AccReduce
40    + MulAccReduce
41    + MulAccReduce<Self, Self::Subfield>
42    + DotProduct
43    + for<'a> DotProduct<Self, &'a Self>
44    + for<'a> DotProduct<&'a Self, &'a Self>
45    + DotProduct<Self, Self::Subfield>
46    + for<'a> DotProduct<&'a Self, Self::Subfield>
47    + Unpin
48{
49    // The underlying prime subfield
50    type Subfield: FieldExtension<Subfield = Self::Subfield>;
51
52    type Degree: ArraySize + Positive;
53    type FieldBitSize: ArraySize + Positive;
54    type FieldBytesSize: ArraySize + Positive;
55
56    fn to_subfield_elements(&self) -> impl ExactSizeIterator<Item = Self::Subfield>;
57    fn from_subfield_elements(elems: &[Self::Subfield]) -> Option<Self>;
58    fn to_le_bytes(&self) -> impl IntoIterator<Item = u8>;
59    fn from_le_bytes(bytes: &[u8]) -> Option<Self>;
60
61    // TODO[next-gen-trait-solver]: Replace this by a higher-rank trait bound
62    // (`for<'a> Mul<&'a Self::Subfield, Output = Self>`) it is stabilized
63    fn mul_by_subfield(&self, other: &Self::Subfield) -> Self;
64
65    fn generator() -> Self;
66
67    fn random_elements<M: Positive>(mut rng: impl RngCore) -> HeapArray<Self, M> {
68        HeapArray::from_fn(|_| <Self as Field>::random(&mut rng))
69    }
70
71    /// Applies a linear orthomorphism to the current value.
72    ///
73    /// * Note: * σ is linear if σ(x + y) = σ(x) + σ(y) and an orthomorphism if σ is a permutation
74    ///   then σ'(x) = σ(x) + x is also a permutation.
75    fn linear_orthomorphism(&self) -> Self {
76        *self * Self::from(2u64)
77    }
78}
79
80pub trait PrimeFieldExtension: FieldExtension<Subfield = Self> {}
81
82impl<F: FieldExtension<Subfield = Self>> PrimeFieldExtension for F {}
primitives/algebra/field/field_extension.rs

primitives/algebra/field/
field_extension.rs
