p3_field/extension/
mod.rs

Help
1use core::{debug_assert, debug_assert_eq, iter};
2
3use crate::field::Field;
4use crate::{naive_poly_mul, ExtensionField};
5
6mod binomial_extension;
7mod complex;
8
9use alloc::vec;
10use alloc::vec::Vec;
11
12pub use binomial_extension::*;
13pub use complex::*;
14
15/// Binomial extension field trait.
16///
17/// This exists if the polynomial ring `F[X]` has an irreducible polynomial `X^d-W`
18/// allowing us to define the binomial extension field `F[X]/(X^d-W)`.
19pub trait BinomiallyExtendable<const D: usize>: Field {
20    const W: Self;
21
22    // DTH_ROOT = W^((n - 1)/D).
23    // n is the order of base field.
24    // Only works when exists k such that n = kD + 1.
25    const DTH_ROOT: Self;
26
27    const EXT_GENERATOR: [Self; D];
28}
29
30pub trait HasFrobenius<F: Field>: ExtensionField<F> {
31    fn frobenius(&self) -> Self;
32    fn repeated_frobenius(&self, count: usize) -> Self;
33    fn frobenius_inv(&self) -> Self;
34
35    fn minimal_poly(mut self) -> Vec<F> {
36        let mut m = vec![Self::ONE];
37        for _ in 0..Self::D {
38            m = naive_poly_mul(&m, &[-self, Self::ONE]);
39            self = self.frobenius();
40        }
41        let mut m_iter = m
42            .into_iter()
43            .map(|c| c.as_base().expect("Extension is not algebraic?"));
44        let m: Vec<F> = m_iter.by_ref().take(Self::D + 1).collect();
45        debug_assert_eq!(m.len(), Self::D + 1);
46        debug_assert_eq!(m.last(), Some(&F::ONE));
47        debug_assert!(m_iter.all(|c| c.is_zero()));
48        m
49    }
50
51    fn galois_group(self) -> Vec<Self> {
52        iter::successors(Some(self), |x| Some(x.frobenius()))
53            .take(Self::D)
54            .collect()
55    }
56}
57
58/// Optional trait for implementing Two Adic Binomial Extension Field.
59pub trait HasTwoAdicBinomialExtension<const D: usize>: BinomiallyExtendable<D> {
60    const EXT_TWO_ADICITY: usize;
61
62    /// Assumes the multiplicative group size has at least `bits` powers of two, otherwise the
63    /// behavior is undefined.
64    fn ext_two_adic_generator(bits: usize) -> [Self; D];
65}
p3_field/extension/mod.rs

p3_field/extension/
mod.rs
