p3_monty_31/
monty_31.rs

1//! An abstraction of 31-bit fields which use a MONTY approach for faster multiplication.
2
3use alloc::vec;
4use alloc::vec::Vec;
5use core::fmt::{self, Debug, Display, Formatter};
6use core::hash::Hash;
7use core::iter::{Product, Sum};
8use core::marker::PhantomData;
9use core::ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Neg, Sub, SubAssign};
10use core::{array, iter};
11
12use num_bigint::BigUint;
13use p3_field::integers::QuotientMap;
14use p3_field::op_assign_macros::{
15    impl_add_assign, impl_div_methods, impl_mul_methods, impl_sub_assign,
16};
17use p3_field::{
18    Field, InjectiveMonomial, Packable, PermutationMonomial, PrimeCharacteristicRing, PrimeField,
19    PrimeField32, PrimeField64, RawDataSerializable, TwoAdicField,
20    impl_raw_serializable_primefield32, quotient_map_small_int,
21};
22use p3_util::{flatten_to_base, gcd_inversion_prime_field_32};
23use rand::Rng;
24use rand::distr::{Distribution, StandardUniform};
25use serde::{Deserialize, Deserializer, Serialize};
26
27use crate::utils::{
28    add, from_monty, halve_u32, large_monty_reduce, monty_reduce, monty_reduce_u128, sub, to_monty,
29    to_monty_64, to_monty_64_signed, to_monty_signed,
30};
31use crate::{FieldParameters, MontyParameters, RelativelyPrimePower, TwoAdicData};
32
33#[derive(Clone, Copy, Default, Eq, Hash, PartialEq)]
34#[repr(transparent)] // Important for reasoning about memory layout.
35#[must_use]
36pub struct MontyField31<MP: MontyParameters> {
37    /// The MONTY form of the field element, saved as a positive integer less than `P`.
38    ///
39    /// This is `pub(crate)` for tests and delayed reduction strategies. If you're accessing `value` outside of those, you're
40    /// likely doing something fishy.
41    pub(crate) value: u32,
42    _phantom: PhantomData<MP>,
43}
44
45impl<MP: MontyParameters> MontyField31<MP> {
46    /// Create a new field element from any `u32`.
47    ///
48    /// Any `u32` value is accepted and automatically converted to Montgomery form.
49    #[inline(always)]
50    pub const fn new(value: u32) -> Self {
51        Self {
52            value: to_monty::<MP>(value),
53            _phantom: PhantomData,
54        }
55    }
56
57    /// Create a new field element from something already in MONTY form.
58    /// This is `pub(crate)` for tests and delayed reduction strategies. If you're using it outside of those, you're
59    /// likely doing something fishy.
60    #[inline(always)]
61    pub(crate) const fn new_monty(value: u32) -> Self {
62        Self {
63            value,
64            _phantom: PhantomData,
65        }
66    }
67
68    /// Produce a u32 in range [0, P) from a field element corresponding to the true value.
69    #[inline(always)]
70    pub(crate) const fn to_u32(elem: &Self) -> u32 {
71        from_monty::<MP>(elem.value)
72    }
73
74    /// Convert a `[u32; N]` array to an array of field elements.
75    ///
76    /// Const version of `input.map(MontyField31::new)`.
77    #[inline]
78    pub const fn new_array<const N: usize>(input: [u32; N]) -> [Self; N] {
79        let mut output = [Self::new_monty(0); N];
80        let mut i = 0;
81        while i < N {
82            output[i] = Self::new(input[i]);
83            i += 1;
84        }
85        output
86    }
87
88    /// Convert a constant 2d u32 array into a constant 2d array of field elements.
89    /// Constant version of array.map(MontyField31::new_array).
90    #[inline]
91    pub const fn new_2d_array<const N: usize, const M: usize>(
92        input: [[u32; N]; M],
93    ) -> [[Self; N]; M] {
94        let mut output = [[Self::new_monty(0); N]; M];
95        let mut i = 0;
96        while i < M {
97            output[i] = Self::new_array(input[i]);
98            i += 1;
99        }
100        output
101    }
102}
103
104impl<FP: FieldParameters> MontyField31<FP> {
105    const MONTY_POWERS_OF_TWO: [Self; 64] = {
106        let mut powers_of_two = [FP::MONTY_ONE; 64];
107        let mut i = 1;
108        while i < 64 {
109            powers_of_two[i] = Self::new_monty(to_monty_64::<FP>(1 << i));
110            i += 1;
111        }
112        powers_of_two
113    };
114
115    const HALF: Self = Self::new(FP::HALF_P_PLUS_1);
116}
117
118impl<FP: MontyParameters> Ord for MontyField31<FP> {
119    #[inline]
120    fn cmp(&self, other: &Self) -> core::cmp::Ordering {
121        Self::to_u32(self).cmp(&Self::to_u32(other))
122    }
123}
124
125impl<FP: MontyParameters> PartialOrd for MontyField31<FP> {
126    #[inline]
127    fn partial_cmp(&self, other: &Self) -> Option<core::cmp::Ordering> {
128        Some(self.cmp(other))
129    }
130}
131
132impl<FP: MontyParameters> Display for MontyField31<FP> {
133    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
134        Display::fmt(&Self::to_u32(self), f)
135    }
136}
137
138impl<FP: MontyParameters> Debug for MontyField31<FP> {
139    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
140        Debug::fmt(&Self::to_u32(self), f)
141    }
142}
143
144impl<FP: MontyParameters> Distribution<MontyField31<FP>> for StandardUniform {
145    #[inline]
146    fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> MontyField31<FP> {
147        loop {
148            let next_u31 = rng.next_u32() >> 1;
149            let is_canonical = next_u31 < FP::PRIME;
150            if is_canonical {
151                return MontyField31::new_monty(next_u31);
152            }
153        }
154    }
155}
156
157impl<FP: FieldParameters> Serialize for MontyField31<FP> {
158    fn serialize<S: serde::Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
159        // It's faster to Serialize and Deserialize in monty form.
160        serializer.serialize_u32(self.value)
161    }
162}
163
164impl<'de, FP: FieldParameters> Deserialize<'de> for MontyField31<FP> {
165    fn deserialize<D: Deserializer<'de>>(d: D) -> Result<Self, D::Error> {
166        // It's faster to Serialize and Deserialize in monty form.
167        let val = u32::deserialize(d)?;
168        Ok(Self::new_monty(val))
169    }
170}
171
172impl<MP: MontyParameters> Packable for MontyField31<MP> {}
173
174impl<FP: FieldParameters> PrimeCharacteristicRing for MontyField31<FP> {
175    type PrimeSubfield = Self;
176
177    const ZERO: Self = FP::MONTY_ZERO;
178    const ONE: Self = FP::MONTY_ONE;
179    const TWO: Self = FP::MONTY_TWO;
180    const NEG_ONE: Self = FP::MONTY_NEG_ONE;
181
182    #[inline(always)]
183    fn from_prime_subfield(f: Self) -> Self {
184        f
185    }
186
187    #[inline]
188    fn halve(&self) -> Self {
189        Self::new_monty(halve_u32::<FP>(self.value))
190    }
191
192    #[inline]
193    fn mul_2exp_u64(&self, exp: u64) -> Self {
194        // The array FP::MONTY_POWERS_OF_TWO contains the powers of 2
195        // from 2^0 to 2^63 in monty form. We can use this to quickly
196        // compute 2^exp.
197        if exp < 64 {
198            *self * Self::MONTY_POWERS_OF_TWO[exp as usize]
199        } else {
200            // For larger values we use the default method.
201            *self * Self::TWO.exp_u64(exp)
202        }
203    }
204
205    #[inline]
206    fn div_2exp_u64(&self, exp: u64) -> Self {
207        if exp <= 32 {
208            // As the monty form of 2^{-exp} is 2^{32 - exp} mod P, for
209            // 0 <= exp <= 32, we can multiply by 2^{-exp} by doing a shift
210            // followed by a monty reduction.
211            let long_prod = (self.value as u64) << (32 - exp);
212            Self::new_monty(monty_reduce::<FP>(long_prod))
213        } else {
214            // For larger values we use a slower method though this is
215            // still much faster than the default method as it avoids the inverse().
216            *self * Self::HALF.exp_u64(exp)
217        }
218    }
219
220    #[inline]
221    fn zero_vec(len: usize) -> Vec<Self> {
222        // SAFETY:
223        // Due to `#[repr(transparent)]`, MontyField31 and u32 have the same size, alignment
224        // and memory layout making `flatten_to_base` safe. This this will create
225        // a vector MontyField31 elements with value set to 0 which is the
226        // MONTY form of 0.
227        unsafe { flatten_to_base(vec![0u32; len]) }
228    }
229
230    #[inline]
231    fn sum_array<const N: usize>(input: &[Self]) -> Self {
232        assert_eq!(N, input.len());
233        // Benchmarking shows that for N <= 7 it's faster to sum the elements directly
234        // but for N > 7 it's faster to use the .sum() methods which passes through u64's
235        // allowing for delayed reductions.
236        match N {
237            0 => Self::ZERO,
238            1 => input[0],
239            2 => input[0] + input[1],
240            3 => input[0] + input[1] + input[2],
241            4 => (input[0] + input[1]) + (input[2] + input[3]),
242            5 => Self::sum_array::<4>(&input[..4]) + Self::sum_array::<1>(&input[4..]),
243            6 => Self::sum_array::<4>(&input[..4]) + Self::sum_array::<2>(&input[4..]),
244            7 => Self::sum_array::<4>(&input[..4]) + Self::sum_array::<3>(&input[4..]),
245            _ => input.iter().copied().sum(),
246        }
247    }
248
249    #[inline]
250    fn dot_product<const N: usize>(lhs: &[Self; N], rhs: &[Self; N]) -> Self {
251        const {
252            assert!(N as u64 <= (1 << 34));
253
254            // This code relies on assumptions about the relative size of the
255            // prime and the monty parameter. If these are changes this needs to be checked.
256            debug_assert!(FP::MONTY_BITS == 32);
257            debug_assert!((FP::PRIME as u64) < (1 << 31));
258        }
259        match N {
260            0 => Self::ZERO,
261            1 => lhs[0] * rhs[0],
262            2 => {
263                // As all values are < P < 2^31, the products are < P^2 < 2^31P.
264                // Hence, summing two together we stay below MONTY*P which means
265                // monty_reduce will produce a valid result.
266                let u64_prod_sum = (lhs[0].value as u64) * (rhs[0].value as u64)
267                    + (lhs[1].value as u64) * (rhs[1].value as u64);
268                Self::new_monty(monty_reduce::<FP>(u64_prod_sum))
269            }
270            3 => {
271                // As all values are < P < 2^31, the products are < P^2 < 2^31P.
272                // Hence, summing three together will be less than 2 * MONTY * P
273                let u64_prod_sum = (lhs[0].value as u64) * (rhs[0].value as u64)
274                    + (lhs[1].value as u64) * (rhs[1].value as u64)
275                    + (lhs[2].value as u64) * (rhs[2].value as u64);
276                Self::new_monty(large_monty_reduce::<FP>(u64_prod_sum))
277            }
278            4 => {
279                // As all values are < P < 2^31, the products are < P^2 < 2^31P.
280                // Hence, summing four together will be less than 2 * MONTY * P.
281                let u64_prod_sum = (lhs[0].value as u64) * (rhs[0].value as u64)
282                    + (lhs[1].value as u64) * (rhs[1].value as u64)
283                    + (lhs[2].value as u64) * (rhs[2].value as u64)
284                    + (lhs[3].value as u64) * (rhs[3].value as u64);
285                Self::new_monty(large_monty_reduce::<FP>(u64_prod_sum))
286            }
287            5 => {
288                let head_sum = (lhs[0].value as u64) * (rhs[0].value as u64)
289                    + (lhs[1].value as u64) * (rhs[1].value as u64)
290                    + (lhs[2].value as u64) * (rhs[2].value as u64)
291                    + (lhs[3].value as u64) * (rhs[3].value as u64);
292                let tail_sum = (lhs[4].value as u64) * (rhs[4].value as u64);
293                // head_sum < 4*P^2, tail_sum < P^2.
294                let head_sum_corr = head_sum.wrapping_sub((FP::PRIME as u64) << FP::MONTY_BITS);
295                // head_sum.min(head_sum_corr) is guaranteed to be < 2*P^2.
296                // Hence sum < 4P^2 < 2 * MONTY * P
297                let sum = head_sum.min(head_sum_corr) + tail_sum;
298                Self::new_monty(large_monty_reduce::<FP>(sum))
299            }
300            6 => {
301                let head_sum = (lhs[0].value as u64) * (rhs[0].value as u64)
302                    + (lhs[1].value as u64) * (rhs[1].value as u64)
303                    + (lhs[2].value as u64) * (rhs[2].value as u64)
304                    + (lhs[3].value as u64) * (rhs[3].value as u64);
305                let tail_sum = (lhs[4].value as u64) * (rhs[4].value as u64)
306                    + (lhs[5].value as u64) * (rhs[5].value as u64);
307                // head_sum < 4*P^2, tail_sum < 2*P^2.
308                let head_sum_corr = head_sum.wrapping_sub((FP::PRIME as u64) << FP::MONTY_BITS);
309                // head_sum.min(head_sum_corr) is guaranteed to be < 2*P^2.
310                // Hence sum < 4P^2 < 2 * MONTY * P
311                let sum = head_sum.min(head_sum_corr) + tail_sum;
312                Self::new_monty(large_monty_reduce::<FP>(sum))
313            }
314            7 => {
315                let head_sum = (lhs[0].value as u64) * (rhs[0].value as u64)
316                    + (lhs[1].value as u64) * (rhs[1].value as u64)
317                    + (lhs[2].value as u64) * (rhs[2].value as u64)
318                    + (lhs[3].value as u64) * (rhs[3].value as u64);
319                let tail_sum = (lhs[4].value as u64) * (rhs[4].value as u64)
320                    + lhs[5].value as u64 * (rhs[5].value as u64)
321                    + lhs[6].value as u64 * (rhs[6].value as u64);
322                // head_sum, tail_sum are guaranteed to be < 4*P^2.
323                let head_sum_corr = head_sum.wrapping_sub((FP::PRIME as u64) << FP::MONTY_BITS);
324                let tail_sum_corr = tail_sum.wrapping_sub((FP::PRIME as u64) << FP::MONTY_BITS);
325                // head_sum.min(head_sum_corr), tail_sum.min(tail_sum_corr) is guaranteed to be < 2*P^2.
326                // Hence sum < 4P^2 < 2 * MONTY * P
327                let sum = head_sum.min(head_sum_corr) + tail_sum.min(tail_sum_corr);
328                Self::new_monty(large_monty_reduce::<FP>(sum))
329            }
330            8 => {
331                let head_sum = (lhs[0].value as u64) * (rhs[0].value as u64)
332                    + (lhs[1].value as u64) * (rhs[1].value as u64)
333                    + (lhs[2].value as u64) * (rhs[2].value as u64)
334                    + (lhs[3].value as u64) * (rhs[3].value as u64);
335                let tail_sum = (lhs[4].value as u64) * (rhs[4].value as u64)
336                    + lhs[5].value as u64 * (rhs[5].value as u64)
337                    + lhs[6].value as u64 * (rhs[6].value as u64)
338                    + lhs[7].value as u64 * (rhs[7].value as u64);
339                // head_sum, tail_sum are guaranteed to be < 4*P^2.
340                let head_sum_corr = head_sum.wrapping_sub((FP::PRIME as u64) << FP::MONTY_BITS);
341                let tail_sum_corr = tail_sum.wrapping_sub((FP::PRIME as u64) << FP::MONTY_BITS);
342                // head_sum.min(head_sum_corr), tail_sum.min(tail_sum_corr) is guaranteed to be < 2*P^2.
343                // Hence sum < 4P^2 < 2 * MONTY * P
344                let sum = head_sum.min(head_sum_corr) + tail_sum.min(tail_sum_corr);
345                Self::new_monty(large_monty_reduce::<FP>(sum))
346            }
347            _ => {
348                // For large enough N, we accumulate into a u128. This helps the compiler as it lets
349                // it do a lot of computation in parallel as it knows that summing u128's is associative.
350                let acc_u128 = lhs
351                    .chunks(4)
352                    .zip(rhs.chunks(4))
353                    .map(|(l, r)| {
354                        // As all values are < P < 2^31, the products are < P^2 < 2^31P.
355                        // Hence, summing four together will not overflow a u64 but will be
356                        // larger than 2^32P.
357                        let u64_prod_sum = l
358                            .iter()
359                            .zip(r)
360                            .map(|(l, r)| (l.value as u64) * (r.value as u64))
361                            .sum::<u64>();
362                        u64_prod_sum as u128
363                    })
364                    .sum();
365                // As N <= 2^34 by the earlier assertion, acc_u128 <= 2^34 * P^2 < 2^34 * 2^62 < 2^96.
366                Self::new_monty(monty_reduce_u128::<FP>(acc_u128))
367            }
368        }
369    }
370}
371
372impl<FP: FieldParameters + RelativelyPrimePower<D>, const D: u64> InjectiveMonomial<D>
373    for MontyField31<FP>
374{
375}
376
377impl<FP: FieldParameters + RelativelyPrimePower<D>, const D: u64> PermutationMonomial<D>
378    for MontyField31<FP>
379{
380    fn injective_exp_root_n(&self) -> Self {
381        FP::exp_root_d(*self)
382    }
383}
384
385impl<FP: FieldParameters> RawDataSerializable for MontyField31<FP> {
386    impl_raw_serializable_primefield32!();
387}
388
389impl<FP: FieldParameters> Field for MontyField31<FP> {
390    #[cfg(all(target_arch = "aarch64", target_feature = "neon"))]
391    type Packing = crate::PackedMontyField31Neon<FP>;
392    #[cfg(all(
393        target_arch = "x86_64",
394        target_feature = "avx2",
395        not(target_feature = "avx512f")
396    ))]
397    type Packing = crate::PackedMontyField31AVX2<FP>;
398    #[cfg(all(target_arch = "x86_64", target_feature = "avx512f"))]
399    type Packing = crate::PackedMontyField31AVX512<FP>;
400    #[cfg(not(any(
401        all(target_arch = "aarch64", target_feature = "neon"),
402        all(
403            target_arch = "x86_64",
404            target_feature = "avx2",
405            not(target_feature = "avx512f")
406        ),
407        all(target_arch = "x86_64", target_feature = "avx512f"),
408    )))]
409    type Packing = Self;
410
411    const GENERATOR: Self = FP::MONTY_GEN;
412
413    fn try_inverse(&self) -> Option<Self> {
414        if self.is_zero() {
415            return None;
416        }
417
418        // The number of bits of FP::PRIME. By the very name of MontyField31 this should always be 31.
419        const NUM_PRIME_BITS: u32 = 31;
420
421        // Get the inverse using a gcd algorithm.
422        // We use `val` to denote the input to `gcd_inversion_prime_field_32` and `R = 2^{MONTY_BITS}`
423        // our monty constant.
424        // The function gcd_inversion_31_bit_field maps `val mod P -> 2^{60}val mod P`
425        let gcd_inverse = gcd_inversion_prime_field_32::<NUM_PRIME_BITS>(self.value, FP::PRIME);
426
427        // Currently |gcd_inverse| <= 2^{NUM_PRIME_BITS - 2} <= 2^{60}
428        // As P > 2^{30}, 0 < 2^{30}P + gcd_inverse < 2^61
429        let pos_inverse = (((FP::PRIME as i64) << 30) + gcd_inverse) as u64;
430
431        // We could do a % operation here, but monty reduction is faster.
432        // This does remove a factor of `R` from the result so we will need to
433        // correct for that.
434        let uncorrected_value = Self::new_monty(monty_reduce::<FP>(pos_inverse));
435
436        // Currently, uncorrected_value = R^{-1} * 2^{60} * val^{-1} mod P = 2^{28} * val^{-1} mod P`.
437        // But `val` is really the monty form of some value `x` satisfying `val = xR mod P`. We want
438        // `x^{-1}R mod P = R^2 x^{-1}R^{-1} mod P = 2^{64} val^{-1} mod P`.
439        // Hence we need to multiply by 2^{64 - 28} = 2^{36}.
440
441        // Unrolling the definitions a little, this 36 comes from: 3 * FP::MONTY_BITS - (2 * NUM_PRIME_BITS - 2)
442
443        Some(uncorrected_value.mul_2exp_u64((3 * FP::MONTY_BITS - (2 * NUM_PRIME_BITS - 2)) as u64))
444    }
445
446    #[inline]
447    fn order() -> BigUint {
448        FP::PRIME.into()
449    }
450}
451
452quotient_map_small_int!(MontyField31, u32, FieldParameters, [u8, u16]);
453quotient_map_small_int!(MontyField31, i32, FieldParameters, [i8, i16]);
454
455impl<FP: FieldParameters> QuotientMap<u32> for MontyField31<FP> {
456    /// Convert a given `u32` integer into an element of the `MontyField31` field.
457    #[inline]
458    fn from_int(int: u32) -> Self {
459        Self::new(int)
460    }
461
462    /// Convert a given `u32` integer into an element of the `MontyField31` field.
463    ///
464    /// Returns `None` if the given integer is greater than the Prime.
465    #[inline]
466    fn from_canonical_checked(int: u32) -> Option<Self> {
467        (int < FP::PRIME).then(|| Self::new(int))
468    }
469
470    /// Convert a given `u32` integer into an element of the `MontyField31` field.
471    ///
472    /// # Safety
473    /// This is always safe as the conversion to monty form can accept any `u32`.
474    #[inline(always)]
475    unsafe fn from_canonical_unchecked(int: u32) -> Self {
476        Self::new(int)
477    }
478}
479
480impl<FP: FieldParameters> QuotientMap<i32> for MontyField31<FP> {
481    /// Convert a given `i32` integer into an element of the `MontyField31` field.
482    #[inline]
483    fn from_int(int: i32) -> Self {
484        Self::new_monty(to_monty_signed::<FP>(int))
485    }
486
487    /// Convert a given `i32` integer into an element of the `MontyField31` field.
488    ///
489    /// Returns `None` if the given integer does not lie in the range `[(1 - P)/2, (P - 1)/2]`.
490    #[inline]
491    fn from_canonical_checked(int: i32) -> Option<Self> {
492        let bound = (FP::PRIME >> 1) as i32;
493        if int <= bound {
494            (int >= (-bound)).then(|| Self::new_monty(to_monty_signed::<FP>(int)))
495        } else {
496            None
497        }
498    }
499
500    /// Convert a given `i32` integer into an element of the `MontyField31` field.
501    ///
502    /// # Safety
503    /// This is always safe as the conversion to monty form can accept any `i32`.
504    #[inline(always)]
505    unsafe fn from_canonical_unchecked(int: i32) -> Self {
506        Self::new_monty(to_monty_signed::<FP>(int))
507    }
508}
509
510impl<FP: FieldParameters> QuotientMap<u64> for MontyField31<FP> {
511    /// Convert a given `u64` integer into an element of the `MontyField31` field.
512    fn from_int(int: u64) -> Self {
513        Self::new_monty(to_monty_64::<FP>(int))
514    }
515
516    /// Convert a given `u64` integer into an element of the `MontyField31` field.
517    ///
518    /// Returns `None` if the given integer is greater than the Prime.
519    fn from_canonical_checked(int: u64) -> Option<Self> {
520        (int < FP::PRIME as u64).then(|| Self::new(int as u32))
521    }
522
523    /// Convert a given `u64` integer into an element of the `MontyField31` field.
524    ///
525    /// # Safety
526    /// This is always safe as the conversion to monty form can accept any `u64`.
527    unsafe fn from_canonical_unchecked(int: u64) -> Self {
528        Self::new_monty(to_monty_64::<FP>(int))
529    }
530}
531
532impl<FP: FieldParameters> QuotientMap<i64> for MontyField31<FP> {
533    /// Convert a given `i64` integer into an element of the `MontyField31` field.
534    fn from_int(int: i64) -> Self {
535        Self::new_monty(to_monty_64_signed::<FP>(int))
536    }
537
538    /// Convert a given `i64` integer into an element of the `MontyField31` field.
539    ///
540    /// Returns `None` if the given integer does not lie in the range `[(1 - P)/2, (P - 1)/2]`.
541    fn from_canonical_checked(int: i64) -> Option<Self> {
542        let bound = (FP::PRIME >> 1) as i64;
543        if int <= bound {
544            (int >= (-bound)).then(|| Self::new_monty(to_monty_signed::<FP>(int as i32)))
545        } else {
546            None
547        }
548    }
549
550    /// Convert a given `i64` integer into an element of the `MontyField31` field.
551    ///
552    /// # Safety
553    /// This is always safe as the conversion to monty form can accept any `i64`.
554    unsafe fn from_canonical_unchecked(int: i64) -> Self {
555        Self::new_monty(to_monty_64_signed::<FP>(int))
556    }
557}
558
559impl<FP: FieldParameters> QuotientMap<u128> for MontyField31<FP> {
560    /// Convert a given `u128` integer into an element of the `MontyField31` field.
561    fn from_int(int: u128) -> Self {
562        Self::new_monty(to_monty::<FP>((int % (FP::PRIME as u128)) as u32))
563    }
564
565    /// Convert a given `u128` integer into an element of the `MontyField31` field.
566    ///
567    /// Returns `None` if the given integer is greater than the Prime.
568    fn from_canonical_checked(int: u128) -> Option<Self> {
569        (int < FP::PRIME as u128).then(|| Self::new(int as u32))
570    }
571
572    /// Convert a given `u128` integer into an element of the `MontyField31` field.
573    ///
574    /// # Safety
575    /// The input must be a valid `u64` element.
576    unsafe fn from_canonical_unchecked(int: u128) -> Self {
577        Self::new_monty(to_monty_64::<FP>(int as u64))
578    }
579}
580
581impl<FP: FieldParameters> QuotientMap<i128> for MontyField31<FP> {
582    /// Convert a given `i128` integer into an element of the `MontyField31` field.
583    fn from_int(int: i128) -> Self {
584        Self::new_monty(to_monty_signed::<FP>((int % (FP::PRIME as i128)) as i32))
585    }
586
587    /// Convert a given `i128` integer into an element of the `MontyField31` field.
588    ///
589    /// Returns `None` if the given integer does not lie in the range `[(1 - P)/2, (P - 1)/2]`.
590    fn from_canonical_checked(int: i128) -> Option<Self> {
591        let bound = (FP::PRIME >> 1) as i128;
592        if int <= bound {
593            (int >= (-bound)).then(|| Self::new_monty(to_monty_signed::<FP>(int as i32)))
594        } else {
595            None
596        }
597    }
598
599    /// Convert a given `i128` integer into an element of the `MontyField31` field.
600    ///
601    /// # Safety
602    /// The input must be a valid `i64` element.
603    unsafe fn from_canonical_unchecked(int: i128) -> Self {
604        Self::new_monty(to_monty_64_signed::<FP>(int as i64))
605    }
606}
607
608impl<FP: FieldParameters> PrimeField for MontyField31<FP> {
609    fn as_canonical_biguint(&self) -> BigUint {
610        self.as_canonical_u32().into()
611    }
612}
613
614impl<FP: FieldParameters> PrimeField64 for MontyField31<FP> {
615    const ORDER_U64: u64 = FP::PRIME as u64;
616
617    #[inline]
618    fn as_canonical_u64(&self) -> u64 {
619        self.as_canonical_u32().into()
620    }
621
622    #[inline]
623    fn to_unique_u64(&self) -> u64 {
624        // The internal representation is already a unique u32 for each field element.
625        // It's fine to hash things in monty form.
626        self.value as u64
627    }
628}
629
630impl<FP: FieldParameters> PrimeField32 for MontyField31<FP> {
631    const ORDER_U32: u32 = FP::PRIME;
632
633    #[inline]
634    fn as_canonical_u32(&self) -> u32 {
635        Self::to_u32(self)
636    }
637
638    #[inline]
639    fn to_unique_u32(&self) -> u32 {
640        // The internal representation is already a unique u32 for each field element.
641        // It's fine to hash things in monty form.
642        self.value
643    }
644}
645
646impl<FP: FieldParameters + TwoAdicData> TwoAdicField for MontyField31<FP> {
647    const TWO_ADICITY: usize = FP::TWO_ADICITY;
648    fn two_adic_generator(bits: usize) -> Self {
649        assert!(bits <= Self::TWO_ADICITY);
650        FP::TWO_ADIC_GENERATORS.as_ref()[bits]
651    }
652}
653
654impl<FP: MontyParameters> Add for MontyField31<FP> {
655    type Output = Self;
656
657    #[inline]
658    fn add(self, rhs: Self) -> Self {
659        Self::new_monty(add::<FP>(self.value, rhs.value))
660    }
661}
662
663impl<FP: MontyParameters> Sub for MontyField31<FP> {
664    type Output = Self;
665
666    #[inline]
667    fn sub(self, rhs: Self) -> Self {
668        Self::new_monty(sub::<FP>(self.value, rhs.value))
669    }
670}
671
672impl<FP: FieldParameters> Neg for MontyField31<FP> {
673    type Output = Self;
674
675    #[inline]
676    fn neg(self) -> Self::Output {
677        Self::ZERO - self
678    }
679}
680
681impl<FP: MontyParameters> Mul for MontyField31<FP> {
682    type Output = Self;
683
684    #[inline]
685    fn mul(self, rhs: Self) -> Self {
686        let long_prod = self.value as u64 * rhs.value as u64;
687        Self::new_monty(monty_reduce::<FP>(long_prod))
688    }
689}
690
691impl_add_assign!(MontyField31, (MontyParameters, MP));
692impl_sub_assign!(MontyField31, (MontyParameters, MP));
693impl_mul_methods!(MontyField31, (FieldParameters, FP));
694impl_div_methods!(MontyField31, MontyField31, (FieldParameters, FP));
695
696impl<FP: MontyParameters> Sum for MontyField31<FP> {
697    #[inline]
698    fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
699        // This is faster than iter.reduce(|x, y| x + y).unwrap_or(Self::ZERO) for iterators of length > 2.
700        // There might be a faster reduction method possible for lengths <= 16 which avoids %.
701
702        // This sum will not overflow so long as iter.len() < 2^33.
703        let sum = iter.map(|x| x.value as u64).sum::<u64>();
704        Self::new_monty((sum % FP::PRIME as u64) as u32)
705    }
706}
p3_monty_31/monty_31.rs

p3_monty_31/
monty_31.rs
