p3_field/extension/
mod.rs

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/// A extension field with a irreducible polynomial X^d-W
17/// such that the extension is `F[X]/(X^d-W)`.
18pub trait BinomiallyExtendable<const D: usize>: Field {
19    fn w() -> Self;
20
21    // DTH_ROOT = W^((n - 1)/D).
22    // n is the order of base field.
23    // Only works when exists k such that n = kD + 1.
24    fn dth_root() -> Self;
25
26    fn ext_generator() -> [Self; D];
27}
28
29pub trait HasFrobenius<F: Field>: ExtensionField<F> {
30    fn frobenius(&self) -> Self;
31    fn repeated_frobenius(&self, count: usize) -> Self;
32    fn frobenius_inv(&self) -> Self;
33
34    fn minimal_poly(mut self) -> Vec<F> {
35        let mut m = vec![Self::one()];
36        for _ in 0..Self::D {
37            m = naive_poly_mul(&m, &[-self, Self::one()]);
38            self = self.frobenius();
39        }
40        let mut m_iter = m
41            .into_iter()
42            .map(|c| c.as_base().expect("Extension is not algebraic?"));
43        let m: Vec<F> = m_iter.by_ref().take(Self::D + 1).collect();
44        debug_assert_eq!(m.len(), Self::D + 1);
45        debug_assert_eq!(m.last(), Some(&F::one()));
46        debug_assert!(m_iter.all(|c| c.is_zero()));
47        m
48    }
49
50    fn galois_group(self) -> Vec<Self> {
51        iter::successors(Some(self), |x| Some(x.frobenius()))
52            .take(Self::D)
53            .collect()
54    }
55}
56
57/// Optional trait for implementing Two Adic Binomial Extension Field.
58pub trait HasTwoAdicBionmialExtension<const D: usize>: BinomiallyExtendable<D> {
59    const EXT_TWO_ADICITY: usize;
60
61    /// Assumes the multiplicative group size has at least `bits` powers of two, otherwise the
62    /// behavior is undefined.
63    fn ext_two_adic_generator(bits: usize) -> [Self; D];
64}
p3_field/extension/mod.rs

p3_field/extension/
mod.rs
