cairo_felt/
lib_bigint_felt.rs

1use crate::ParseFeltError;
2
3use crate::bigint_felt::{FeltBigInt, FIELD_HIGH, FIELD_LOW};
4use num_bigint::{BigInt, BigUint, U64Digits};
5use num_integer::Integer;
6use num_traits::{Bounded, FromPrimitive, Num, One, Pow, Signed, ToPrimitive, Zero};
7use serde::{Deserialize, Serialize};
8
9use core::{
10    convert::Into,
11    fmt,
12    iter::Sum,
13    ops::{
14        Add, AddAssign, BitAnd, BitOr, BitXor, Div, Mul, MulAssign, Neg, Rem, Shl, Shr, ShrAssign,
15        Sub, SubAssign,
16    },
17};
18
19#[cfg(all(not(feature = "std"), feature = "alloc"))]
20use alloc::{string::String, vec::Vec};
21
22#[cfg(all(feature = "arbitrary", feature = "std"))]
23use arbitrary::Arbitrary;
24
25pub(crate) trait FeltOps {
26    fn new<T: Into<FeltBigInt<FIELD_HIGH, FIELD_LOW>>>(value: T) -> Self;
27
28    fn modpow(
29        &self,
30        exponent: &FeltBigInt<FIELD_HIGH, FIELD_LOW>,
31        modulus: &FeltBigInt<FIELD_HIGH, FIELD_LOW>,
32    ) -> Self;
33
34    fn iter_u64_digits(&self) -> U64Digits;
35
36    #[cfg(any(feature = "std", feature = "alloc"))]
37    fn to_signed_bytes_le(&self) -> Vec<u8>;
38
39    #[cfg(any(feature = "std", feature = "alloc"))]
40    fn to_bytes_be(&self) -> Vec<u8>;
41
42    fn parse_bytes(buf: &[u8], radix: u32) -> Option<FeltBigInt<FIELD_HIGH, FIELD_LOW>>;
43
44    fn from_bytes_be(bytes: &[u8]) -> Self;
45
46    fn from_bytes_le(bytes: &[u8]) -> Self;
47
48    #[cfg(any(feature = "std", feature = "alloc"))]
49    fn to_str_radix(&self, radix: u32) -> String;
50
51    fn to_signed_felt(&self) -> BigInt;
52
53    fn to_bigint(&self) -> BigInt;
54
55    fn to_biguint(&self) -> BigUint;
56
57    fn bits(&self) -> u64;
58
59    fn prime() -> BigUint;
60}
61
62#[macro_export]
63macro_rules! felt_str {
64    ($val: expr) => {
65        $crate::Felt252::parse_bytes($val.as_bytes(), 10_u32).expect("Couldn't parse bytes")
66    };
67    ($val: expr, $opt: expr) => {
68        $crate::Felt252::parse_bytes($val.as_bytes(), $opt as u32).expect("Couldn't parse bytes")
69    };
70}
71
72#[cfg_attr(all(feature = "arbitrary", feature = "std"), derive(Arbitrary))]
73#[derive(Eq, Hash, PartialEq, PartialOrd, Ord, Clone, Deserialize, Default, Serialize)]
74pub struct Felt252 {
75    pub(crate) value: FeltBigInt<FIELD_HIGH, FIELD_LOW>,
76}
77
78macro_rules! from_num {
79    ($type:ty) => {
80        impl From<$type> for Felt252 {
81            fn from(value: $type) -> Self {
82                Self {
83                    value: value.into(),
84                }
85            }
86        }
87    };
88}
89
90from_num!(i8);
91from_num!(i16);
92from_num!(i32);
93from_num!(i64);
94from_num!(i128);
95from_num!(isize);
96from_num!(u8);
97from_num!(u16);
98from_num!(u32);
99from_num!(u64);
100from_num!(u128);
101from_num!(usize);
102from_num!(BigInt);
103from_num!(&BigInt);
104from_num!(BigUint);
105from_num!(&BigUint);
106
107impl From<bool> for Felt252 {
108    fn from(flag: bool) -> Self {
109        if flag {
110            Self::one()
111        } else {
112            Self::zero()
113        }
114    }
115}
116
117impl Felt252 {
118    pub fn new<T: Into<Felt252>>(value: T) -> Self {
119        value.into()
120    }
121
122    #[deprecated]
123    pub fn modpow(&self, exponent: &Felt252, modulus: &Felt252) -> Self {
124        Self {
125            value: self.value.modpow(&exponent.value, &modulus.value),
126        }
127    }
128
129    pub fn iter_u64_digits(&self) -> U64Digits {
130        self.value.iter_u64_digits()
131    }
132
133    pub fn to_le_bytes(&self) -> [u8; 32] {
134        let mut res = [0u8; 32];
135        let mut iter = self.iter_u64_digits();
136        let (d0, d1, d2, d3) = (
137            iter.next().unwrap_or_default().to_le_bytes(),
138            iter.next().unwrap_or_default().to_le_bytes(),
139            iter.next().unwrap_or_default().to_le_bytes(),
140            iter.next().unwrap_or_default().to_le_bytes(),
141        );
142        res[..8].copy_from_slice(&d0);
143        res[8..16].copy_from_slice(&d1);
144        res[16..24].copy_from_slice(&d2);
145        res[24..].copy_from_slice(&d3);
146        res
147    }
148
149    pub fn to_be_bytes(&self) -> [u8; 32] {
150        let mut bytes = self.to_le_bytes();
151        bytes.reverse();
152        bytes
153    }
154
155    pub fn to_le_digits(&self) -> [u64; 4] {
156        let mut iter = self.iter_u64_digits();
157        [
158            iter.next().unwrap_or_default(),
159            iter.next().unwrap_or_default(),
160            iter.next().unwrap_or_default(),
161            iter.next().unwrap_or_default(),
162        ]
163    }
164
165    #[cfg(any(feature = "std", feature = "alloc"))]
166    #[deprecated]
167    pub fn to_signed_bytes_le(&self) -> Vec<u8> {
168        // NOTE: this is unsigned
169        self.value.to_signed_bytes_le()
170    }
171    #[cfg(any(feature = "std", feature = "alloc"))]
172    pub fn to_bytes_be(&self) -> Vec<u8> {
173        self.value.to_bytes_be()
174    }
175
176    pub fn parse_bytes(buf: &[u8], radix: u32) -> Option<Self> {
177        Some(Self {
178            value: FeltBigInt::parse_bytes(buf, radix)?,
179        })
180    }
181    pub fn from_bytes_be(bytes: &[u8]) -> Self {
182        Self {
183            value: FeltBigInt::from_bytes_be(bytes),
184        }
185    }
186    pub fn from_bytes_le(bytes: &[u8]) -> Self {
187        Self {
188            value: FeltBigInt::from_bytes_le(bytes),
189        }
190    }
191    pub fn from_bytes_ne(bytes: &[u8]) -> Self {
192        // Call either version depending on target endianness
193        #[cfg(target_endian = "little")]
194        let res = Self::from_bytes_le(bytes);
195        #[cfg(target_endian = "big")]
196        let res = Self::from_bytes_be(bytes);
197        res
198    }
199    #[cfg(any(feature = "std", feature = "alloc"))]
200    pub fn to_str_radix(&self, radix: u32) -> String {
201        self.value.to_str_radix(radix)
202    }
203
204    /// Converts [`Felt252`] into a [`BigInt`] number in the range: `(- FIELD / 2, FIELD / 2)`.
205    ///
206    /// # Examples
207    ///
208    /// ```
209    /// # use crate::cairo_felt::Felt252;
210    /// # use num_bigint::BigInt;
211    /// # use num_traits::Bounded;
212    /// let positive = Felt252::new(5);
213    /// assert_eq!(positive.to_signed_felt(), Into::<num_bigint::BigInt>::into(5));
214    ///
215    /// let negative = Felt252::max_value();
216    /// assert_eq!(negative.to_signed_felt(), Into::<num_bigint::BigInt>::into(-1));
217    /// ```
218    pub fn to_signed_felt(&self) -> BigInt {
219        #[allow(deprecated)]
220        self.value.to_signed_felt()
221    }
222
223    // Converts [`Felt252`]'s representation directly into a [`BigInt`].
224    // Equivalent to doing felt.to_biguint().to_bigint().
225    pub fn to_bigint(&self) -> BigInt {
226        #[allow(deprecated)]
227        self.value.to_bigint()
228    }
229
230    /// Converts [`Felt252`] into a [`BigUint`] number.
231    ///
232    /// # Examples
233    ///
234    /// ```
235    /// # use crate::cairo_felt::Felt252;
236    /// # use num_bigint::BigUint;
237    /// # use num_traits::{Num, Bounded};
238    /// let positive = Felt252::new(5);
239    /// assert_eq!(positive.to_biguint(), Into::<num_bigint::BigUint>::into(5_u32));
240    ///
241    /// let negative = Felt252::max_value();
242    /// assert_eq!(negative.to_biguint(), BigUint::from_str_radix("800000000000011000000000000000000000000000000000000000000000000", 16).unwrap());
243    /// ```
244    pub fn to_biguint(&self) -> BigUint {
245        #[allow(deprecated)]
246        self.value.to_biguint()
247    }
248    pub fn sqrt(&self) -> Self {
249        // Based on Tonelli-Shanks' algorithm for finding square roots
250        // and sympy's library implementation of said algorithm.
251        if self.is_zero() || self.is_one() {
252            return self.clone();
253        }
254
255        let max_felt = Felt252::max_value();
256        let trailing_prime = Felt252::max_value() >> 192; // 0x800000000000011
257
258        let a = self.pow(&trailing_prime);
259        let d = (&Felt252::new(3_i32)).pow(&trailing_prime);
260        let mut m = Felt252::zero();
261        let mut exponent = Felt252::one() << 191_u32;
262        let mut adm;
263        for i in 0..192_u32 {
264            adm = &a * &(&d).pow(&m);
265            adm = (&adm).pow(&exponent);
266            exponent >>= 1;
267            // if adm ≡ -1 (mod CAIRO_PRIME)
268            if adm == max_felt {
269                m += Felt252::one() << i;
270            }
271        }
272        let root_1 = self.pow(&((trailing_prime + 1_u32) >> 1)) * (&d).pow(&(m >> 1));
273        let root_2 = &max_felt - &root_1 + 1_usize;
274        if root_1 < root_2 {
275            root_1
276        } else {
277            root_2
278        }
279    }
280
281    pub fn bits(&self) -> u64 {
282        self.value.bits()
283    }
284
285    pub fn prime() -> BigUint {
286        FeltBigInt::prime()
287    }
288}
289
290impl Add for Felt252 {
291    type Output = Self;
292    fn add(self, rhs: Self) -> Self {
293        Self {
294            value: self.value + rhs.value,
295        }
296    }
297}
298
299impl<'a> Add for &'a Felt252 {
300    type Output = Felt252;
301    fn add(self, rhs: Self) -> Self::Output {
302        Self::Output {
303            value: &self.value + &rhs.value,
304        }
305    }
306}
307
308impl<'a> Add<&'a Felt252> for Felt252 {
309    type Output = Self;
310    fn add(self, rhs: &Self) -> Self::Output {
311        Self::Output {
312            value: self.value + &rhs.value,
313        }
314    }
315}
316
317impl Add<u32> for Felt252 {
318    type Output = Self;
319    fn add(self, rhs: u32) -> Self {
320        Self {
321            value: self.value + rhs,
322        }
323    }
324}
325
326impl Add<usize> for Felt252 {
327    type Output = Self;
328    fn add(self, rhs: usize) -> Self {
329        Self {
330            value: self.value + rhs,
331        }
332    }
333}
334
335impl<'a> Add<usize> for &'a Felt252 {
336    type Output = Felt252;
337    fn add(self, rhs: usize) -> Self::Output {
338        Self::Output {
339            value: &self.value + rhs,
340        }
341    }
342}
343
344impl Add<u64> for &Felt252 {
345    type Output = Felt252;
346    fn add(self, rhs: u64) -> Self::Output {
347        Self::Output {
348            value: &self.value + rhs,
349        }
350    }
351}
352
353// This is special cased and optimized compared to the obvious implementation
354// due to `pc_update` relying on this, which makes it a major bottleneck for
355// execution. Testing for this function is extensive, comprised of explicit
356// edge and special cases testing and property tests, all comparing to the
357// more intuitive `(rhs + self).to_u64()` implementation.
358// This particular implementation is much more complex than a slightly more
359// intuitive one based on a single match. However, this is 8-62% faster
360// depending on the case being bencharked, with an average of 32%, so it's
361// worth it.
362impl Add<&Felt252> for u64 {
363    type Output = Option<u64>;
364
365    fn add(self, rhs: &Felt252) -> Option<u64> {
366        const PRIME_DIGITS_LE_HI: (u64, u64, u64) =
367            (0x0000000000000000, 0x0000000000000000, 0x0800000000000011);
368        const PRIME_MINUS_U64_MAX_DIGITS_LE_HI: (u64, u64, u64) =
369            (0xffffffffffffffff, 0xffffffffffffffff, 0x0800000000000010);
370
371        // Iterate through the 64 bits digits in little-endian order to
372        // characterize how the sum will behave.
373        let mut rhs_digits = rhs.iter_u64_digits();
374        // No digits means `rhs` is `0`, so the sum is simply `self`.
375        let Some(low) = rhs_digits.next() else {
376            return Some(self);
377        };
378        // A single digit means this is effectively the sum of two `u64` numbers.
379        let Some(h0) = rhs_digits.next() else {
380            return self.checked_add(low)
381        };
382        // Now we need to compare the 3 most significant digits.
383        // There are two relevant cases from now on, either `rhs` behaves like a
384        // substraction of a `u64` or the result of the sum falls out of range.
385        let (h1, h2) = (rhs_digits.next()?, rhs_digits.next()?);
386        match (h0, h1, h2) {
387            // The 3 MSB only match the prime for Felt252::max_value(), which is -1
388            // in the signed field, so this is equivalent to substracting 1 to `self`.
389            #[allow(clippy::suspicious_arithmetic_impl)]
390            PRIME_DIGITS_LE_HI => self.checked_sub(1),
391            // For the remaining values between `[-u64::MAX..0]` (where `{0, -1}` have
392            // already been covered) the MSB matches that of `PRIME - u64::MAX`.
393            // Because we're in the negative number case, we count down. Because `0`
394            // and `-1` correspond to different MSBs, `0` and `1` in the LSB are less
395            // than `-u64::MAX`, the smallest value we can add to (read, substract it's
396            // magnitude from) a `u64` number, meaning we exclude them from the valid
397            // case.
398            // For the remaining range, we make take the absolute value module-2 while
399            // correcting by substracting `1` (note we actually substract `2` because
400            // the absolute value itself requires substracting `1`.
401            #[allow(clippy::suspicious_arithmetic_impl)]
402            PRIME_MINUS_U64_MAX_DIGITS_LE_HI if low >= 2 => {
403                (self).checked_sub(u64::MAX - (low - 2))
404            }
405            // Any other case will result in an addition that is out of bounds, so
406            // the addition fails, returning `None`.
407            _ => None,
408        }
409    }
410}
411
412impl AddAssign for Felt252 {
413    fn add_assign(&mut self, rhs: Self) {
414        self.value += rhs.value;
415    }
416}
417
418impl<'a> AddAssign<&'a Felt252> for Felt252 {
419    fn add_assign(&mut self, rhs: &Self) {
420        self.value += &rhs.value;
421    }
422}
423
424impl Sum for Felt252 {
425    fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
426        iter.fold(Felt252::zero(), |mut acc, x| {
427            acc += x;
428            acc
429        })
430    }
431}
432
433impl Neg for Felt252 {
434    type Output = Self;
435    fn neg(self) -> Self {
436        Self {
437            value: self.value.neg(),
438        }
439    }
440}
441
442impl<'a> Neg for &'a Felt252 {
443    type Output = Felt252;
444    fn neg(self) -> Self::Output {
445        Self::Output {
446            value: (&self.value).neg(),
447        }
448    }
449}
450
451impl Sub for Felt252 {
452    type Output = Self;
453    fn sub(self, rhs: Self) -> Self {
454        Self {
455            value: self.value - rhs.value,
456        }
457    }
458}
459
460impl<'a> Sub for &'a Felt252 {
461    type Output = Felt252;
462    fn sub(self, rhs: Self) -> Self::Output {
463        Self::Output {
464            value: &self.value - &rhs.value,
465        }
466    }
467}
468
469impl<'a> Sub<&'a Felt252> for Felt252 {
470    type Output = Self;
471    fn sub(self, rhs: &Self) -> Self {
472        Self {
473            value: self.value - &rhs.value,
474        }
475    }
476}
477
478impl Sub<&Felt252> for usize {
479    type Output = Felt252;
480    fn sub(self, rhs: &Self::Output) -> Self::Output {
481        Self::Output {
482            value: self - &rhs.value,
483        }
484    }
485}
486
487impl SubAssign for Felt252 {
488    fn sub_assign(&mut self, rhs: Self) {
489        self.value -= rhs.value
490    }
491}
492
493impl<'a> SubAssign<&'a Felt252> for Felt252 {
494    fn sub_assign(&mut self, rhs: &Self) {
495        self.value -= &rhs.value;
496    }
497}
498
499impl Sub<u32> for Felt252 {
500    type Output = Self;
501    fn sub(self, rhs: u32) -> Self {
502        Self {
503            value: self.value - rhs,
504        }
505    }
506}
507
508impl<'a> Sub<u32> for &'a Felt252 {
509    type Output = Felt252;
510    fn sub(self, rhs: u32) -> Self::Output {
511        Self::Output {
512            value: &self.value - rhs,
513        }
514    }
515}
516
517impl Sub<usize> for Felt252 {
518    type Output = Self;
519    fn sub(self, rhs: usize) -> Self {
520        Self {
521            value: self.value - rhs,
522        }
523    }
524}
525
526impl Mul for Felt252 {
527    type Output = Self;
528    fn mul(self, rhs: Self) -> Self {
529        Self {
530            value: self.value * rhs.value,
531        }
532    }
533}
534
535impl<'a> Mul for &'a Felt252 {
536    type Output = Felt252;
537    fn mul(self, rhs: Self) -> Self::Output {
538        Self::Output {
539            value: &self.value * &rhs.value,
540        }
541    }
542}
543
544impl<'a> Mul<&'a Felt252> for Felt252 {
545    type Output = Self;
546    fn mul(self, rhs: &Self) -> Self {
547        Self {
548            value: self.value * &rhs.value,
549        }
550    }
551}
552
553impl<'a> MulAssign<&'a Felt252> for Felt252 {
554    fn mul_assign(&mut self, rhs: &Self) {
555        self.value *= &rhs.value;
556    }
557}
558
559impl Pow<u32> for Felt252 {
560    type Output = Self;
561    fn pow(self, rhs: u32) -> Self {
562        Self {
563            value: self.value.pow(rhs),
564        }
565    }
566}
567
568impl<'a> Pow<u32> for &'a Felt252 {
569    type Output = Felt252;
570    fn pow(self, rhs: u32) -> Self::Output {
571        Self::Output {
572            value: (&self.value).pow(rhs),
573        }
574    }
575}
576
577impl<'a> Pow<&'a Felt252> for &'a Felt252 {
578    type Output = Felt252;
579    fn pow(self, rhs: &'a Felt252) -> Self::Output {
580        Self::Output {
581            value: (&self.value).pow(&rhs.value),
582        }
583    }
584}
585
586impl Div for Felt252 {
587    type Output = Self;
588    fn div(self, rhs: Self) -> Self {
589        Self {
590            value: self.value / rhs.value,
591        }
592    }
593}
594
595impl<'a> Div for &'a Felt252 {
596    type Output = Felt252;
597    fn div(self, rhs: Self) -> Self::Output {
598        Self::Output {
599            value: &self.value / &rhs.value,
600        }
601    }
602}
603
604impl<'a> Div<Felt252> for &'a Felt252 {
605    type Output = Felt252;
606    fn div(self, rhs: Self::Output) -> Self::Output {
607        Self::Output {
608            value: &self.value / rhs.value,
609        }
610    }
611}
612
613impl Rem for Felt252 {
614    type Output = Self;
615    fn rem(self, rhs: Self) -> Self {
616        Self {
617            value: self.value % rhs.value,
618        }
619    }
620}
621
622impl<'a> Rem<&'a Felt252> for Felt252 {
623    type Output = Self;
624    fn rem(self, rhs: &Self) -> Self {
625        Self {
626            value: self.value % &rhs.value,
627        }
628    }
629}
630
631impl Zero for Felt252 {
632    fn zero() -> Self {
633        Self {
634            value: FeltBigInt::zero(),
635        }
636    }
637
638    fn is_zero(&self) -> bool {
639        self.value.is_zero()
640    }
641}
642
643impl One for Felt252 {
644    fn one() -> Self {
645        Self {
646            value: FeltBigInt::one(),
647        }
648    }
649
650    fn is_one(&self) -> bool {
651        self.value.is_one()
652    }
653}
654
655impl Bounded for Felt252 {
656    fn min_value() -> Self {
657        Self {
658            value: FeltBigInt::min_value(),
659        }
660    }
661
662    fn max_value() -> Self {
663        Self {
664            value: FeltBigInt::max_value(),
665        }
666    }
667}
668
669impl Num for Felt252 {
670    type FromStrRadixErr = ParseFeltError;
671    fn from_str_radix(string: &str, radix: u32) -> Result<Self, Self::FromStrRadixErr> {
672        Ok(Self {
673            value: FeltBigInt::from_str_radix(string, radix)?,
674        })
675    }
676}
677
678impl Integer for Felt252 {
679    fn div_floor(&self, rhs: &Self) -> Self {
680        Self {
681            value: self.value.div_floor(&rhs.value),
682        }
683    }
684
685    fn div_rem(&self, other: &Self) -> (Self, Self) {
686        let (div, rem) = self.value.div_rem(&other.value);
687        (Self { value: div }, Self { value: rem })
688    }
689
690    fn divides(&self, other: &Self) -> bool {
691        self.value.divides(&other.value)
692    }
693
694    fn gcd(&self, other: &Self) -> Self {
695        Self {
696            value: self.value.gcd(&other.value),
697        }
698    }
699
700    fn is_even(&self) -> bool {
701        self.value.is_even()
702    }
703
704    fn is_multiple_of(&self, other: &Self) -> bool {
705        self.value.is_multiple_of(&other.value)
706    }
707
708    fn is_odd(&self) -> bool {
709        self.value.is_odd()
710    }
711
712    fn lcm(&self, other: &Self) -> Self {
713        Self {
714            value: self.value.lcm(&other.value),
715        }
716    }
717
718    fn mod_floor(&self, rhs: &Self) -> Self {
719        Self {
720            value: self.value.mod_floor(&rhs.value),
721        }
722    }
723}
724
725impl Signed for Felt252 {
726    fn abs(&self) -> Self {
727        Self {
728            value: self.value.abs(),
729        }
730    }
731
732    fn abs_sub(&self, other: &Self) -> Self {
733        Self {
734            value: self.value.abs_sub(&other.value),
735        }
736    }
737
738    fn signum(&self) -> Self {
739        Self {
740            value: self.value.signum(),
741        }
742    }
743
744    fn is_positive(&self) -> bool {
745        self.value.is_positive()
746    }
747
748    fn is_negative(&self) -> bool {
749        self.value.is_negative()
750    }
751}
752
753impl Shl<u32> for Felt252 {
754    type Output = Self;
755    fn shl(self, rhs: u32) -> Self {
756        Self {
757            value: self.value << rhs,
758        }
759    }
760}
761
762impl<'a> Shl<u32> for &'a Felt252 {
763    type Output = Felt252;
764    fn shl(self, rhs: u32) -> Self::Output {
765        Self::Output {
766            value: &self.value << rhs,
767        }
768    }
769}
770
771impl Shl<usize> for Felt252 {
772    type Output = Self;
773    fn shl(self, rhs: usize) -> Self {
774        Self {
775            value: self.value << rhs,
776        }
777    }
778}
779
780impl<'a> Shl<usize> for &'a Felt252 {
781    type Output = Felt252;
782    fn shl(self, rhs: usize) -> Self::Output {
783        Self::Output {
784            value: &self.value << rhs,
785        }
786    }
787}
788
789impl Shr<u32> for Felt252 {
790    type Output = Self;
791    fn shr(self, rhs: u32) -> Self {
792        Self {
793            value: self.value >> rhs,
794        }
795    }
796}
797
798impl<'a> Shr<u32> for &'a Felt252 {
799    type Output = Felt252;
800    fn shr(self, rhs: u32) -> Self::Output {
801        Self::Output {
802            value: &self.value >> rhs,
803        }
804    }
805}
806
807impl ShrAssign<usize> for Felt252 {
808    fn shr_assign(&mut self, rhs: usize) {
809        self.value >>= rhs
810    }
811}
812
813impl<'a> BitAnd for &'a Felt252 {
814    type Output = Felt252;
815    fn bitand(self, rhs: Self) -> Self::Output {
816        Self::Output {
817            value: &self.value & &rhs.value,
818        }
819    }
820}
821
822impl<'a> BitAnd<&'a Felt252> for Felt252 {
823    type Output = Self;
824    fn bitand(self, rhs: &Self) -> Self {
825        Self {
826            value: self.value & &rhs.value,
827        }
828    }
829}
830
831impl<'a> BitAnd<Felt252> for &'a Felt252 {
832    type Output = Felt252;
833    fn bitand(self, rhs: Self::Output) -> Self::Output {
834        Self::Output {
835            value: &self.value & rhs.value,
836        }
837    }
838}
839
840impl<'a> BitOr for &'a Felt252 {
841    type Output = Felt252;
842    fn bitor(self, rhs: Self) -> Self::Output {
843        Self::Output {
844            value: &self.value | &rhs.value,
845        }
846    }
847}
848
849impl<'a> BitXor for &'a Felt252 {
850    type Output = Felt252;
851    fn bitxor(self, rhs: Self) -> Self::Output {
852        Self::Output {
853            value: &self.value ^ &rhs.value,
854        }
855    }
856}
857
858impl ToPrimitive for Felt252 {
859    fn to_u128(&self) -> Option<u128> {
860        self.value.to_u128()
861    }
862
863    fn to_u64(&self) -> Option<u64> {
864        self.value.to_u64()
865    }
866
867    fn to_i64(&self) -> Option<i64> {
868        self.value.to_i64()
869    }
870}
871
872impl FromPrimitive for Felt252 {
873    fn from_u64(n: u64) -> Option<Self> {
874        FeltBigInt::from_u64(n).map(|n| Self { value: n })
875    }
876
877    fn from_i64(n: i64) -> Option<Self> {
878        FeltBigInt::from_i64(n).map(|n| Self { value: n })
879    }
880}
881
882impl fmt::Display for Felt252 {
883    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
884        write!(f, "{}", self.value)
885    }
886}
887
888impl fmt::Debug for Felt252 {
889    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
890        write!(f, "{}", self.value)
891    }
892}
893
894macro_rules! assert_felt_methods {
895    ($type:ty) => {
896        const _: () = {
897            fn assert_felt_ops<T: FeltOps>() {}
898            fn assertion() {
899                assert_felt_ops::<$type>();
900            }
901        };
902    };
903}
904
905macro_rules! assert_felt_impl {
906    ($type:ty) => {
907        const _: () = {
908            fn assert_add<T: Add>() {}
909            fn assert_add_ref<'a, T: Add<&'a $type>>() {}
910            fn assert_add_u32<T: Add<u32>>() {}
911            fn assert_add_usize<T: Add<usize>>() {}
912            fn assert_add_assign<T: AddAssign>() {}
913            fn assert_add_assign_ref<'a, T: AddAssign<&'a $type>>() {}
914            fn assert_sum<T: Sum<$type>>() {}
915            fn assert_neg<T: Neg>() {}
916            fn assert_sub<T: Sub>() {}
917            fn assert_sub_ref<'a, T: Sub<&'a $type>>() {}
918            fn assert_sub_assign<T: SubAssign>() {}
919            fn assert_sub_assign_ref<'a, T: SubAssign<&'a $type>>() {}
920            fn assert_sub_u32<T: Sub<u32>>() {}
921            fn assert_sub_usize<T: Sub<usize>>() {}
922            fn assert_mul<T: Mul>() {}
923            fn assert_mul_ref<'a, T: Mul<&'a $type>>() {}
924            fn assert_mul_assign_ref<'a, T: MulAssign<&'a $type>>() {}
925            fn assert_pow_u32<T: Pow<u32>>() {}
926            fn assert_pow_felt<'a, T: Pow<&'a $type>>() {}
927            fn assert_div<T: Div>() {}
928            fn assert_ref_div<T: Div<$type>>() {}
929            fn assert_rem<T: Rem>() {}
930            fn assert_rem_ref<'a, T: Rem<&'a $type>>() {}
931            fn assert_zero<T: Zero>() {}
932            fn assert_one<T: One>() {}
933            fn assert_bounded<T: Bounded>() {}
934            fn assert_num<T: Num>() {}
935            fn assert_integer<T: Integer>() {}
936            fn assert_signed<T: Signed>() {}
937            fn assert_shl_u32<T: Shl<u32>>() {}
938            fn assert_shl_usize<T: Shl<usize>>() {}
939            fn assert_shr_u32<T: Shr<u32>>() {}
940            fn assert_shr_assign_usize<T: ShrAssign<usize>>() {}
941            fn assert_bitand<T: BitAnd>() {}
942            fn assert_bitand_ref<'a, T: BitAnd<&'a $type>>() {}
943            fn assert_ref_bitand<T: BitAnd<$type>>() {}
944            fn assert_bitor<T: BitOr>() {}
945            fn assert_bitxor<T: BitXor>() {}
946            fn assert_from_primitive<T: FromPrimitive>() {}
947            fn assert_to_primitive<T: ToPrimitive>() {}
948            fn assert_display<T: fmt::Display>() {}
949            fn assert_debug<T: fmt::Debug>() {}
950
951            #[allow(dead_code)]
952            fn assert_all() {
953                assert_add::<$type>();
954                assert_add::<&$type>();
955                assert_add_ref::<$type>();
956                assert_add_u32::<$type>();
957                assert_add_usize::<$type>();
958                assert_add_usize::<&$type>();
959                assert_add_assign::<$type>();
960                assert_add_assign_ref::<$type>();
961                assert_sum::<$type>();
962                assert_neg::<$type>();
963                assert_neg::<&$type>();
964                assert_sub::<$type>();
965                assert_sub::<&$type>();
966                assert_sub_ref::<$type>();
967                assert_sub_assign::<$type>();
968                assert_sub_assign_ref::<$type>();
969                assert_sub_u32::<$type>();
970                assert_sub_u32::<&$type>();
971                assert_sub_usize::<$type>();
972                assert_mul::<$type>();
973                assert_mul::<&$type>();
974                assert_mul_ref::<$type>();
975                assert_mul_assign_ref::<$type>();
976                assert_pow_u32::<$type>();
977                assert_pow_felt::<&$type>();
978                assert_div::<$type>();
979                assert_div::<&$type>();
980                assert_ref_div::<&$type>();
981                assert_rem::<$type>();
982                assert_rem_ref::<$type>();
983                assert_zero::<$type>();
984                assert_one::<$type>();
985                assert_bounded::<$type>();
986                assert_num::<$type>();
987                assert_integer::<$type>();
988                assert_signed::<$type>();
989                assert_shl_u32::<$type>();
990                assert_shl_u32::<&$type>();
991                assert_shl_usize::<$type>();
992                assert_shl_usize::<&$type>();
993                assert_shr_u32::<$type>();
994                assert_shr_u32::<&$type>();
995                assert_shr_assign_usize::<$type>();
996                assert_bitand::<&$type>();
997                assert_bitand_ref::<$type>();
998                assert_ref_bitand::<&$type>();
999                assert_bitor::<&$type>();
1000                assert_bitxor::<&$type>();
1001                assert_from_primitive::<$type>();
1002                assert_to_primitive::<$type>();
1003                assert_display::<$type>();
1004                assert_debug::<$type>();
1005            }
1006        };
1007    };
1008}
1009
1010assert_felt_methods!(FeltBigInt<FIELD_HIGH, FIELD_LOW>);
1011assert_felt_impl!(FeltBigInt<FIELD_HIGH, FIELD_LOW>);
1012assert_felt_impl!(Felt252);
1013
1014#[cfg(test)]
1015mod test {
1016    use super::*;
1017    use crate::{arbitrary::nonzero_felt252, PRIME_STR};
1018    use core::cmp;
1019    use rstest::rstest;
1020
1021    use proptest::prelude::*;
1022
1023    proptest! {
1024        #[test]
1025        #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1026        // Property-based test that ensures, for 100 felt values that are randomly generated
1027        // each time tests are run, that a new felt doesn't fall outside the range [0, p].
1028        // In this and some of the following tests, The value of {x} can be either [0] or a
1029        // very large number, in order to try to overflow the value of {p} and thus ensure the
1030        // modular arithmetic is working correctly.
1031        fn new_in_range(ref x in any::<[u8; 40]>()) {
1032            let x = Felt252::from_bytes_be(x);
1033            let p = &BigUint::parse_bytes(PRIME_STR[2..].as_bytes(), 16).unwrap();
1034            prop_assert!(&x.to_biguint() < p);
1035        }
1036
1037        #[test]
1038        #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1039        fn from_bytes_be(high: u128, low: u128) {
1040            let expected = (Felt252::from(high) << 128_usize) + Felt252::from(low);
1041            let mut bytes = [0; 32];
1042            // big-endian order: [ high, low ]
1043            bytes[..16].copy_from_slice(&high.to_be_bytes());
1044            bytes[16..].copy_from_slice(&low.to_be_bytes());
1045            let got = Felt252::from_bytes_be(&bytes);
1046            prop_assert_eq!(got, expected);
1047        }
1048
1049        #[test]
1050        #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1051        fn from_bytes_le(high: u128, low: u128) {
1052            let expected = (Felt252::from(high) << 128_usize) + Felt252::from(low);
1053            let mut bytes = [0; 32];
1054            // little-endian order: [ low, high ]
1055            bytes[..16].copy_from_slice(&low.to_le_bytes());
1056            bytes[16..].copy_from_slice(&high.to_le_bytes());
1057            let got = Felt252::from_bytes_le(&bytes);
1058            prop_assert_eq!(got, expected);
1059        }
1060
1061
1062        #[test]
1063        #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1064        fn to_be_bytes(ref x in any::<Felt252>()) {
1065            let bytes = x.to_be_bytes();
1066            let y = &Felt252::from_bytes_be(&bytes);
1067            prop_assert_eq!(x, y);
1068        }
1069
1070        #[test]
1071        #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1072        fn to_le_bytes(ref x in any::<Felt252>()) {
1073            let mut bytes = x.to_le_bytes();
1074            // Convert to big endian for test
1075            bytes.reverse();
1076            let y = &Felt252::from_bytes_be(&bytes);
1077            prop_assert_eq!(x, y);
1078        }
1079
1080        #[test]
1081        #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1082        fn to_le_digits(ref x in any::<Felt252>()) {
1083            let digits: [u64; 4] = x.to_le_digits();
1084            let mut bytes: Vec<_> = digits
1085                .into_iter()
1086                .flat_map(|x| x.to_le_bytes())
1087                .collect();
1088            // Convert to big endian for test
1089            bytes.reverse();
1090            let y = &Felt252::from_bytes_be(&bytes);
1091            prop_assert_eq!(x, y);
1092        }
1093
1094        #[test]
1095        #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1096        fn to_u128_ok(x in any::<u128>()) {
1097            let y = Felt252::from(x);
1098            let y = y.to_u128();
1099            prop_assert_eq!(Some(x), y);
1100        }
1101
1102        #[test]
1103        #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1104        fn to_u128_out_of_range(x in nonzero_felt252()) {
1105            let y = x + Felt252::from(u128::MAX);
1106            let y = y.to_u128();
1107            prop_assert_eq!(None, y);
1108        }
1109
1110        #[test]
1111        #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1112        // Property-based test that ensures, for 100 felt values that are randomly
1113        // generated each time tests are run, that a felt created using Felt252::from_bytes_be doesn't
1114        // fall outside the range [0, p].
1115        // In this and some of the following tests, The value of {x} can be either [0] or a very large number,
1116        // in order to try to overflow the value of {p} and thus ensure the modular arithmetic is working correctly.
1117        fn from_bytes_be_in_range(ref x in any::<[u8; 40]>()) {
1118            let x = Felt252::from_bytes_be(x);
1119            let max_felt = Felt252::max_value();
1120            prop_assert!(x <= max_felt);
1121        }
1122
1123        #[test]
1124        #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1125        // Property-based test that ensures, for 100 felt values that are randomly generated each time
1126        // tests are run, that the negative of a felt doesn't fall outside the range [0, p].
1127        fn neg_in_range(x in any::<Felt252>()) {
1128            let p = &BigUint::parse_bytes(PRIME_STR[2..].as_bytes(), 16).unwrap();
1129
1130            let neg = -x.clone();
1131            let as_uint = &neg.to_biguint();
1132            prop_assert!(as_uint < p);
1133
1134            // test reference variant
1135            let neg = -&x;
1136            let as_uint = &neg.to_biguint();
1137            prop_assert!(as_uint < p);
1138        }
1139
1140        #[test]
1141        #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1142        // Property-based test that ensures, for 100 {x} and {y} values that are randomly generated
1143        // each time tests are run, that a subtraction between two felts {x} and {y} and doesn't fall
1144        // outside the range [0, p]. The values of {x} and {y} can be either [0] or a very large number.
1145        fn sub(ref x in any::<Felt252>(), ref y in any::<Felt252>()) {
1146            let (x_int, y_int) = (&x.to_biguint(), &y.to_biguint());
1147            let p = &BigUint::parse_bytes(PRIME_STR[2..].as_bytes(), 16).unwrap();
1148
1149            let sub_xy = x - y;
1150            prop_assert!(&sub_xy.to_biguint() < p);
1151            prop_assert_eq!(Felt252::from(p + x_int - y_int), sub_xy);
1152
1153            let sub_yx = y - x;
1154            prop_assert!(&sub_yx.to_biguint() < p);
1155            prop_assert_eq!(Felt252::from(p + y_int - x_int), sub_yx);
1156        }
1157
1158        #[test]
1159        #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1160        // Property-based test that ensures, for 100 {x} and {y} values that are randomly generated
1161        // each time tests are run, that a subtraction with assignment between two felts {x} and {y}
1162        // and doesn't fall outside the range [0, p]. The values of {x} and {y} can be either [0] or a very large number.
1163        fn sub_assign_in_range(mut x in any::<Felt252>(), y in any::<Felt252>()) {
1164            let p = &BigUint::parse_bytes(PRIME_STR[2..].as_bytes(), 16).unwrap();
1165
1166            x -= y.clone();
1167            let as_uint = &x.to_biguint();
1168            prop_assert!(as_uint < p, "{}", as_uint);
1169
1170            // test reference variant
1171            x -= &y;
1172            let as_uint = &x.to_biguint();
1173            prop_assert!(as_uint < p, "{}", as_uint);
1174        }
1175
1176        #[test]
1177        #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1178        // Property-based test that ensures, for 100 {x} and {y} values that are randomly
1179        // generated each time tests are run, that a multiplication between two felts {x}
1180        // and {y} and doesn't fall outside the range [0, p]. The values of {x} and {y}
1181        // can be either [0] or a very large number.
1182        fn mul(ref x in any::<Felt252>(), ref y in any::<Felt252>()) {
1183            let xy_int = x.to_biguint() * y.to_biguint();
1184
1185            let p = &BigUint::parse_bytes(PRIME_STR[2..].as_bytes(), 16).unwrap();
1186
1187            let (xy, yx) = (x * y, y * x);
1188            prop_assert_eq!(&xy, &yx);
1189            prop_assert_eq!(xy.to_biguint(), xy_int.mod_floor(p));
1190            prop_assert!(&xy.to_biguint() < p);
1191        }
1192
1193        #[test]
1194        #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1195        // Property-based test that ensures, for 100 pairs of {x} and {y} values that
1196        // are randomly generated each time tests are run, that a multiplication with
1197        // assignment between two felts {x} and {y} and doesn't fall outside the range [0, p].
1198        // The values of {x} and {y} can be either [0] or a very large number.
1199        fn mul_assign_in_range(mut x in any::<Felt252>(), y in any::<Felt252>()) {
1200            let p = &BigUint::parse_bytes(PRIME_STR[2..].as_bytes(), 16).unwrap();
1201
1202            x *= &y;
1203            let as_uint = &x.to_biguint();
1204            prop_assert!(as_uint < p, "{}", as_uint);
1205        }
1206
1207        #[test]
1208        #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1209        // Property-based test that ensures, for 100 pairs of {x} and {y} values that are
1210        // randomly generated each time tests are run, that the result of the division of
1211        // {x} by {y} is the inverse multiplicative of {x} --that is, multiplying the result
1212        // by {y} returns the original number {x}. The values of {x} and {y} can be either
1213        // [0] or a very large number.
1214        fn div_is_mul_inv(ref x in any::<Felt252>(), ref y in nonzero_felt252()) {
1215            let p = &BigUint::parse_bytes(PRIME_STR[2..].as_bytes(), 16).unwrap();
1216            prop_assume!(!y.is_zero());
1217
1218            let q = x / y;
1219            let as_uint = &q.to_biguint();
1220            prop_assert!(as_uint < p, "{}", as_uint);
1221            prop_assert_eq!(&(q * y), x);
1222        }
1223
1224        #[test]
1225        #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1226        // Property-based test that ensures, for 100 {value}s that are randomly generated
1227        // each time tests are run, that performing a bit shift to the left by {shift_amount}
1228        // of bits (between 0 and 999) returns a result that is inside of the range [0, p].
1229        fn shift_left_in_range(value in any::<Felt252>(), shift_amount in 0..1000_u32){
1230            let p = &BigUint::parse_bytes(PRIME_STR[2..].as_bytes(), 16).unwrap();
1231
1232            let result = (value.clone() << shift_amount).to_biguint();
1233            prop_assert!(&result < p);
1234
1235            let result = (&value << shift_amount).to_biguint();
1236            prop_assert!(&result < p);
1237        }
1238
1239        #[test]
1240        #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1241        // Property-based test that ensures, for 100 {value}s that are randomly
1242        // generated each time tests are run, that performing a bit shift to the right
1243        // by {shift_amount} of bits (between 0 and 999) returns a result that is inside of the range [0, p].
1244        fn shift_right_in_range(value in any::<Felt252>(), shift_amount in 0..1000_u32){
1245            let result = (value >> shift_amount).to_biguint();
1246            let p = &BigUint::parse_bytes(PRIME_STR[2..].as_bytes(), 16).unwrap();
1247            prop_assert!(&result < p);
1248        }
1249
1250        #[test]
1251        #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1252        // Property-based test that ensures, for 100 {value}s that are randomly generated
1253        // each time tests are run, that performing a bit shift to the right by {shift_amount}
1254        // of bits (between 0 and 999), with assignment, returns a result that is inside of the range [0, p].
1255        // "With assignment" means that the result of the operation is autommatically assigned
1256        // to the variable value, replacing its previous content.
1257        fn shift_right_assign_in_range(mut value in any::<Felt252>(), shift_amount in 0..1000_usize){
1258            let p = BigUint::parse_bytes(PRIME_STR[2..].as_bytes(), 16).unwrap();
1259            value >>= shift_amount;
1260            prop_assert!(value.to_biguint() < p);
1261        }
1262
1263        #[test]
1264        #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1265        // Property based test that ensures, for 100 pairs of values {x} and {y}
1266        // generated at random each time tests are run, that performing a BitAnd
1267        // operation between them returns a result that is inside of the range [0, p].
1268        fn bitand_in_range(x in any::<Felt252>(), y in any::<Felt252>()){
1269            let p = BigUint::parse_bytes(PRIME_STR[2..].as_bytes(), 16).unwrap();
1270            let result = x & &y;
1271            result.to_biguint();
1272            prop_assert!(result.to_biguint() < p);
1273        }
1274
1275        #[test]
1276        #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1277        // Property based test that ensures, for 100 pairs of values {x} and {y}
1278        // generated at random each time tests are run, that performing a BitOr
1279        // operation between them returns a result that is inside of the range [0, p].
1280        fn bitor_in_range(x in any::<Felt252>(), y in any::<Felt252>()){
1281            let p = BigUint::parse_bytes(PRIME_STR[2..].as_bytes(), 16).unwrap();
1282            let result = &x | &y;
1283            prop_assert!(result.to_biguint() < p);
1284        }
1285
1286        #[test]
1287        #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1288        // Property based test that ensures, for 100 pairs of values {x} and {y}
1289        // generated at random each time tests are run, that performing a BitXor
1290        // operation between them returns a result that is inside of the range [0, p].
1291        fn bitxor_in_range(x in any::<Felt252>(), y in any::<Felt252>()){
1292            let p = BigUint::parse_bytes(PRIME_STR[2..].as_bytes(), 16).unwrap();
1293            let result = &x ^ &y;
1294            prop_assert!(result.to_biguint() < p);
1295        }
1296
1297        #[test]
1298        #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1299        // Property-based test that ensures, for 100 values {x} that are randomly
1300        // generated each time tests are run, that raising {x} to the {y}th power
1301        // returns a result that is inside of the range [0, p].
1302        fn pow_in_range(base in any::<Felt252>(), exp in 0..100_u32){
1303            let p = &BigUint::parse_bytes(PRIME_STR[2..].as_bytes(), 16).unwrap();
1304
1305            let result = Pow::pow(base.clone(), exp);
1306            let as_uint = &result.to_biguint();
1307            prop_assert!(as_uint < p, "{}", as_uint);
1308
1309            // test reference variant
1310            let result = Pow::pow(&base, exp);
1311            let as_uint = &result.to_biguint();
1312            prop_assert!(as_uint < p, "{}", as_uint);
1313        }
1314
1315        #[test]
1316        #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1317        // Property-based test that ensures, for 100 values {x} that are randomly
1318        // generated each time tests are run, that raising {x} to the {y}th power
1319        // returns a result that is inside of the range [0, p].
1320        fn pow_felt_in_range(base in any::<Felt252>(), exponent in any::<Felt252>()){
1321            let p = BigUint::parse_bytes(PRIME_STR[2..].as_bytes(), 16).unwrap();
1322
1323            let result = Pow::pow(&base, &exponent);
1324            let as_uint = result.to_biguint();
1325            prop_assert!(as_uint < p, "{}", as_uint);
1326
1327            // test reference variant
1328            let result: Felt252 = Pow::pow(&base, &exponent);
1329            let as_uint = result.to_biguint();
1330            prop_assert!(as_uint < p, "{}", as_uint);
1331        }
1332
1333        #[test]
1334        #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1335        // Property based test that ensures, for 100 pairs of values {x} and {y}
1336        // generated at random each time tests are run, that performing a Sum operation
1337        // between them returns a result that is inside of the range [0, p].
1338        fn sum_in_range(x in any::<Felt252>(), y in any::<Felt252>()){
1339            let p = &BigUint::parse_bytes(PRIME_STR[2..].as_bytes(), 16).unwrap();
1340
1341            let result = x + y;
1342            let as_uint = &result.to_biguint();
1343            prop_assert!(as_uint < p, "{}", as_uint);
1344        }
1345
1346        #[test]
1347        #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1348        // Property test to check that the remainder of a division between 100 pairs of
1349        // values {x} and {y},generated at random each time tests are run, falls in the
1350        // range [0, p]. x and y can either take the value of 0 or a large integer.
1351        // In Cairo, the result of x / y is defined to always satisfy the equation
1352        // (x / y) * y == x, so the remainder is 0 most of the time.
1353        fn rem_in_range(x in any::<Felt252>(), y in nonzero_felt252()) {
1354            let p = &BigUint::parse_bytes(PRIME_STR[2..].as_bytes(), 16).unwrap();
1355
1356            let result = x.clone() % y.clone();
1357            let as_uint = &result.to_biguint();
1358            prop_assert!(as_uint < p, "{}", as_uint);
1359
1360            // test reference variant
1361            let result = x % &y;
1362            let as_uint = &result.to_biguint();
1363            prop_assert!(as_uint < p, "{}", as_uint);
1364        }
1365
1366        #[test]
1367        #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1368        // Property based test that ensures, for 100 Felt252s {x} generated at
1369        // random each time tests are run, that converting them into the u64 type
1370        // returns a result that is inside of the range [0, p].
1371        fn from_u64_and_to_u64_primitive(x in any::<u64>()) {
1372           let x_felt:Felt252 = Felt252::from_u64(x).unwrap();
1373           let x_u64:u64 = Felt252::to_u64(&x_felt).unwrap();
1374
1375            prop_assert_eq!(x, x_u64);
1376        }
1377
1378        #[test]
1379        #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1380        fn from_i64_and_to_i64_primitive(x in any::<u32>()) {
1381            let x: i64 = x as i64;
1382            let x_felt:Felt252 = Felt252::from_i64(x).unwrap();
1383            let x_i64:i64 = Felt252::to_i64(&x_felt).unwrap();
1384            prop_assert_eq!(x, x_i64);
1385        }
1386
1387        #[test]
1388        // Property test to check that lcm(x, y) works. Since we're operating in a prime field, lcm
1389        // will just be the smaller number.
1390        fn lcm_doesnt_panic(x in any::<Felt252>(), y in any::<Felt252>()) {
1391            let lcm = x.lcm(&y);
1392            prop_assert!(lcm == cmp::max(x, y));
1393        }
1394
1395        #[test]
1396        #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1397        // Property test to check that is_multiple_of(x, y) works. Since we're operating in a prime field, is_multiple_of
1398        // will always be true
1399        fn is_multiple_of_doesnt_panic(x in any::<Felt252>(), y in any::<Felt252>()) {
1400            prop_assert!(x.is_multiple_of(&y));
1401        }
1402
1403        #[test]
1404        fn divides_doesnt_panic(x in any::<Felt252>(), y in any::<Felt252>()) {
1405            prop_assert!(x.divides(&y));
1406        }
1407
1408        #[test]
1409        fn gcd_doesnt_panic(x in any::<Felt252>(), y in any::<Felt252>()) {
1410            let gcd1 = x.gcd(&y);
1411            let gcd2 = y.gcd(&x);
1412            prop_assert_eq!(gcd1, gcd2);
1413        }
1414
1415        #[test]
1416        fn is_even(x in any::<Felt252>()) {
1417            prop_assert_eq!(x.is_even(), x.to_biguint().is_even());
1418        }
1419
1420        #[test]
1421        fn is_odd(x in any::<Felt252>()) {
1422            prop_assert_eq!(x.is_odd(), x.to_biguint().is_odd());
1423        }
1424
1425        /// Tests the additive identity of the implementation of Zero trait for felts
1426        ///
1427        /// ```{.text}
1428        /// x + 0 = x       ∀ x
1429        /// 0 + x = x       ∀ x
1430        /// ```
1431        #[test]
1432        fn zero_additive_identity(ref x in any::<Felt252>()) {
1433            let zero = Felt252::zero();
1434            prop_assert_eq!(x, &(x + &zero));
1435            prop_assert_eq!(x, &(&zero + x));
1436        }
1437
1438        /// Tests the multiplicative identity of the implementation of One trait for felts
1439        ///
1440        /// ```{.text}
1441        /// x * 1 = x       ∀ x
1442        /// 1 * x = x       ∀ x
1443        /// ```
1444        #[test]
1445        fn one_multiplicative_identity(ref x in any::<Felt252>()) {
1446            let one = Felt252::one();
1447            prop_assert_eq!(x, &(x * &one));
1448            prop_assert_eq!(x, &(&one * x));
1449        }
1450
1451        #[test]
1452        fn felt_is_always_positive(x in any::<Felt252>()) {
1453            prop_assert!(x.is_positive())
1454        }
1455
1456        #[test]
1457        fn felt_is_never_negative(x in any::<Felt252>()) {
1458            prop_assert!(!x.is_negative())
1459        }
1460
1461        #[test]
1462        fn non_zero_felt_signum_is_always_one(ref x in nonzero_felt252()) {
1463            let one = Felt252::one();
1464            prop_assert_eq!(x.signum(), one)
1465        }
1466
1467        #[test]
1468        fn sub_abs(x in any::<Felt252>(), y in any::<Felt252>()) {
1469            let expected_abs_sub = if x > y {&x - &y} else {&y - &x};
1470
1471            prop_assert_eq!(x.abs_sub(&y), expected_abs_sub)
1472        }
1473
1474        #[test]
1475        fn abs(x in any::<Felt252>()) {
1476            prop_assert_eq!(&x, &x.abs())
1477        }
1478
1479        #[test]
1480        fn modpow_in_range(x in any::<Felt252>(), y in any::<Felt252>()) {
1481            let p = BigUint::parse_bytes(PRIME_STR[2..].as_bytes(), 16).unwrap();
1482
1483            let p_felt = Felt252::max_value();
1484
1485            #[allow(deprecated)]
1486            let modpow = x.modpow(&y, &p_felt).to_biguint();
1487            prop_assert!(modpow < p, "{}", modpow);
1488        }
1489
1490        #[test]
1491        fn sqrt_in_range(x in any::<Felt252>()) {
1492            let p = BigUint::parse_bytes(PRIME_STR[2..].as_bytes(), 16).unwrap();
1493
1494            let sqrt = x.sqrt().to_biguint();
1495            prop_assert!(sqrt < p, "{}", sqrt);
1496        }
1497
1498        #[test]
1499        fn sqrt_is_inv_square(x in any::<Felt252>()) {
1500            let x_sq = &x * &x;
1501            let sqrt = x_sq.sqrt();
1502
1503            if sqrt != x {
1504                prop_assert_eq!(Felt252::max_value() - sqrt + 1_usize, x);
1505            } else {
1506                prop_assert_eq!(sqrt, x);
1507            }
1508        }
1509
1510        #[test]
1511        fn add_to_u64(x in any::<u64>(), ref felt in any::<Felt252>()) {
1512            let sum = (felt + x).to_u64();
1513            prop_assert_eq!(x + felt, sum);
1514        }
1515
1516        #[test]
1517        fn add_to_u64_extremes(x in any::<u64>()) {
1518            let big_zero = &Felt252::zero();
1519            let big_max = &Felt252::max_value();
1520            let big_min = &(big_zero + (i64::MIN as usize));
1521
1522            let sum_max = (big_max + x).to_u64();
1523            prop_assert_eq!(x + big_max, sum_max);
1524            let sum_min = (big_min + x).to_u64();
1525            prop_assert_eq!(x + big_min, sum_min);
1526            let sum_zero = (big_zero + x).to_u64();
1527            prop_assert_eq!(x + big_zero, sum_zero);
1528        }
1529
1530        #[test]
1531        fn add_u32_in_range(x in any::<Felt252>(), y in any::<u32>()) {
1532            let p = BigUint::parse_bytes(PRIME_STR[2..].as_bytes(), 16).unwrap();
1533            let x_add_y = (x + y).to_biguint();
1534            prop_assert!(x_add_y < p, "{}", x_add_y);
1535        }
1536
1537        #[test]
1538        fn add_u32_is_inv_sub(x in any::<Felt252>(), y in any::<u32>()) {
1539            let expected_y = (x.clone() + y - x).to_u32().unwrap();
1540            prop_assert_eq!(expected_y, y, "{}", expected_y);
1541        }
1542
1543        #[test]
1544        fn sub_u32_in_range(x in any::<Felt252>(), y in any::<u32>()) {
1545            let p = BigUint::parse_bytes(PRIME_STR[2..].as_bytes(), 16).unwrap();
1546            let x_sub_y = (x - y).to_biguint();
1547            prop_assert!(x_sub_y < p, "{}", x_sub_y);
1548        }
1549
1550        #[test]
1551        fn sub_u32_is_inv_add(x in any::<Felt252>(), y in any::<u32>()) {
1552            prop_assert_eq!(x.clone() - y + y, x)
1553        }
1554
1555        #[test]
1556        fn sub_usize_in_range(x in any::<Felt252>(), y in any::<usize>()) {
1557            let p = BigUint::parse_bytes(PRIME_STR[2..].as_bytes(), 16).unwrap();
1558            let x_sub_y = (x - y).to_biguint();
1559            prop_assert!(x_sub_y < p, "{}", x_sub_y);
1560        }
1561
1562        #[test]
1563        fn sub_usize_is_inv_add(x in any::<Felt252>(), y in any::<usize>()) {
1564            prop_assert_eq!(x.clone() - y + y, x)
1565        }
1566
1567        #[test]
1568        fn add_in_range(x in any::<Felt252>(), y in any::<Felt252>()) {
1569            let p = &BigUint::parse_bytes(PRIME_STR[2..].as_bytes(), 16).unwrap();
1570
1571            let sub = x + y;
1572            let as_uint = &sub.to_biguint();
1573            prop_assert!(as_uint < p, "{}", as_uint);
1574        }
1575
1576        #[test]
1577        fn add_is_inv_sub(ref x in any::<Felt252>(), ref y in any::<Felt252>()) {
1578            let expected_y = x + y - x;
1579            prop_assert_eq!(&expected_y, y, "{}", y);
1580        }
1581
1582        #[test]
1583        fn add_assign_in_range(mut x in any::<Felt252>(), y in any::<Felt252>()) {
1584            let p = &BigUint::parse_bytes(PRIME_STR[2..].as_bytes(), 16).unwrap();
1585
1586            x += y.clone();
1587            let as_uint = &x.to_biguint();
1588            prop_assert!(as_uint < p, "{}", as_uint);
1589
1590            // test reference variant
1591            x += &y;
1592            let as_uint = &x.to_biguint();
1593            prop_assert!(as_uint < p, "{}", as_uint);
1594        }
1595    }
1596
1597    #[rstest]
1598    fn add_to_u64_edge_cases(
1599        #[values(0, 1, u64::MAX)] x: u64,
1600        #[values(-2, -1, 0, 1, 1i128.neg(), i64::MIN as i128, u64::MAX as i128, u64::MAX as i128 + 1, (u64::MAX as i128).neg())]
1601        y: i128,
1602    ) {
1603        let y = Felt252::from(y);
1604        assert_eq!(x + &y, (&y + x).to_u64());
1605    }
1606
1607    #[test]
1608    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1609    // Checks that the result of adding two zeroes is zero
1610    fn sum_zeros_in_range() {
1611        let x = Felt252::new(0);
1612        let y = Felt252::new(0);
1613        let z = Felt252::new(0);
1614        assert_eq!(x + y, z)
1615    }
1616
1617    #[test]
1618    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1619    // Checks that the result of multiplying two zeroes is zero
1620    fn mul_zeros_in_range() {
1621        let x = Felt252::new(0);
1622        let y = Felt252::new(0);
1623        let z = Felt252::new(0);
1624        assert_eq!(x * y, z)
1625    }
1626
1627    #[test]
1628    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1629    // Checks that the result of performing a bit and operation between zeroes is zero
1630    fn bit_and_zeros_in_range() {
1631        let x = Felt252::new(0);
1632        let y = Felt252::new(0);
1633        let z = Felt252::new(0);
1634        assert_eq!(&x & &y, z)
1635    }
1636
1637    #[test]
1638    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1639    // Checks that the result of perfforming a bit or operation between zeroes is zero
1640    fn bit_or_zeros_in_range() {
1641        let x = Felt252::new(0);
1642        let y = Felt252::new(0);
1643        let z = Felt252::new(0);
1644        assert_eq!(&x | &y, z)
1645    }
1646
1647    #[test]
1648    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1649    // Checks that the result of perfforming a bit xor operation between zeroes is zero
1650    fn bit_xor_zeros_in_range() {
1651        let x = Felt252::new(0);
1652        let y = Felt252::new(0);
1653        let z = Felt252::new(0);
1654        assert_eq!(&x ^ &y, z)
1655    }
1656
1657    #[test]
1658    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1659    // Tests that the maximum value a Felt252 can take is equal to (prime - 1)
1660    fn upper_bound() {
1661        let prime = &BigUint::parse_bytes(PRIME_STR[2..].as_bytes(), 16).unwrap();
1662        let unit = BigUint::one();
1663        let felt_max_value = Felt252::max_value().to_biguint();
1664        assert_eq!(prime - unit, felt_max_value)
1665    }
1666
1667    #[test]
1668    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1669    // Tests that the minimum value a Felt252 can take is equal to zero.
1670    fn lower_bound() {
1671        let zero = BigUint::zero();
1672        let felt_min_value = Felt252::min_value().to_biguint();
1673        assert_eq!(zero, felt_min_value)
1674    }
1675
1676    #[test]
1677    fn zero_value() {
1678        let zero = BigUint::zero();
1679        let felt_zero = Felt252::zero().to_biguint();
1680        assert_eq!(zero, felt_zero)
1681    }
1682
1683    #[test]
1684    fn is_zero() {
1685        let felt_zero = Felt252::zero();
1686        let felt_non_zero = Felt252::new(3);
1687        assert!(felt_zero.is_zero());
1688        assert!(!felt_non_zero.is_zero())
1689    }
1690
1691    #[test]
1692    fn one_value() {
1693        let one = BigUint::one();
1694        let felt_one = Felt252::one().to_biguint();
1695        assert_eq!(one, felt_one)
1696    }
1697
1698    #[test]
1699    fn is_one() {
1700        let felt_one = Felt252::one();
1701        let felt_non_one = Felt252::new(8);
1702        assert!(felt_one.is_one());
1703        assert!(!felt_non_one.is_one())
1704    }
1705
1706    #[test]
1707    fn signum_of_zero_is_zero() {
1708        let zero = Felt252::zero();
1709        assert_eq!(&zero.signum(), &zero)
1710    }
1711
1712    #[test]
1713    fn from_bytes_ne() {
1714        let expected = Felt252::zero();
1715        let bytes = [0; 32];
1716        let got = Felt252::from_bytes_ne(&bytes);
1717        assert_eq!(got, expected);
1718    }
1719}
cairo_felt/lib_bigint_felt.rs

cairo_felt/
lib_bigint_felt.rs
