p3_mersenne_31/
complex.rs

1//! Implementation of the quadratic extension of the Mersenne31 field
2//! by X^2 + 1.
3//!
4//! Note that X^2 + 1 is irreducible over p = Mersenne31 field because
5//! kronecker(-1, p) = -1, that is, -1 is not square in F_p.
6
7use p3_field::PrimeCharacteristicRing;
8use p3_field::extension::{Complex, ComplexExtendable, HasTwoAdicBinomialExtension};
9
10use crate::Mersenne31;
11
12impl ComplexExtendable for Mersenne31 {
13    const CIRCLE_TWO_ADICITY: usize = 31;
14
15    // sage: p = 2^31 - 1
16    // sage: F = GF(p)
17    // sage: R.<x> = F[]
18    // sage: F2.<u> = F.extension(x^2 + 1)
19    // sage: F2.multiplicative_generator()
20    // u + 12
21    const COMPLEX_GENERATOR: Complex<Self> = Complex::new_complex(Self::new(12), Self::ONE);
22
23    fn circle_two_adic_generator(bits: usize) -> Complex<Self> {
24        // Generator of the whole 2^TWO_ADICITY group
25        // sage: p = 2^31 - 1
26        // sage: F = GF(p)
27        // sage: R.<x> = F[]
28        // sage: F2.<u> = F.extension(x^2 + 1)
29        // sage: g = F2.multiplicative_generator()^((p^2 - 1) / 2^31); g
30        // 1584694829*u + 311014874
31        // sage: assert(g.multiplicative_order() == 2^31)
32        // sage: assert(g.norm() == 1)
33        assert!(bits <= Self::CIRCLE_TWO_ADICITY);
34        let base = Complex::new_complex(
35            Self::new_reduced(311_014_874),
36            Self::new_reduced(1_584_694_829),
37        );
38        base.exp_power_of_2(Self::CIRCLE_TWO_ADICITY - bits)
39    }
40}
41
42impl HasTwoAdicBinomialExtension<2> for Mersenne31 {
43    const EXT_TWO_ADICITY: usize = 32;
44
45    fn ext_two_adic_generator(bits: usize) -> [Self; 2] {
46        assert!(bits <= Self::EXT_TWO_ADICITY);
47        Self::EXT_TWO_ADIC_GENERATORS[bits]
48    }
49}
50
51#[cfg(test)]
52mod tests {
53    use num_bigint::BigUint;
54    use p3_field::{ExtensionField, PrimeField32};
55    use p3_field_testing::{
56        test_extension_field, test_field, test_packed_extension_field, test_two_adic_field,
57    };
58
59    use super::*;
60
61    type Fi = Complex<Mersenne31>;
62    type F = Mersenne31;
63
64    #[test]
65    fn add() {
66        // real part
67        assert_eq!(Fi::ONE + Fi::ONE, Fi::TWO);
68        assert_eq!(Fi::NEG_ONE + Fi::ONE, Fi::ZERO);
69        assert_eq!(Fi::NEG_ONE + Fi::TWO, Fi::ONE);
70        assert_eq!((Fi::NEG_ONE + Fi::NEG_ONE).real(), F::new(F::ORDER_U32 - 2));
71
72        // complex part
73        assert_eq!(
74            Fi::new_imag(F::ONE) + Fi::new_imag(F::ONE),
75            Fi::new_imag(F::TWO)
76        );
77        assert_eq!(
78            Fi::new_imag(F::NEG_ONE) + Fi::new_imag(F::ONE),
79            Fi::new_imag(F::ZERO)
80        );
81        assert_eq!(
82            Fi::new_imag(F::NEG_ONE) + Fi::new_imag(F::TWO),
83            Fi::new_imag(F::ONE)
84        );
85        assert_eq!(
86            (Fi::new_imag(F::NEG_ONE) + Fi::new_imag(F::NEG_ONE)).imag(),
87            F::new(F::ORDER_U32 - 2)
88        );
89
90        // further tests
91        assert_eq!(
92            Fi::new_complex(F::ONE, F::TWO) + Fi::new_complex(F::ONE, F::ONE),
93            Fi::new_complex(F::TWO, F::new(3))
94        );
95        assert_eq!(
96            Fi::new_complex(F::NEG_ONE, F::NEG_ONE) + Fi::new_complex(F::ONE, F::ONE),
97            Fi::ZERO
98        );
99        assert_eq!(
100            Fi::new_complex(F::NEG_ONE, F::ONE) + Fi::new_complex(F::TWO, F::new(F::ORDER_U32 - 2)),
101            Fi::new_complex(F::ONE, F::NEG_ONE)
102        );
103    }
104
105    #[test]
106    fn sub() {
107        // real part
108        assert_eq!(Fi::ONE - Fi::ONE, Fi::ZERO);
109        assert_eq!(Fi::TWO - Fi::TWO, Fi::ZERO);
110        assert_eq!(Fi::NEG_ONE - Fi::NEG_ONE, Fi::ZERO);
111        assert_eq!(Fi::TWO - Fi::ONE, Fi::ONE);
112        assert_eq!(Fi::NEG_ONE - Fi::ZERO, Fi::NEG_ONE);
113
114        // complex part
115        assert_eq!(Fi::new_imag(F::ONE) - Fi::new_imag(F::ONE), Fi::ZERO);
116        assert_eq!(Fi::new_imag(F::TWO) - Fi::new_imag(F::TWO), Fi::ZERO);
117        assert_eq!(
118            Fi::new_imag(F::NEG_ONE) - Fi::new_imag(F::NEG_ONE),
119            Fi::ZERO
120        );
121        assert_eq!(
122            Fi::new_imag(F::TWO) - Fi::new_imag(F::ONE),
123            Fi::new_imag(F::ONE)
124        );
125        assert_eq!(
126            Fi::new_imag(F::NEG_ONE) - Fi::ZERO,
127            Fi::new_imag(F::NEG_ONE)
128        );
129    }
130
131    #[test]
132    fn mul() {
133        assert_eq!(
134            Fi::new_complex(F::TWO, F::TWO) * Fi::new_complex(F::new(4), F::new(5)),
135            Fi::new_complex(-F::TWO, F::new(18))
136        );
137    }
138
139    #[test]
140    fn mul_2exp_u64() {
141        // real part
142        // 1 * 2^0 = 1.
143        assert_eq!(Fi::ONE.mul_2exp_u64(0), Fi::ONE);
144        // 2 * 2^30 = 2^31 = 1.
145        assert_eq!(Fi::TWO.mul_2exp_u64(30), Fi::ONE);
146        // 5 * 2^2 = 20.
147        assert_eq!(
148            Fi::new_real(F::new(5)).mul_2exp_u64(2),
149            Fi::new_real(F::new(20))
150        );
151
152        // complex part
153        // i * 2^0 = i.
154        assert_eq!(Fi::new_imag(F::ONE).mul_2exp_u64(0), Fi::new_imag(F::ONE));
155        // (2i) * 2^30 = (2^31) * i = i.
156        assert_eq!(Fi::new_imag(F::TWO).mul_2exp_u64(30), Fi::new_imag(F::ONE));
157        // 5i * 2^2 = 20i.
158        assert_eq!(
159            Fi::new_imag(F::new(5)).mul_2exp_u64(2),
160            Fi::new_imag(F::new(20))
161        );
162    }
163
164    // There is a redundant representation of zero but we already tested it
165    // when testing the base field.
166    const ZEROS: [Fi; 1] = [Fi::ZERO];
167    const ONES: [Fi; 1] = [Fi::ONE];
168
169    // Get the prime factorization of the order of the multiplicative group.
170    // i.e. the prime factorization of P^2 - 1.
171    fn multiplicative_group_prime_factorization() -> [(BigUint, u32); 7] {
172        [
173            (BigUint::from(2u8), 32),
174            (BigUint::from(3u8), 2),
175            (BigUint::from(7u8), 1),
176            (BigUint::from(11u8), 1),
177            (BigUint::from(31u8), 1),
178            (BigUint::from(151u8), 1),
179            (BigUint::from(331u16), 1),
180        ]
181    }
182
183    test_field!(
184        super::Fi,
185        &super::ZEROS,
186        &super::ONES,
187        &super::multiplicative_group_prime_factorization()
188    );
189
190    test_extension_field!(super::F, super::Fi);
191    test_two_adic_field!(super::Fi);
192
193    type Pef = <Fi as ExtensionField<F>>::ExtensionPacking;
194    const PACKED_ZEROS: [Pef; 1] = [Pef::ZERO];
195    const PACKED_ONES: [Pef; 1] = [Pef::ONE];
196    test_packed_extension_field!(super::Pef, &super::PACKED_ZEROS, &super::PACKED_ONES);
197}
p3_mersenne_31/complex.rs

p3_mersenne_31/
complex.rs
