p3_goldilocks/
extension.rs

1use p3_field::extension::{
2    BinomiallyExtendable, BinomiallyExtendableAlgebra, HasTwoAdicBinomialExtension,
3};
4use p3_field::{PrimeCharacteristicRing, TwoAdicField, field_to_array};
5
6use crate::Goldilocks;
7
8impl BinomiallyExtendableAlgebra<Self, 2> for Goldilocks {}
9
10impl BinomiallyExtendable<2> for Goldilocks {
11    // Verifiable in Sage with
12    // `R.<x> = GF(p)[]; assert (x^2 - 7).is_irreducible()`.
13    const W: Self = Self::new(7);
14
15    // DTH_ROOT = W^((p - 1)/2).
16    const DTH_ROOT: Self = Self::new(18446744069414584320);
17
18    const EXT_GENERATOR: [Self; 2] = [
19        Self::new(18081566051660590251),
20        Self::new(16121475356294670766),
21    ];
22}
23
24impl HasTwoAdicBinomialExtension<2> for Goldilocks {
25    const EXT_TWO_ADICITY: usize = 33;
26
27    fn ext_two_adic_generator(bits: usize) -> [Self; 2] {
28        assert!(bits <= 33);
29
30        if bits == 33 {
31            [Self::ZERO, Self::new(15659105665374529263)]
32        } else {
33            [Self::two_adic_generator(bits), Self::ZERO]
34        }
35    }
36}
37
38impl BinomiallyExtendableAlgebra<Self, 5> for Goldilocks {}
39
40impl BinomiallyExtendable<5> for Goldilocks {
41    // Verifiable via:
42    //  ```sage
43    //  # Define Fp
44    //  p = 2**64 - 2**32 + 1
45    //  F = GF(p)
46
47    //  # Define Fp[z]
48    //  R.<z> = PolynomialRing(F)
49
50    //  # The polynomial x^5-3 is irreducible
51    //  assert(R(z^5-3).is_irreducible())
52    //  ```
53    const W: Self = Self::new(3);
54
55    // 5-th root = w^((p - 1)/5)
56    const DTH_ROOT: Self = Self::new(1041288259238279555);
57
58    // Generator of the extension field
59    // Obtained by finding the smallest Hamming weight vector
60    // with appropriate order, starting at [0,1,0,0,0]
61    const EXT_GENERATOR: [Self; 5] = [Self::TWO, Self::ONE, Self::ZERO, Self::ZERO, Self::ZERO];
62}
63
64impl HasTwoAdicBinomialExtension<5> for Goldilocks {
65    const EXT_TWO_ADICITY: usize = 32;
66
67    fn ext_two_adic_generator(bits: usize) -> [Self; 5] {
68        assert!(bits <= 32);
69
70        field_to_array(Self::two_adic_generator(bits))
71    }
72}
73
74#[cfg(test)]
75mod test_quadratic_extension {
76
77    use num_bigint::BigUint;
78    use p3_field::extension::BinomialExtensionField;
79    use p3_field::{ExtensionField, PrimeCharacteristicRing};
80    use p3_field_testing::{
81        test_extension_field, test_field, test_packed_extension_field,
82        test_two_adic_extension_field,
83    };
84
85    use crate::Goldilocks;
86
87    type F = Goldilocks;
88    type EF = BinomialExtensionField<F, 2>;
89
90    // There is a redundant representation of zero but we already tested it
91    // when testing the base field.
92    const ZEROS: [EF; 1] = [EF::ZERO];
93    const ONES: [EF; 1] = [EF::ONE];
94
95    // Get the prime factorization of the order of the multiplicative group.
96    // i.e. the prime factorization of P^2 - 1.
97    fn multiplicative_group_prime_factorization() -> [(BigUint, u32); 9] {
98        [
99            (BigUint::from(2u8), 33),
100            (BigUint::from(3u8), 1),
101            (BigUint::from(5u8), 1),
102            (BigUint::from(7u8), 1),
103            (BigUint::from(17u8), 1),
104            (BigUint::from(179u8), 1),
105            (BigUint::from(257u16), 1),
106            (BigUint::from(65537u32), 1),
107            (BigUint::from(7361031152998637u64), 1),
108        ]
109    }
110
111    test_field!(
112        super::EF,
113        &super::ZEROS,
114        &super::ONES,
115        &super::multiplicative_group_prime_factorization()
116    );
117
118    test_extension_field!(super::F, super::EF);
119    test_two_adic_extension_field!(super::F, super::EF);
120
121    type Pef = <EF as ExtensionField<F>>::ExtensionPacking;
122    const PACKED_ZEROS: [Pef; 1] = [Pef::ZERO];
123    const PACKED_ONES: [Pef; 1] = [Pef::ONE];
124    test_packed_extension_field!(
125        super::F,
126        super::EF,
127        super::Pef,
128        &super::PACKED_ZEROS,
129        &super::PACKED_ONES
130    );
131}
132
133#[cfg(test)]
134mod test_quintic_extension {
135
136    use num_bigint::BigUint;
137    use p3_field::extension::BinomialExtensionField;
138    use p3_field::{ExtensionField, PrimeCharacteristicRing};
139    use p3_field_testing::{
140        test_extension_field, test_field, test_packed_extension_field,
141        test_two_adic_extension_field,
142    };
143
144    use crate::Goldilocks;
145
146    type F = Goldilocks;
147    type EF = BinomialExtensionField<F, 5>;
148
149    // There is a redundant representation of zero but we already tested it
150    // when testing the base field.
151    const ZEROS: [EF; 1] = [EF::ZERO];
152    const ONES: [EF; 1] = [EF::ONE];
153
154    // Get the prime factorization of the order of the multiplicative group.
155    // i.e. the prime factorization of P^5 - 1.
156    fn multiplicative_group_prime_factorization() -> [(num_bigint::BigUint, u32); 10] {
157        [
158            (BigUint::from(2u8), 32),
159            (BigUint::from(3u8), 1),
160            (BigUint::from(5u8), 2),
161            (BigUint::from(17u8), 1),
162            (BigUint::from(257u16), 1),
163            (BigUint::from(45971u16), 1),
164            (BigUint::from(65537u32), 1),
165            (BigUint::from(255006435240067831u64), 1),
166            (BigUint::from(280083648770327405561u128), 1),
167            (BigUint::from(7053197395277272939628824863222181u128), 1),
168        ]
169    }
170
171    test_field!(
172        super::EF,
173        &super::ZEROS,
174        &super::ONES,
175        &super::multiplicative_group_prime_factorization()
176    );
177
178    test_extension_field!(super::F, super::EF);
179    test_two_adic_extension_field!(super::F, super::EF);
180
181    type Pef = <EF as ExtensionField<F>>::ExtensionPacking;
182    const PACKED_ZEROS: [Pef; 1] = [Pef::ZERO];
183    const PACKED_ONES: [Pef; 1] = [Pef::ONE];
184    test_packed_extension_field!(
185        super::F,
186        super::EF,
187        super::Pef,
188        &super::PACKED_ZEROS,
189        &super::PACKED_ONES
190    );
191}
p3_goldilocks/extension.rs

p3_goldilocks/
extension.rs
