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

haloumi_core/
felt.rs
