risc0_zkp_core/
fp.rs

1// Copyright 2022 Risc0, Inc.
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15//! Support for the base finite field modulo 15*2^27 + 1
16
17use core::ops;
18
19use bytemuck::{Pod, Zeroable};
20use rand::Rng;
21
22use crate::Random;
23
24/// The modulus of the field.
25pub const P: u32 = 15 * (1 << 27) + 1;
26/// The modulus of the field as a u64.
27pub const P_U64: u64 = P as u64;
28
29/// The Fp class is an element of the finite field F_p, where P is the prime
30/// number 15*2^27 + 1. Put another way, Fp is basically integer arithmetic
31/// modulo P.
32///
33/// The `Fp` datatype is the core type of all of the operations done within the
34/// zero knowledge proofs, and is the smallest 'addressable' datatype, and the
35/// base type of which all composite types are built. In many ways, one can
36/// imagine it as the word size of a very strange architecture.
37///
38/// This specific prime P was chosen to:
39/// - Be less than 2^31 so that it fits within a 32 bit word and doesn't
40///   overflow on addition.
41/// - Otherwise have as large a power of 2 in the factors of P-1 as possible.
42///
43/// This last property is useful for number theoretical transforms (the fast
44/// fourier transform equivelant on finite fields). See NTT.h for details.
45///
46/// The Fp class wraps all the standard arithmetic operations to make the finite
47/// field elements look basically like ordinary numbers (which they mostly are).
48#[derive(Clone, Copy, Debug, Default, Eq, PartialEq, PartialOrd, Zeroable, Pod)]
49#[repr(transparent)]
50pub struct Fp(u32);
51
52impl Fp {
53    /// Create a new [Fp] from a raw integer.
54    pub const fn new(x: u32) -> Self {
55        Self(x)
56    }
57
58    /// Return the maximum value that an [Fp] can take.
59    pub fn max() -> Self {
60        Self(P - 1)
61    }
62
63    /// Raise an `Fp` value to the power of `n`.
64    pub fn pow(self, n: usize) -> Self {
65        let mut n = n;
66        let mut tot = Fp(1);
67        let mut x = self;
68        while n != 0 {
69            if n % 2 == 1 {
70                tot *= x;
71            }
72            n = n / 2;
73            x *= x;
74        }
75        tot
76    }
77
78    /// Compute the multiplicative inverse of `x`, or `1 / x` in finite field
79    /// terms. Since `x ^ (P - 1) == 1 % P` for any `x != 0` (as a
80    /// consequence of Fermat's little theorem), it follows that `x *
81    /// x ^ (P - 2) == 1 % P` for `x != 0`.  That is, `x ^ (P - 2)` is the
82    /// multiplicative inverse of `x`. Computed this way, the *inverse* of
83    /// zero comes out as zero, which is convenient in many cases, so we
84    /// leave it.
85    pub fn inv(self) -> Self {
86        self.pow((P - 2) as usize)
87    }
88}
89
90/// Provides support for multiplying by a factor with an `Fp` type.
91pub trait FpMul {
92    /// Multiply `self` by a factor of `Fp` type.
93    fn fp_mul(self, x: Fp) -> Self;
94}
95
96impl FpMul for Fp {
97    fn fp_mul(self, x: Fp) -> Self {
98        self * x
99    }
100}
101
102impl Random for Fp {
103    fn random<R: Rng>(rng: &mut R) -> Self {
104        // Reject the last modulo-P region of possible uint32_t values, since it's
105        // uneven and will only return random values less than (2^32 % P).
106        const REJECT_CUTOFF: u32 = (u32::MAX / P) * P;
107        let mut val: u32 = rng.gen();
108
109        while val >= REJECT_CUTOFF {
110            val = rng.gen();
111        }
112        Fp::from(val)
113    }
114}
115
116impl ops::Add for Fp {
117    type Output = Self;
118    fn add(self, rhs: Self) -> Self {
119        Fp(add(self.0, rhs.0))
120    }
121}
122
123impl ops::AddAssign for Fp {
124    fn add_assign(&mut self, rhs: Self) {
125        self.0 = add(self.0, rhs.0)
126    }
127}
128
129impl ops::Sub for Fp {
130    type Output = Self;
131    fn sub(self, rhs: Self) -> Self {
132        Fp(sub(self.0, rhs.0))
133    }
134}
135
136impl ops::SubAssign for Fp {
137    fn sub_assign(&mut self, rhs: Self) {
138        self.0 = sub(self.0, rhs.0)
139    }
140}
141
142impl ops::Mul for Fp {
143    type Output = Self;
144    fn mul(self, rhs: Self) -> Self {
145        Fp(mul(self.0, rhs.0))
146    }
147}
148
149impl ops::MulAssign for Fp {
150    fn mul_assign(&mut self, rhs: Self) {
151        self.0 = mul(self.0, rhs.0)
152    }
153}
154
155impl ops::Neg for Fp {
156    type Output = Self;
157    fn neg(self) -> Self {
158        Fp(0) - self
159    }
160}
161
162impl From<Fp> for u32 {
163    fn from(x: Fp) -> Self {
164        x.0
165    }
166}
167
168impl From<&Fp> for u32 {
169    fn from(x: &Fp) -> Self {
170        x.0
171    }
172}
173
174impl From<Fp> for u64 {
175    fn from(x: Fp) -> Self {
176        x.0.into()
177    }
178}
179
180impl From<u32> for Fp {
181    fn from(x: u32) -> Self {
182        Fp(x % P)
183    }
184}
185
186impl From<u64> for Fp {
187    fn from(x: u64) -> Self {
188        Fp((x % P_U64) as u32)
189    }
190}
191
192fn add(lhs: u32, rhs: u32) -> u32 {
193    let x = lhs + rhs;
194    return if x >= P { x - P } else { x };
195}
196
197fn sub(lhs: u32, rhs: u32) -> u32 {
198    let x = lhs.wrapping_sub(rhs);
199    return if x > P { x.wrapping_add(P) } else { x };
200}
201
202fn mul(lhs: u32, rhs: u32) -> u32 {
203    (((lhs as u64) * (rhs as u64)) % P_U64) as u32
204}
205
206#[cfg(test)]
207mod tests {
208    use super::{Fp, P, P_U64};
209    use crate::Random;
210    use rand::SeedableRng;
211
212    #[test]
213    fn inv() {
214        // Smoke test for inv
215        assert_eq!(Fp(5).inv() * Fp(5), Fp(1));
216    }
217
218    #[test]
219    fn pow() {
220        // Smoke tests for pow
221        assert_eq!(Fp(5).pow(0), Fp(1));
222        assert_eq!(Fp(5).pow(1), Fp(5));
223        assert_eq!(Fp(5).pow(2), Fp(25));
224        // Mathematica says PowerMod[5, 1000, 15*2^27 + 1] == 589699054
225        assert_eq!(Fp(5).pow(1000), Fp(589699054));
226        assert_eq!(Fp(5).pow((P - 2) as usize) * Fp(5), Fp(1));
227        assert_eq!(Fp(5).pow((P - 1) as usize), Fp(1));
228    }
229
230    #[test]
231    fn compare_native() {
232        // Compare core operations against simple % P implementations
233        let mut rng = rand::rngs::SmallRng::seed_from_u64(2);
234        for _ in 0..100_000 {
235            let fa = Fp::random(&mut rng);
236            let fb = Fp::random(&mut rng);
237            let a: u64 = fa.into();
238            let b: u64 = fb.into();
239            assert_eq!(fa + fb, Fp::from(a + b));
240            assert_eq!(fa - fb, Fp::from(a + (P_U64 - b)));
241            assert_eq!(fa * fb, Fp::from(a * b));
242        }
243    }
244}
risc0_zkp_core/fp.rs

risc0_zkp_core/
fp.rs
