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::{Array, ArraySize};
9use serde::{Deserialize, Serialize};
10use subtle::Choice;
11use wincode::{SchemaRead, SchemaWrite};
12
13use crate::{
14    algebra::{
15        ops::{AccReduce, DotProduct, MulAccReduce},
16        uniform_bytes::FromUniformBytes,
17    },
18    random::Random,
19    types::{identifiers::Named, Positive},
20};
21
22pub type ByteSize<F> = <F as FieldExtension>::FieldBytesSize;
23pub type BitSize<F> = <F as FieldExtension>::FieldBitSize;
24pub type FieldDegree<F> = <F as FieldExtension>::Degree;
25pub type Subfield<F> = <F as FieldExtension>::Subfield;
26
27/// A generic trait for field extensions
28pub trait FieldExtension:
29    Field
30    + Ord
31    + Debug
32    + PartialEq
33    + Hash
34    + Random
35    + Mul<Self::Subfield, Output = Self>
36    + MulAssign<Self::Subfield>
37    + Serialize
38    + for<'de> Deserialize<'de>
39    + SchemaWrite<Src = Self>
40    + for<'a> SchemaRead<'a, Dst = Self>
41    + FromUniformBytes
42    + From<u64>
43    + From<u128>
44    + AccReduce
45    + MulAccReduce
46    + MulAccReduce<Self, Self::Subfield>
47    + DotProduct
48    + for<'a> DotProduct<Self, &'a Self>
49    + for<'a> DotProduct<&'a Self, &'a Self>
50    + DotProduct<Self, Self::Subfield>
51    + for<'a> DotProduct<&'a Self, Self::Subfield>
52    + Unpin
53    + Named
54{
55    // The underlying prime subfield
56    type Subfield: FieldExtension<Subfield = Self::Subfield>;
57
58    type Degree: ArraySize + Positive;
59    type FieldBitSize: ArraySize + Positive;
60    type FieldBytesSize: ArraySize + Positive;
61
62    fn to_subfield_elements(&self) -> Array<Self::Subfield, Self::Degree>;
63    fn from_subfield_elements(elems: Array<Self::Subfield, Self::Degree>) -> Self;
64    /// Lift a field element to this extension field.
65    ///
66    /// Default implementation calls `Self::from_subfield_elements(Array::from([elem, 0, 0, ...]))`.
67    fn from_subfield_element(elem: Self::Subfield) -> Self {
68        let mut elems = Array::from_fn(|_| Self::Subfield::ZERO);
69        elems[0] = elem;
70        Self::from_subfield_elements(elems)
71    }
72    fn to_le_bytes(&self) -> Array<u8, Self::FieldBytesSize>;
73    fn from_le_bytes(bytes: &[u8]) -> Option<Self>;
74
75    // TODO[next-gen-trait-solver]: Replace this by a higher-rank trait bound
76    // (`for<'a> Mul<&'a Self::Subfield, Output = Self>`) when it is stabilized
77    fn mul_by_subfield(&self, other: &Self::Subfield) -> Self;
78
79    fn generator() -> Self;
80
81    /// Applies a linear orthomorphism to the current value.
82    ///
83    /// * Note: * σ is linear if σ(x + y) = σ(x) + σ(y) and an orthomorphism if σ is a permutation
84    ///   then σ'(x) = σ(x) + x is also a permutation.
85    fn linear_orthomorphism(&self) -> Self {
86        *self * Self::from(2u64)
87    }
88
89    /// Computes `(is_square, sqrt(num / div))`, equivalent to [`Field::sqrt_ratio`].
90    ///
91    /// The default delegates to the generic [`Field::sqrt_ratio`], but fields whose modulus admits
92    /// a faster closed form (e.g. primes ≡ 3 mod 4 or ≡ 5 mod 8) can override this to avoid the
93    /// generic Tonelli–Shanks path.
94    fn sqrt_ratio_ext(num: &Self, div: &Self) -> (Choice, Self) {
95        <Self as Field>::sqrt_ratio(num, div)
96    }
97}
98
99pub trait PrimeFieldExtension: FieldExtension<Subfield = Self> {}
100
101impl<F: FieldExtension<Subfield = Self>> PrimeFieldExtension for F {}
primitives/algebra/field/field_extension.rs

primitives/algebra/field/
field_extension.rs
