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

haloumi_core/
felt.rs
