p3_baby_bear/
baby_bear.rs

Help
1use p3_field::{exp_1725656503, exp_u64_by_squaring, Field, FieldAlgebra};
2use p3_monty_31::{
3    BarrettParameters, BinomialExtensionData, FieldParameters, MontyField31, MontyParameters,
4    PackedMontyParameters, TwoAdicData,
5};
6
7/// The prime field `2^31 - 2^27 + 1`, a.k.a. the Baby Bear field.
8pub type BabyBear = MontyField31<BabyBearParameters>;
9
10#[derive(Copy, Clone, Default, Debug, Eq, Hash, PartialEq)]
11pub struct BabyBearParameters;
12
13impl MontyParameters for BabyBearParameters {
14    /// The Baby Bear prime: 2^31 - 2^27 + 1.
15    /// This is the unique 31-bit prime with the highest possible 2 adicity (27).
16    const PRIME: u32 = 0x78000001;
17
18    const MONTY_BITS: u32 = 32;
19    const MONTY_MU: u32 = 0x88000001;
20}
21
22impl PackedMontyParameters for BabyBearParameters {}
23
24impl BarrettParameters for BabyBearParameters {}
25
26impl FieldParameters for BabyBearParameters {
27    const MONTY_GEN: BabyBear = BabyBear::new(31);
28
29    fn exp_u64_generic<FA: FieldAlgebra>(val: FA, power: u64) -> FA {
30        match power {
31            1725656503 => exp_1725656503(val), // used to compute x^{1/7}
32            _ => exp_u64_by_squaring(val, power),
33        }
34    }
35
36    fn try_inverse<F: Field>(p1: F) -> Option<F> {
37        if p1.is_zero() {
38            return None;
39        }
40
41        // From Fermat's little theorem, in a prime field `F_p`, the inverse of `a` is `a^(p-2)`.
42        // Here p-2 = 2013265919 = 1110111111111111111111111111111_2.
43        // Uses 30 Squares + 7 Multiplications => 37 Operations total.
44
45        let p100000000 = p1.exp_power_of_2(8);
46        let p100000001 = p100000000 * p1;
47        let p10000000000000000 = p100000000.exp_power_of_2(8);
48        let p10000000100000001 = p10000000000000000 * p100000001;
49        let p10000000100000001000 = p10000000100000001.exp_power_of_2(3);
50        let p1000000010000000100000000 = p10000000100000001000.exp_power_of_2(5);
51        let p1000000010000000100000001 = p1000000010000000100000000 * p1;
52        let p1000010010000100100001001 = p1000000010000000100000001 * p10000000100000001000;
53        let p10000000100000001000000010 = p1000000010000000100000001.square();
54        let p11000010110000101100001011 = p10000000100000001000000010 * p1000010010000100100001001;
55        let p100000001000000010000000100 = p10000000100000001000000010.square();
56        let p111000011110000111100001111 =
57            p100000001000000010000000100 * p11000010110000101100001011;
58        let p1110000111100001111000011110000 = p111000011110000111100001111.exp_power_of_2(4);
59        let p1110111111111111111111111111111 =
60            p1110000111100001111000011110000 * p111000011110000111100001111;
61
62        Some(p1110111111111111111111111111111)
63    }
64}
65
66impl TwoAdicData for BabyBearParameters {
67    const TWO_ADICITY: usize = 27;
68
69    type ArrayLike = &'static [BabyBear];
70
71    const TWO_ADIC_GENERATORS: Self::ArrayLike = &BabyBear::new_array([
72        0x1, 0x78000000, 0x67055c21, 0x5ee99486, 0xbb4c4e4, 0x2d4cc4da, 0x669d6090, 0x17b56c64,
73        0x67456167, 0x688442f9, 0x145e952d, 0x4fe61226, 0x4c734715, 0x11c33e2a, 0x62c3d2b1,
74        0x77cad399, 0x54c131f4, 0x4cabd6a6, 0x5cf5713f, 0x3e9430e8, 0xba067a3, 0x18adc27d,
75        0x21fd55bc, 0x4b859b3d, 0x3bd57996, 0x4483d85a, 0x3a26eef8, 0x1a427a41,
76    ]);
77
78    const ROOTS_8: Self::ArrayLike = &BabyBear::new_array([0x1, 0x5ee99486, 0x67055c21, 0xc9ea3ba]);
79    const INV_ROOTS_8: Self::ArrayLike =
80        &BabyBear::new_array([0x1, 0x6b615c47, 0x10faa3e0, 0x19166b7b]);
81
82    const ROOTS_16: Self::ArrayLike = &BabyBear::new_array([
83        0x1, 0xbb4c4e4, 0x5ee99486, 0x4b49e08, 0x67055c21, 0x5376917a, 0xc9ea3ba, 0x563112a7,
84    ]);
85    const INV_ROOTS_16: Self::ArrayLike = &BabyBear::new_array([
86        0x1, 0x21ceed5a, 0x6b615c47, 0x24896e87, 0x10faa3e0, 0x734b61f9, 0x19166b7b, 0x6c4b3b1d,
87    ]);
88}
89
90impl BinomialExtensionData<4> for BabyBearParameters {
91    const W: BabyBear = BabyBear::new(11);
92    const DTH_ROOT: BabyBear = BabyBear::new(1728404513);
93    const EXT_GENERATOR: [BabyBear; 4] = BabyBear::new_array([8, 1, 0, 0]);
94    const EXT_TWO_ADICITY: usize = 29;
95
96    type ArrayLike = [[BabyBear; 4]; 2];
97    const TWO_ADIC_EXTENSION_GENERATORS: Self::ArrayLike =
98        BabyBear::new_2d_array([[0, 0, 1996171314, 0], [0, 0, 0, 124907976]]);
99}
100
101impl BinomialExtensionData<5> for BabyBearParameters {
102    const W: BabyBear = BabyBear::new(2);
103    const DTH_ROOT: BabyBear = BabyBear::new(815036133);
104    const EXT_GENERATOR: [BabyBear; 5] = BabyBear::new_array([8, 1, 0, 0, 0]);
105    const EXT_TWO_ADICITY: usize = 27;
106
107    type ArrayLike = [[BabyBear; 5]; 0];
108    const TWO_ADIC_EXTENSION_GENERATORS: Self::ArrayLike = [];
109}
110
111#[cfg(test)]
112mod tests {
113    use core::array;
114
115    use p3_field::{PrimeField32, PrimeField64, TwoAdicField};
116    use p3_field_testing::{test_field, test_field_dft, test_two_adic_field};
117
118    use super::*;
119
120    type F = BabyBear;
121
122    #[test]
123    fn test_baby_bear_two_adicity_generators() {
124        let base = BabyBear::from_canonical_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_canonical_u32)
139        )
140    }
141
142    #[test]
143    fn test_baby_bear() {
144        let f = F::from_canonical_u32(100);
145        assert_eq!(f.as_canonical_u64(), 100);
146
147        let f = F::from_canonical_u32(0);
148        assert!(f.is_zero());
149
150        let f = F::from_wrapped_u32(F::ORDER_U32);
151        assert!(f.is_zero());
152
153        let f_1 = F::ONE;
154        let f_1_copy = F::from_canonical_u32(1);
155
156        let expected_result = F::ZERO;
157        assert_eq!(f_1 - f_1_copy, expected_result);
158
159        let expected_result = F::TWO;
160        assert_eq!(f_1 + f_1_copy, expected_result);
161
162        let f_2 = F::from_canonical_u32(2);
163        let expected_result = F::from_canonical_u32(3);
164        assert_eq!(f_1 + f_1_copy * f_2, expected_result);
165
166        let expected_result = F::from_canonical_u32(5);
167        assert_eq!(f_1 + f_2 * f_2, expected_result);
168
169        let f_p_minus_1 = F::from_canonical_u32(F::ORDER_U32 - 1);
170        let expected_result = F::ZERO;
171        assert_eq!(f_1 + f_p_minus_1, expected_result);
172
173        let f_p_minus_2 = F::from_canonical_u32(F::ORDER_U32 - 2);
174        let expected_result = F::from_canonical_u32(F::ORDER_U32 - 3);
175        assert_eq!(f_p_minus_1 + f_p_minus_2, expected_result);
176
177        let expected_result = F::from_canonical_u32(1);
178        assert_eq!(f_p_minus_1 - f_p_minus_2, expected_result);
179
180        let expected_result = f_p_minus_1;
181        assert_eq!(f_p_minus_2 - f_p_minus_1, expected_result);
182
183        let expected_result = f_p_minus_2;
184        assert_eq!(f_p_minus_1 - f_1, expected_result);
185
186        let m1 = F::from_canonical_u32(0x34167c58);
187        let m2 = F::from_canonical_u32(0x61f3207b);
188        let expected_prod = F::from_canonical_u32(0x1b5c8046);
189        assert_eq!(m1 * m2, expected_prod);
190
191        assert_eq!(m1.exp_u64(1725656503).exp_const_u64::<7>(), m1);
192        assert_eq!(m2.exp_u64(1725656503).exp_const_u64::<7>(), m2);
193        assert_eq!(f_2.exp_u64(1725656503).exp_const_u64::<7>(), f_2);
194
195        let f_serialized = serde_json::to_string(&f).unwrap();
196        let f_deserialized: F = serde_json::from_str(&f_serialized).unwrap();
197        assert_eq!(f, f_deserialized);
198
199        let f_1_serialized = serde_json::to_string(&f_1).unwrap();
200        let f_1_deserialized: F = serde_json::from_str(&f_1_serialized).unwrap();
201        let f_1_serialized_again = serde_json::to_string(&f_1_deserialized).unwrap();
202        let f_1_deserialized_again: F = serde_json::from_str(&f_1_serialized_again).unwrap();
203        assert_eq!(f_1, f_1_deserialized);
204        assert_eq!(f_1, f_1_deserialized_again);
205
206        let f_2_serialized = serde_json::to_string(&f_2).unwrap();
207        let f_2_deserialized: F = serde_json::from_str(&f_2_serialized).unwrap();
208        assert_eq!(f_2, f_2_deserialized);
209
210        let f_p_minus_1_serialized = serde_json::to_string(&f_p_minus_1).unwrap();
211        let f_p_minus_1_deserialized: F = serde_json::from_str(&f_p_minus_1_serialized).unwrap();
212        assert_eq!(f_p_minus_1, f_p_minus_1_deserialized);
213
214        let f_p_minus_2_serialized = serde_json::to_string(&f_p_minus_2).unwrap();
215        let f_p_minus_2_deserialized: F = serde_json::from_str(&f_p_minus_2_serialized).unwrap();
216        assert_eq!(f_p_minus_2, f_p_minus_2_deserialized);
217
218        let m1_serialized = serde_json::to_string(&m1).unwrap();
219        let m1_deserialized: F = serde_json::from_str(&m1_serialized).unwrap();
220        assert_eq!(m1, m1_deserialized);
221
222        let m2_serialized = serde_json::to_string(&m2).unwrap();
223        let m2_deserialized: F = serde_json::from_str(&m2_serialized).unwrap();
224        assert_eq!(m2, m2_deserialized);
225    }
226
227    test_field!(crate::BabyBear);
228    test_two_adic_field!(crate::BabyBear);
229
230    test_field_dft!(radix2dit, crate::BabyBear, p3_dft::Radix2Dit<_>);
231    test_field_dft!(bowers, crate::BabyBear, p3_dft::Radix2Bowers);
232    test_field_dft!(parallel, crate::BabyBear, p3_dft::Radix2DitParallel::<_>);
233    test_field_dft!(
234        recur_dft,
235        crate::BabyBear,
236        p3_monty_31::dft::RecursiveDft<_>
237    );
238}
p3_baby_bear/baby_bear.rs

p3_baby_bear/
baby_bear.rs
