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        if exp < 64 {
212            *self * Self::MONTY_POWERS_OF_TWO[exp as usize]
213        } else {
214            // For larger values we use the default method.
215            *self * Self::TWO.exp_u64(exp)
216        }
217    }
218
219    #[inline]
220    fn div_2exp_u64(&self, exp: u64) -> Self {
221        if exp <= 32 {
222            // As the monty form of 2^{-exp} is 2^{32 - exp} mod P, for
223            // 0 <= exp <= 32, we can multiply by 2^{-exp} by doing a shift
224            // followed by a monty reduction.
225            let long_prod = (self.value as u64) << (32 - exp);
226            Self::new_monty(monty_reduce::<FP>(long_prod))
227        } else {
228            // For larger values we use a slower method though this is
229            // still much faster than the default method as it avoids the inverse().
230            *self * Self::HALF.exp_u64(exp)
231        }
232    }
233
234    #[inline]
235    fn zero_vec(len: usize) -> Vec<Self> {
236        // SAFETY:
237        // Due to `#[repr(transparent)]`, MontyField31 and u32 have the same size, alignment
238        // and memory layout making `flatten_to_base` safe. This this will create
239        // a vector MontyField31 elements with value set to 0 which is the
240        // MONTY form of 0.
241        unsafe { flatten_to_base(vec![0u32; len]) }
242    }
243
244    #[inline]
245    fn sum_array<const N: usize>(input: &[Self]) -> Self {
246        assert_eq!(N, input.len());
247        // Benchmarking shows that for N <= 7 it's faster to sum the elements directly
248        // but for N > 7 it's faster to use the .sum() methods which passes through u64's
249        // allowing for delayed reductions.
250        match N {
251            0 => Self::ZERO,
252            1 => input[0],
253            2 => input[0] + input[1],
254            3 => input[0] + input[1] + input[2],
255            4 => (input[0] + input[1]) + (input[2] + input[3]),
256            5 => Self::sum_array::<4>(&input[..4]) + Self::sum_array::<1>(&input[4..]),
257            6 => Self::sum_array::<4>(&input[..4]) + Self::sum_array::<2>(&input[4..]),
258            7 => Self::sum_array::<4>(&input[..4]) + Self::sum_array::<3>(&input[4..]),
259            _ => input.iter().copied().sum(),
260        }
261    }
262
263    #[inline]
264    fn dot_product<const N: usize>(lhs: &[Self; N], rhs: &[Self; N]) -> Self {
265        const {
266            assert!(N as u64 <= (1 << 34));
267
268            // This code relies on assumptions about the relative size of the
269            // prime and the monty parameter. If these are changes this needs to be checked.
270            debug_assert!(FP::MONTY_BITS == 32);
271            debug_assert!((FP::PRIME as u64) < (1 << 31));
272        }
273        match N {
274            0 => Self::ZERO,
275            1 => lhs[0] * rhs[0],
276            2 => {
277                // As all values are < P < 2^31, the products are < P^2 < 2^31P.
278                // Hence, summing two together we stay below MONTY*P which means
279                // monty_reduce will produce a valid result.
280                let u64_prod_sum = (lhs[0].value as u64) * (rhs[0].value as u64)
281                    + (lhs[1].value as u64) * (rhs[1].value as u64);
282                Self::new_monty(monty_reduce::<FP>(u64_prod_sum))
283            }
284            3 => {
285                // As all values are < P < 2^31, the products are < P^2 < 2^31P.
286                // Hence, summing three together will be less than 2 * MONTY * P
287                let u64_prod_sum = (lhs[0].value as u64) * (rhs[0].value as u64)
288                    + (lhs[1].value as u64) * (rhs[1].value as u64)
289                    + (lhs[2].value as u64) * (rhs[2].value as u64);
290                Self::new_monty(large_monty_reduce::<FP>(u64_prod_sum))
291            }
292            4 => {
293                // As all values are < P < 2^31, the products are < P^2 < 2^31P.
294                // Hence, summing four together will be less than 2 * MONTY * P.
295                let u64_prod_sum = (lhs[0].value as u64) * (rhs[0].value as u64)
296                    + (lhs[1].value as u64) * (rhs[1].value as u64)
297                    + (lhs[2].value as u64) * (rhs[2].value as u64)
298                    + (lhs[3].value as u64) * (rhs[3].value as u64);
299                Self::new_monty(large_monty_reduce::<FP>(u64_prod_sum))
300            }
301            5 => {
302                let head_sum = (lhs[0].value as u64) * (rhs[0].value as u64)
303                    + (lhs[1].value as u64) * (rhs[1].value as u64)
304                    + (lhs[2].value as u64) * (rhs[2].value as u64)
305                    + (lhs[3].value as u64) * (rhs[3].value as u64);
306                let tail_sum = (lhs[4].value as u64) * (rhs[4].value as u64);
307                // head_sum < 4*P^2, tail_sum < 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            6 => {
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                // head_sum < 4*P^2, tail_sum < 2*P^2.
322                let head_sum_corr = head_sum.wrapping_sub((FP::PRIME as u64) << FP::MONTY_BITS);
323                // head_sum.min(head_sum_corr) is guaranteed to be < 2*P^2.
324                // Hence sum < 4P^2 < 2 * MONTY * P
325                let sum = head_sum.min(head_sum_corr) + tail_sum;
326                Self::new_monty(large_monty_reduce::<FP>(sum))
327            }
328            7 => {
329                let head_sum = (lhs[0].value as u64) * (rhs[0].value as u64)
330                    + (lhs[1].value as u64) * (rhs[1].value as u64)
331                    + (lhs[2].value as u64) * (rhs[2].value as u64)
332                    + (lhs[3].value as u64) * (rhs[3].value as u64);
333                let tail_sum = (lhs[4].value as u64) * (rhs[4].value as u64)
334                    + lhs[5].value as u64 * (rhs[5].value as u64)
335                    + lhs[6].value as u64 * (rhs[6].value as u64);
336                // head_sum, tail_sum are guaranteed to be < 4*P^2.
337                let head_sum_corr = head_sum.wrapping_sub((FP::PRIME as u64) << FP::MONTY_BITS);
338                let tail_sum_corr = tail_sum.wrapping_sub((FP::PRIME as u64) << FP::MONTY_BITS);
339                // head_sum.min(head_sum_corr), tail_sum.min(tail_sum_corr) is guaranteed to be < 2*P^2.
340                // Hence sum < 4P^2 < 2 * MONTY * P
341                let sum = head_sum.min(head_sum_corr) + tail_sum.min(tail_sum_corr);
342                Self::new_monty(large_monty_reduce::<FP>(sum))
343            }
344            8 => {
345                let head_sum = (lhs[0].value as u64) * (rhs[0].value as u64)
346                    + (lhs[1].value as u64) * (rhs[1].value as u64)
347                    + (lhs[2].value as u64) * (rhs[2].value as u64)
348                    + (lhs[3].value as u64) * (rhs[3].value as u64);
349                let tail_sum = (lhs[4].value as u64) * (rhs[4].value as u64)
350                    + lhs[5].value as u64 * (rhs[5].value as u64)
351                    + lhs[6].value as u64 * (rhs[6].value as u64)
352                    + lhs[7].value as u64 * (rhs[7].value as u64);
353                // head_sum, tail_sum are guaranteed to be < 4*P^2.
354                let head_sum_corr = head_sum.wrapping_sub((FP::PRIME as u64) << FP::MONTY_BITS);
355                let tail_sum_corr = tail_sum.wrapping_sub((FP::PRIME as u64) << FP::MONTY_BITS);
356                // head_sum.min(head_sum_corr), tail_sum.min(tail_sum_corr) is guaranteed to be < 2*P^2.
357                // Hence sum < 4P^2 < 2 * MONTY * P
358                let sum = head_sum.min(head_sum_corr) + tail_sum.min(tail_sum_corr);
359                Self::new_monty(large_monty_reduce::<FP>(sum))
360            }
361            _ => {
362                // For large enough N, we accumulate into a u128. This helps the compiler as it lets
363                // it do a lot of computation in parallel as it knows that summing u128's is associative.
364                let acc_u128 = lhs
365                    .chunks(4)
366                    .zip(rhs.chunks(4))
367                    .map(|(l, r)| {
368                        // As all values are < P < 2^31, the products are < P^2 < 2^31P.
369                        // Hence, summing four together will not overflow a u64 but will be
370                        // larger than 2^32P.
371                        let u64_prod_sum = l
372                            .iter()
373                            .zip(r)
374                            .map(|(l, r)| (l.value as u64) * (r.value as u64))
375                            .sum::<u64>();
376                        u64_prod_sum as u128
377                    })
378                    .sum();
379                // As N <= 2^34 by the earlier assertion, acc_u128 <= 2^34 * P^2 < 2^34 * 2^62 < 2^96.
380                Self::new_monty(monty_reduce_u128::<FP>(acc_u128))
381            }
382        }
383    }
384}
385
386impl<FP: FieldParameters + RelativelyPrimePower<D>, const D: u64> InjectiveMonomial<D>
387    for MontyField31<FP>
388{
389}
390
391impl<FP: FieldParameters + RelativelyPrimePower<D>, const D: u64> PermutationMonomial<D>
392    for MontyField31<FP>
393{
394    fn injective_exp_root_n(&self) -> Self {
395        FP::exp_root_d(*self)
396    }
397}
398
399impl<FP: FieldParameters> RawDataSerializable for MontyField31<FP> {
400    impl_raw_serializable_primefield32!();
401}
402
403impl<FP: FieldParameters> Field for MontyField31<FP> {
404    #[cfg(all(target_arch = "aarch64", target_feature = "neon"))]
405    type Packing = crate::PackedMontyField31Neon<FP>;
406    #[cfg(all(
407        target_arch = "x86_64",
408        target_feature = "avx2",
409        not(target_feature = "avx512f")
410    ))]
411    type Packing = crate::PackedMontyField31AVX2<FP>;
412    #[cfg(all(target_arch = "x86_64", target_feature = "avx512f"))]
413    type Packing = crate::PackedMontyField31AVX512<FP>;
414    #[cfg(not(any(
415        all(target_arch = "aarch64", target_feature = "neon"),
416        all(
417            target_arch = "x86_64",
418            target_feature = "avx2",
419            not(target_feature = "avx512f")
420        ),
421        all(target_arch = "x86_64", target_feature = "avx512f"),
422    )))]
423    type Packing = Self;
424
425    const GENERATOR: Self = FP::MONTY_GEN;
426
427    fn try_inverse(&self) -> Option<Self> {
428        if self.is_zero() {
429            return None;
430        }
431
432        // The number of bits of FP::PRIME. By the very name of MontyField31 this should always be 31.
433        const NUM_PRIME_BITS: u32 = 31;
434
435        // Get the inverse using a gcd algorithm.
436        // We use `val` to denote the input to `gcd_inversion_prime_field_32` and `R = 2^{MONTY_BITS}`
437        // our monty constant.
438        // The function gcd_inversion_31_bit_field maps `val mod P -> 2^{60}val mod P`
439        let gcd_inverse = gcd_inversion_prime_field_32::<NUM_PRIME_BITS>(self.value, FP::PRIME);
440
441        // Currently |gcd_inverse| <= 2^{NUM_PRIME_BITS - 2} <= 2^{60}
442        // As P > 2^{30}, 0 < 2^{30}P + gcd_inverse < 2^61
443        let pos_inverse = (((FP::PRIME as i64) << 30) + gcd_inverse) as u64;
444
445        // We could do a % operation here, but monty reduction is faster.
446        // This does remove a factor of `R` from the result so we will need to
447        // correct for that.
448        let uncorrected_value = Self::new_monty(monty_reduce::<FP>(pos_inverse));
449
450        // Currently, uncorrected_value = R^{-1} * 2^{60} * val^{-1} mod P = 2^{28} * val^{-1} mod P`.
451        // But `val` is really the monty form of some value `x` satisfying `val = xR mod P`. We want
452        // `x^{-1}R mod P = R^2 x^{-1}R^{-1} mod P = 2^{64} val^{-1} mod P`.
453        // Hence we need to multiply by 2^{64 - 28} = 2^{36}.
454
455        // Unrolling the definitions a little, this 36 comes from: 3 * FP::MONTY_BITS - (2 * NUM_PRIME_BITS - 2)
456
457        Some(uncorrected_value.mul_2exp_u64((3 * FP::MONTY_BITS - (2 * NUM_PRIME_BITS - 2)) as u64))
458    }
459
460    #[inline]
461    fn order() -> BigUint {
462        FP::PRIME.into()
463    }
464}
465
466quotient_map_small_int!(MontyField31, u32, FieldParameters, [u8, u16]);
467quotient_map_small_int!(MontyField31, i32, FieldParameters, [i8, i16]);
468
469impl<FP: FieldParameters> QuotientMap<u32> for MontyField31<FP> {
470    /// Convert a given `u32` integer into an element of the `MontyField31` field.
471    #[inline]
472    fn from_int(int: u32) -> Self {
473        Self::new(int)
474    }
475
476    /// Convert a given `u32` integer into an element of the `MontyField31` field.
477    ///
478    /// Returns `None` if the given integer is greater than the Prime.
479    #[inline]
480    fn from_canonical_checked(int: u32) -> Option<Self> {
481        (int < FP::PRIME).then(|| Self::new(int))
482    }
483
484    /// Convert a given `u32` integer into an element of the `MontyField31` field.
485    ///
486    /// # Safety
487    /// This is always safe as the conversion to monty form can accept any `u32`.
488    #[inline(always)]
489    unsafe fn from_canonical_unchecked(int: u32) -> Self {
490        Self::new(int)
491    }
492}
493
494impl<FP: FieldParameters> QuotientMap<i32> for MontyField31<FP> {
495    /// Convert a given `i32` integer into an element of the `MontyField31` field.
496    #[inline]
497    fn from_int(int: i32) -> Self {
498        Self::new_monty(to_monty_signed::<FP>(int))
499    }
500
501    /// Convert a given `i32` integer into an element of the `MontyField31` field.
502    ///
503    /// Returns `None` if the given integer does not lie in the range `[(1 - P)/2, (P - 1)/2]`.
504    #[inline]
505    fn from_canonical_checked(int: i32) -> Option<Self> {
506        let bound = (FP::PRIME >> 1) as i32;
507        if int <= bound {
508            (int >= (-bound)).then(|| Self::new_monty(to_monty_signed::<FP>(int)))
509        } else {
510            None
511        }
512    }
513
514    /// Convert a given `i32` integer into an element of the `MontyField31` field.
515    ///
516    /// # Safety
517    /// This is always safe as the conversion to monty form can accept any `i32`.
518    #[inline(always)]
519    unsafe fn from_canonical_unchecked(int: i32) -> Self {
520        Self::new_monty(to_monty_signed::<FP>(int))
521    }
522}
523
524impl<FP: FieldParameters> QuotientMap<u64> for MontyField31<FP> {
525    /// Convert a given `u64` integer into an element of the `MontyField31` field.
526    fn from_int(int: u64) -> Self {
527        Self::new_monty(to_monty_64::<FP>(int))
528    }
529
530    /// Convert a given `u64` integer into an element of the `MontyField31` field.
531    ///
532    /// Returns `None` if the given integer is greater than the Prime.
533    fn from_canonical_checked(int: u64) -> Option<Self> {
534        (int < FP::PRIME as u64).then(|| Self::new(int as u32))
535    }
536
537    /// Convert a given `u64` integer into an element of the `MontyField31` field.
538    ///
539    /// # Safety
540    /// This is always safe as the conversion to monty form can accept any `u64`.
541    unsafe fn from_canonical_unchecked(int: u64) -> Self {
542        Self::new_monty(to_monty_64::<FP>(int))
543    }
544}
545
546impl<FP: FieldParameters> QuotientMap<i64> for MontyField31<FP> {
547    /// Convert a given `i64` integer into an element of the `MontyField31` field.
548    fn from_int(int: i64) -> Self {
549        Self::new_monty(to_monty_64_signed::<FP>(int))
550    }
551
552    /// Convert a given `i64` integer into an element of the `MontyField31` field.
553    ///
554    /// Returns `None` if the given integer does not lie in the range `[(1 - P)/2, (P - 1)/2]`.
555    fn from_canonical_checked(int: i64) -> Option<Self> {
556        let bound = (FP::PRIME >> 1) as i64;
557        if int <= bound {
558            (int >= (-bound)).then(|| Self::new_monty(to_monty_signed::<FP>(int as i32)))
559        } else {
560            None
561        }
562    }
563
564    /// Convert a given `i64` integer into an element of the `MontyField31` field.
565    ///
566    /// # Safety
567    /// This is always safe as the conversion to monty form can accept any `i64`.
568    unsafe fn from_canonical_unchecked(int: i64) -> Self {
569        Self::new_monty(to_monty_64_signed::<FP>(int))
570    }
571}
572
573impl<FP: FieldParameters> QuotientMap<u128> for MontyField31<FP> {
574    /// Convert a given `u128` integer into an element of the `MontyField31` field.
575    fn from_int(int: u128) -> Self {
576        Self::new_monty(to_monty::<FP>((int % (FP::PRIME as u128)) as u32))
577    }
578
579    /// Convert a given `u128` integer into an element of the `MontyField31` field.
580    ///
581    /// Returns `None` if the given integer is greater than the Prime.
582    fn from_canonical_checked(int: u128) -> Option<Self> {
583        (int < FP::PRIME as u128).then(|| Self::new(int as u32))
584    }
585
586    /// Convert a given `u128` integer into an element of the `MontyField31` field.
587    ///
588    /// # Safety
589    /// The input must be a valid `u64` element.
590    unsafe fn from_canonical_unchecked(int: u128) -> Self {
591        Self::new_monty(to_monty_64::<FP>(int as u64))
592    }
593}
594
595impl<FP: FieldParameters> QuotientMap<i128> for MontyField31<FP> {
596    /// Convert a given `i128` integer into an element of the `MontyField31` field.
597    fn from_int(int: i128) -> Self {
598        Self::new_monty(to_monty_signed::<FP>((int % (FP::PRIME as i128)) as i32))
599    }
600
601    /// Convert a given `i128` integer into an element of the `MontyField31` field.
602    ///
603    /// Returns `None` if the given integer does not lie in the range `[(1 - P)/2, (P - 1)/2]`.
604    fn from_canonical_checked(int: i128) -> Option<Self> {
605        let bound = (FP::PRIME >> 1) as i128;
606        if int <= bound {
607            (int >= (-bound)).then(|| Self::new_monty(to_monty_signed::<FP>(int as i32)))
608        } else {
609            None
610        }
611    }
612
613    /// Convert a given `i128` integer into an element of the `MontyField31` field.
614    ///
615    /// # Safety
616    /// The input must be a valid `i64` element.
617    unsafe fn from_canonical_unchecked(int: i128) -> Self {
618        Self::new_monty(to_monty_64_signed::<FP>(int as i64))
619    }
620}
621
622impl<FP: FieldParameters> PrimeField for MontyField31<FP> {
623    fn as_canonical_biguint(&self) -> BigUint {
624        self.as_canonical_u32().into()
625    }
626}
627
628impl<FP: FieldParameters> PrimeField64 for MontyField31<FP> {
629    const ORDER_U64: u64 = FP::PRIME as u64;
630
631    #[inline]
632    fn as_canonical_u64(&self) -> u64 {
633        self.as_canonical_u32().into()
634    }
635
636    #[inline]
637    fn to_unique_u64(&self) -> u64 {
638        // The internal representation is already a unique u32 for each field element.
639        // It's fine to hash things in monty form.
640        self.value as u64
641    }
642}
643
644impl<FP: FieldParameters> PrimeField32 for MontyField31<FP> {
645    const ORDER_U32: u32 = FP::PRIME;
646
647    #[inline]
648    fn as_canonical_u32(&self) -> u32 {
649        Self::to_u32(self)
650    }
651
652    #[inline]
653    fn to_unique_u32(&self) -> u32 {
654        // The internal representation is already a unique u32 for each field element.
655        // It's fine to hash things in monty form.
656        self.value
657    }
658}
659
660impl<FP: FieldParameters + TwoAdicData> TwoAdicField for MontyField31<FP> {
661    const TWO_ADICITY: usize = FP::TWO_ADICITY;
662    fn two_adic_generator(bits: usize) -> Self {
663        const {
664            // Verify that 2^TWO_ADICITY divides PRIME - 1.
665            assert!(
666                (FP::PRIME as u64 - 1).is_multiple_of(1u64 << FP::TWO_ADICITY),
667                "2^TWO_ADICITY must divide PRIME - 1"
668            );
669            // Verify maximality: 2^(TWO_ADICITY+1) must NOT divide PRIME - 1.
670            assert!(
671                ((FP::PRIME as u64 - 1) >> FP::TWO_ADICITY) % 2 == 1,
672                "TWO_ADICITY must be maximal"
673            );
674        }
675        assert!(bits <= Self::TWO_ADICITY);
676        FP::TWO_ADIC_GENERATORS.as_ref()[bits]
677    }
678}
679
680impl<FP: MontyParameters> Add for MontyField31<FP> {
681    type Output = Self;
682
683    #[inline]
684    fn add(self, rhs: Self) -> Self {
685        Self::new_monty(add::<FP>(self.value, rhs.value))
686    }
687}
688
689impl<FP: MontyParameters> Sub for MontyField31<FP> {
690    type Output = Self;
691
692    #[inline]
693    fn sub(self, rhs: Self) -> Self {
694        Self::new_monty(sub::<FP>(self.value, rhs.value))
695    }
696}
697
698impl<FP: FieldParameters> Neg for MontyField31<FP> {
699    type Output = Self;
700
701    #[inline]
702    fn neg(self) -> Self::Output {
703        Self::ZERO - self
704    }
705}
706
707impl<FP: MontyParameters> Mul for MontyField31<FP> {
708    type Output = Self;
709
710    #[inline]
711    fn mul(self, rhs: Self) -> Self {
712        let long_prod = self.value as u64 * rhs.value as u64;
713        Self::new_monty(monty_reduce::<FP>(long_prod))
714    }
715}
716
717impl_add_assign!(MontyField31, (MontyParameters, MP));
718impl_sub_assign!(MontyField31, (MontyParameters, MP));
719impl_mul_methods!(MontyField31, (FieldParameters, FP));
720impl_div_methods!(MontyField31, MontyField31, (FieldParameters, FP));
721
722impl<FP: MontyParameters> Sum for MontyField31<FP> {
723    #[inline]
724    fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
725        // This is faster than iter.reduce(|x, y| x + y).unwrap_or(Self::ZERO) for iterators of length > 2.
726        // There might be a faster reduction method possible for lengths <= 16 which avoids %.
727
728        // This sum will not overflow so long as iter.len() < 2^33.
729        let sum = iter.map(|x| x.value as u64).sum::<u64>();
730        Self::new_monty((sum % FP::PRIME as u64) as u32)
731    }
732}
p3_monty_31/monty_31.rs

p3_monty_31/
monty_31.rs
