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, 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
129#[cfg(test)]
130mod tests {
131    use num_bigint::BigUint;
132    use p3_field::extension::BinomialExtensionField;
133    use p3_field::{InjectiveMonomial, PermutationMonomial, PrimeField64, TwoAdicField};
134    use p3_field_testing::{
135        test_field, test_field_dft, test_field_json_serialization, test_prime_field,
136        test_prime_field_32, test_prime_field_64, test_two_adic_field,
137    };
138
139    use super::*;
140
141    type F = KoalaBear;
142    type EF = BinomialExtensionField<F, 4>;
143
144    #[test]
145    fn test_koala_bear_two_adicity_generators() {
146        let base = KoalaBear::from_u32(0x6ac49f88);
147        for bits in 0..=KoalaBear::TWO_ADICITY {
148            assert_eq!(
149                KoalaBear::two_adic_generator(bits),
150                base.exp_power_of_2(KoalaBear::TWO_ADICITY - bits)
151            );
152        }
153    }
154
155    #[test]
156    fn test_koala_bear() {
157        let f = F::from_u32(100);
158        assert_eq!(f.as_canonical_u64(), 100);
159
160        let f_1 = F::ONE;
161        let f_2 = F::TWO;
162        let f_p_minus_1 = F::NEG_ONE;
163        let f_p_minus_2 = F::NEG_ONE + F::NEG_ONE;
164        let m1 = F::from_u32(0x34167c58);
165        let m2 = F::from_u32(0x61f3207b);
166        let expected_prod = F::from_u32(0x54b46b81);
167        assert_eq!(m1 * m2, expected_prod);
168
169        assert_eq!(m1.injective_exp_n().injective_exp_root_n(), m1);
170        assert_eq!(m2.injective_exp_n().injective_exp_root_n(), m2);
171        assert_eq!(f_2.injective_exp_n().injective_exp_root_n(), f_2);
172
173        test_field_json_serialization(&[f, f_1, f_2, f_p_minus_1, f_p_minus_2, m1, m2]);
174    }
175
176    // MontyField31's have no redundant representations.
177    const ZEROS: [KoalaBear; 1] = [KoalaBear::ZERO];
178    const ONES: [KoalaBear; 1] = [KoalaBear::ONE];
179
180    // Get the prime factorization of the order of the multiplicative group.
181    // i.e. the prime factorization of P - 1.
182    fn multiplicative_group_prime_factorization() -> [(BigUint, u32); 2] {
183        [(BigUint::from(2u8), 24), (BigUint::from(127u8), 1)]
184    }
185
186    test_field!(
187        crate::KoalaBear,
188        &super::ZEROS,
189        &super::ONES,
190        &super::multiplicative_group_prime_factorization()
191    );
192    test_two_adic_field!(crate::KoalaBear);
193
194    test_field_dft!(radix2dit, crate::KoalaBear, super::EF, p3_dft::Radix2Dit<_>);
195    test_field_dft!(bowers, crate::KoalaBear, super::EF, p3_dft::Radix2Bowers);
196    test_field_dft!(
197        parallel,
198        crate::KoalaBear,
199        super::EF,
200        p3_dft::Radix2DitParallel::<crate::KoalaBear>
201    );
202    test_field_dft!(
203        recur_dft,
204        crate::KoalaBear,
205        super::EF,
206        p3_monty_31::dft::RecursiveDft<_>
207    );
208    test_prime_field!(crate::KoalaBear);
209    test_prime_field_64!(crate::KoalaBear, &super::ZEROS, &super::ONES);
210    test_prime_field_32!(crate::KoalaBear, &super::ZEROS, &super::ONES);
211}
p3_koala_bear/koala_bear.rs

p3_koala_bear/
koala_bear.rs
