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

primitives/algebra/field/
field_extension.rs
