haloumi_core/
felt.rs

1//! Felt type.
2
3use ff::PrimeField;
4use internment::Intern;
5use num_bigint::BigUint;
6use std::ops::{Add, AddAssign, Deref, Mul, MulAssign, Neg, Rem, RemAssign, Sub, SubAssign};
7
8/// Interned value of the prime of a finite field.
9#[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
10pub struct Prime(Intern<BigUint>);
11
12impl Prime {
13    /// Creates the prime from the given [`PrimeField`].
14    pub fn new<F: PrimeField>() -> Self {
15        let f = -F::ONE;
16        Self(Intern::new(
17            BigUint::from_bytes_le(f.to_repr().as_ref()) + 1usize,
18        ))
19    }
20
21    fn value(&self) -> &BigUint {
22        self.0.as_ref()
23    }
24
25    fn minus_one(&self) -> Felt {
26        Felt::from_parts(self.value() - 1usize, *self)
27    }
28}
29
30/// Lightweight representation of a constant value.
31///
32/// The actual value is interned which allows this type to be [`Copy`] and
33/// avoids duplication of commonly used values.
34#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
35pub struct Felt {
36    value: Intern<BigUint>,
37    prime: Prime,
38}
39
40impl Felt {
41    /// Creates a new felt from an implementation of [`PrimeField`].
42    pub fn new<F: PrimeField>(f: F) -> Self {
43        Self {
44            value: Intern::new(BigUint::from_bytes_le(f.to_repr().as_ref())),
45            prime: Prime::new::<F>(),
46        }
47    }
48
49    /// Creates a new felt from its raw parts.
50    pub fn from_parts(value: BigUint, prime: Prime) -> Self {
51        Self {
52            value: Intern::new(value),
53            prime,
54        }
55    }
56
57    /// Returns the value of the field prime.
58    pub fn prime(&self) -> Prime {
59        self.prime
60    }
61
62    /// Creates a felt from anything that can become a [`BigUint`].
63    ///
64    /// Use this method only during testing.
65    #[cfg(test)]
66    pub fn new_from<F: PrimeField>(i: impl Into<BigUint>) -> Self {
67        Self {
68            value: Intern::new(i.into()),
69            prime: Prime::new::<F>(),
70        }
71    }
72
73    fn replace(self, value: BigUint) -> Self {
74        Self {
75            value: Intern::new(value % self.prime.value()),
76            prime: self.prime,
77        }
78    }
79
80    /// Returns true if the felt represents -1 mod P.
81    pub fn is_minus_one(&self) -> bool {
82        *self == self.prime().minus_one()
83    }
84}
85
86impl<F: PrimeField> From<F> for Felt {
87    fn from(value: F) -> Self {
88        Self::new(value)
89    }
90}
91
92impl std::fmt::Debug for Felt {
93    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
94        write!(f, "{:?}", self.as_ref())
95    }
96}
97
98impl<T> PartialEq<T> for Felt
99where
100    T: Into<BigUint> + Copy,
101{
102    fn eq(&self, other: &T) -> bool {
103        let other: BigUint = (*other).into() % self.prime.value();
104        self.as_ref().eq(&other)
105    }
106}
107
108impl AsRef<BigUint> for Felt {
109    fn as_ref(&self) -> &BigUint {
110        self.value.as_ref()
111    }
112}
113
114impl Deref for Felt {
115    type Target = BigUint;
116
117    fn deref(&self) -> &Self::Target {
118        self.as_ref()
119    }
120}
121
122impl Rem for Felt {
123    type Output = Self;
124
125    /// # Panics
126    ///
127    /// If the primes are different.
128    fn rem(self, rhs: Self) -> Self::Output {
129        assert_eq!(self.prime, rhs.prime);
130        if self < rhs {
131            return self;
132        }
133        self.replace(self.as_ref() % rhs.as_ref())
134    }
135}
136
137impl Rem<Prime> for Felt {
138    type Output = Self;
139
140    fn rem(self, prime: Prime) -> Self::Output {
141        if self.prime() == prime {
142            return self;
143        }
144        if self.prime() > prime {
145            return Self::from_parts(self.value.as_ref().clone(), prime);
146        }
147        Self::from_parts(self.as_ref() % prime.value(), prime)
148    }
149}
150
151impl RemAssign for Felt {
152    /// # Panics
153    ///
154    /// If the primes are different.
155    fn rem_assign(&mut self, rhs: Self) {
156        *self = *self % rhs;
157    }
158}
159
160impl RemAssign<Prime> for Felt {
161    fn rem_assign(&mut self, rhs: Prime) {
162        *self = *self % rhs;
163    }
164}
165
166impl Sub for Felt {
167    type Output = Self;
168
169    /// # Panics
170    ///
171    /// If the primes are different.
172    fn sub(self, rhs: Self) -> Self::Output {
173        assert_eq!(self.prime, rhs.prime);
174        if self < rhs {
175            let diff = rhs.as_ref() - self.as_ref();
176            return self.replace(self.prime.value() - diff);
177        }
178
179        self.replace(self.as_ref() - rhs.as_ref())
180    }
181}
182
183impl SubAssign for Felt {
184    /// # Panics
185    ///
186    /// If the primes are different.
187    fn sub_assign(&mut self, rhs: Self) {
188        *self = *self - rhs;
189    }
190}
191
192impl Add for Felt {
193    type Output = Felt;
194
195    /// # Panics
196    ///
197    /// If the primes are different.
198    fn add(self, rhs: Self) -> Self::Output {
199        assert_eq!(self.prime, rhs.prime);
200        self.replace(self.as_ref() + rhs.as_ref())
201    }
202}
203
204impl AddAssign for Felt {
205    /// # Panics
206    ///
207    /// If the primes are different.
208    fn add_assign(&mut self, rhs: Self) {
209        *self = *self + rhs;
210    }
211}
212
213impl Mul for Felt {
214    type Output = Felt;
215
216    /// # Panics
217    ///
218    /// If the primes are different.
219    fn mul(self, rhs: Self) -> Self::Output {
220        assert_eq!(self.prime, rhs.prime);
221        self.replace(self.as_ref() * rhs.as_ref())
222    }
223}
224
225impl MulAssign for Felt {
226    /// # Panics
227    ///
228    /// If the primes are different.
229    fn mul_assign(&mut self, rhs: Self) {
230        *self = *self * rhs;
231    }
232}
233
234impl Neg for Felt {
235    type Output = Self;
236
237    fn neg(self) -> Self::Output {
238        self.replace(self.prime().value() - self.as_ref())
239    }
240}
241
242impl std::fmt::Display for Felt {
243    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
244        write!(f, "{}", self.as_ref())
245    }
246}
247
248#[allow(missing_docs)]
249#[cfg(test)]
250pub mod tests {
251
252    use super::*;
253    use ff::PrimeField;
254    use halo2curves::bn256::Fq;
255    use num_bigint::BigInt;
256    use quickcheck_macros::quickcheck;
257
258    /// Implementation of BabyBear used for testing the [`Felt`](super::Felt) type.
259    #[derive(PrimeField)]
260    #[PrimeFieldModulus = "2013265921"]
261    #[PrimeFieldGenerator = "31"]
262    #[PrimeFieldReprEndianness = "little"]
263    pub struct BabyBear([u64; 1]);
264    const BABYBEAR: u32 = 2013265921;
265
266    #[quickcheck]
267    fn partial_eq_for_other_types(x: u32) {
268        let v: u32 = x % BABYBEAR;
269        let v_f = Felt::new(BabyBear::from(x as u64));
270        if x < BABYBEAR {
271            assert_eq!(v, x);
272        } else {
273            assert_ne!(v, x);
274        }
275        assert_eq!(v_f, x);
276    }
277
278    #[quickcheck]
279    fn mul(x: u32, y: u32) {
280        let r = Felt::new(BabyBear::from(x as u64)) * Felt::new(BabyBear::from(y as u64));
281        let e = (BigUint::from(x) * BigUint::from(y)) % BigUint::from(BABYBEAR);
282
283        assert_eq!(r.as_ref(), &e);
284    }
285
286    #[quickcheck]
287    fn sum(x: u32, y: u32) {
288        let r = Felt::new(BabyBear::from(x as u64)) + Felt::new(BabyBear::from(y as u64));
289        let e = (BigUint::from(x) + BigUint::from(y)) % BigUint::from(BABYBEAR);
290
291        assert_eq!(r.as_ref(), &e);
292    }
293
294    #[quickcheck]
295    fn sub(x: u32, y: u32) {
296        let r = Felt::new(BabyBear::from(x as u64)) - Felt::new(BabyBear::from(y as u64));
297        let e = if x >= y {
298            (BigUint::from(x) - BigUint::from(y)) % BigUint::from(BABYBEAR)
299        } else {
300            let b = BigInt::from(BABYBEAR);
301            let mut i = BigInt::from(x) - BigInt::from(y);
302            while i.sign() == num_bigint::Sign::Minus {
303                i += &b;
304            }
305            i.try_into().unwrap()
306        };
307
308        assert_eq!(r.as_ref(), &e);
309    }
310
311    #[quickcheck]
312    fn same_prime_eq(i: u64) {
313        let x = Felt::new(BabyBear::from(i));
314        let y = Felt::new(BabyBear::from(i));
315        assert_eq!(x, y);
316    }
317
318    #[quickcheck]
319    fn different_primes_eq(i: u64) {
320        let x = Felt::new(BabyBear::from(i));
321        let y = Felt::new(Fq::from(i));
322        assert_ne!(x, y);
323    }
324
325    #[quickcheck]
326    #[should_panic]
327    fn different_primes_sum(a: u64, b: u64) {
328        let a = Felt::new(BabyBear::from(a));
329        let b = Felt::new(Fq::from(b));
330        let _ = a + b;
331    }
332
333    #[quickcheck]
334    #[should_panic]
335    fn different_primes_sum_assign(a: u64, b: u64) {
336        let mut a = Felt::new(BabyBear::from(a));
337        let b = Felt::new(Fq::from(b));
338        a += b;
339    }
340
341    #[quickcheck]
342    #[should_panic]
343    fn different_primes_mul(a: u64, b: u64) {
344        let a = Felt::new(BabyBear::from(a));
345        let b = Felt::new(Fq::from(b));
346        let _ = a * b;
347    }
348
349    #[quickcheck]
350    #[should_panic]
351    fn different_primes_mul_assign(a: u64, b: u64) {
352        let mut a = Felt::new(BabyBear::from(a));
353        let b = Felt::new(Fq::from(b));
354        a *= b;
355    }
356
357    #[quickcheck]
358    #[should_panic]
359    fn different_primes_sub(a: u64, b: u64) {
360        let a = Felt::new(BabyBear::from(a));
361        let b = Felt::new(Fq::from(b));
362        let _ = a - b;
363    }
364
365    #[quickcheck]
366    #[should_panic]
367    fn different_primes_sub_assign(a: u64, b: u64) {
368        let mut a = Felt::new(BabyBear::from(a));
369        let b = Felt::new(Fq::from(b));
370        a -= b;
371    }
372
373    #[quickcheck]
374    #[should_panic]
375    fn different_primes_rem(a: u64, b: u64) {
376        let a = Felt::new(BabyBear::from(a));
377        let b = Felt::new(Fq::from(b));
378        let _ = a % b;
379    }
380
381    #[quickcheck]
382    #[should_panic]
383    fn different_primes_rem_assign(a: u64, b: u64) {
384        let mut a = Felt::new(BabyBear::from(a));
385        let b = Felt::new(Fq::from(b));
386        a %= b;
387    }
388}
haloumi_core/felt.rs

haloumi_core/
felt.rs
