p3_koala_bear/
koala_bear.rs

1use p3_field::exponentiation::exp_1420470955;
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^24 + 1`, a.k.a. the Koala Bear field.
9pub type KoalaBear = MontyField31<KoalaBearParameters>;
10
11#[derive(Copy, Clone, Default, Debug, Eq, Hash, PartialEq)]
12pub struct KoalaBearParameters;
13
14impl MontyParameters for KoalaBearParameters {
15    /// The KoalaBear prime: 2^31 - 2^24 + 1
16    /// This is a 31-bit prime with the highest possible two adicity if we additionally demand that
17    /// the cube map (x -> x^3) is an automorphism of the multiplicative group.
18    /// It's not unique, as there is one other option with equal 2 adicity: 2^30 + 2^27 + 2^24 + 1.
19    /// There is also one 29-bit prime with higher two adicity which might be appropriate for some applications: 2^29 - 2^26 + 1.
20    const PRIME: u32 = 0x7f000001;
21
22    const MONTY_BITS: u32 = 32;
23    const MONTY_MU: u32 = 0x81000001;
24}
25
26impl PackedMontyParameters for KoalaBearParameters {}
27
28impl BarrettParameters for KoalaBearParameters {}
29
30impl FieldParameters for KoalaBearParameters {
31    const MONTY_GEN: KoalaBear = KoalaBear::new(3);
32}
33
34impl RelativelyPrimePower<3> for KoalaBearParameters {
35    /// In the field `KoalaBear`, `a^{1/3}` is equal to a^{1420470955}.
36    ///
37    /// This follows from the calculation `3 * 1420470955 = 2*(2^31 - 2^24) + 1 = 1 mod (p - 1)`.
38    fn exp_root_d<R: PrimeCharacteristicRing>(val: R) -> R {
39        exp_1420470955(val)
40    }
41}
42
43impl TwoAdicData for KoalaBearParameters {
44    const TWO_ADICITY: usize = 24;
45
46    type ArrayLike = &'static [KoalaBear];
47
48    const TWO_ADIC_GENERATORS: Self::ArrayLike = &KoalaBear::new_array([
49        0x1, 0x7f000000, 0x7e010002, 0x6832fe4a, 0x8dbd69c, 0xa28f031, 0x5c4a5b99, 0x29b75a80,
50        0x17668b8a, 0x27ad539b, 0x334d48c7, 0x7744959c, 0x768fc6fa, 0x303964b2, 0x3e687d4d,
51        0x45a60e61, 0x6e2f4d7a, 0x163bd499, 0x6c4a8a45, 0x143ef899, 0x514ddcad, 0x484ef19b,
52        0x205d63c3, 0x68e7dd49, 0x6ac49f88,
53    ]);
54
55    const ROOTS_8: Self::ArrayLike =
56        &KoalaBear::new_array([0x1, 0x6832fe4a, 0x7e010002, 0x174e3650]);
57    const INV_ROOTS_8: Self::ArrayLike =
58        &KoalaBear::new_array([0x1, 0x67b1c9b1, 0xfeffff, 0x16cd01b7]);
59
60    const ROOTS_16: Self::ArrayLike = &KoalaBear::new_array([
61        0x1, 0x8dbd69c, 0x6832fe4a, 0x27ae21e2, 0x7e010002, 0x3a89a025, 0x174e3650, 0x27dfce22,
62    ]);
63    const INV_ROOTS_16: Self::ArrayLike = &KoalaBear::new_array([
64        0x1, 0x572031df, 0x67b1c9b1, 0x44765fdc, 0xfeffff, 0x5751de1f, 0x16cd01b7, 0x76242965,
65    ]);
66}
67
68impl BinomialExtensionData<4> for KoalaBearParameters {
69    const W: KoalaBear = KoalaBear::new(3);
70
71    #[inline(always)]
72    fn mul_w<A: Algebra<MontyField31<Self>>>(a: A) -> A {
73        a.double() + a
74    }
75
76    const DTH_ROOT: KoalaBear = KoalaBear::new(2113994754);
77    const EXT_GENERATOR: [KoalaBear; 4] = KoalaBear::new_array([2, 1, 0, 0]);
78    const EXT_TWO_ADICITY: usize = 26;
79
80    type ArrayLike = [[KoalaBear; 4]; 2];
81
82    const TWO_ADIC_EXTENSION_GENERATORS: Self::ArrayLike =
83        KoalaBear::new_2d_array([[0, 0, 1759267465, 0], [0, 0, 0, 777715144]]);
84}
85
86impl BinomialExtensionData<8> for KoalaBearParameters {
87    const W: KoalaBear = KoalaBear::new(3);
88    const DTH_ROOT: KoalaBear = KoalaBear::new(1748172362);
89    const EXT_GENERATOR: [KoalaBear; 8] = KoalaBear::new_array([10, 1, 0, 0, 0, 0, 0, 0]);
90    const EXT_TWO_ADICITY: usize = 27;
91
92    type ArrayLike = [[KoalaBear; 8]; 3];
93
94    const TWO_ADIC_EXTENSION_GENERATORS: Self::ArrayLike = KoalaBear::new_2d_array([
95        [0, 0, 0, 0, 1759267465, 0, 0, 0],
96        [0, 0, 0, 0, 0, 0, 777715144, 0],
97        [0, 0, 0, 0, 0, 0, 0, 14348907],
98    ]);
99
100    #[inline(always)]
101    fn mul_w<A: Algebra<MontyField31<Self>>>(a: A) -> A {
102        a.double() + a
103    }
104}
105
106#[cfg(test)]
107mod tests {
108    use num_bigint::BigUint;
109    use p3_field::extension::BinomialExtensionField;
110    use p3_field::{InjectiveMonomial, PermutationMonomial, PrimeField64, TwoAdicField};
111    use p3_field_testing::{
112        test_field, test_field_dft, test_prime_field, test_prime_field_32, test_prime_field_64,
113        test_two_adic_field,
114    };
115
116    use super::*;
117
118    type F = KoalaBear;
119    type EF = BinomialExtensionField<F, 4>;
120
121    #[test]
122    fn test_koala_bear_two_adicity_generators() {
123        let base = KoalaBear::from_u32(0x6ac49f88);
124        for bits in 0..=KoalaBear::TWO_ADICITY {
125            assert_eq!(
126                KoalaBear::two_adic_generator(bits),
127                base.exp_power_of_2(KoalaBear::TWO_ADICITY - bits)
128            );
129        }
130    }
131
132    #[test]
133    fn test_koala_bear() {
134        let f = F::from_u32(100);
135        assert_eq!(f.as_canonical_u64(), 100);
136
137        let f_1 = F::ONE;
138        let f_2 = F::TWO;
139        let f_p_minus_1 = F::NEG_ONE;
140        let f_p_minus_2 = F::NEG_ONE + F::NEG_ONE;
141        let m1 = F::from_u32(0x34167c58);
142        let m2 = F::from_u32(0x61f3207b);
143        let expected_prod = F::from_u32(0x54b46b81);
144        assert_eq!(m1 * m2, expected_prod);
145
146        assert_eq!(m1.injective_exp_n().injective_exp_root_n(), m1);
147        assert_eq!(m2.injective_exp_n().injective_exp_root_n(), m2);
148        assert_eq!(f_2.injective_exp_n().injective_exp_root_n(), f_2);
149
150        let f_serialized = serde_json::to_string(&f).unwrap();
151        let f_deserialized: F = serde_json::from_str(&f_serialized).unwrap();
152        assert_eq!(f, f_deserialized);
153
154        let f_1_serialized = serde_json::to_string(&f_1).unwrap();
155        let f_1_deserialized: F = serde_json::from_str(&f_1_serialized).unwrap();
156        let f_1_serialized_again = serde_json::to_string(&f_1_deserialized).unwrap();
157        let f_1_deserialized_again: F = serde_json::from_str(&f_1_serialized_again).unwrap();
158        assert_eq!(f_1, f_1_deserialized);
159        assert_eq!(f_1, f_1_deserialized_again);
160
161        let f_2_serialized = serde_json::to_string(&f_2).unwrap();
162        let f_2_deserialized: F = serde_json::from_str(&f_2_serialized).unwrap();
163        assert_eq!(f_2, f_2_deserialized);
164
165        let f_p_minus_1_serialized = serde_json::to_string(&f_p_minus_1).unwrap();
166        let f_p_minus_1_deserialized: F = serde_json::from_str(&f_p_minus_1_serialized).unwrap();
167        assert_eq!(f_p_minus_1, f_p_minus_1_deserialized);
168
169        let f_p_minus_2_serialized = serde_json::to_string(&f_p_minus_2).unwrap();
170        let f_p_minus_2_deserialized: F = serde_json::from_str(&f_p_minus_2_serialized).unwrap();
171        assert_eq!(f_p_minus_2, f_p_minus_2_deserialized);
172
173        let m1_serialized = serde_json::to_string(&m1).unwrap();
174        let m1_deserialized: F = serde_json::from_str(&m1_serialized).unwrap();
175        assert_eq!(m1, m1_deserialized);
176
177        let m2_serialized = serde_json::to_string(&m2).unwrap();
178        let m2_deserialized: F = serde_json::from_str(&m2_serialized).unwrap();
179        assert_eq!(m2, m2_deserialized);
180    }
181
182    // MontyField31's have no redundant representations.
183    const ZEROS: [KoalaBear; 1] = [KoalaBear::ZERO];
184    const ONES: [KoalaBear; 1] = [KoalaBear::ONE];
185
186    // Get the prime factorization of the order of the multiplicative group.
187    // i.e. the prime factorization of P - 1.
188    fn multiplicative_group_prime_factorization() -> [(BigUint, u32); 2] {
189        [(BigUint::from(2u8), 24), (BigUint::from(127u8), 1)]
190    }
191
192    test_field!(
193        crate::KoalaBear,
194        &super::ZEROS,
195        &super::ONES,
196        &super::multiplicative_group_prime_factorization()
197    );
198    test_two_adic_field!(crate::KoalaBear);
199
200    test_field_dft!(radix2dit, crate::KoalaBear, super::EF, p3_dft::Radix2Dit<_>);
201    test_field_dft!(bowers, crate::KoalaBear, super::EF, p3_dft::Radix2Bowers);
202    test_field_dft!(
203        parallel,
204        crate::KoalaBear,
205        super::EF,
206        p3_dft::Radix2DitParallel::<crate::KoalaBear>
207    );
208    test_field_dft!(
209        recur_dft,
210        crate::KoalaBear,
211        super::EF,
212        p3_monty_31::dft::RecursiveDft<_>
213    );
214    test_prime_field!(crate::KoalaBear);
215    test_prime_field_64!(crate::KoalaBear, &super::ZEROS, &super::ONES);
216    test_prime_field_32!(crate::KoalaBear, &super::ZEROS, &super::ONES);
217}
p3_koala_bear/koala_bear.rs

p3_koala_bear/
koala_bear.rs
