p3_baby_bear/
baby_bear.rs

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

p3_baby_bear/
baby_bear.rs
