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

p3_monty_31/
monty_31.rs
