trident/field/
goldilocks.rs

1//! Goldilocks prime field: p = 2^64 - 2^32 + 1.
2//!
3//! Used by: Triton VM, Miden VM, OpenVM, Plonky3.
4//!
5//! The Goldilocks prime has efficient reduction: since 2^64 ≡ 2^32 - 1 (mod p),
6//! products in u128 can be reduced without general division.
7
8use super::PrimeField;
9
10/// Goldilocks prime: p = 2^64 - 2^32 + 1 = 0xFFFF_FFFF_0000_0001.
11pub const MODULUS: u64 = 0xFFFF_FFFF_0000_0001;
12
13/// A Goldilocks field element (u64 in [0, p)).
14#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
15pub struct Goldilocks(pub u64);
16
17impl Goldilocks {
18    /// Reduce a u128 value modulo p using the identity 2^64 ≡ 2^32 - 1 (mod p).
19    #[inline]
20    fn reduce128(x: u128) -> Self {
21        let lo = x as u64;
22        let hi = (x >> 64) as u64;
23        let hi_shifted = (hi as u128) * ((1u128 << 32) - 1);
24        let sum = lo as u128 + hi_shifted;
25        let lo2 = sum as u64;
26        let hi2 = (sum >> 64) as u64;
27        if hi2 == 0 {
28            Self(if lo2 >= MODULUS { lo2 - MODULUS } else { lo2 })
29        } else {
30            let r = lo2 as u128 + (hi2 as u128) * ((1u128 << 32) - 1);
31            let lo3 = r as u64;
32            let hi3 = (r >> 64) as u64;
33            if hi3 == 0 {
34                Self(if lo3 >= MODULUS { lo3 - MODULUS } else { lo3 })
35            } else {
36                let v = lo3.wrapping_add(hi3.wrapping_mul(u32::MAX as u64));
37                Self(if v >= MODULUS { v - MODULUS } else { v })
38            }
39        }
40    }
41
42    /// The Poseidon2 S-box for Goldilocks: x^7.
43    #[inline]
44    pub fn sbox(self) -> Self {
45        let x2 = self.mul(self);
46        let x3 = x2.mul(self);
47        let x6 = x3.mul(x3);
48        x6.mul(self)
49    }
50}
51
52impl PrimeField for Goldilocks {
53    const MODULUS: u128 = MODULUS as u128;
54    const BITS: u32 = 64;
55    const ZERO: Self = Self(0);
56    const ONE: Self = Self(1);
57
58    #[inline]
59    fn from_u64(v: u64) -> Self {
60        Self(v % MODULUS)
61    }
62
63    #[inline]
64    fn to_u64(self) -> u64 {
65        self.0
66    }
67
68    #[inline]
69    fn add(self, rhs: Self) -> Self {
70        let (sum, carry) = self.0.overflowing_add(rhs.0);
71        if carry {
72            let r = sum + (u32::MAX as u64);
73            Self(if r >= MODULUS { r - MODULUS } else { r })
74        } else {
75            Self(if sum >= MODULUS { sum - MODULUS } else { sum })
76        }
77    }
78
79    #[inline]
80    fn sub(self, rhs: Self) -> Self {
81        if self.0 >= rhs.0 {
82            Self(self.0 - rhs.0)
83        } else {
84            Self(MODULUS - rhs.0 + self.0)
85        }
86    }
87
88    #[inline]
89    fn mul(self, rhs: Self) -> Self {
90        Self::reduce128((self.0 as u128) * (rhs.0 as u128))
91    }
92
93    #[inline]
94    fn neg(self) -> Self {
95        if self.0 == 0 {
96            Self(0)
97        } else {
98            Self(MODULUS - self.0)
99        }
100    }
101}
trident/field/goldilocks.rs

trident/field/
goldilocks.rs
