p3_mersenne_31/
extension.rs

1use p3_field::extension::{
2    BinomiallyExtendable, BinomiallyExtendableAlgebra, Complex, HasComplexBinomialExtension,
3    HasTwoAdicComplexBinomialExtension,
4};
5use p3_field::{PrimeCharacteristicRing, TwoAdicField, field_to_array};
6
7use crate::Mersenne31;
8
9impl BinomiallyExtendableAlgebra<Self, 3> for Mersenne31 {}
10
11impl BinomiallyExtendable<3> for Mersenne31 {
12    // ```sage
13    // p = 2^31 - 1
14    // F = GF(p)
15    // R.<x> = F[]
16    // assert (x^3 - 5).is_irreducible()
17    // ```
18    const W: Self = Self::new(5);
19
20    // ```sage
21    // F(5)^((p-1)/3)
22    // ```
23    const DTH_ROOT: Self = Self::new(1513477735);
24
25    // ```sage
26    // F.extension(x^3 - 5, 'u').multiplicative_generator()
27    // ```
28    const EXT_GENERATOR: [Self; 3] = [Self::new(10), Self::ONE, Self::ZERO];
29}
30
31impl HasComplexBinomialExtension<2> for Mersenne31 {
32    // Verifiable in Sage with
33    // ```sage
34    // p = 2**31 - 1  # Mersenne31
35    // F = GF(p)  # The base field GF(p)
36    // R.<x> = F[]  # The polynomial ring over F
37    // K.<i> = F.extension(x^2 + 1)  # The complex extension field
38    // R2.<y> = K[]
39    // f2 = y^2 - i - 2
40    // assert f2.is_irreducible()
41    // ```
42    const W: Complex<Self> = Complex::new_complex(Self::TWO, Self::ONE);
43
44    // DTH_ROOT = W^((p^2 - 1)/2).
45    const DTH_ROOT: Complex<Self> = Complex::new_real(Self::new(2147483646));
46
47    // Verifiable in Sage with
48    // ```sage
49    // K2.<j> = K.extension(f2)
50    //  g = j + 6
51    // for f in factor(p^4 - 1):
52    //   assert g^((p^4-1) // f) != 1
53    // ```
54    const EXT_GENERATOR: [Complex<Self>; 2] = [Complex::new_real(Self::new(6)), Complex::ONE];
55}
56
57impl HasTwoAdicComplexBinomialExtension<2> for Mersenne31 {
58    const COMPLEX_EXT_TWO_ADICITY: usize = 33;
59
60    fn complex_ext_two_adic_generator(bits: usize) -> [Complex<Self>; 2] {
61        assert!(bits <= 33);
62        if bits == 33 {
63            [
64                Complex::ZERO,
65                Complex::new_complex(Self::new_reduced(1437746044), Self::new_reduced(946469285)),
66            ]
67        } else {
68            [Complex::two_adic_generator(bits), Complex::ZERO]
69        }
70    }
71}
72
73impl HasComplexBinomialExtension<3> for Mersenne31 {
74    // Verifiable in Sage with
75    // ```sage
76    // p = 2**31 - 1  # Mersenne31
77    // F = GF(p)  # The base field GF(p)
78    // R.<x> = F[]  # The polynomial ring over F
79    // K.<i> = F.extension(x^2 + 1)  # The complex extension field
80    // R2.<y> = K[]
81    // f2 = y^3 - 5*i
82    // assert f2.is_irreducible()
83    // ```
84    const W: Complex<Self> = Complex::new_imag(Self::new(5));
85
86    // DTH_ROOT = W^((p^2 - 1)/2).
87    const DTH_ROOT: Complex<Self> = Complex::new_real(Self::new(634005911));
88
89    // Verifiable in Sage with
90    // ```sage
91    // K2.<j> = K.extension(f2)
92    //  g = j + 5
93    // for f in factor(p^6 - 1):
94    //   assert g^((p^6-1) // f) != 1
95    // ```
96    const EXT_GENERATOR: [Complex<Self>; 3] = [
97        Complex::new_real(Self::new(5)),
98        Complex::new_real(Self::ONE),
99        Complex::ZERO,
100    ];
101}
102
103impl HasTwoAdicComplexBinomialExtension<3> for Mersenne31 {
104    const COMPLEX_EXT_TWO_ADICITY: usize = 32;
105
106    fn complex_ext_two_adic_generator(bits: usize) -> [Complex<Self>; 3] {
107        field_to_array(Complex::two_adic_generator(bits))
108    }
109}
110
111#[cfg(test)]
112mod test_cubic_extension {
113    use num_bigint::BigUint;
114    use p3_field::extension::BinomialExtensionField;
115    use p3_field::{ExtensionField, PrimeCharacteristicRing};
116    use p3_field_testing::{test_extension_field, test_field, test_packed_extension_field};
117
118    use crate::Mersenne31;
119
120    type F = Mersenne31;
121    type EF = BinomialExtensionField<F, 3>;
122
123    // There is a redundant representation of zero but we already tested it
124    // when testing the base field.
125    const ZEROS: [EF; 1] = [EF::ZERO];
126    const ONES: [EF; 1] = [EF::ONE];
127
128    // Get the prime factorization of the order of the multiplicative group.
129    // i.e. the prime factorization of P^3 - 1.
130    fn multiplicative_group_prime_factorization() -> [(BigUint, u32); 9] {
131        [
132            (BigUint::from(2u8), 1),
133            (BigUint::from(3u8), 3),
134            (BigUint::from(7u8), 1),
135            (BigUint::from(11u8), 1),
136            (BigUint::from(31u8), 1),
137            (BigUint::from(151u8), 1),
138            (BigUint::from(331u16), 1),
139            (BigUint::from(529510939u32), 1),
140            (BigUint::from(2903110321u32), 1),
141        ]
142    }
143
144    test_extension_field!(super::F, super::EF);
145
146    test_field!(
147        super::EF,
148        &super::ZEROS,
149        &super::ONES,
150        &super::multiplicative_group_prime_factorization()
151    );
152
153    type Pef = <EF as ExtensionField<F>>::ExtensionPacking;
154    const PACKED_ZEROS: [Pef; 1] = [Pef::ZERO];
155    const PACKED_ONES: [Pef; 1] = [Pef::ONE];
156    test_packed_extension_field!(
157        super::F,
158        super::EF,
159        super::Pef,
160        &super::PACKED_ZEROS,
161        &super::PACKED_ONES
162    );
163}
164
165#[cfg(test)]
166mod test_cubic_complex_extension {
167    use num_bigint::BigUint;
168    use p3_field::extension::{BinomialExtensionField, Complex};
169    use p3_field::{ExtensionField, PrimeCharacteristicRing};
170    use p3_field_testing::{
171        test_extension_field, test_field, test_packed_extension_field,
172        test_two_adic_extension_field,
173    };
174
175    use crate::Mersenne31;
176
177    type F = Complex<Mersenne31>;
178    type EF = BinomialExtensionField<F, 3>;
179
180    // There is a redundant representation of zero but we already tested it
181    // when testing the base field.
182    const ZEROS: [EF; 1] = [EF::ZERO];
183    const ONES: [EF; 1] = [EF::ONE];
184
185    // Get the prime factorization of the order of the multiplicative group.
186    // i.e. the prime factorization of P^6 - 1.
187    fn multiplicative_group_prime_factorization() -> [(BigUint, u32); 14] {
188        [
189            (BigUint::from(2u8), 32),
190            (BigUint::from(3u8), 3),
191            (BigUint::from(7u8), 1),
192            (BigUint::from(11u8), 1),
193            (BigUint::from(13u8), 1),
194            (BigUint::from(31u8), 1),
195            (BigUint::from(43u8), 2),
196            (BigUint::from(79u8), 1),
197            (BigUint::from(151u8), 1),
198            (BigUint::from(331u16), 1),
199            (BigUint::from(1381u16), 1),
200            (BigUint::from(529510939u32), 1),
201            (BigUint::from(1758566101u32), 1),
202            (BigUint::from(2903110321u32), 1),
203        ]
204    }
205
206    test_field!(
207        super::EF,
208        &super::ZEROS,
209        &super::ONES,
210        &super::multiplicative_group_prime_factorization()
211    );
212
213    test_extension_field!(super::F, super::EF);
214
215    test_two_adic_extension_field!(super::F, super::EF);
216
217    type Pef = <EF as ExtensionField<F>>::ExtensionPacking;
218    const PACKED_ZEROS: [Pef; 1] = [Pef::ZERO];
219    const PACKED_ONES: [Pef; 1] = [Pef::ONE];
220    test_packed_extension_field!(
221        super::F,
222        super::EF,
223        super::Pef,
224        &super::PACKED_ZEROS,
225        &super::PACKED_ONES
226    );
227}
228
229#[cfg(test)]
230mod test_quadratic_complex_extension {
231
232    use num_bigint::BigUint;
233    use p3_field::extension::{BinomialExtensionField, Complex};
234    use p3_field::{ExtensionField, PrimeCharacteristicRing};
235    use p3_field_testing::{
236        test_extension_field, test_field, test_packed_extension_field,
237        test_two_adic_extension_field,
238    };
239
240    use crate::Mersenne31;
241
242    type F = Complex<Mersenne31>;
243    type EF = BinomialExtensionField<F, 2>;
244
245    // There is a redundant representation of zero but we already tested it
246    // when testing the base field.
247    const ZEROS: [EF; 1] = [EF::ZERO];
248    const ONES: [EF; 1] = [EF::ONE];
249
250    // Get the prime factorization of the order of the multiplicative group.
251    // i.e. the prime factorization of P^4 - 1.
252    fn multiplicative_group_prime_factorization() -> [(BigUint, u32); 11] {
253        [
254            (BigUint::from(2u8), 33),
255            (BigUint::from(3u8), 2),
256            (BigUint::from(5u8), 1),
257            (BigUint::from(7u8), 1),
258            (BigUint::from(11u8), 1),
259            (BigUint::from(31u8), 1),
260            (BigUint::from(151u8), 1),
261            (BigUint::from(331u16), 1),
262            (BigUint::from(733u16), 1),
263            (BigUint::from(1709u16), 1),
264            (BigUint::from(368140581013u64), 1),
265        ]
266    }
267
268    test_field!(
269        super::EF,
270        &super::ZEROS,
271        &super::ONES,
272        &super::multiplicative_group_prime_factorization()
273    );
274
275    test_extension_field!(super::F, super::EF);
276
277    test_two_adic_extension_field!(super::F, super::EF);
278
279    type Pef = <EF as ExtensionField<F>>::ExtensionPacking;
280    const PACKED_ZEROS: [Pef; 1] = [Pef::ZERO];
281    const PACKED_ONES: [Pef; 1] = [Pef::ONE];
282    test_packed_extension_field!(
283        super::F,
284        super::EF,
285        super::Pef,
286        &super::PACKED_ZEROS,
287        &super::PACKED_ONES
288    );
289}
p3_mersenne_31/extension.rs

p3_mersenne_31/
extension.rs
