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 Mersenne31 {
13    /// Precomputed table of generators for two-adic subgroups of the circle group
14    /// (the norm-1 subgroup of the degree two extension field over Mersenne31).
15    /// The `i`'th element is a generator of the subgroup of order `2^i`.
16    const CIRCLE_TWO_ADIC_GENERATORS: [Complex<Self>; 32] = [
17        Complex::new_complex(Self::new(1), Self::new(0)),
18        Complex::new_complex(Self::new(2_147_483_646), Self::new(0)),
19        Complex::new_complex(Self::new(0), Self::new(2_147_483_646)),
20        Complex::new_complex(Self::new(32_768), Self::new(2_147_450_879)),
21        Complex::new_complex(Self::new(590_768_354), Self::new(978_592_373)),
22        Complex::new_complex(Self::new(1_179_735_656), Self::new(1_241_207_368)),
23        Complex::new_complex(Self::new(1_567_857_810), Self::new(456_695_729)),
24        Complex::new_complex(Self::new(1_774_253_895), Self::new(1_309_288_441)),
25        Complex::new_complex(Self::new(736_262_640), Self::new(1_553_669_210)),
26        Complex::new_complex(Self::new(1_819_216_575), Self::new(1_662_816_114)),
27        Complex::new_complex(Self::new(1_323_191_254), Self::new(1_936_974_060)),
28        Complex::new_complex(Self::new(605_622_498), Self::new(1_964_232_216)),
29        Complex::new_complex(Self::new(343_674_985), Self::new(501_786_993)),
30        Complex::new_complex(Self::new(1_995_316_534), Self::new(149_306_621)),
31        Complex::new_complex(Self::new(2_107_600_913), Self::new(1_378_821_388)),
32        Complex::new_complex(Self::new(541_476_169), Self::new(2_101_081_972)),
33        Complex::new_complex(Self::new(2_135_874_973), Self::new(483_411_332)),
34        Complex::new_complex(Self::new(2_097_144_245), Self::new(1_684_033_590)),
35        Complex::new_complex(Self::new(1_662_322_247), Self::new(670_236_780)),
36        Complex::new_complex(Self::new(1_172_215_635), Self::new(595_888_646)),
37        Complex::new_complex(Self::new(241_940_101), Self::new(323_856_519)),
38        Complex::new_complex(Self::new(1_957_194_259), Self::new(2_139_647_100)),
39        Complex::new_complex(Self::new(1_957_419_629), Self::new(1_541_039_442)),
40        Complex::new_complex(Self::new(1_062_045_235), Self::new(1_824_580_421)),
41        Complex::new_complex(Self::new(1_929_382_196), Self::new(1_664_698_822)),
42        Complex::new_complex(Self::new(1_889_294_251), Self::new(331_248_939)),
43        Complex::new_complex(Self::new(1_214_231_414), Self::new(1_646_302_518)),
44        Complex::new_complex(Self::new(1_765_392_370), Self::new(461_136_547)),
45        Complex::new_complex(Self::new(1_629_751_483), Self::new(66_485_474)),
46        Complex::new_complex(Self::new(1_501_355_827), Self::new(1_439_063_420)),
47        Complex::new_complex(Self::new(509_778_402), Self::new(800_467_507)),
48        Complex::new_complex(Self::new(311_014_874), Self::new(1_584_694_829)),
49    ];
50}
51
52impl ComplexExtendable for Mersenne31 {
53    const CIRCLE_TWO_ADICITY: usize = 31;
54
55    // sage: p = 2^31 - 1
56    // sage: F = GF(p)
57    // sage: R.<x> = F[]
58    // sage: F2.<u> = F.extension(x^2 + 1)
59    // sage: F2.multiplicative_generator()
60    // u + 12
61    const COMPLEX_GENERATOR: Complex<Self> = Complex::new_complex(Self::new(12), Self::ONE);
62
63    fn circle_two_adic_generator(bits: usize) -> Complex<Self> {
64        // Generator of the whole 2^TWO_ADICITY group
65        // sage: p = 2^31 - 1
66        // sage: F = GF(p)
67        // sage: R.<x> = F[]
68        // sage: F2.<u> = F.extension(x^2 + 1)
69        // sage: g = F2.multiplicative_generator()^((p^2 - 1) / 2^31); g
70        // 1584694829*u + 311014874
71        // sage: assert(g.multiplicative_order() == 2^31)
72        // sage: assert(g.norm() == 1)
73        assert!(bits <= Self::CIRCLE_TWO_ADICITY);
74        Self::CIRCLE_TWO_ADIC_GENERATORS[bits]
75    }
76}
77
78impl HasTwoAdicBinomialExtension<2> for Mersenne31 {
79    const EXT_TWO_ADICITY: usize = 32;
80
81    fn ext_two_adic_generator(bits: usize) -> [Self; 2] {
82        assert!(bits <= Self::EXT_TWO_ADICITY);
83        Self::EXT_TWO_ADIC_GENERATORS[bits]
84    }
85}
86
87#[cfg(test)]
88mod tests {
89    use num_bigint::BigUint;
90    use p3_field::{ExtensionField, PrimeField32};
91    use p3_field_testing::{
92        test_extension_field, test_field, test_packed_extension_field, test_two_adic_field,
93    };
94
95    use super::*;
96
97    type Fi = Complex<Mersenne31>;
98    type F = Mersenne31;
99
100    #[test]
101    fn add() {
102        // real part
103        assert_eq!(Fi::ONE + Fi::ONE, Fi::TWO);
104        assert_eq!(Fi::NEG_ONE + Fi::ONE, Fi::ZERO);
105        assert_eq!(Fi::NEG_ONE + Fi::TWO, Fi::ONE);
106        assert_eq!((Fi::NEG_ONE + Fi::NEG_ONE).real(), F::new(F::ORDER_U32 - 2));
107
108        // complex part
109        assert_eq!(
110            Fi::new_imag(F::ONE) + Fi::new_imag(F::ONE),
111            Fi::new_imag(F::TWO)
112        );
113        assert_eq!(
114            Fi::new_imag(F::NEG_ONE) + Fi::new_imag(F::ONE),
115            Fi::new_imag(F::ZERO)
116        );
117        assert_eq!(
118            Fi::new_imag(F::NEG_ONE) + Fi::new_imag(F::TWO),
119            Fi::new_imag(F::ONE)
120        );
121        assert_eq!(
122            (Fi::new_imag(F::NEG_ONE) + Fi::new_imag(F::NEG_ONE)).imag(),
123            F::new(F::ORDER_U32 - 2)
124        );
125
126        // further tests
127        assert_eq!(
128            Fi::new_complex(F::ONE, F::TWO) + Fi::new_complex(F::ONE, F::ONE),
129            Fi::new_complex(F::TWO, F::new(3))
130        );
131        assert_eq!(
132            Fi::new_complex(F::NEG_ONE, F::NEG_ONE) + Fi::new_complex(F::ONE, F::ONE),
133            Fi::ZERO
134        );
135        assert_eq!(
136            Fi::new_complex(F::NEG_ONE, F::ONE) + Fi::new_complex(F::TWO, F::new(F::ORDER_U32 - 2)),
137            Fi::new_complex(F::ONE, F::NEG_ONE)
138        );
139    }
140
141    #[test]
142    fn sub() {
143        // real part
144        assert_eq!(Fi::ONE - Fi::ONE, Fi::ZERO);
145        assert_eq!(Fi::TWO - Fi::TWO, Fi::ZERO);
146        assert_eq!(Fi::NEG_ONE - Fi::NEG_ONE, Fi::ZERO);
147        assert_eq!(Fi::TWO - Fi::ONE, Fi::ONE);
148        assert_eq!(Fi::NEG_ONE - Fi::ZERO, Fi::NEG_ONE);
149
150        // complex part
151        assert_eq!(Fi::new_imag(F::ONE) - Fi::new_imag(F::ONE), Fi::ZERO);
152        assert_eq!(Fi::new_imag(F::TWO) - Fi::new_imag(F::TWO), Fi::ZERO);
153        assert_eq!(
154            Fi::new_imag(F::NEG_ONE) - Fi::new_imag(F::NEG_ONE),
155            Fi::ZERO
156        );
157        assert_eq!(
158            Fi::new_imag(F::TWO) - Fi::new_imag(F::ONE),
159            Fi::new_imag(F::ONE)
160        );
161        assert_eq!(
162            Fi::new_imag(F::NEG_ONE) - Fi::ZERO,
163            Fi::new_imag(F::NEG_ONE)
164        );
165    }
166
167    #[test]
168    fn mul() {
169        assert_eq!(
170            Fi::new_complex(F::TWO, F::TWO) * Fi::new_complex(F::new(4), F::new(5)),
171            Fi::new_complex(-F::TWO, F::new(18))
172        );
173    }
174
175    #[test]
176    fn mul_2exp_u64() {
177        // real part
178        // 1 * 2^0 = 1.
179        assert_eq!(Fi::ONE.mul_2exp_u64(0), Fi::ONE);
180        // 2 * 2^30 = 2^31 = 1.
181        assert_eq!(Fi::TWO.mul_2exp_u64(30), Fi::ONE);
182        // 5 * 2^2 = 20.
183        assert_eq!(
184            Fi::new_real(F::new(5)).mul_2exp_u64(2),
185            Fi::new_real(F::new(20))
186        );
187
188        // complex part
189        // i * 2^0 = i.
190        assert_eq!(Fi::new_imag(F::ONE).mul_2exp_u64(0), Fi::new_imag(F::ONE));
191        // (2i) * 2^30 = (2^31) * i = i.
192        assert_eq!(Fi::new_imag(F::TWO).mul_2exp_u64(30), Fi::new_imag(F::ONE));
193        // 5i * 2^2 = 20i.
194        assert_eq!(
195            Fi::new_imag(F::new(5)).mul_2exp_u64(2),
196            Fi::new_imag(F::new(20))
197        );
198    }
199
200    #[test]
201    fn circle_two_adic_generators_table_matches_repeated_squaring() {
202        let base = Fi::new_complex(F::new(311_014_874), F::new(1_584_694_829));
203        for bits in 0..=Mersenne31::CIRCLE_TWO_ADICITY {
204            assert_eq!(
205                Mersenne31::CIRCLE_TWO_ADIC_GENERATORS[bits],
206                base.exp_power_of_2(Mersenne31::CIRCLE_TWO_ADICITY - bits)
207            );
208        }
209    }
210
211    // There is a redundant representation of zero but we already tested it
212    // when testing the base field.
213    const ZEROS: [Fi; 1] = [Fi::ZERO];
214    const ONES: [Fi; 1] = [Fi::ONE];
215
216    // Get the prime factorization of the order of the multiplicative group.
217    // i.e. the prime factorization of P^2 - 1.
218    fn multiplicative_group_prime_factorization() -> [(BigUint, u32); 7] {
219        [
220            (BigUint::from(2u8), 32),
221            (BigUint::from(3u8), 2),
222            (BigUint::from(7u8), 1),
223            (BigUint::from(11u8), 1),
224            (BigUint::from(31u8), 1),
225            (BigUint::from(151u8), 1),
226            (BigUint::from(331u16), 1),
227        ]
228    }
229
230    test_field!(
231        super::Fi,
232        &super::ZEROS,
233        &super::ONES,
234        &super::multiplicative_group_prime_factorization()
235    );
236
237    test_extension_field!(super::F, super::Fi);
238    test_two_adic_field!(super::Fi);
239
240    type Pef = <Fi as ExtensionField<F>>::ExtensionPacking;
241    const PACKED_ZEROS: [Pef; 1] = [Pef::ZERO];
242    const PACKED_ONES: [Pef; 1] = [Pef::ONE];
243    test_packed_extension_field!(
244        super::F,
245        super::Fi,
246        super::Pef,
247        &super::PACKED_ZEROS,
248        &super::PACKED_ONES
249    );
250    p3_field_testing::test_packed_binomial_extension_division!(F, 2);
251}
p3_mersenne_31/complex.rs

p3_mersenne_31/
complex.rs
