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

p3_monty_31/
monty_31.rs
