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(1437746044), Self::new(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!(super::Pef, &super::PACKED_ZEROS, &super::PACKED_ONES);
157}
158
159#[cfg(test)]
160mod test_cubic_complex_extension {
161    use num_bigint::BigUint;
162    use p3_field::extension::{BinomialExtensionField, Complex};
163    use p3_field::{ExtensionField, PrimeCharacteristicRing};
164    use p3_field_testing::{
165        test_extension_field, test_field, test_packed_extension_field,
166        test_two_adic_extension_field,
167    };
168
169    use crate::Mersenne31;
170
171    type F = Complex<Mersenne31>;
172    type EF = BinomialExtensionField<F, 3>;
173
174    // There is a redundant representation of zero but we already tested it
175    // when testing the base field.
176    const ZEROS: [EF; 1] = [EF::ZERO];
177    const ONES: [EF; 1] = [EF::ONE];
178
179    // Get the prime factorization of the order of the multiplicative group.
180    // i.e. the prime factorization of P^6 - 1.
181    fn multiplicative_group_prime_factorization() -> [(BigUint, u32); 14] {
182        [
183            (BigUint::from(2u8), 32),
184            (BigUint::from(3u8), 3),
185            (BigUint::from(7u8), 1),
186            (BigUint::from(11u8), 1),
187            (BigUint::from(13u8), 1),
188            (BigUint::from(31u8), 1),
189            (BigUint::from(43u8), 2),
190            (BigUint::from(79u8), 1),
191            (BigUint::from(151u8), 1),
192            (BigUint::from(331u16), 1),
193            (BigUint::from(1381u16), 1),
194            (BigUint::from(529510939u32), 1),
195            (BigUint::from(1758566101u32), 1),
196            (BigUint::from(2903110321u32), 1),
197        ]
198    }
199
200    test_field!(
201        super::EF,
202        &super::ZEROS,
203        &super::ONES,
204        &super::multiplicative_group_prime_factorization()
205    );
206
207    test_extension_field!(super::F, super::EF);
208
209    test_two_adic_extension_field!(super::F, super::EF);
210
211    type Pef = <EF as ExtensionField<F>>::ExtensionPacking;
212    const PACKED_ZEROS: [Pef; 1] = [Pef::ZERO];
213    const PACKED_ONES: [Pef; 1] = [Pef::ONE];
214    test_packed_extension_field!(super::Pef, &super::PACKED_ZEROS, &super::PACKED_ONES);
215}
216
217#[cfg(test)]
218mod test_quadratic_complex_extension {
219
220    use num_bigint::BigUint;
221    use p3_field::extension::{BinomialExtensionField, Complex};
222    use p3_field::{ExtensionField, PrimeCharacteristicRing};
223    use p3_field_testing::{
224        test_extension_field, test_field, test_packed_extension_field,
225        test_two_adic_extension_field,
226    };
227
228    use crate::Mersenne31;
229
230    type F = Complex<Mersenne31>;
231    type EF = BinomialExtensionField<F, 2>;
232
233    // There is a redundant representation of zero but we already tested it
234    // when testing the base field.
235    const ZEROS: [EF; 1] = [EF::ZERO];
236    const ONES: [EF; 1] = [EF::ONE];
237
238    // Get the prime factorization of the order of the multiplicative group.
239    // i.e. the prime factorization of P^4 - 1.
240    fn multiplicative_group_prime_factorization() -> [(BigUint, u32); 11] {
241        [
242            (BigUint::from(2u8), 33),
243            (BigUint::from(3u8), 2),
244            (BigUint::from(5u8), 1),
245            (BigUint::from(7u8), 1),
246            (BigUint::from(11u8), 1),
247            (BigUint::from(31u8), 1),
248            (BigUint::from(151u8), 1),
249            (BigUint::from(331u16), 1),
250            (BigUint::from(733u16), 1),
251            (BigUint::from(1709u16), 1),
252            (BigUint::from(368140581013u64), 1),
253        ]
254    }
255
256    test_field!(
257        super::EF,
258        &super::ZEROS,
259        &super::ONES,
260        &super::multiplicative_group_prime_factorization()
261    );
262
263    test_extension_field!(super::F, super::EF);
264
265    test_two_adic_extension_field!(super::F, super::EF);
266
267    type Pef = <EF as ExtensionField<F>>::ExtensionPacking;
268    const PACKED_ZEROS: [Pef; 1] = [Pef::ZERO];
269    const PACKED_ONES: [Pef; 1] = [Pef::ONE];
270    test_packed_extension_field!(super::Pef, &super::PACKED_ZEROS, &super::PACKED_ONES);
271}
p3_mersenne_31/extension.rs

p3_mersenne_31/
extension.rs
