p3_field/extension/
mod.rs

1use core::iter;
2
3use crate::ExtensionField;
4use crate::field::Field;
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>: Field {
23    /// The constant coefficient `W` in the binomial `X^D - W`.
24    const W: Self;
25
26    /// A `D`-th root of unity derived from `W`.
27    ///
28    /// This is `W^((n - 1)/D)`, where `n` is the order of the field.
29    /// Valid only when `n = kD + 1` for some `k`.
30    const DTH_ROOT: Self;
31
32    /// A generator for the extension field, expressed as a degree-`D` polynomial.
33    ///
34    /// This is an array of size `D`, where each entry is a base field element.
35    const EXT_GENERATOR: [Self; D];
36}
37
38/// Trait for extension fields that support Frobenius automorphisms.
39///
40/// The Frobenius automorphism is a field map `x ↦ x^n`,
41/// where `n` is the order of the base field.
42///
43/// This map is an automorphism of the field that fixes the base field.
44pub trait HasFrobenius<F: Field>: ExtensionField<F> {
45    /// Apply the Frobenius automorphism once.
46    ///
47    /// Equivalent to raising the element to the `n`th power.
48    fn frobenius(&self) -> Self;
49
50    /// Apply the Frobenius automorphism `count` times.
51    ///
52    /// Equivalent to raising to the `n^count` power.
53    fn repeated_frobenius(&self, count: usize) -> Self;
54
55    /// Compute the inverse Frobenius map.
56    ///
57    /// Returns the unique element `y` such that `self = y^n`.
58    fn frobenius_inv(&self) -> Self;
59
60    /// Returns the full Galois orbit of the element under Frobenius.
61    ///
62    /// This is the sequence `[x, x^n, x^{n^2}, ..., x^{n^{D-1}}]`,
63    /// where `D` is the extension degree.
64    fn galois_orbit(self) -> Vec<Self> {
65        iter::successors(Some(self), |x| Some(x.frobenius()))
66            .take(Self::DIMENSION)
67            .collect()
68    }
69}
70
71/// Trait for binomial extensions that support a two-adic subgroup generator.
72pub trait HasTwoAdicBinomialExtension<const D: usize>: BinomiallyExtendable<D> {
73    /// Two-adicity of the multiplicative group of the extension field.
74    ///
75    /// This is the number of times 2 divides the order of the field minus 1.
76    const EXT_TWO_ADICITY: usize;
77
78    /// Returns a two-adic generator for the extension field.
79    ///
80    /// This is used to generate the 2^bits-th roots of unity in the extension field.
81    /// Behavior is undefined if `bits > EXT_TWO_ADICITY`.
82    fn ext_two_adic_generator(bits: usize) -> [Self; D];
83}
p3_field/extension/mod.rs

p3_field/extension/
mod.rs
