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

p3_mersenne_31/
complex.rs
