plonky2_field/extension/
mod.rs

1use alloc::vec::Vec;
2
3use crate::types::Field;
4
5pub mod algebra;
6pub mod quadratic;
7pub mod quartic;
8pub mod quintic;
9
10/// Optimal extension field trait.
11/// A degree `d` field extension is optimal if there exists a base field element `W`,
12/// such that the extension is `F[X]/(X^d-W)`.
13#[allow(clippy::upper_case_acronyms)]
14pub trait OEF<const D: usize>: FieldExtension<D> {
15    // Element W of BaseField, such that `X^d - W` is irreducible over BaseField.
16    const W: Self::BaseField;
17
18    // Element of BaseField such that DTH_ROOT^D == 1. Implementers
19    // should set this to W^((p - 1)/D), where W is as above and p is
20    // the order of the BaseField.
21    const DTH_ROOT: Self::BaseField;
22}
23
24impl<F: Field> OEF<1> for F {
25    const W: Self::BaseField = F::ONE;
26    const DTH_ROOT: Self::BaseField = F::ONE;
27}
28
29pub trait Frobenius<const D: usize>: OEF<D> {
30    /// FrobeniusField automorphisms: x -> x^p, where p is the order of BaseField.
31    fn frobenius(&self) -> Self {
32        self.repeated_frobenius(1)
33    }
34
35    /// Repeated Frobenius automorphisms: x -> x^(p^count).
36    ///
37    /// Follows precomputation suggestion in Section 11.3.3 of the
38    /// Handbook of Elliptic and Hyperelliptic Curve Cryptography.
39    fn repeated_frobenius(&self, count: usize) -> Self {
40        if count == 0 {
41            return *self;
42        } else if count >= D {
43            // x |-> x^(p^D) is the identity, so x^(p^count) ==
44            // x^(p^(count % D))
45            return self.repeated_frobenius(count % D);
46        }
47        let arr = self.to_basefield_array();
48
49        // z0 = DTH_ROOT^count = W^(k * count) where k = floor((p^D-1)/D)
50        let mut z0 = Self::DTH_ROOT;
51        for _ in 1..count {
52            z0 *= Self::DTH_ROOT;
53        }
54
55        let mut res = [Self::BaseField::ZERO; D];
56        for (i, z) in z0.powers().take(D).enumerate() {
57            res[i] = arr[i] * z;
58        }
59
60        Self::from_basefield_array(res)
61    }
62}
63
64pub trait Extendable<const D: usize>: Field + Sized {
65    type Extension: Field + OEF<D, BaseField = Self> + Frobenius<D> + From<Self>;
66
67    const W: Self;
68
69    const DTH_ROOT: Self;
70
71    /// Chosen so that when raised to the power `(p^D - 1) >> F::Extension::TWO_ADICITY)`
72    /// we obtain F::EXT_POWER_OF_TWO_GENERATOR.
73    const EXT_MULTIPLICATIVE_GROUP_GENERATOR: [Self; D];
74
75    /// Chosen so that when raised to the power `1<<(Self::TWO_ADICITY-Self::BaseField::TWO_ADICITY)`,
76    /// we get `Self::BaseField::POWER_OF_TWO_GENERATOR`. This makes `primitive_root_of_unity` coherent
77    /// with the base field which implies that the FFT commutes with field inclusion.
78    const EXT_POWER_OF_TWO_GENERATOR: [Self; D];
79}
80
81impl<F: Field + Frobenius<1> + FieldExtension<1, BaseField = F>> Extendable<1> for F {
82    type Extension = F;
83    const W: Self = F::ONE;
84    const DTH_ROOT: Self = F::ONE;
85    const EXT_MULTIPLICATIVE_GROUP_GENERATOR: [Self; 1] = [F::MULTIPLICATIVE_GROUP_GENERATOR];
86    const EXT_POWER_OF_TWO_GENERATOR: [Self; 1] = [F::POWER_OF_TWO_GENERATOR];
87}
88
89pub trait FieldExtension<const D: usize>: Field {
90    type BaseField: Field;
91
92    fn to_basefield_array(&self) -> [Self::BaseField; D];
93
94    fn from_basefield_array(arr: [Self::BaseField; D]) -> Self;
95
96    fn from_basefield(x: Self::BaseField) -> Self;
97
98    fn is_in_basefield(&self) -> bool {
99        self.to_basefield_array()[1..].iter().all(|x| x.is_zero())
100    }
101
102    fn scalar_mul(&self, scalar: Self::BaseField) -> Self {
103        let mut res = self.to_basefield_array();
104        res.iter_mut().for_each(|x| {
105            *x *= scalar;
106        });
107        Self::from_basefield_array(res)
108    }
109}
110
111impl<F: Field> FieldExtension<1> for F {
112    type BaseField = F;
113
114    fn to_basefield_array(&self) -> [Self::BaseField; 1] {
115        [*self]
116    }
117
118    fn from_basefield_array(arr: [Self::BaseField; 1]) -> Self {
119        arr[0]
120    }
121
122    fn from_basefield(x: Self::BaseField) -> Self {
123        x
124    }
125}
126
127/// Flatten the slice by sending every extension field element to its D-sized canonical representation.
128pub fn flatten<F, const D: usize>(l: &[F::Extension]) -> Vec<F>
129where
130    F: Field + Extendable<D>,
131{
132    l.iter()
133        .flat_map(|x| x.to_basefield_array().to_vec())
134        .collect()
135}
136
137/// Batch every D-sized chunks into extension field elements.
138pub fn unflatten<F, const D: usize>(l: &[F]) -> Vec<F::Extension>
139where
140    F: Field + Extendable<D>,
141{
142    debug_assert_eq!(l.len() % D, 0);
143    l.chunks_exact(D)
144        .map(|c| F::Extension::from_basefield_array(c.to_vec().try_into().unwrap()))
145        .collect()
146}
plonky2_field/extension/mod.rs

plonky2_field/extension/
mod.rs
