twenty_first/math/
b_field_element.rs

1use std::convert::TryFrom;
2use std::fmt;
3use std::hash::Hash;
4use std::iter::Sum;
5use std::num::TryFromIntError;
6use std::ops::Add;
7use std::ops::AddAssign;
8use std::ops::Div;
9use std::ops::Mul;
10use std::ops::MulAssign;
11use std::ops::Neg;
12use std::ops::Sub;
13use std::ops::SubAssign;
14use std::str::FromStr;
15
16use arbitrary::Arbitrary;
17use arbitrary::Unstructured;
18use get_size2::GetSize;
19use num_traits::ConstOne;
20use num_traits::ConstZero;
21use num_traits::One;
22use num_traits::Zero;
23use phf::phf_map;
24use rand::distr::Distribution;
25use rand::distr::StandardUniform;
26use rand::Rng;
27use serde::Deserialize;
28use serde::Deserializer;
29use serde::Serialize;
30use serde::Serializer;
31
32use super::traits::Inverse;
33use super::traits::PrimitiveRootOfUnity;
34use super::x_field_element::XFieldElement;
35use crate::error::ParseBFieldElementError;
36use crate::math::traits::CyclicGroupGenerator;
37use crate::math::traits::FiniteField;
38use crate::math::traits::ModPowU32;
39use crate::math::traits::ModPowU64;
40
41const PRIMITIVE_ROOTS: phf::Map<u64, u64> = phf_map! {
42    0u64 => 1,
43    1u64 => 1,
44    2u64 => 18446744069414584320,
45    4u64 => 281474976710656,
46    8u64 => 18446744069397807105,
47    16u64 => 17293822564807737345,
48    32u64 => 70368744161280,
49    64u64 => 549755813888,
50    128u64 => 17870292113338400769,
51    256u64 => 13797081185216407910,
52    512u64 => 1803076106186727246,
53    1024u64 => 11353340290879379826,
54    2048u64 => 455906449640507599,
55    4096u64 => 17492915097719143606,
56    8192u64 => 1532612707718625687,
57    16384u64 => 16207902636198568418,
58    32768u64 => 17776499369601055404,
59    65536u64 => 6115771955107415310,
60    131072u64 => 12380578893860276750,
61    262144u64 => 9306717745644682924,
62    524288u64 => 18146160046829613826,
63    1048576u64 => 3511170319078647661,
64    2097152u64 => 17654865857378133588,
65    4194304u64 => 5416168637041100469,
66    8388608u64 => 16905767614792059275,
67    16777216u64 => 9713644485405565297,
68    33554432u64 => 5456943929260765144,
69    67108864u64 => 17096174751763063430,
70    134217728u64 => 1213594585890690845,
71    268435456u64 => 6414415596519834757,
72    536870912u64 => 16116352524544190054,
73    1073741824u64 => 9123114210336311365,
74    2147483648u64 => 4614640910117430873,
75    4294967296u64 => 1753635133440165772,
76};
77
78/// Base field element ∈ ℤ_{2^64 - 2^32 + 1}.
79///
80/// In Montgomery representation. This implementation follows <https://eprint.iacr.org/2022/274.pdf>
81/// and <https://github.com/novifinancial/winterfell/pull/101/files>.
82#[derive(Debug, Copy, Clone, Default, Hash, PartialEq, Eq)]
83pub struct BFieldElement(u64);
84
85/// Simplifies constructing [base field element][BFieldElement]s.
86///
87/// The type [`BFieldElement`] must be in scope for this macro to work.
88/// See [`BFieldElement::from`] for supported types.
89///
90/// # Examples
91///
92/// ```
93/// # use twenty_first::prelude::*;
94/// let a = bfe!(42);
95/// let b = bfe!(-12); // correctly translates to `BFieldElement::P - 12`
96/// let c = bfe!(42 - 12);
97/// assert_eq!(a + b, c);
98///```
99#[macro_export]
100macro_rules! bfe {
101    ($value:expr) => {
102        BFieldElement::from($value)
103    };
104}
105
106/// Simplifies constructing vectors of [base field element][BFieldElement]s.
107///
108/// The type [`BFieldElement`] must be in scope for this macro to work. See also [`bfe!`].
109///
110/// # Examples
111///
112/// ```
113/// # use twenty_first::prelude::*;
114/// let a = bfe_vec![1, 2, 3];
115/// let b = vec![bfe!(1), bfe!(2), bfe!(3)];
116/// assert_eq!(a, b);
117/// ```
118///
119/// ```
120/// # use twenty_first::prelude::*;
121/// let a = bfe_vec![42; 15];
122/// let b = vec![bfe!(42); 15];
123/// assert_eq!(a, b);
124/// ```
125///
126#[macro_export]
127macro_rules! bfe_vec {
128    ($b:expr; $n:expr) => {
129        vec![BFieldElement::from($b); $n]
130    };
131    ($($b:expr),* $(,)?) => {
132        vec![$(BFieldElement::from($b)),*]
133    };
134}
135
136/// Simplifies constructing arrays of [base field element][BFieldElement]s.
137///
138/// The type [`BFieldElement`] must be in scope for this macro to work. See also [`bfe!`].
139///
140/// # Examples
141///
142/// ```
143/// # use twenty_first::prelude::*;
144/// let a = bfe_array![1, 2, 3];
145/// let b = [bfe!(1), bfe!(2), bfe!(3)];
146/// assert_eq!(a, b);
147/// ```
148///
149/// ```
150/// # use twenty_first::prelude::*;
151/// let a = bfe_array![42; 15];
152/// let b = [bfe!(42); 15];
153/// assert_eq!(a, b);
154/// ```
155#[macro_export]
156macro_rules! bfe_array {
157    ($b:expr; $n:expr) => {
158        [BFieldElement::from($b); $n]
159    };
160    ($($b:expr),* $(,)?) => {
161        [$(BFieldElement::from($b)),*]
162    };
163}
164
165impl GetSize for BFieldElement {
166    fn get_stack_size() -> usize {
167        std::mem::size_of::<Self>()
168    }
169
170    fn get_heap_size(&self) -> usize {
171        0
172    }
173}
174
175impl<'a> Arbitrary<'a> for BFieldElement {
176    fn arbitrary(u: &mut Unstructured<'a>) -> arbitrary::Result<Self> {
177        u.arbitrary().map(BFieldElement::new)
178    }
179}
180
181impl Serialize for BFieldElement {
182    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
183    where
184        S: Serializer,
185    {
186        self.value().serialize(serializer)
187    }
188}
189
190impl<'de> Deserialize<'de> for BFieldElement {
191    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
192    where
193        D: Deserializer<'de>,
194    {
195        Ok(Self::new(u64::deserialize(deserializer)?))
196    }
197}
198
199impl Sum for BFieldElement {
200    fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
201        iter.reduce(|a, b| a + b)
202            .unwrap_or_else(BFieldElement::zero)
203    }
204}
205
206impl BFieldElement {
207    pub const BYTES: usize = 8;
208
209    /// The base field's prime, _i.e._, 2^64 - 2^32 + 1.
210    pub const P: u64 = 0xffff_ffff_0000_0001;
211    pub const MAX: u64 = Self::P - 1;
212
213    /// 2^128 mod P; this is used for conversion of elements into Montgomery representation.
214    const R2: u64 = 0xffff_fffe_0000_0001;
215
216    /// -2^-1
217    pub const MINUS_TWO_INVERSE: Self = Self::new(0x7fff_ffff_8000_0000);
218
219    #[inline]
220    pub const fn new(value: u64) -> Self {
221        Self(Self::montyred((value as u128) * (Self::R2 as u128)))
222    }
223
224    /// Construct a new base field element iff the given value is
225    /// [canonical][Self::is_canonical], an error otherwise.
226    fn try_new(v: u64) -> Result<Self, ParseBFieldElementError> {
227        Self::is_canonical(v)
228            .then(|| Self::new(v))
229            .ok_or(ParseBFieldElementError::NotCanonical(v))
230    }
231
232    #[inline]
233    pub const fn value(&self) -> u64 {
234        self.canonical_representation()
235    }
236
237    #[must_use]
238    #[inline]
239    pub fn inverse(&self) -> Self {
240        #[inline(always)]
241        const fn exp(base: BFieldElement, exponent: u64) -> BFieldElement {
242            let mut res = base;
243            let mut i = 0;
244            while i < exponent {
245                res = BFieldElement(BFieldElement::montyred(res.0 as u128 * res.0 as u128));
246                i += 1;
247            }
248            res
249        }
250
251        let x = *self;
252        assert_ne!(
253            x,
254            Self::zero(),
255            "Attempted to find the multiplicative inverse of zero."
256        );
257
258        let bin_2_ones = x.square() * x;
259        let bin_3_ones = bin_2_ones.square() * x;
260        let bin_6_ones = exp(bin_3_ones, 3) * bin_3_ones;
261        let bin_12_ones = exp(bin_6_ones, 6) * bin_6_ones;
262        let bin_24_ones = exp(bin_12_ones, 12) * bin_12_ones;
263        let bin_30_ones = exp(bin_24_ones, 6) * bin_6_ones;
264        let bin_31_ones = bin_30_ones.square() * x;
265        let bin_31_ones_1_zero = bin_31_ones.square();
266        let bin_32_ones = bin_31_ones.square() * x;
267
268        exp(bin_31_ones_1_zero, 32) * bin_32_ones
269    }
270
271    #[inline]
272    /// Square the base M times and multiply the result by the tail value
273    pub const fn power_accumulator<const N: usize, const M: usize>(
274        base: [Self; N],
275        tail: [Self; N],
276    ) -> [Self; N] {
277        let mut result = base;
278        let mut i = 0;
279        while i < M {
280            let mut j = 0;
281            while j < N {
282                result[j] = Self(Self::montyred(result[j].0 as u128 * result[j].0 as u128));
283                j += 1;
284            }
285            i += 1;
286        }
287
288        let mut j = 0;
289        while j < N {
290            result[j] = Self(Self::montyred(result[j].0 as u128 * tail[j].0 as u128));
291            j += 1;
292        }
293        result
294    }
295
296    /// Get a generator for the entire field
297    pub const fn generator() -> Self {
298        BFieldElement::new(7)
299    }
300
301    #[inline]
302    pub const fn lift(&self) -> XFieldElement {
303        XFieldElement::new_const(*self)
304    }
305
306    // You should probably only use `increment` and `decrement` for testing purposes
307    pub fn increment(&mut self) {
308        *self += Self::one();
309    }
310
311    // You should probably only use `increment` and `decrement` for testing purposes
312    pub fn decrement(&mut self) {
313        *self -= Self::one();
314    }
315
316    #[inline]
317    const fn canonical_representation(&self) -> u64 {
318        Self::montyred(self.0 as u128)
319    }
320
321    #[must_use]
322    #[inline]
323    pub const fn mod_pow(&self, exp: u64) -> Self {
324        let mut acc = BFieldElement::ONE;
325        let bit_length = u64::BITS - exp.leading_zeros();
326        let mut i = 0;
327        while i < bit_length {
328            acc = Self(Self::montyred(acc.0 as u128 * acc.0 as u128));
329            if exp & (1 << (bit_length - 1 - i)) != 0 {
330                acc = Self(Self::montyred(acc.0 as u128 * self.0 as u128));
331            }
332            i += 1;
333        }
334
335        acc
336    }
337
338    /// Montgomery reduction
339    #[inline(always)]
340    pub const fn montyred(x: u128) -> u64 {
341        // See reference above for a description of the following implementation.
342        let xl = x as u64;
343        let xh = (x >> 64) as u64;
344        let (a, e) = xl.overflowing_add(xl << 32);
345
346        let b = a.wrapping_sub(a >> 32).wrapping_sub(e as u64);
347
348        let (r, c) = xh.overflowing_sub(b);
349
350        // See https://github.com/Neptune-Crypto/twenty-first/pull/70 for various ways
351        // of expressing this.
352        r.wrapping_sub((1 + !Self::P) * c as u64)
353    }
354
355    /// Return the raw bytes or 8-bit chunks of the Montgomery
356    /// representation, in little-endian byte order
357    pub const fn raw_bytes(&self) -> [u8; 8] {
358        self.0.to_le_bytes()
359    }
360
361    /// Take a slice of 8 bytes and interpret it as an integer in
362    /// little-endian byte order, and cast it to a BFieldElement
363    /// in Montgomery representation
364    pub const fn from_raw_bytes(bytes: &[u8; 8]) -> Self {
365        Self(u64::from_le_bytes(*bytes))
366    }
367
368    /// Return the raw 16-bit chunks of the Montgomery
369    /// representation, in little-endian chunk order
370    pub const fn raw_u16s(&self) -> [u16; 4] {
371        [
372            (self.0 & 0xffff) as u16,
373            ((self.0 >> 16) & 0xffff) as u16,
374            ((self.0 >> 32) & 0xffff) as u16,
375            ((self.0 >> 48) & 0xffff) as u16,
376        ]
377    }
378
379    /// Take a slice of 4 16-bit chunks and interpret it as an integer in
380    /// little-endian chunk order, and cast it to a BFieldElement
381    /// in Montgomery representation
382    pub const fn from_raw_u16s(chunks: &[u16; 4]) -> Self {
383        Self(
384            ((chunks[3] as u64) << 48)
385                | ((chunks[2] as u64) << 32)
386                | ((chunks[1] as u64) << 16)
387                | (chunks[0] as u64),
388        )
389    }
390
391    #[inline]
392    pub fn raw_u128(&self) -> u128 {
393        self.0.into()
394    }
395
396    #[inline]
397    pub const fn from_raw_u64(e: u64) -> BFieldElement {
398        BFieldElement(e)
399    }
400
401    #[inline]
402    pub const fn raw_u64(&self) -> u64 {
403        self.0
404    }
405
406    #[inline]
407    pub const fn is_canonical(x: u64) -> bool {
408        x < Self::P
409    }
410}
411
412impl fmt::Display for BFieldElement {
413    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
414        let canonical_value = Self::canonical_representation(self);
415        let cutoff = 256;
416        if canonical_value >= Self::P - cutoff {
417            write!(f, "-{}", Self::P - canonical_value)
418        } else if canonical_value <= cutoff {
419            write!(f, "{canonical_value}")
420        } else {
421            write!(f, "{canonical_value:>020}")
422        }
423    }
424}
425
426impl FromStr for BFieldElement {
427    type Err = ParseBFieldElementError;
428
429    fn from_str(s: &str) -> Result<Self, Self::Err> {
430        let parsed = s.parse().map_err(Self::Err::ParseU64Error)?;
431        Self::try_new(parsed)
432    }
433}
434
435impl From<usize> for BFieldElement {
436    fn from(value: usize) -> Self {
437        // targets with wider target pointers don't exist at the time of writing
438        #[cfg(any(
439            target_pointer_width = "16",
440            target_pointer_width = "32",
441            target_pointer_width = "64",
442        ))]
443        Self::new(value as u64)
444    }
445}
446
447impl From<u128> for BFieldElement {
448    fn from(value: u128) -> Self {
449        fn mod_reduce(x: u128) -> u64 {
450            const LOWER_MASK: u64 = 0xFFFF_FFFF;
451
452            let x_lo = x as u64;
453            let x_hi = (x >> 64) as u64;
454            let x_hi_lo = (x_hi as u32) as u64;
455            let x_hi_hi = x_hi >> 32;
456
457            // x_lo - x_hi_hi; potential underflow because `x_hi_hi` may be greater than `x_lo`
458            let (tmp0, is_underflow) = x_lo.overflowing_sub(x_hi_hi);
459            let tmp1 = tmp0.wrapping_sub(LOWER_MASK * (is_underflow as u64));
460
461            // guaranteed not to underflow
462            let tmp2 = (x_hi_lo << 32) - x_hi_lo;
463
464            // adding tmp values gives final result;
465            // potential overflow because each of the `tmp`s may be up to 64 bits
466            let (result, is_overflow) = tmp1.overflowing_add(tmp2);
467            result.wrapping_add(LOWER_MASK * (is_overflow as u64))
468        }
469
470        Self::new(mod_reduce(value))
471    }
472}
473
474macro_rules! impl_from_small_unsigned_int_for_bfe {
475    ($($t:ident),+ $(,)?) => {$(
476        impl From<$t> for BFieldElement {
477            fn from(value: $t) -> Self {
478                Self::new(u64::from(value))
479            }
480        }
481    )+};
482}
483
484impl_from_small_unsigned_int_for_bfe!(u8, u16, u32, u64);
485
486impl From<isize> for BFieldElement {
487    fn from(value: isize) -> Self {
488        // targets with wider target pointers don't exist at the time of writing
489        #[cfg(target_pointer_width = "16")]
490        {
491            (value as i16).into()
492        }
493        #[cfg(target_pointer_width = "32")]
494        {
495            (value as i32).into()
496        }
497        #[cfg(target_pointer_width = "64")]
498        {
499            (value as i64).into()
500        }
501    }
502}
503
504impl From<i64> for BFieldElement {
505    fn from(value: i64) -> Self {
506        match i128::from(value) {
507            0.. => value as u128,
508            _ => (value as u128) - BFieldElement::R2 as u128,
509        }
510        .into()
511    }
512}
513
514macro_rules! impl_from_small_signed_int_for_bfe {
515    ($($t:ident),+ $(,)?) => {$(
516        impl From<$t> for BFieldElement {
517            fn from(value: $t) -> Self {
518                i64::from(value).into()
519            }
520        }
521    )+};
522}
523
524impl_from_small_signed_int_for_bfe!(i8, i16, i32);
525
526macro_rules! impl_try_from_bfe_for_int {
527    ($($t:ident),+ $(,)?) => {$(
528        impl TryFrom<BFieldElement> for $t {
529            type Error = TryFromIntError;
530
531            fn try_from(value: BFieldElement) -> Result<Self, Self::Error> {
532                $t::try_from(value.canonical_representation())
533            }
534        }
535
536        impl TryFrom<&BFieldElement> for $t {
537            type Error = TryFromIntError;
538
539            fn try_from(value: &BFieldElement) -> Result<Self, Self::Error> {
540                $t::try_from(value.canonical_representation())
541            }
542        }
543    )+};
544}
545
546impl_try_from_bfe_for_int!(u8, i8, u16, i16, u32, i32, usize, isize);
547
548macro_rules! impl_from_bfe_for_int {
549    ($($t:ident),+ $(,)?) => {$(
550        impl From<BFieldElement> for $t {
551            fn from(elem: BFieldElement) -> Self {
552                Self::from(elem.canonical_representation())
553            }
554        }
555
556        impl From<&BFieldElement> for $t {
557            fn from(elem: &BFieldElement) -> Self {
558                Self::from(elem.canonical_representation())
559            }
560        }
561    )+};
562}
563
564impl_from_bfe_for_int!(u64, u128, i128);
565
566impl From<BFieldElement> for i64 {
567    fn from(elem: BFieldElement) -> Self {
568        bfe_to_i64(&elem)
569    }
570}
571
572impl From<&BFieldElement> for i64 {
573    fn from(elem: &BFieldElement) -> Self {
574        bfe_to_i64(elem)
575    }
576}
577
578const fn bfe_to_i64(bfe: &BFieldElement) -> i64 {
579    let v = bfe.canonical_representation();
580    if v <= i64::MAX as u64 {
581        v as i64
582    } else {
583        (v as i128 - BFieldElement::P as i128) as i64
584    }
585}
586
587/// Convert a B-field element to a byte array.
588/// The client uses this for its database.
589impl From<BFieldElement> for [u8; BFieldElement::BYTES] {
590    fn from(bfe: BFieldElement) -> Self {
591        // It's crucial to map this to the canonical representation before converting.
592        // Otherwise, the representation is degenerate.
593        bfe.canonical_representation().to_le_bytes()
594    }
595}
596
597impl TryFrom<[u8; BFieldElement::BYTES]> for BFieldElement {
598    type Error = ParseBFieldElementError;
599
600    fn try_from(array: [u8; BFieldElement::BYTES]) -> Result<Self, Self::Error> {
601        Self::try_new(u64::from_le_bytes(array))
602    }
603}
604
605impl TryFrom<&[u8]> for BFieldElement {
606    type Error = ParseBFieldElementError;
607
608    fn try_from(bytes: &[u8]) -> Result<Self, Self::Error> {
609        <[u8; BFieldElement::BYTES]>::try_from(bytes)
610            .map_err(|_| Self::Error::InvalidNumBytes(bytes.len()))?
611            .try_into()
612    }
613}
614
615impl Inverse for BFieldElement {
616    #[must_use]
617    #[inline]
618    fn inverse(&self) -> Self {
619        self.inverse()
620    }
621}
622
623impl ModPowU32 for BFieldElement {
624    #[inline]
625    fn mod_pow_u32(&self, exp: u32) -> Self {
626        self.mod_pow(exp as u64)
627    }
628}
629
630impl CyclicGroupGenerator for BFieldElement {
631    fn get_cyclic_group_elements(&self, max: Option<usize>) -> Vec<Self> {
632        let mut val = *self;
633        let mut ret: Vec<Self> = vec![Self::one()];
634
635        loop {
636            ret.push(val);
637            val *= *self;
638            if val.is_one() || max.is_some() && ret.len() >= max.unwrap() {
639                break;
640            }
641        }
642        ret
643    }
644}
645
646impl Distribution<BFieldElement> for StandardUniform {
647    fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> BFieldElement {
648        BFieldElement::new(rng.random_range(0..=BFieldElement::MAX))
649    }
650}
651
652impl FiniteField for BFieldElement {}
653
654impl Zero for BFieldElement {
655    #[inline]
656    fn zero() -> Self {
657        Self::ZERO
658    }
659
660    #[inline]
661    fn is_zero(&self) -> bool {
662        self == &Self::ZERO
663    }
664}
665
666impl ConstZero for BFieldElement {
667    const ZERO: Self = Self::new(0);
668}
669
670impl One for BFieldElement {
671    #[inline]
672    fn one() -> Self {
673        Self::ONE
674    }
675
676    #[inline]
677    fn is_one(&self) -> bool {
678        self == &Self::ONE
679    }
680}
681
682impl ConstOne for BFieldElement {
683    const ONE: Self = Self::new(1);
684}
685
686impl Add for BFieldElement {
687    type Output = Self;
688
689    #[allow(clippy::suspicious_arithmetic_impl)]
690    #[inline(always)]
691    fn add(self, rhs: Self) -> Self {
692        // Compute a + b = a - (p - b).
693        let (x1, c1) = self.0.overflowing_sub(Self::P - rhs.0);
694
695        // The following if/else is equivalent to the commented-out code below but
696        // the if/else was found to be faster.
697        // let adj = 0u32.wrapping_sub(c1 as u32);
698        // Self(x1.wrapping_sub(adj as u64))
699        // See
700        // https://github.com/Neptune-Crypto/twenty-first/pull/70
701        if c1 {
702            Self(x1.wrapping_add(Self::P))
703        } else {
704            Self(x1)
705        }
706    }
707}
708
709impl AddAssign for BFieldElement {
710    #[inline(always)]
711    fn add_assign(&mut self, rhs: Self) {
712        *self = *self + rhs
713    }
714}
715
716impl SubAssign for BFieldElement {
717    #[inline]
718    fn sub_assign(&mut self, rhs: Self) {
719        *self = *self - rhs
720    }
721}
722
723impl MulAssign for BFieldElement {
724    #[inline]
725    fn mul_assign(&mut self, rhs: Self) {
726        *self = *self * rhs;
727    }
728}
729
730impl Mul for BFieldElement {
731    type Output = Self;
732
733    #[inline]
734    fn mul(self, rhs: Self) -> Self {
735        Self(Self::montyred((self.0 as u128) * (rhs.0 as u128)))
736    }
737}
738
739impl Neg for BFieldElement {
740    type Output = Self;
741
742    #[inline]
743    fn neg(self) -> Self {
744        Self::zero() - self
745    }
746}
747
748impl Sub for BFieldElement {
749    type Output = Self;
750
751    #[allow(clippy::suspicious_arithmetic_impl)]
752    #[inline]
753    fn sub(self, rhs: Self) -> Self {
754        let (x1, c1) = self.0.overflowing_sub(rhs.0);
755
756        // The following code is equivalent to the commented-out code below
757        // but they were determined to have near-equiavalent running times. Maybe because
758        // subtraction is not used very often.
759        // See: https://github.com/Neptune-Crypto/twenty-first/pull/70
760        // 1st alternative:
761        // if c1 {
762        //     Self(x1.wrapping_add(Self::P))
763        // } else {
764        //     Self(x1)
765        // }
766        // 2nd alternative:
767        // let adj = 0u32.wrapping_sub(c1 as u32);
768        // Self(x1.wrapping_sub(adj as u64))
769        Self(x1.wrapping_sub((1 + !Self::P) * c1 as u64))
770    }
771}
772
773impl Div for BFieldElement {
774    type Output = Self;
775
776    #[allow(clippy::suspicious_arithmetic_impl)]
777    fn div(self, other: Self) -> Self {
778        other.inverse() * self
779    }
780}
781
782// TODO: We probably wanna make use of Rust's Pow, but for now we copy from ...big:
783impl ModPowU64 for BFieldElement {
784    #[inline]
785    fn mod_pow_u64(&self, pow: u64) -> Self {
786        self.mod_pow(pow)
787    }
788}
789
790impl PrimitiveRootOfUnity for BFieldElement {
791    fn primitive_root_of_unity(n: u64) -> Option<BFieldElement> {
792        PRIMITIVE_ROOTS.get(&n).map(|&r| BFieldElement::new(r))
793    }
794}
795
796#[cfg(test)]
797mod b_prime_field_element_test {
798    use std::collections::hash_map::DefaultHasher;
799    use std::hash::Hasher;
800
801    use itertools::izip;
802    use proptest::prelude::*;
803    use proptest_arbitrary_interop::arb;
804    use rand::random;
805    use test_strategy::proptest;
806
807    use crate::math::b_field_element::*;
808    use crate::math::other::random_elements;
809    use crate::math::polynomial::Polynomial;
810
811    impl proptest::arbitrary::Arbitrary for BFieldElement {
812        type Parameters = ();
813
814        fn arbitrary_with(_: Self::Parameters) -> Self::Strategy {
815            arb().boxed()
816        }
817
818        type Strategy = BoxedStrategy<Self>;
819    }
820
821    #[proptest]
822    fn get_size(bfe: BFieldElement) {
823        prop_assert_eq!(8, bfe.get_size());
824    }
825
826    #[proptest]
827    fn serialization_and_deserialization_to_and_from_json_is_identity(bfe: BFieldElement) {
828        let serialized = serde_json::to_string(&bfe).unwrap();
829        let deserialized: BFieldElement = serde_json::from_str(&serialized).unwrap();
830        prop_assert_eq!(bfe, deserialized);
831    }
832
833    #[proptest]
834    fn deserializing_u64_is_like_calling_new(#[strategy(0..=BFieldElement::MAX)] value: u64) {
835        let bfe = BFieldElement::new(value);
836        let deserialized: BFieldElement = serde_json::from_str(&value.to_string()).unwrap();
837        prop_assert_eq!(bfe, deserialized);
838    }
839
840    #[proptest]
841    fn parsing_string_representing_canonical_u64_gives_correct_bfield_element(
842        #[strategy(0..=BFieldElement::MAX)] v: u64,
843    ) {
844        let bfe = BFieldElement::from_str(&v.to_string()).unwrap();
845        prop_assert_eq!(v, bfe.value());
846    }
847
848    #[proptest]
849    fn parsing_string_representing_too_big_u64_as_bfield_element_gives_error(
850        #[strategy(BFieldElement::P..)] v: u64,
851    ) {
852        let err = BFieldElement::from_str(&v.to_string()).err().unwrap();
853        prop_assert_eq!(ParseBFieldElementError::NotCanonical(v), err);
854    }
855
856    #[proptest]
857    fn zero_is_neutral_element_for_addition(bfe: BFieldElement) {
858        let zero = BFieldElement::ZERO;
859        prop_assert_eq!(bfe + zero, bfe);
860    }
861
862    #[proptest]
863    fn one_is_neutral_element_for_multiplication(bfe: BFieldElement) {
864        let one = BFieldElement::ONE;
865        prop_assert_eq!(bfe * one, bfe);
866    }
867
868    #[proptest]
869    fn addition_is_commutative(element_0: BFieldElement, element_1: BFieldElement) {
870        prop_assert_eq!(element_0 + element_1, element_1 + element_0);
871    }
872
873    #[proptest]
874    fn multiplication_is_commutative(element_0: BFieldElement, element_1: BFieldElement) {
875        prop_assert_eq!(element_0 * element_1, element_1 * element_0);
876    }
877
878    #[proptest]
879
880    fn addition_is_associative(
881        element_0: BFieldElement,
882        element_1: BFieldElement,
883        element_2: BFieldElement,
884    ) {
885        prop_assert_eq!(
886            (element_0 + element_1) + element_2,
887            element_0 + (element_1 + element_2)
888        );
889    }
890
891    #[proptest]
892    fn multiplication_is_associative(
893        element_0: BFieldElement,
894        element_1: BFieldElement,
895        element_2: BFieldElement,
896    ) {
897        prop_assert_eq!(
898            (element_0 * element_1) * element_2,
899            element_0 * (element_1 * element_2)
900        );
901    }
902
903    #[proptest]
904    fn multiplication_distributes_over_addition(
905        element_0: BFieldElement,
906        element_1: BFieldElement,
907        element_2: BFieldElement,
908    ) {
909        prop_assert_eq!(
910            element_0 * (element_1 + element_2),
911            element_0 * element_1 + element_0 * element_2
912        );
913    }
914
915    #[proptest]
916    fn multiplication_with_inverse_gives_identity(#[filter(!#bfe.is_zero())] bfe: BFieldElement) {
917        prop_assert!((bfe.inverse() * bfe).is_one());
918    }
919
920    #[proptest]
921    fn division_by_self_gives_identity(#[filter(!#bfe.is_zero())] bfe: BFieldElement) {
922        prop_assert!((bfe / bfe).is_one());
923    }
924
925    #[proptest]
926    fn values_larger_than_modulus_are_handled_correctly(
927        #[strategy(BFieldElement::P..)] large_value: u64,
928    ) {
929        let bfe = BFieldElement::new(large_value);
930        let expected_value = large_value - BFieldElement::P;
931        prop_assert_eq!(expected_value, bfe.value());
932    }
933
934    #[test]
935    fn display_test() {
936        let seven: BFieldElement = BFieldElement::new(7);
937        assert_eq!("7", format!("{seven}"));
938
939        let minus_one: BFieldElement = BFieldElement::new(BFieldElement::P - 1);
940        assert_eq!("-1", format!("{minus_one}"));
941
942        let minus_fifteen: BFieldElement = BFieldElement::new(BFieldElement::P - 15);
943        assert_eq!("-15", format!("{minus_fifteen}"));
944    }
945
946    #[test]
947    fn zero_is_zero() {
948        let zero = BFieldElement::zero();
949        assert!(zero.is_zero());
950        assert_eq!(zero, BFieldElement::ZERO);
951    }
952
953    #[proptest]
954    fn not_zero_is_nonzero(bfe: BFieldElement) {
955        if bfe.value() == 0 {
956            return Ok(());
957        }
958        prop_assert!(!bfe.is_zero());
959    }
960
961    #[test]
962    fn one_is_one() {
963        let one = BFieldElement::one();
964        assert!(one.is_one());
965        assert_eq!(one, BFieldElement::ONE);
966    }
967
968    #[proptest]
969    fn not_one_is_not_one(bfe: BFieldElement) {
970        if bfe.value() == 1 {
971            return Ok(());
972        }
973        prop_assert!(!bfe.is_one());
974    }
975
976    #[test]
977    fn one_unequal_zero() {
978        let one = BFieldElement::ONE;
979        let zero = BFieldElement::ZERO;
980        assert_ne!(one, zero);
981    }
982
983    #[proptest]
984    fn byte_array_of_small_field_elements_is_zero_at_high_indices(value: u8) {
985        let bfe = BFieldElement::new(value as u64);
986        let byte_array: [u8; 8] = bfe.into();
987
988        prop_assert_eq!(value, byte_array[0]);
989        (1..8).for_each(|i| {
990            assert_eq!(0, byte_array[i]);
991        });
992    }
993
994    #[proptest]
995    fn byte_array_conversion(bfe: BFieldElement) {
996        let array: [u8; 8] = bfe.into();
997        let bfe_recalculated: BFieldElement = array.try_into()?;
998        prop_assert_eq!(bfe, bfe_recalculated);
999    }
1000
1001    #[proptest]
1002    fn byte_array_outside_range_is_not_accepted(#[strategy(BFieldElement::P..)] value: u64) {
1003        let byte_array = value.to_le_bytes();
1004        prop_assert!(BFieldElement::try_from(byte_array).is_err());
1005    }
1006
1007    #[proptest]
1008    fn value_is_preserved(#[strategy(0..BFieldElement::P)] value: u64) {
1009        prop_assert_eq!(value, BFieldElement::new(value).value());
1010    }
1011
1012    #[test]
1013    fn supposed_generator_is_generator() {
1014        let generator = BFieldElement::generator();
1015        let largest_meaningful_power = BFieldElement::P - 1;
1016        let generator_pow_p = generator.mod_pow(largest_meaningful_power);
1017        let generator_pow_p_half = generator.mod_pow(largest_meaningful_power / 2);
1018
1019        assert_eq!(BFieldElement::ONE, generator_pow_p);
1020        assert_ne!(BFieldElement::ONE, generator_pow_p_half);
1021    }
1022
1023    #[proptest]
1024    fn lift_then_unlift_preserves_element(bfe: BFieldElement) {
1025        prop_assert_eq!(Some(bfe), bfe.lift().unlift());
1026    }
1027
1028    #[proptest]
1029    fn increment(mut bfe: BFieldElement) {
1030        let old_value = bfe.value();
1031        bfe.increment();
1032        let expected_value = (old_value + 1) % BFieldElement::P;
1033        prop_assert_eq!(expected_value, bfe.value());
1034    }
1035
1036    #[test]
1037    fn incrementing_max_value_wraps_around() {
1038        let mut bfe = BFieldElement::new(BFieldElement::MAX);
1039        bfe.increment();
1040        assert_eq!(0, bfe.value());
1041    }
1042
1043    #[proptest]
1044    fn decrement(mut bfe: BFieldElement) {
1045        let old_value = bfe.value();
1046        bfe.decrement();
1047        let expected_value = old_value.checked_sub(1).unwrap_or(BFieldElement::P - 1);
1048        prop_assert_eq!(expected_value, bfe.value());
1049    }
1050
1051    #[test]
1052    fn decrementing_min_value_wraps_around() {
1053        let mut bfe = BFieldElement::ZERO;
1054        bfe.decrement();
1055        assert_eq!(BFieldElement::MAX, bfe.value());
1056    }
1057
1058    #[test]
1059    fn empty_batch_inversion() {
1060        let empty_inv = BFieldElement::batch_inversion(vec![]);
1061        assert!(empty_inv.is_empty());
1062    }
1063
1064    #[proptest]
1065    fn batch_inversion(bfes: Vec<BFieldElement>) {
1066        let bfes_inv = BFieldElement::batch_inversion(bfes.clone());
1067        prop_assert_eq!(bfes.len(), bfes_inv.len());
1068        for (bfe, bfe_inv) in izip!(bfes, bfes_inv) {
1069            prop_assert_eq!(BFieldElement::ONE, bfe * bfe_inv);
1070        }
1071    }
1072
1073    #[test]
1074    fn power_accumulator_simple_test() {
1075        let input_a = [
1076            BFieldElement::new(10),
1077            BFieldElement::new(100),
1078            BFieldElement::new(1000),
1079            BFieldElement::new(1),
1080        ];
1081        let input_b = [
1082            BFieldElement::new(5),
1083            BFieldElement::new(6),
1084            BFieldElement::new(7),
1085            BFieldElement::new(8),
1086        ];
1087        let powers: [BFieldElement; 4] = BFieldElement::power_accumulator::<4, 2>(input_a, input_b);
1088        assert_eq!(BFieldElement::new(50000), powers[0]);
1089        assert_eq!(BFieldElement::new(600000000), powers[1]);
1090        assert_eq!(BFieldElement::new(7000000000000), powers[2]);
1091        assert_eq!(BFieldElement::new(8), powers[3]);
1092    }
1093
1094    #[test]
1095    fn mul_div_plus_minus_neg_property_based_test() {
1096        let elements: Vec<BFieldElement> = random_elements(300);
1097        let power_input_b: [BFieldElement; 6] = random();
1098        for i in 1..elements.len() {
1099            let a = elements[i - 1];
1100            let b = elements[i];
1101
1102            let ab = a * b;
1103            let a_o_b = a / b;
1104            let b_o_a = b / a;
1105            assert_eq!(a, ab / b);
1106            assert_eq!(b, ab / a);
1107            assert_eq!(a, a_o_b * b);
1108            assert_eq!(b, b_o_a * a);
1109            assert!((a_o_b * b_o_a).is_one());
1110            assert_eq!(a * a, a.square());
1111
1112            assert_eq!(a - b + b, a);
1113            assert_eq!(b - a + a, b);
1114            assert!((a - a).is_zero());
1115            assert!((b - b).is_zero());
1116
1117            // Test the add/sub/mul assign operators
1118            let mut a_minus_b = a;
1119            a_minus_b -= b;
1120            assert_eq!(a - b, a_minus_b);
1121
1122            let mut a_plus_b = a;
1123            a_plus_b += b;
1124            assert_eq!(a + b, a_plus_b);
1125
1126            let mut a_mul_b = a;
1127            a_mul_b *= b;
1128            assert_eq!(a * b, a_mul_b);
1129            assert_eq!(b * a, a_mul_b);
1130
1131            // Test negation
1132            assert!((-a + a).is_zero());
1133            assert!((-b + b).is_zero());
1134            assert!((-ab + ab).is_zero());
1135            assert!((-a_o_b + a_o_b).is_zero());
1136            assert!((-b_o_a + b_o_a).is_zero());
1137            assert!((-a_minus_b + a_minus_b).is_zero());
1138            assert!((-a_plus_b + a_plus_b).is_zero());
1139            assert!((-a_mul_b + a_mul_b).is_zero());
1140
1141            // Test power_accumulator
1142            let power_input_a = [a, b, ab, a_o_b, b_o_a, a_minus_b];
1143            let powers = BFieldElement::power_accumulator::<6, 4>(power_input_a, power_input_b);
1144            for ((result_element, input_a), input_b) in powers
1145                .iter()
1146                .zip(power_input_a.iter())
1147                .zip(power_input_b.iter())
1148            {
1149                assert_eq!(input_a.mod_pow(16) * *input_b, *result_element);
1150            }
1151        }
1152    }
1153
1154    #[test]
1155    fn mul_div_pbt() {
1156        // Verify that the mul result is sane
1157        let rands: Vec<BFieldElement> = random_elements(100);
1158        for i in 1..rands.len() {
1159            let prod_mul = rands[i - 1] * rands[i];
1160            let mut prod_mul_assign = rands[i - 1];
1161            prod_mul_assign *= rands[i];
1162            assert_eq!(
1163                prod_mul, prod_mul_assign,
1164                "mul and mul_assign must be the same for B field elements"
1165            );
1166            assert_eq!(prod_mul / rands[i - 1], rands[i]);
1167            assert_eq!(prod_mul / rands[i], rands[i - 1]);
1168        }
1169    }
1170
1171    #[test]
1172    fn add_sub_wrap_around_test() {
1173        // Ensure that something that exceeds P but is smaller than $2^64$
1174        // is still the correct field element. The property-based test is unlikely
1175        // to hit such an element as the chances of doing so are about 2^(-32) for
1176        // random uniform numbers. So we test this in a separate test
1177        let element = BFieldElement::new(4);
1178        let sum = BFieldElement::new(BFieldElement::MAX) + element;
1179        assert_eq!(BFieldElement::new(3), sum);
1180        let diff = sum - element;
1181        assert_eq!(BFieldElement::new(BFieldElement::MAX), diff);
1182    }
1183
1184    #[test]
1185    fn neg_test() {
1186        assert_eq!(-BFieldElement::ZERO, BFieldElement::ZERO);
1187        assert_eq!(
1188            (-BFieldElement::ONE).canonical_representation(),
1189            BFieldElement::MAX
1190        );
1191        let max = BFieldElement::new(BFieldElement::MAX);
1192        let max_plus_one = max + BFieldElement::ONE;
1193        let max_plus_two = max_plus_one + BFieldElement::ONE;
1194        assert_eq!(BFieldElement::ZERO, -max_plus_one);
1195        assert_eq!(max, -max_plus_two);
1196    }
1197
1198    #[test]
1199    fn equality_and_hash_test() {
1200        assert_eq!(BFieldElement::ZERO, BFieldElement::ZERO);
1201        assert_eq!(BFieldElement::ONE, BFieldElement::ONE);
1202        assert_ne!(BFieldElement::ONE, BFieldElement::ZERO);
1203        assert_eq!(BFieldElement::new(42), BFieldElement::new(42));
1204        assert_ne!(BFieldElement::new(42), BFieldElement::new(43));
1205
1206        assert_eq!(
1207            BFieldElement::new(102),
1208            BFieldElement::new(BFieldElement::MAX) + BFieldElement::new(103)
1209        );
1210        assert_ne!(
1211            BFieldElement::new(103),
1212            BFieldElement::new(BFieldElement::MAX) + BFieldElement::new(103)
1213        );
1214
1215        // Verify that hashing works for canonical representations
1216        let mut hasher_a = DefaultHasher::new();
1217        let mut hasher_b = DefaultHasher::new();
1218
1219        std::hash::Hash::hash(&BFieldElement::new(42), &mut hasher_a);
1220        std::hash::Hash::hash(&BFieldElement::new(42), &mut hasher_b);
1221        assert_eq!(hasher_a.finish(), hasher_b.finish());
1222
1223        // Verify that hashing works for non-canonical representations
1224        hasher_a = DefaultHasher::new();
1225        hasher_b = DefaultHasher::new();
1226        let non_canonical = BFieldElement::new(BFieldElement::MAX) + BFieldElement::new(103);
1227        std::hash::Hash::hash(&(non_canonical), &mut hasher_a);
1228        std::hash::Hash::hash(&BFieldElement::new(102), &mut hasher_b);
1229        assert_eq!(hasher_a.finish(), hasher_b.finish());
1230    }
1231
1232    #[test]
1233    fn create_polynomial_test() {
1234        let a = Polynomial::from([1, 3, 7]);
1235        let b = Polynomial::from([2, 5, -1]);
1236        let expected = Polynomial::<BFieldElement>::from([3, 8, 6]);
1237
1238        assert_eq!(expected, a + b);
1239    }
1240
1241    #[test]
1242    fn mod_pow_test_powers_of_two() {
1243        let two = BFieldElement::new(2);
1244        // 2^63 < 2^64, so no wrap-around of B-field element
1245        for i in 0..64 {
1246            assert_eq!(BFieldElement::new(1 << i), two.mod_pow(i));
1247        }
1248    }
1249
1250    #[test]
1251    fn mod_pow_test_powers_of_three() {
1252        let three = BFieldElement::new(3);
1253        // 3^40 < 2^64, so no wrap-around of B-field element
1254        for i in 0..41 {
1255            assert_eq!(BFieldElement::new(3u64.pow(i as u32)), three.mod_pow(i));
1256        }
1257    }
1258
1259    #[test]
1260    fn mod_pow_test() {
1261        // These values were found by finding primitive roots of unity and verifying
1262        // that they are group generators of the right order
1263        assert!(BFieldElement::new(281474976710656).mod_pow(4).is_one());
1264        assert_eq!(
1265            BFieldElement::new(281474976710656),
1266            BFieldElement::new(281474976710656).mod_pow(5)
1267        );
1268        assert!(BFieldElement::new(18446744069414584320).mod_pow(2).is_one());
1269        assert!(BFieldElement::new(18446744069397807105).mod_pow(8).is_one());
1270        assert!(BFieldElement::new(2625919085333925275).mod_pow(10).is_one());
1271        assert!(BFieldElement::new(281474976645120).mod_pow(12).is_one());
1272        assert!(BFieldElement::new(0).mod_pow(0).is_one());
1273    }
1274
1275    #[test]
1276    fn get_primitive_root_of_unity_test() {
1277        for i in 1..33 {
1278            let power = 1 << i;
1279            let root_result = BFieldElement::primitive_root_of_unity(power);
1280            match root_result {
1281                Some(root) => println!("{power} => {root},"),
1282                None => println!("Found no primitive root of unity for n = {power}"),
1283            };
1284            let root = root_result.unwrap();
1285            assert!(root.mod_pow(power).is_one());
1286            assert!(!root.mod_pow(power / 2).is_one());
1287        }
1288    }
1289
1290    #[test]
1291    #[should_panic(expected = "Attempted to find the multiplicative inverse of zero.")]
1292    fn multiplicative_inverse_of_zero() {
1293        let zero = BFieldElement::ZERO;
1294        let _ = zero.inverse();
1295    }
1296
1297    #[test]
1298    fn u32_conversion() {
1299        let val = BFieldElement::new(u32::MAX as u64);
1300        let as_u32: u32 = val.try_into().unwrap();
1301        assert_eq!(u32::MAX, as_u32);
1302
1303        for i in 1..100 {
1304            let invalid_val_0 = BFieldElement::new((u32::MAX as u64) + i);
1305            let converted_0 = TryInto::<u32>::try_into(invalid_val_0);
1306            assert!(converted_0.is_err());
1307        }
1308    }
1309
1310    #[test]
1311    fn inverse_or_zero_bfe() {
1312        let zero = BFieldElement::ZERO;
1313        let one = BFieldElement::ONE;
1314        assert_eq!(zero, zero.inverse_or_zero());
1315
1316        let mut rng = rand::rng();
1317        let elem: BFieldElement = rng.random();
1318        if elem.is_zero() {
1319            assert_eq!(zero, elem.inverse_or_zero())
1320        } else {
1321            assert_eq!(one, elem * elem.inverse_or_zero());
1322        }
1323    }
1324
1325    #[test]
1326    fn test_random_squares() {
1327        let mut rng = rand::rng();
1328        let p = BFieldElement::P;
1329        for _ in 0..100 {
1330            let a = rng.random_range(0..p);
1331            let asq = (((a as u128) * (a as u128)) % (p as u128)) as u64;
1332            let b = BFieldElement::new(a);
1333            let bsq = BFieldElement::new(asq);
1334            assert_eq!(bsq, b * b);
1335            assert_eq!(bsq.value(), (b * b).value());
1336            assert_eq!(b.value(), a);
1337            assert_eq!(bsq.value(), asq);
1338        }
1339        let one = BFieldElement::new(1);
1340        assert_eq!(one, one * one);
1341    }
1342
1343    #[test]
1344    fn equals() {
1345        let a = BFieldElement::ONE;
1346        let b = bfe!(BFieldElement::MAX) * bfe!(BFieldElement::MAX);
1347
1348        // elements are equal
1349        assert_eq!(a, b);
1350        assert_eq!(a.value(), b.value());
1351    }
1352
1353    #[test]
1354    fn test_random_raw() {
1355        let mut rng = rand::rng();
1356        for _ in 0..100 {
1357            let e: BFieldElement = rng.random();
1358            let bytes = e.raw_bytes();
1359            let c = BFieldElement::from_raw_bytes(&bytes);
1360            assert_eq!(e, c);
1361
1362            let mut f = 0u64;
1363            for (i, b) in bytes.iter().enumerate() {
1364                f += (*b as u64) << (8 * i);
1365            }
1366            assert_eq!(e, BFieldElement(f));
1367
1368            let chunks = e.raw_u16s();
1369            let g = BFieldElement::from_raw_u16s(&chunks);
1370            assert_eq!(e, g);
1371
1372            let mut h = 0u64;
1373            for (i, ch) in chunks.iter().enumerate() {
1374                h += (*ch as u64) << (16 * i);
1375            }
1376            assert_eq!(e, BFieldElement(h));
1377        }
1378    }
1379
1380    #[test]
1381    fn test_fixed_inverse() {
1382        // (8561862112314395584, 17307602810081694772)
1383        let a = BFieldElement::new(8561862112314395584);
1384        let a_inv = a.inverse();
1385        let a_inv_or_0 = a.inverse_or_zero();
1386        let expected = BFieldElement::new(17307602810081694772);
1387        assert_eq!(a_inv, a_inv_or_0);
1388        assert_eq!(a_inv, expected);
1389    }
1390
1391    #[test]
1392    fn test_fixed_modpow() {
1393        let exponent = 16608971246357572739u64;
1394        let base = BFieldElement::new(7808276826625786800);
1395        let expected = BFieldElement::new(2288673415394035783);
1396        assert_eq!(base.mod_pow_u64(exponent), expected);
1397    }
1398
1399    #[test]
1400    fn test_fixed_mul() {
1401        {
1402            let a = BFieldElement::new(2779336007265862836);
1403            let b = BFieldElement::new(8146517303801474933);
1404            let c = a * b;
1405            let expected = BFieldElement::new(1857758653037316764);
1406            assert_eq!(c, expected);
1407        }
1408
1409        {
1410            let a = BFieldElement::new(9223372036854775808);
1411            let b = BFieldElement::new(9223372036854775808);
1412            let c = a * b;
1413            let expected = BFieldElement::new(18446744068340842497);
1414            assert_eq!(c, expected);
1415        }
1416    }
1417
1418    #[proptest]
1419    fn conversion_from_i32_to_bfe_is_correct(v: i32) {
1420        let bfe = BFieldElement::from(v);
1421        match v {
1422            0.. => prop_assert_eq!(u64::try_from(v)?, bfe.value()),
1423            _ => prop_assert_eq!(u64::try_from(-v)?, BFieldElement::P - bfe.value()),
1424        }
1425    }
1426
1427    #[proptest]
1428    fn conversion_from_isize_to_bfe_is_correct(v: isize) {
1429        let bfe = BFieldElement::from(v);
1430        match v {
1431            0.. => prop_assert_eq!(u64::try_from(v)?, bfe.value()),
1432            _ => prop_assert_eq!(u64::try_from(-v)?, BFieldElement::P - bfe.value()),
1433        }
1434    }
1435
1436    #[test]
1437    fn bfield_element_can_be_converted_to_and_from_many_types() {
1438        let _ = BFieldElement::from(0_u8);
1439        let _ = BFieldElement::from(0_u16);
1440        let _ = BFieldElement::from(0_u32);
1441        let _ = BFieldElement::from(0_u64);
1442        let _ = BFieldElement::from(0_u128);
1443        let _ = BFieldElement::from(0_usize);
1444
1445        let max = bfe!(BFieldElement::MAX);
1446        assert_eq!(max, BFieldElement::from(-1_i8));
1447        assert_eq!(max, BFieldElement::from(-1_i16));
1448        assert_eq!(max, BFieldElement::from(-1_i32));
1449        assert_eq!(max, BFieldElement::from(-1_i64));
1450        assert_eq!(max, BFieldElement::from(-1_isize));
1451
1452        assert!(u8::try_from(BFieldElement::ZERO).is_ok());
1453        assert!(i8::try_from(BFieldElement::ZERO).is_ok());
1454        assert!(u16::try_from(BFieldElement::ZERO).is_ok());
1455        assert!(i16::try_from(BFieldElement::ZERO).is_ok());
1456        assert!(u32::try_from(BFieldElement::ZERO).is_ok());
1457        assert!(i32::try_from(BFieldElement::ZERO).is_ok());
1458        assert!(usize::try_from(BFieldElement::ZERO).is_ok());
1459        assert!(isize::try_from(BFieldElement::ZERO).is_ok());
1460
1461        let _ = u64::from(max);
1462        let _ = i64::from(max);
1463        let _ = u128::from(max);
1464        let _ = i128::from(max);
1465    }
1466
1467    #[test]
1468    fn bfield_conversion_works_for_types_min_and_max() {
1469        let _ = BFieldElement::from(u8::MIN);
1470        let _ = BFieldElement::from(u8::MAX);
1471        let _ = BFieldElement::from(u16::MIN);
1472        let _ = BFieldElement::from(u16::MAX);
1473        let _ = BFieldElement::from(u32::MIN);
1474        let _ = BFieldElement::from(u32::MAX);
1475        let _ = BFieldElement::from(u64::MIN);
1476        let _ = BFieldElement::from(u64::MAX);
1477        let _ = BFieldElement::from(u128::MIN);
1478        let _ = BFieldElement::from(u128::MAX);
1479        let _ = BFieldElement::from(usize::MIN);
1480        let _ = BFieldElement::from(usize::MAX);
1481        let _ = BFieldElement::from(i8::MIN);
1482        let _ = BFieldElement::from(i8::MAX);
1483        let _ = BFieldElement::from(i16::MIN);
1484        let _ = BFieldElement::from(i16::MAX);
1485        let _ = BFieldElement::from(i32::MIN);
1486        let _ = BFieldElement::from(i32::MAX);
1487        let _ = BFieldElement::from(i64::MIN);
1488        let _ = BFieldElement::from(i64::MAX);
1489        let _ = BFieldElement::from(isize::MIN);
1490        let _ = BFieldElement::from(isize::MAX);
1491    }
1492
1493    #[proptest]
1494    fn naive_and_actual_conversion_from_u128_agree(v: u128) {
1495        fn naive_conversion(x: u128) -> BFieldElement {
1496            let p = BFieldElement::P as u128;
1497            let value = (x % p) as u64;
1498            BFieldElement::new(value)
1499        }
1500
1501        prop_assert_eq!(naive_conversion(v), BFieldElement::from(v));
1502    }
1503
1504    #[proptest]
1505    fn naive_and_actual_conversion_from_i64_agree(v: i64) {
1506        fn naive_conversion(x: i64) -> BFieldElement {
1507            let p = BFieldElement::P as i128;
1508            let value = i128::from(x).rem_euclid(p) as u64;
1509            BFieldElement::new(value)
1510        }
1511
1512        prop_assert_eq!(naive_conversion(v), BFieldElement::from(v));
1513    }
1514
1515    #[test]
1516    fn bfe_macro_can_be_used() {
1517        let b = bfe!(42);
1518        let _ = bfe!(42u32);
1519        let _ = bfe!(-1);
1520        let _ = bfe!(b);
1521        let _ = bfe!(b.0);
1522        let _ = bfe!(42_usize);
1523        let _ = bfe!(-2_isize);
1524
1525        let c: Vec<BFieldElement> = bfe_vec![1, 2, 3];
1526        let d: [BFieldElement; 3] = bfe_array![1, 2, 3];
1527        assert_eq!(c, d);
1528    }
1529
1530    #[proptest]
1531    fn bfe_macro_produces_same_result_as_calling_new(value: u64) {
1532        prop_assert_eq!(BFieldElement::new(value), bfe!(value));
1533    }
1534
1535    #[test]
1536    fn const_minus_two_inverse_is_really_minus_two_inverse() {
1537        assert_eq!(bfe!(-2).inverse(), BFieldElement::MINUS_TWO_INVERSE);
1538    }
1539}
twenty_first/math/b_field_element.rs

twenty_first/math/
b_field_element.rs
