p3_field/extension/
complex.rs

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

p3_field/extension/
complex.rs
