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!(super::Pef, &super::PACKED_ZEROS, &super::PACKED_ONES);
125}
126
127#[cfg(test)]
128mod test_quintic_extension {
129
130    use num_bigint::BigUint;
131    use p3_field::extension::BinomialExtensionField;
132    use p3_field::{ExtensionField, PrimeCharacteristicRing};
133    use p3_field_testing::{
134        test_extension_field, test_field, test_packed_extension_field,
135        test_two_adic_extension_field,
136    };
137
138    use crate::Goldilocks;
139
140    type F = Goldilocks;
141    type EF = BinomialExtensionField<F, 5>;
142
143    // There is a redundant representation of zero but we already tested it
144    // when testing the base field.
145    const ZEROS: [EF; 1] = [EF::ZERO];
146    const ONES: [EF; 1] = [EF::ONE];
147
148    // Get the prime factorization of the order of the multiplicative group.
149    // i.e. the prime factorization of P^5 - 1.
150    fn multiplicative_group_prime_factorization() -> [(num_bigint::BigUint, u32); 10] {
151        [
152            (BigUint::from(2u8), 32),
153            (BigUint::from(3u8), 1),
154            (BigUint::from(5u8), 2),
155            (BigUint::from(17u8), 1),
156            (BigUint::from(257u16), 1),
157            (BigUint::from(45971u16), 1),
158            (BigUint::from(65537u32), 1),
159            (BigUint::from(255006435240067831u64), 1),
160            (BigUint::from(280083648770327405561u128), 1),
161            (BigUint::from(7053197395277272939628824863222181u128), 1),
162        ]
163    }
164
165    test_field!(
166        super::EF,
167        &super::ZEROS,
168        &super::ONES,
169        &super::multiplicative_group_prime_factorization()
170    );
171
172    test_extension_field!(super::F, super::EF);
173    test_two_adic_extension_field!(super::F, super::EF);
174
175    type Pef = <EF as ExtensionField<F>>::ExtensionPacking;
176    const PACKED_ZEROS: [Pef; 1] = [Pef::ZERO];
177    const PACKED_ONES: [Pef; 1] = [Pef::ONE];
178    test_packed_extension_field!(super::Pef, &super::PACKED_ZEROS, &super::PACKED_ONES);
179}
p3_goldilocks/extension.rs

p3_goldilocks/
extension.rs
