p3_koala_bear/
koala_bear.rs

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

p3_koala_bear/
koala_bear.rs
