p3_field/extension/
complex.rs

1use super::{BinomialExtensionField, BinomiallyExtendable, HasTwoAdicBinomialExtension};
2use crate::{Algebra, Field, PrimeCharacteristicRing};
3
4pub type Complex<F> = BinomialExtensionField<F, 2>;
5
6/// A field for which `p = 3 (mod 4)`. Equivalently, `-1` is not a square,
7/// so the complex extension can be defined `F[i] = F[X]/(X^2+1)`.
8pub trait ComplexExtendable: Field {
9    /// The two-adicity of `p+1`, the order of the circle group.
10    const CIRCLE_TWO_ADICITY: usize;
11
12    const COMPLEX_GENERATOR: Complex<Self>;
13
14    fn circle_two_adic_generator(bits: usize) -> Complex<Self>;
15}
16
17impl<F: ComplexExtendable> BinomiallyExtendable<2> for F {
18    const W: Self = F::NEG_ONE;
19
20    // since `p = 3 (mod 4)`, `(p-1)/2` is always odd,
21    // so `(-1)^((p-1)/2) = -1`
22    const DTH_ROOT: Self = F::NEG_ONE;
23
24    const EXT_GENERATOR: [Self; 2] = F::COMPLEX_GENERATOR.value;
25}
26
27/// Convenience methods for complex extensions
28impl<R: PrimeCharacteristicRing> Complex<R> {
29    #[inline(always)]
30    pub const fn new_complex(real: R, imag: R) -> Self {
31        Self::new([real, imag])
32    }
33
34    #[inline(always)]
35    pub const fn new_real(real: R) -> Self {
36        Self::new_complex(real, R::ZERO)
37    }
38
39    #[inline(always)]
40    pub const fn new_imag(imag: R) -> Self {
41        Self::new_complex(R::ZERO, imag)
42    }
43
44    #[inline(always)]
45    pub fn real(&self) -> R {
46        self.value[0].clone()
47    }
48
49    #[inline(always)]
50    pub fn imag(&self) -> R {
51        self.value[1].clone()
52    }
53
54    #[inline(always)]
55    pub fn conjugate(&self) -> Self {
56        Self::new_complex(self.real(), self.imag().neg())
57    }
58
59    #[inline]
60    pub fn norm(&self) -> R {
61        self.real().square() + self.imag().square()
62    }
63
64    #[inline(always)]
65    pub fn to_array(&self) -> [R; 2] {
66        self.value.clone()
67    }
68
69    // Sometimes we want to rotate over an extension that's not necessarily ComplexExtendable,
70    // but still on the circle.
71    pub fn rotate<Ext: Algebra<R>>(&self, rhs: &Complex<Ext>) -> Complex<Ext> {
72        Complex::<Ext>::new_complex(
73            rhs.real() * self.real() - rhs.imag() * self.imag(),
74            rhs.imag() * self.real() + rhs.real() * self.imag(),
75        )
76    }
77}
78
79/// The complex extension of this field has a binomial extension.
80///
81/// This exists if the polynomial ring `F[i][X]` has an irreducible polynomial `X^d-W`
82/// allowing us to define the binomial extension field `F[i][X]/(X^d-W)`.
83pub trait HasComplexBinomialExtension<const D: usize>: ComplexExtendable {
84    const W: Complex<Self>;
85
86    // DTH_ROOT = W^((n - 1)/D).
87    // n is the order of base field.
88    // Only works when exists k such that n = kD + 1.
89    const DTH_ROOT: Complex<Self>;
90
91    const EXT_GENERATOR: [Complex<Self>; D];
92}
93
94impl<F, const D: usize> BinomiallyExtendable<D> for Complex<F>
95where
96    F: HasComplexBinomialExtension<D>,
97{
98    const W: Self = <F as HasComplexBinomialExtension<D>>::W;
99
100    const DTH_ROOT: Self = <F as HasComplexBinomialExtension<D>>::DTH_ROOT;
101
102    const EXT_GENERATOR: [Self; D] = F::EXT_GENERATOR;
103}
104
105/// The complex extension of this field has a two-adic binomial extension.
106pub trait HasTwoAdicComplexBinomialExtension<const D: usize>:
107    HasComplexBinomialExtension<D>
108{
109    const COMPLEX_EXT_TWO_ADICITY: usize;
110
111    fn complex_ext_two_adic_generator(bits: usize) -> [Complex<Self>; D];
112}
113
114impl<F, const D: usize> HasTwoAdicBinomialExtension<D> for Complex<F>
115where
116    F: HasTwoAdicComplexBinomialExtension<D>,
117{
118    const EXT_TWO_ADICITY: usize = F::COMPLEX_EXT_TWO_ADICITY;
119
120    #[inline(always)]
121    fn ext_two_adic_generator(bits: usize) -> [Self; D] {
122        F::complex_ext_two_adic_generator(bits)
123    }
124}
p3_field/extension/complex.rs

p3_field/extension/
complex.rs
