p3_field/extension/
complex.rs

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

p3_field/extension/
complex.rs
