p3_field/extension/
mod.rs

1use core::iter;
2
3use crate::field::Field;
4use crate::{Algebra, ExtensionField};
5
6mod binomial_extension;
7mod complex;
8mod packed_binomial_extension;
9
10use alloc::vec::Vec;
11
12pub use binomial_extension::*;
13pub use complex::*;
14pub use packed_binomial_extension::*;
15
16/// Trait for fields that support binomial extension of the form `F[X]/(X^D - W)`.
17///
18/// A type implementing this trait can define a degree-`D` extension field using an
19/// irreducible binomial polynomial `X^D - W`, where `W` is a nonzero constant in the base field.
20///
21/// This is used to construct extension fields with efficient arithmetic.
22pub trait BinomiallyExtendable<const D: usize>:
23    Field + BinomiallyExtendableAlgebra<Self, D>
24{
25    /// The constant coefficient `W` in the binomial `X^D - W`.
26    const W: Self;
27
28    /// A `D`-th root of unity derived from `W`.
29    ///
30    /// This is `W^((n - 1)/D)`, where `n` is the order of the field.
31    /// Valid only when `n = kD + 1` for some `k`.
32    const DTH_ROOT: Self;
33
34    /// A generator for the extension field, expressed as a degree-`D` polynomial.
35    ///
36    /// This is an array of size `D`, where each entry is a base field element.
37    const EXT_GENERATOR: [Self; D];
38}
39
40/// Trait for algebras which support binomial extensions of the form `A[X]/(X^D - W)`
41/// with `W` in the base field `F`.
42pub trait BinomiallyExtendableAlgebra<F: Field, const D: usize>: Algebra<F> {
43    /// Multiplication in the algebra extension ring `A<X> / (X^D - W)`.
44    ///
45    /// Some algebras may want to reimplement this with faster methods.
46    #[inline]
47    fn binomial_mul(a: &[Self; D], b: &[Self; D], res: &mut [Self; D], w: F) {
48        binomial_mul::<F, Self, Self, D>(a, b, res, w);
49    }
50
51    /// Addition of elements in the algebra extension ring `A<X> / (X^D - W)`.
52    ///
53    /// As addition has no dependence on `W` so this is equivalent
54    /// to an algorithm for adding arrays of elements of `A`.
55    ///
56    /// Some algebras may want to reimplement this with faster methods.
57    #[inline]
58    #[must_use]
59    fn binomial_add(a: &[Self; D], b: &[Self; D]) -> [Self; D] {
60        vector_add(a, b)
61    }
62
63    /// Subtraction of elements in the algebra extension ring `A<X> / (X^D - W)`.
64    ///
65    /// As subtraction has no dependence on `W` so this is equivalent
66    /// to an algorithm for subtracting arrays of elements of `A`.
67    ///
68    /// Some algebras may want to reimplement this with faster methods.
69    #[inline]
70    #[must_use]
71    fn binomial_sub(a: &[Self; D], b: &[Self; D]) -> [Self; D] {
72        vector_sub(a, b)
73    }
74
75    #[inline]
76    fn binomial_base_mul(lhs: [Self; D], rhs: Self) -> [Self; D] {
77        lhs.map(|x| x * rhs.clone())
78    }
79}
80
81/// Trait for extension fields that support Frobenius automorphisms.
82///
83/// The Frobenius automorphism is a field map `x ↦ x^n`,
84/// where `n` is the order of the base field.
85///
86/// This map is an automorphism of the field that fixes the base field.
87pub trait HasFrobenius<F: Field>: ExtensionField<F> {
88    /// Apply the Frobenius automorphism once.
89    ///
90    /// Equivalent to raising the element to the `n`th power.
91    #[must_use]
92    fn frobenius(&self) -> Self;
93
94    /// Apply the Frobenius automorphism `count` times.
95    ///
96    /// Equivalent to raising to the `n^count` power.
97    #[must_use]
98    fn repeated_frobenius(&self, count: usize) -> Self;
99
100    /// Computes the pseudo inverse of the given field element.
101    ///
102    /// Returns `0` if `self == 0`, and `1/self` otherwise.
103    /// In other words, returns `self^(n^D - 2)` where `D` is the extension degree.
104    #[must_use]
105    fn pseudo_inv(&self) -> Self;
106
107    /// Returns the full Galois orbit of the element under Frobenius.
108    ///
109    /// This is the sequence `[x, x^n, x^{n^2}, ..., x^{n^{D-1}}]`,
110    /// where `D` is the extension degree.
111    #[must_use]
112    fn galois_orbit(self) -> Vec<Self> {
113        iter::successors(Some(self), |x| Some(x.frobenius()))
114            .take(Self::DIMENSION)
115            .collect()
116    }
117}
118
119/// Trait for binomial extensions that support a two-adic subgroup generator.
120pub trait HasTwoAdicBinomialExtension<const D: usize>: BinomiallyExtendable<D> {
121    /// Two-adicity of the multiplicative group of the extension field.
122    ///
123    /// This is the number of times 2 divides the order of the field minus 1.
124    const EXT_TWO_ADICITY: usize;
125
126    /// Returns a two-adic generator for the extension field.
127    ///
128    /// This is used to generate the 2^bits-th roots of unity in the extension field.
129    /// Behavior is undefined if `bits > EXT_TWO_ADICITY`.
130    #[must_use]
131    fn ext_two_adic_generator(bits: usize) -> [Self; D];
132}
p3_field/extension/mod.rs

p3_field/extension/
mod.rs
