trident/field/
mersenne31.rs

1//! Mersenne31 prime field: p = 2^31 - 1 = 0x7FFF_FFFF.
2//!
3//! Used by: Plonky3, Circle STARKs.
4//!
5//! A Mersenne prime with extremely efficient reduction: multiplication
6//! reduces via shift-and-add since 2^31 ≡ 1 (mod p).
7
8use super::PrimeField;
9
10/// Mersenne31 prime: p = 2^31 - 1 = 2147483647.
11pub const MODULUS: u64 = 0x7FFF_FFFF;
12
13/// A Mersenne31 field element (u64 in [0, p)).
14#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
15pub struct Mersenne31(pub u64);
16
17impl Mersenne31 {
18    /// Reduce a u64 value modulo p using the Mersenne identity:
19    /// 2^31 ≡ 1 (mod p), so (hi << 31 | lo) ≡ hi + lo (mod p).
20    #[inline]
21    fn reduce(v: u64) -> Self {
22        let lo = v & MODULUS;
23        let hi = v >> 31;
24        let sum = lo + hi;
25        Self(if sum >= MODULUS { sum - MODULUS } else { sum })
26    }
27}
28
29impl PrimeField for Mersenne31 {
30    const MODULUS: u128 = MODULUS as u128;
31    const BITS: u32 = 31;
32    const ZERO: Self = Self(0);
33    const ONE: Self = Self(1);
34
35    #[inline]
36    fn from_u64(v: u64) -> Self {
37        Self::reduce(v % MODULUS)
38    }
39
40    #[inline]
41    fn to_u64(self) -> u64 {
42        self.0
43    }
44
45    #[inline]
46    fn add(self, rhs: Self) -> Self {
47        let sum = self.0 + rhs.0;
48        Self(if sum >= MODULUS { sum - MODULUS } else { sum })
49    }
50
51    #[inline]
52    fn sub(self, rhs: Self) -> Self {
53        if self.0 >= rhs.0 {
54            Self(self.0 - rhs.0)
55        } else {
56            Self(MODULUS - rhs.0 + self.0)
57        }
58    }
59
60    #[inline]
61    fn mul(self, rhs: Self) -> Self {
62        let product = self.0 as u128 * rhs.0 as u128;
63        // Reduce using 2^31 ≡ 1: split into 31-bit chunks
64        let lo = (product & MODULUS as u128) as u64;
65        let hi = (product >> 31) as u64;
66        Self::reduce(lo + hi)
67    }
68
69    #[inline]
70    fn neg(self) -> Self {
71        if self.0 == 0 {
72            Self(0)
73        } else {
74            Self(MODULUS - self.0)
75        }
76    }
77}
trident/field/mersenne31.rs

trident/field/
mersenne31.rs
