twenty_first/math/
b_field_element.rs

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

twenty_first/math/
b_field_element.rs
