p3_field/extension/
complex.rs

Help
1use super::{BinomialExtensionField, BinomiallyExtendable, HasTwoAdicBinomialExtension};
2use crate::{Field, FieldAlgebra, FieldExtensionAlgebra};
3
4pub type Complex<FA> = BinomialExtensionField<FA, 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<FA: FieldAlgebra> Complex<FA> {
29    #[inline(always)]
30    pub const fn new(real: FA, imag: FA) -> Self {
31        Self {
32            value: [real, imag],
33        }
34    }
35
36    #[inline(always)]
37    pub const fn new_real(real: FA) -> Self {
38        Self::new(real, FA::ZERO)
39    }
40
41    #[inline(always)]
42    pub const fn new_imag(imag: FA) -> Self {
43        Self::new(FA::ZERO, imag)
44    }
45
46    #[inline(always)]
47    pub fn real(&self) -> FA {
48        self.value[0].clone()
49    }
50
51    #[inline(always)]
52    pub fn imag(&self) -> FA {
53        self.value[1].clone()
54    }
55
56    #[inline(always)]
57    pub fn conjugate(&self) -> Self {
58        Self::new(self.real(), self.imag().neg())
59    }
60
61    #[inline]
62    pub fn norm(&self) -> FA {
63        self.real().square() + self.imag().square()
64    }
65
66    #[inline(always)]
67    pub fn to_array(&self) -> [FA; 2] {
68        self.value.clone()
69    }
70
71    // Sometimes we want to rotate over an extension that's not necessarily ComplexExtendable,
72    // but still on the circle.
73    pub fn rotate<Ext: FieldExtensionAlgebra<FA>>(&self, rhs: Complex<Ext>) -> Complex<Ext> {
74        Complex::<Ext>::new(
75            rhs.real() * self.real() - rhs.imag() * self.imag(),
76            rhs.imag() * self.real() + rhs.real() * self.imag(),
77        )
78    }
79}
80
81/// The complex extension of this field has a binomial extension.
82///
83/// This exists if the polynomial ring `F[i][X]` has an irreducible polynomial `X^d-W`
84/// allowing us to define the binomial extension field `F[i][X]/(X^d-W)`.
85pub trait HasComplexBinomialExtension<const D: usize>: ComplexExtendable {
86    const W: Complex<Self>;
87
88    // DTH_ROOT = W^((n - 1)/D).
89    // n is the order of base field.
90    // Only works when exists k such that n = kD + 1.
91    const DTH_ROOT: Complex<Self>;
92
93    const EXT_GENERATOR: [Complex<Self>; D];
94}
95
96impl<F, const D: usize> BinomiallyExtendable<D> for Complex<F>
97where
98    F: HasComplexBinomialExtension<D>,
99{
100    const W: Self = <F as HasComplexBinomialExtension<D>>::W;
101
102    const DTH_ROOT: Self = <F as HasComplexBinomialExtension<D>>::DTH_ROOT;
103
104    const EXT_GENERATOR: [Self; D] = F::EXT_GENERATOR;
105}
106
107/// The complex extension of this field has a two-adic binomial extension.
108pub trait HasTwoAdicComplexBinomialExtension<const D: usize>:
109    HasComplexBinomialExtension<D>
110{
111    const COMPLEX_EXT_TWO_ADICITY: usize;
112
113    fn complex_ext_two_adic_generator(bits: usize) -> [Complex<Self>; D];
114}
115
116impl<F, const D: usize> HasTwoAdicBinomialExtension<D> for Complex<F>
117where
118    F: HasTwoAdicComplexBinomialExtension<D>,
119{
120    const EXT_TWO_ADICITY: usize = F::COMPLEX_EXT_TWO_ADICITY;
121
122    #[inline(always)]
123    fn ext_two_adic_generator(bits: usize) -> [Self; D] {
124        F::complex_ext_two_adic_generator(bits)
125    }
126}
p3_field/extension/complex.rs

p3_field/extension/
complex.rs
