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

p3_monty_31/
monty_31.rs
