p3_baby_bear/
baby_bear.rs

1use p3_field::exponentiation::exp_1725656503;
2use p3_field::{Algebra, PrimeCharacteristicRing};
3use p3_monty_31::{
4    BarrettParameters, BinomialExtensionData, FieldParameters, MontyField31, MontyParameters,
5    PackedMontyParameters, RelativelyPrimePower, TwoAdicData,
6};
7
8/// The prime field `2^31 - 2^27 + 1`, a.k.a. the Baby Bear field.
9pub type BabyBear = MontyField31<BabyBearParameters>;
10
11#[derive(Copy, Clone, Default, Debug, Eq, Hash, PartialEq)]
12pub struct BabyBearParameters;
13
14impl MontyParameters for BabyBearParameters {
15    /// The Baby Bear prime: 2^31 - 2^27 + 1.
16    /// This is the unique 31-bit prime with the highest possible 2 adicity (27).
17    const PRIME: u32 = 0x78000001;
18
19    const MONTY_BITS: u32 = 32;
20    const MONTY_MU: u32 = 0x88000001;
21}
22
23impl PackedMontyParameters for BabyBearParameters {}
24
25impl BarrettParameters for BabyBearParameters {}
26
27impl FieldParameters for BabyBearParameters {
28    const MONTY_GEN: BabyBear = BabyBear::new(31);
29}
30
31impl RelativelyPrimePower<7> for BabyBearParameters {
32    /// In the field `BabyBear`, `a^{1/7}` is equal to a^{1725656503}.
33    ///
34    /// This follows from the calculation `7 * 1725656503 = 6*(2^31 - 2^27) + 1 = 1 mod (p - 1)`.
35    fn exp_root_d<R: PrimeCharacteristicRing>(val: R) -> R {
36        exp_1725656503(val)
37    }
38}
39
40impl TwoAdicData for BabyBearParameters {
41    const TWO_ADICITY: usize = 27;
42
43    type ArrayLike = &'static [BabyBear];
44
45    const TWO_ADIC_GENERATORS: Self::ArrayLike = &BabyBear::new_array([
46        0x1, 0x78000000, 0x67055c21, 0x5ee99486, 0xbb4c4e4, 0x2d4cc4da, 0x669d6090, 0x17b56c64,
47        0x67456167, 0x688442f9, 0x145e952d, 0x4fe61226, 0x4c734715, 0x11c33e2a, 0x62c3d2b1,
48        0x77cad399, 0x54c131f4, 0x4cabd6a6, 0x5cf5713f, 0x3e9430e8, 0xba067a3, 0x18adc27d,
49        0x21fd55bc, 0x4b859b3d, 0x3bd57996, 0x4483d85a, 0x3a26eef8, 0x1a427a41,
50    ]);
51
52    const ROOTS_8: Self::ArrayLike = &BabyBear::new_array([0x1, 0x5ee99486, 0x67055c21, 0xc9ea3ba]);
53    const INV_ROOTS_8: Self::ArrayLike =
54        &BabyBear::new_array([0x1, 0x6b615c47, 0x10faa3e0, 0x19166b7b]);
55
56    const ROOTS_16: Self::ArrayLike = &BabyBear::new_array([
57        0x1, 0xbb4c4e4, 0x5ee99486, 0x4b49e08, 0x67055c21, 0x5376917a, 0xc9ea3ba, 0x563112a7,
58    ]);
59    const INV_ROOTS_16: Self::ArrayLike = &BabyBear::new_array([
60        0x1, 0x21ceed5a, 0x6b615c47, 0x24896e87, 0x10faa3e0, 0x734b61f9, 0x19166b7b, 0x6c4b3b1d,
61    ]);
62}
63
64impl BinomialExtensionData<4> for BabyBearParameters {
65    const W: BabyBear = BabyBear::new(11);
66    const DTH_ROOT: BabyBear = BabyBear::new(1728404513);
67    const EXT_GENERATOR: [BabyBear; 4] = BabyBear::new_array([8, 1, 0, 0]);
68    const EXT_TWO_ADICITY: usize = 29;
69
70    type ArrayLike = [[BabyBear; 4]; 2];
71    const TWO_ADIC_EXTENSION_GENERATORS: Self::ArrayLike =
72        BabyBear::new_2d_array([[0, 0, 1996171314, 0], [0, 0, 0, 124907976]]);
73}
74
75impl BinomialExtensionData<5> for BabyBearParameters {
76    const W: BabyBear = BabyBear::new(2);
77
78    #[inline(always)]
79    fn mul_w<A: Algebra<MontyField31<Self>>>(a: A) -> A {
80        a.double()
81    }
82
83    const DTH_ROOT: BabyBear = BabyBear::new(815036133);
84    const EXT_GENERATOR: [BabyBear; 5] = BabyBear::new_array([8, 1, 0, 0, 0]);
85    const EXT_TWO_ADICITY: usize = 27;
86
87    type ArrayLike = [[BabyBear; 5]; 0];
88    const TWO_ADIC_EXTENSION_GENERATORS: Self::ArrayLike = [];
89}
90
91impl BinomialExtensionData<8> for BabyBearParameters {
92    const W: BabyBear = BabyBear::new(11);
93    const DTH_ROOT: BabyBear = BabyBear::new(420899707);
94    const EXT_GENERATOR: [BabyBear; 8] = BabyBear::new_array([5, 1, 0, 0, 0, 0, 0, 0]);
95    const EXT_TWO_ADICITY: usize = 30;
96
97    type ArrayLike = [[BabyBear; 8]; 3];
98    const TWO_ADIC_EXTENSION_GENERATORS: Self::ArrayLike = BabyBear::new_2d_array([
99        [0, 0, 0, 0, 1996171314, 0, 0, 0],
100        [0, 0, 0, 0, 0, 0, 124907976, 0],
101        [0, 0, 0, 518392818, 0, 0, 0, 0],
102    ]);
103}
104
105#[cfg(test)]
106mod tests {
107    use core::array;
108
109    use num_bigint::BigUint;
110    use p3_field::extension::BinomialExtensionField;
111    use p3_field::{InjectiveMonomial, PermutationMonomial, PrimeField64, TwoAdicField};
112    use p3_field_testing::{
113        test_field, test_field_dft, test_field_dft_consistency, test_field_dft_large,
114        test_prime_field, test_prime_field_32, test_prime_field_64, test_two_adic_field,
115    };
116
117    use super::*;
118
119    type F = BabyBear;
120    type EF = BinomialExtensionField<F, 4>;
121
122    #[test]
123    fn test_baby_bear_two_adicity_generators() {
124        let base = BabyBear::from_u32(0x1a427a41);
125        for bits in 0..=BabyBear::TWO_ADICITY {
126            assert_eq!(
127                BabyBear::two_adic_generator(bits),
128                base.exp_power_of_2(BabyBear::TWO_ADICITY - bits)
129            );
130        }
131    }
132
133    #[test]
134    fn test_to_babybear_array() {
135        let range_array: [u32; 32] = array::from_fn(|i| i as u32);
136        assert_eq!(
137            BabyBear::new_array(range_array),
138            range_array.map(F::from_u32)
139        );
140    }
141
142    #[test]
143    fn test_baby_bear() {
144        let f = F::from_u32(100);
145        assert_eq!(f.as_canonical_u64(), 100);
146
147        let f_1 = F::ONE;
148        let f_2 = F::TWO;
149        let f_p_minus_1 = F::NEG_ONE;
150        let f_p_minus_2 = F::NEG_ONE + F::NEG_ONE;
151        let m1 = F::from_u32(0x34167c58);
152        let m2 = F::from_u32(0x61f3207b);
153        let expected_prod = F::from_u32(0x1b5c8046);
154        assert_eq!(m1 * m2, expected_prod);
155
156        assert_eq!(m1.injective_exp_n().injective_exp_root_n(), m1);
157        assert_eq!(m2.injective_exp_n().injective_exp_root_n(), m2);
158        assert_eq!(F::TWO.injective_exp_n().injective_exp_root_n(), F::TWO);
159
160        let f_serialized = serde_json::to_string(&f).unwrap();
161        let f_deserialized: F = serde_json::from_str(&f_serialized).unwrap();
162        assert_eq!(f, f_deserialized);
163
164        let f_1_serialized = serde_json::to_string(&f_1).unwrap();
165        let f_1_deserialized: F = serde_json::from_str(&f_1_serialized).unwrap();
166        let f_1_serialized_again = serde_json::to_string(&f_1_deserialized).unwrap();
167        let f_1_deserialized_again: F = serde_json::from_str(&f_1_serialized_again).unwrap();
168        assert_eq!(f_1, f_1_deserialized);
169        assert_eq!(f_1, f_1_deserialized_again);
170
171        let f_2_serialized = serde_json::to_string(&f_2).unwrap();
172        let f_2_deserialized: F = serde_json::from_str(&f_2_serialized).unwrap();
173        assert_eq!(f_2, f_2_deserialized);
174
175        let f_p_minus_1_serialized = serde_json::to_string(&f_p_minus_1).unwrap();
176        let f_p_minus_1_deserialized: F = serde_json::from_str(&f_p_minus_1_serialized).unwrap();
177        assert_eq!(f_p_minus_1, f_p_minus_1_deserialized);
178
179        let f_p_minus_2_serialized = serde_json::to_string(&f_p_minus_2).unwrap();
180        let f_p_minus_2_deserialized: F = serde_json::from_str(&f_p_minus_2_serialized).unwrap();
181        assert_eq!(f_p_minus_2, f_p_minus_2_deserialized);
182
183        let m1_serialized = serde_json::to_string(&m1).unwrap();
184        let m1_deserialized: F = serde_json::from_str(&m1_serialized).unwrap();
185        assert_eq!(m1, m1_deserialized);
186
187        let m2_serialized = serde_json::to_string(&m2).unwrap();
188        let m2_deserialized: F = serde_json::from_str(&m2_serialized).unwrap();
189        assert_eq!(m2, m2_deserialized);
190    }
191
192    // MontyField31's have no redundant representations.
193    const ZEROS: [BabyBear; 1] = [BabyBear::ZERO];
194    const ONES: [BabyBear; 1] = [BabyBear::ONE];
195
196    // Get the prime factorization of the order of the multiplicative group.
197    // i.e. the prime factorization of P - 1.
198    fn multiplicative_group_prime_factorization() -> [(BigUint, u32); 3] {
199        [
200            (BigUint::from(2u8), 27),
201            (BigUint::from(3u8), 1),
202            (BigUint::from(5u8), 1),
203        ]
204    }
205
206    test_field!(
207        crate::BabyBear,
208        &super::ZEROS,
209        &super::ONES,
210        &super::multiplicative_group_prime_factorization()
211    );
212    test_two_adic_field!(crate::BabyBear);
213
214    test_field_dft!(radix2dit, crate::BabyBear, super::EF, p3_dft::Radix2Dit<_>);
215    test_field_dft!(
216        radix2smallbatch,
217        crate::BabyBear,
218        super::EF,
219        p3_dft::Radix2DFTSmallBatch<_>
220    );
221    test_field_dft!(bowers, crate::BabyBear, super::EF, p3_dft::Radix2Bowers);
222    test_field_dft!(
223        parallel,
224        crate::BabyBear,
225        super::EF,
226        p3_dft::Radix2DitParallel::<_>
227    );
228    test_field_dft!(
229        recur_dft,
230        crate::BabyBear,
231        super::EF,
232        p3_monty_31::dft::RecursiveDft<_>
233    );
234    test_field_dft_consistency!(
235        radix2_smallbatch_and_ditparallel,
236        crate::BabyBear,
237        super::EF,
238        p3_dft::Radix2DFTSmallBatch<_>,
239        p3_dft::Radix2DitParallel<_>
240    );
241    test_field_dft_large!(
242        radix2smallbatch_large,
243        crate::BabyBear,
244        super::EF,
245        p3_dft::Radix2DFTSmallBatch<_>
246    );
247
248    test_field_dft_large!(
249        parallel_large,
250        crate::BabyBear,
251        super::EF,
252        p3_dft::Radix2DitParallel<_>
253    );
254
255    test_field_dft_large!(
256        recur_dft_large,
257        crate::BabyBear,
258        super::EF,
259        p3_monty_31::dft::RecursiveDft<_>
260    );
261    test_prime_field!(crate::BabyBear);
262    test_prime_field_64!(crate::BabyBear, &super::ZEROS, &super::ONES);
263    test_prime_field_32!(crate::BabyBear, &super::ZEROS, &super::ONES);
264}
p3_baby_bear/baby_bear.rs

p3_baby_bear/
baby_bear.rs
