twenty_first/math/
x_field_element.rs

1use std::fmt::Display;
2use std::iter::Sum;
3use std::ops::Add;
4use std::ops::AddAssign;
5use std::ops::Div;
6use std::ops::Mul;
7use std::ops::MulAssign;
8use std::ops::Neg;
9use std::ops::Sub;
10use std::ops::SubAssign;
11
12use arbitrary::Arbitrary;
13use bfieldcodec_derive::BFieldCodec;
14use num_traits::ConstOne;
15use num_traits::ConstZero;
16use num_traits::One;
17use num_traits::Zero;
18use rand::Rng;
19use rand::distr::Distribution;
20use rand::distr::StandardUniform;
21use serde::Deserialize;
22use serde::Serialize;
23
24use crate::bfe_vec;
25use crate::error::TryFromXFieldElementError;
26use crate::math::b_field_element::BFieldElement;
27use crate::math::polynomial::Polynomial;
28use crate::math::traits::CyclicGroupGenerator;
29use crate::math::traits::FiniteField;
30use crate::math::traits::Inverse;
31use crate::math::traits::ModPowU32;
32use crate::math::traits::ModPowU64;
33use crate::math::traits::PrimitiveRootOfUnity;
34use crate::tip5::Digest;
35
36pub const EXTENSION_DEGREE: usize = 3;
37
38#[derive(
39    Debug, PartialEq, Eq, Copy, Clone, Hash, Serialize, Deserialize, BFieldCodec, Arbitrary,
40)]
41#[repr(transparent)]
42pub struct XFieldElement {
43    pub coefficients: [BFieldElement; EXTENSION_DEGREE],
44}
45
46/// Simplifies constructing [extension field element](XFieldElement)s.
47///
48/// The type [`XFieldElement`] must be in scope for this macro to work.
49/// See [`XFieldElement::from`] for supported types.
50///
51/// # Examples
52///
53/// ```
54/// # use twenty_first::prelude::*;
55/// let a = xfe!(1);
56/// let b = xfe!([2, 0, 5]);
57/// let c = xfe!([3, 0, 2 + 3]);
58/// assert_eq!(a + b, c);
59/// ```
60#[macro_export]
61macro_rules! xfe {
62    ($value:expr) => {
63        XFieldElement::from($value)
64    };
65}
66
67/// Simplifies constructing vectors of [extension field element][XFieldElement]s.
68///
69/// The type [`XFieldElement`] must be in scope for this macro to work. See also [`xfe!`].
70///
71/// # Examples
72///
73/// Vector of [constants](XFieldElement::new_const).
74///
75/// ```
76/// # use twenty_first::prelude::*;
77/// let a = xfe_vec![1, 2, 3];
78/// let b = vec![xfe!(1), xfe!(2), xfe!(3)];
79/// assert_eq!(a, b);
80/// ```
81///
82/// Vector of general [extension field element](XFieldElement)s.
83///
84/// ```
85/// # use twenty_first::prelude::*;
86/// let a = xfe_vec![[1, 0, 0], [0, 2, 0], [0, 0, 3]];
87/// let b = vec![xfe!([1, 0, 0]), xfe!([0, 2, 0]), xfe!([0, 0, 3])];
88/// assert_eq!(a, b);
89/// ```
90///
91/// Vector with the same [constant](XFieldElement::new_const) for every entry.
92///
93/// ```
94/// # use twenty_first::prelude::*;
95/// let a = xfe_vec![42; 15];
96/// let b = vec![xfe!(42); 15];
97/// assert_eq!(a, b);
98/// ```
99///
100/// Vector with the same general [extension field element](XFieldElement) for every entry.
101///
102/// ```
103/// # use twenty_first::prelude::*;
104/// let a = xfe_vec![[42, 43, 44]; 15];
105/// let b = vec![xfe!([42, 43, 44]); 15];
106/// assert_eq!(a, b);
107/// ```
108#[macro_export]
109macro_rules! xfe_vec {
110    ($x:expr; $n:expr) => {
111        vec![XFieldElement::from($x); $n]
112    };
113    ([$c0:expr, $c1:expr, $c2:expr]; $n:expr) => {
114        vec![XFieldElement::from([$c0, $c1, $c2]); $n]
115    };
116    ($($x:expr),* $(,)?) => {
117        vec![$(XFieldElement::from($x)),*]
118    };
119    ($([$c0:expr, $c1:expr, $c2:expr]),* $(,)?) => {
120        vec![$(XFieldElement::from([$c0, $c1, $c2])),*]
121    };
122}
123
124/// Simplifies constructing arrays of [extension field element][XFieldElement]s.
125///
126/// The type [`XFieldElement`] must be in scope for this macro to work. See also [`xfe!`].
127///
128/// # Examples
129///
130/// Array of [constants](XFieldElement::new_const).
131///
132/// ```
133/// # use twenty_first::prelude::*;
134/// let a = xfe_array![1, 2, 3];
135/// let b = [xfe!(1), xfe!(2), xfe!(3)];
136/// assert_eq!(a, b);
137/// ```
138///
139/// Array of general [extension field element](XFieldElement)s.
140///
141/// ```
142/// # use twenty_first::prelude::*;
143/// let a = xfe_array![[1, 0, 0], [0, 2, 0], [0, 0, 3]];
144/// let b = [xfe!([1, 0, 0]), xfe!([0, 2, 0]), xfe!([0, 0, 3])];
145/// assert_eq!(a, b);
146/// ```
147///
148/// Array with the same [constant](XFieldElement::new_const) for every entry.
149///
150/// ```
151/// # use twenty_first::prelude::*;
152/// let a = xfe_array![42; 15];
153/// let b = [xfe!(42); 15];
154/// assert_eq!(a, b);
155/// ```
156///
157/// Array with the same general [extension field element](XFieldElement) for every entry.
158///
159/// ```
160/// # use twenty_first::prelude::*;
161/// let a = xfe_array![[42, 43, 44]; 15];
162/// let b = [xfe!([42, 43, 44]); 15];
163/// assert_eq!(a, b);
164/// ```
165#[macro_export]
166macro_rules! xfe_array {
167    ($x:expr; $n:expr) => {
168        [XFieldElement::from($x); $n]
169    };
170    ([$c0:expr, $c1:expr, $c2:expr]; $n:expr) => {
171        [XFieldElement::from([$c0, $c1, $c2]); $n]
172    };
173    ($($x:expr),* $(,)?) => {
174        [$(XFieldElement::from($x)),*]
175    };
176    ($([$c0:expr, $c1:expr, $c2:expr]),* $(,)?) => {
177        [$(XFieldElement::from([$c0, $c1, $c2])),*]
178    };
179}
180
181/// Re-interpret a slice of [`XFieldElement`]s as a slice of [`BFieldElement`]s
182/// without any memory allocation.
183///
184/// This function is semantically similar to [flat-mapping] the coefficients of
185/// the `XFieldElement`s (see examples). However, this function does not perform
186/// any memory allocation, which makes is particularly useful in
187/// high-performance scenarios.
188///
189/// # Examples
190///
191/// Re-interpretation behaves like flattening, but does not allocate or copy any
192/// data.
193///
194/// ```
195/// # use twenty_first::prelude::*;
196/// # use twenty_first::math::x_field_element::as_flat_slice;
197/// let xfes = xfe_vec![[17, 18, 19], [42, 42, 44], [97, 98, 99]];
198/// let bfes = bfe_vec![17, 18, 19, 42, 42, 44, 97, 98, 99];
199/// assert_eq!(&bfes, as_flat_slice(&xfes));
200/// ```
201///
202/// This can be particularly useful for hashing sequences of [`XFieldElement]`s,
203/// where ownership is irrelevant:
204///
205/// ```
206/// # use twenty_first::prelude::*;
207/// # use twenty_first::math::x_field_element::as_flat_slice;
208/// let xfes = xfe_vec![42; 17];
209/// let xfe_digest = Tip5::hash_varlen(as_flat_slice(&xfes));
210///
211/// // alternative requires copying data
212/// let bfes = xfes.into_iter().flat_map(|xfe| xfe.coefficients).collect::<Vec<_>>();
213/// let bfe_digest = Tip5::hash_varlen(&bfes);
214///
215/// assert_eq!(bfe_digest, xfe_digest);
216/// ```
217///
218/// [hashing]: crate::tip5::Tip5::hash_varlen
219/// [Tip5]: crate::tip5::Tip5
220/// [flat-mapping]: Iterator::flat_map
221pub fn as_flat_slice(xfe_slice: &[XFieldElement]) -> &[BFieldElement] {
222    let slice_pointer = xfe_slice.as_ptr() as *const BFieldElement;
223    let bfe_slice_len = xfe_slice.len() * EXTENSION_DEGREE;
224
225    // SAFETY:
226    // - The slice_pointer is non-null, and is valid for reads for
227    //   xfe_slice.len() * size_of::<XFieldElement>() ==
228    //   xfe_slice.len() * size_of::<BFieldElement>() * EXTENSION_DEGREE
229    //   many bytes, and is properly aligned because both BFieldElement and
230    //   XFieldElement are #[repr(transparent)]. In particular:
231    //   - The entire memory range of the slice is contained within a single
232    //     allocated object. This is because of
233    //     (a) the origin of `slice_pointer` being a slice, and
234    //     (b) the layout and ABI of XFieldElement is identical to
235    //         [BFieldElement; EXTENSION_DEGREE] because of
236    //         #[repr(transparent)]
237    //   - The slice_pointer is non-null and aligned, again because of
238    //     #[repr(transparent)] on BFieldElement and XFieldElement.
239    // - The slice_pointer points to xfe_slice.len() * EXTENSION_DEGREE
240    //   consecutive properly initialized values of type BFieldElement,
241    //   again because of #[repr(transparent)] on BFieldElement and
242    //   XFieldElement.
243    // - The memory referenced by the returned slice cannot be mutated for
244    //   the duration of the lifetime of xfe_slice thanks to rust's
245    //   “mut XOR shared” compile time guarantees.
246    // - The total size of the produced slice is no larger than isize::MAX
247    //   since it is identical to the total size of the initial size, and
248    //   adding that size to the slice_pointer does not “wrap around” the
249    //   address space because both, the slice_pointer and the total size
250    //   have been obtained through safe code or unsafe code for which the
251    //   safety invariants have been upheld.
252    unsafe { std::slice::from_raw_parts(slice_pointer, bfe_slice_len) }
253}
254
255impl From<XFieldElement> for Digest {
256    /// Interpret the `XFieldElement` as a [`Digest`]. No hashing is performed.
257    /// This interpretation can be useful for [`Tip5`](crate::prelude::Tip5)
258    /// and, by extension, allows building
259    /// [`MerkleTree`](crate::prelude::MerkleTree)s directly from
260    /// `XFieldElement`s.
261    fn from(xfe: XFieldElement) -> Self {
262        let [c0, c1, c2] = xfe.coefficients;
263        Digest::new([c0, c1, c2, BFieldElement::ZERO, BFieldElement::ZERO])
264    }
265}
266
267impl TryFrom<Digest> for XFieldElement {
268    type Error = TryFromXFieldElementError;
269
270    fn try_from(digest: Digest) -> Result<Self, Self::Error> {
271        let Digest([c0, c1, c2, BFieldElement::ZERO, BFieldElement::ZERO]) = digest else {
272            return Err(TryFromXFieldElementError::InvalidDigest);
273        };
274
275        Ok(Self::new([c0, c1, c2]))
276    }
277}
278
279impl Sum for XFieldElement {
280    fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
281        iter.reduce(|a, b| a + b).unwrap_or(XFieldElement::ZERO)
282    }
283}
284
285impl<T> From<T> for XFieldElement
286where
287    T: Into<BFieldElement>,
288{
289    fn from(value: T) -> Self {
290        Self::new_const(value.into())
291    }
292}
293
294impl<T> From<[T; EXTENSION_DEGREE]> for XFieldElement
295where
296    T: Into<BFieldElement>,
297{
298    fn from(value: [T; EXTENSION_DEGREE]) -> Self {
299        Self::new(value.map(Into::into))
300    }
301}
302
303impl From<Polynomial<'_, BFieldElement>> for XFieldElement {
304    fn from(poly: Polynomial<'_, BFieldElement>) -> Self {
305        let (_, rem) = poly.naive_divide(&Self::shah_polynomial());
306        let mut xfe = [BFieldElement::ZERO; EXTENSION_DEGREE];
307
308        let Ok(rem_degree) = usize::try_from(rem.degree()) else {
309            return Self::ZERO;
310        };
311        xfe[..=rem_degree].copy_from_slice(&rem.coefficients()[..=rem_degree]);
312
313        XFieldElement::new(xfe)
314    }
315}
316
317impl TryFrom<&[BFieldElement]> for XFieldElement {
318    type Error = TryFromXFieldElementError;
319
320    fn try_from(value: &[BFieldElement]) -> Result<Self, Self::Error> {
321        value
322            .try_into()
323            .map(XFieldElement::new)
324            .map_err(|_| Self::Error::InvalidLength(value.len()))
325    }
326}
327
328impl TryFrom<Vec<BFieldElement>> for XFieldElement {
329    type Error = TryFromXFieldElementError;
330
331    fn try_from(value: Vec<BFieldElement>) -> Result<Self, Self::Error> {
332        XFieldElement::try_from(value.as_ref())
333    }
334}
335
336impl XFieldElement {
337    /// The quotient defining the [field extension](XFieldElement) over the
338    /// [base field](BFieldElement), namely x³ - x + 1.
339    #[inline]
340    pub fn shah_polynomial() -> Polynomial<'static, BFieldElement> {
341        Polynomial::new(bfe_vec![1, -1, 0, 1])
342    }
343
344    #[inline]
345    pub const fn new(coefficients: [BFieldElement; EXTENSION_DEGREE]) -> Self {
346        Self { coefficients }
347    }
348
349    #[inline]
350    pub const fn new_const(element: BFieldElement) -> Self {
351        let zero = BFieldElement::ZERO;
352        Self::new([element, zero, zero])
353    }
354
355    #[must_use]
356    pub fn inverse(&self) -> Self {
357        assert!(
358            !self.is_zero(),
359            "Cannot invert the zero element in the extension field."
360        );
361        let self_as_poly: Polynomial<BFieldElement> = self.to_owned().into();
362        let (_, a, _) = Polynomial::<BFieldElement>::xgcd(self_as_poly, Self::shah_polynomial());
363        a.into()
364    }
365
366    pub fn unlift(&self) -> Option<BFieldElement> {
367        if self.coefficients[1].is_zero() && self.coefficients[2].is_zero() {
368            Some(self.coefficients[0])
369        } else {
370            None
371        }
372    }
373
374    // `increment` and `decrement` are mainly used for testing purposes
375    pub fn increment(&mut self, index: usize) {
376        self.coefficients[index].increment();
377    }
378
379    pub fn decrement(&mut self, index: usize) {
380        self.coefficients[index].decrement();
381    }
382}
383
384impl Inverse for XFieldElement {
385    fn inverse(&self) -> Self {
386        self.inverse()
387    }
388}
389
390impl PrimitiveRootOfUnity for XFieldElement {
391    fn primitive_root_of_unity(n: u64) -> Option<XFieldElement> {
392        let b_root = BFieldElement::primitive_root_of_unity(n);
393        b_root.map(XFieldElement::new_const)
394    }
395}
396
397impl Distribution<XFieldElement> for StandardUniform {
398    fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> XFieldElement {
399        XFieldElement::new(rng.random())
400    }
401}
402
403impl CyclicGroupGenerator for XFieldElement {
404    fn get_cyclic_group_elements(&self, max: Option<usize>) -> Vec<Self> {
405        let mut val = *self;
406        let mut ret: Vec<Self> = vec![Self::one()];
407
408        loop {
409            ret.push(val);
410            val *= *self;
411            if val.is_one() || max.is_some() && ret.len() >= max.unwrap() {
412                break;
413            }
414        }
415        ret
416    }
417}
418
419impl Display for XFieldElement {
420    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
421        if let Some(bfe) = self.unlift() {
422            return write!(f, "{bfe}_xfe");
423        }
424
425        let [c0, c1, c2] = self.coefficients;
426        write!(f, "({c2:>020}·x² + {c1:>020}·x + {c0:>020})")
427    }
428}
429
430impl Zero for XFieldElement {
431    fn zero() -> Self {
432        Self::ZERO
433    }
434
435    fn is_zero(&self) -> bool {
436        self == &Self::ZERO
437    }
438}
439
440impl ConstZero for XFieldElement {
441    const ZERO: Self = Self::new([BFieldElement::ZERO; EXTENSION_DEGREE]);
442}
443
444impl One for XFieldElement {
445    fn one() -> Self {
446        Self::ONE
447    }
448
449    fn is_one(&self) -> bool {
450        self == &Self::ONE
451    }
452}
453
454impl ConstOne for XFieldElement {
455    const ONE: Self = Self::new([BFieldElement::ONE, BFieldElement::ZERO, BFieldElement::ZERO]);
456}
457
458impl FiniteField for XFieldElement {}
459
460impl Add<XFieldElement> for XFieldElement {
461    type Output = Self;
462
463    #[inline]
464    fn add(self, other: Self) -> Self {
465        let [s0, s1, s2] = self.coefficients;
466        let [o0, o1, o2] = other.coefficients;
467        let coefficients = [s0 + o0, s1 + o1, s2 + o2];
468        Self { coefficients }
469    }
470}
471
472impl Add<BFieldElement> for XFieldElement {
473    type Output = Self;
474
475    #[inline]
476    fn add(mut self, other: BFieldElement) -> Self {
477        self.coefficients[0] += other;
478        self
479    }
480}
481
482/// The `bfe + xfe -> xfe` instance belongs to BFieldElement.
483impl Add<XFieldElement> for BFieldElement {
484    type Output = XFieldElement;
485
486    #[inline]
487    fn add(self, mut other: XFieldElement) -> XFieldElement {
488        other.coefficients[0] += self;
489        other
490    }
491}
492
493impl Mul<XFieldElement> for XFieldElement {
494    type Output = Self;
495
496    #[inline]
497    fn mul(self, other: Self) -> Self {
498        // XField * XField means:
499        //
500        // (ax^2 + bx + c) * (dx^2 + ex + f)   (mod x^3 - x + 1)
501        //
502        // =   adx^4 + aex^3 + afx^2
503        //   + bdx^3 + bex^2 + bfx
504        //   + cdx^2 + cex   + cf
505        //
506        // = adx^4 + (ae + bd)x^3 + (af + be + cd)x^2 + (bf + ce)x + cf   (mod x^3 - x + 1)
507
508        let [c, b, a] = self.coefficients;
509        let [f, e, d] = other.coefficients;
510
511        let r0 = c * f - a * e - b * d;
512        let r1 = b * f + c * e - a * d + a * e + b * d;
513        let r2 = a * f + b * e + c * d + a * d;
514
515        Self::new([r0, r1, r2])
516    }
517}
518
519/// XField * BField means scalar multiplication of the
520/// BFieldElement onto each coefficient of the XField.
521impl Mul<BFieldElement> for XFieldElement {
522    type Output = Self;
523
524    #[inline]
525    fn mul(self, other: BFieldElement) -> Self {
526        let coefficients = self.coefficients.map(|c| c * other);
527        Self { coefficients }
528    }
529}
530
531impl Mul<XFieldElement> for BFieldElement {
532    type Output = XFieldElement;
533
534    #[inline]
535    fn mul(self, other: XFieldElement) -> XFieldElement {
536        let coefficients = other.coefficients.map(|c| c * self);
537        XFieldElement { coefficients }
538    }
539}
540
541impl Neg for XFieldElement {
542    type Output = Self;
543
544    #[inline]
545    fn neg(self) -> Self {
546        let coefficients = self.coefficients.map(Neg::neg);
547        Self { coefficients }
548    }
549}
550
551impl Sub<XFieldElement> for XFieldElement {
552    type Output = Self;
553
554    #[inline]
555    fn sub(self, other: Self) -> Self {
556        self + (-other)
557    }
558}
559
560impl Sub<BFieldElement> for XFieldElement {
561    type Output = Self;
562
563    #[inline]
564    fn sub(self, other: BFieldElement) -> Self {
565        self + (-other)
566    }
567}
568
569impl Sub<XFieldElement> for BFieldElement {
570    type Output = XFieldElement;
571
572    #[inline]
573    fn sub(self, other: XFieldElement) -> XFieldElement {
574        self + (-other)
575    }
576}
577
578impl AddAssign<XFieldElement> for XFieldElement {
579    #[inline]
580    fn add_assign(&mut self, rhs: Self) {
581        self.coefficients[0] += rhs.coefficients[0];
582        self.coefficients[1] += rhs.coefficients[1];
583        self.coefficients[2] += rhs.coefficients[2];
584    }
585}
586
587impl AddAssign<BFieldElement> for XFieldElement {
588    #[inline]
589    fn add_assign(&mut self, rhs: BFieldElement) {
590        self.coefficients[0] += rhs;
591    }
592}
593
594impl MulAssign<XFieldElement> for XFieldElement {
595    #[inline]
596    fn mul_assign(&mut self, rhs: Self) {
597        *self = *self * rhs;
598    }
599}
600
601impl MulAssign<BFieldElement> for XFieldElement {
602    #[inline]
603    fn mul_assign(&mut self, rhs: BFieldElement) {
604        *self = *self * rhs;
605    }
606}
607
608impl SubAssign<XFieldElement> for XFieldElement {
609    #[inline]
610    fn sub_assign(&mut self, rhs: Self) {
611        self.coefficients[0] -= rhs.coefficients[0];
612        self.coefficients[1] -= rhs.coefficients[1];
613        self.coefficients[2] -= rhs.coefficients[2];
614    }
615}
616
617impl SubAssign<BFieldElement> for XFieldElement {
618    #[inline]
619    fn sub_assign(&mut self, rhs: BFieldElement) {
620        self.coefficients[0] -= rhs;
621    }
622}
623
624impl Div for XFieldElement {
625    type Output = Self;
626
627    #[expect(clippy::suspicious_arithmetic_impl)]
628    fn div(self, other: Self) -> Self {
629        self * other.inverse()
630    }
631}
632
633impl ModPowU64 for XFieldElement {
634    #[inline]
635    fn mod_pow_u64(&self, exponent: u64) -> Self {
636        let mut x = *self;
637        let mut result = Self::one();
638        let mut i = exponent;
639
640        while i > 0 {
641            if i & 1 == 1 {
642                result *= x;
643            }
644
645            x *= x;
646            i >>= 1;
647        }
648
649        result
650    }
651}
652
653impl ModPowU32 for XFieldElement {
654    #[inline]
655    fn mod_pow_u32(&self, exp: u32) -> Self {
656        self.mod_pow_u64(exp as u64)
657    }
658}
659
660#[cfg(test)]
661#[cfg_attr(coverage_nightly, coverage(off))]
662mod tests {
663    use itertools::Itertools;
664    use itertools::izip;
665    use num_traits::ConstOne;
666    use proptest::collection::vec;
667    use proptest::prelude::*;
668    use proptest_arbitrary_interop::arb;
669    use test_strategy::proptest;
670
671    use super::*;
672    use crate::bfe;
673    use crate::math::b_field_element::*;
674    use crate::math::ntt::intt;
675    use crate::math::ntt::ntt;
676    use crate::math::other::random_elements;
677
678    impl proptest::arbitrary::Arbitrary for XFieldElement {
679        type Parameters = ();
680
681        fn arbitrary_with(_: Self::Parameters) -> Self::Strategy {
682            arb().boxed()
683        }
684
685        type Strategy = BoxedStrategy<Self>;
686    }
687
688    #[test]
689    fn one_zero_test() {
690        let one = XFieldElement::one();
691        assert!(one.is_one());
692        assert!(one.coefficients[0].is_one());
693        assert!(one.coefficients[1].is_zero());
694        assert!(one.coefficients[2].is_zero());
695        assert_eq!(one, XFieldElement::ONE);
696        let zero = XFieldElement::zero();
697        assert!(zero.is_zero());
698        assert!(zero.coefficients[0].is_zero());
699        assert!(zero.coefficients[1].is_zero());
700        assert!(zero.coefficients[2].is_zero());
701        assert_eq!(zero, XFieldElement::ZERO);
702        let two = XFieldElement::new([
703            BFieldElement::new(2),
704            BFieldElement::ZERO,
705            BFieldElement::ZERO,
706        ]);
707        assert!(!two.is_one());
708        assert!(!zero.is_one());
709        let one_as_constant_term_0 = XFieldElement::new([
710            BFieldElement::new(1),
711            BFieldElement::ONE,
712            BFieldElement::ZERO,
713        ]);
714        let one_as_constant_term_1 = XFieldElement::new([
715            BFieldElement::new(1),
716            BFieldElement::ZERO,
717            BFieldElement::ONE,
718        ]);
719        assert!(!one_as_constant_term_0.is_one());
720        assert!(!one_as_constant_term_1.is_one());
721        assert!(!one_as_constant_term_0.is_zero());
722        assert!(!one_as_constant_term_1.is_zero());
723    }
724
725    #[test]
726    fn x_field_random_element_generation_test() {
727        let rand_xs: Vec<XFieldElement> = random_elements(14);
728        assert_eq!(14, rand_xs.len());
729
730        // TODO: Consider doing a statistical test.
731        assert!(rand_xs.into_iter().all_unique());
732    }
733
734    #[test]
735    fn incr_decr_test() {
736        let one_const = XFieldElement::new([1, 0, 0].map(BFieldElement::new));
737        let two_const = XFieldElement::new([2, 0, 0].map(BFieldElement::new));
738        let one_x = XFieldElement::new([0, 1, 0].map(BFieldElement::new));
739        let two_x = XFieldElement::new([0, 2, 0].map(BFieldElement::new));
740        let one_x_squared = XFieldElement::new([0, 0, 1].map(BFieldElement::new));
741        let two_x_squared = XFieldElement::new([0, 0, 2].map(BFieldElement::new));
742        let max_const = XFieldElement::new([BFieldElement::MAX, 0, 0].map(BFieldElement::new));
743        let max_x = XFieldElement::new([0, BFieldElement::MAX, 0].map(BFieldElement::new));
744        let max_x_squared = XFieldElement::new([0, 0, BFieldElement::MAX].map(BFieldElement::new));
745        let mut val = XFieldElement::ZERO;
746        val.increment(0);
747        assert!(val.is_one());
748        val.increment(0);
749        assert_eq!(two_const, val);
750        val.decrement(0);
751        assert!(val.is_one());
752        val.decrement(0);
753        assert!(val.is_zero());
754        val.decrement(0);
755        assert_eq!(max_const, val);
756        val.decrement(0);
757        assert_eq!(max_const - XFieldElement::ONE, val);
758        val.decrement(0);
759        assert_eq!(max_const - XFieldElement::ONE - XFieldElement::ONE, val);
760        val.increment(0);
761        val.increment(0);
762        val.increment(0);
763        assert!(val.is_zero());
764        val.increment(1);
765        assert_eq!(one_x, val);
766        val.increment(1);
767        assert_eq!(two_x, val);
768        val.decrement(1);
769        val.decrement(1);
770        assert!(val.is_zero());
771        val.decrement(1);
772        assert_eq!(max_x, val);
773        val.increment(1);
774        val.increment(2);
775        assert_eq!(one_x_squared, val);
776        val.increment(2);
777        assert_eq!(two_x_squared, val);
778        val.decrement(2);
779        val.decrement(2);
780        assert!(val.is_zero());
781        val.decrement(2);
782        assert_eq!(max_x_squared, val);
783        val.decrement(1);
784        val.decrement(0);
785        assert_eq!(max_x_squared + max_x + max_const, val);
786        val.decrement(2);
787        val.decrement(1);
788        val.decrement(0);
789        assert_eq!(
790            max_x_squared + max_x + max_const - one_const - one_x - one_x_squared,
791            val
792        );
793    }
794
795    #[test]
796    fn x_field_add_test() {
797        let poly1 = XFieldElement::new([2, 0, 0].map(BFieldElement::new));
798        let poly2 = XFieldElement::new([3, 0, 0].map(BFieldElement::new));
799
800        let mut poly_sum = XFieldElement::new([5, 0, 0].map(BFieldElement::new));
801        assert_eq!(poly_sum, poly1 + poly2);
802
803        let poly3 = XFieldElement::new([0, 5, 0].map(BFieldElement::new));
804        let poly4 = XFieldElement::new([0, 7, 0].map(BFieldElement::new));
805
806        poly_sum = XFieldElement::new([0, 12, 0].map(BFieldElement::new));
807        assert_eq!(poly_sum, poly3 + poly4);
808
809        let poly5 = XFieldElement::new([0, 0, 14].map(BFieldElement::new));
810        let poly6 = XFieldElement::new([0, 0, 23].map(BFieldElement::new));
811
812        poly_sum = XFieldElement::new([0, 0, 37].map(BFieldElement::new));
813        assert_eq!(poly_sum, poly5 + poly6);
814
815        let poly7 = XFieldElement::new([0, 0, BFieldElement::MAX].map(BFieldElement::new));
816        let poly8 = XFieldElement::new([0, 0, 23].map(BFieldElement::new));
817
818        poly_sum = XFieldElement::new([0, 0, 22].map(BFieldElement::new));
819        assert_eq!(poly_sum, poly7 + poly8);
820
821        let poly9 = XFieldElement::new([BFieldElement::MAX - 2, 12, 4].map(BFieldElement::new));
822        let poly10 = XFieldElement::new([2, 45000, BFieldElement::MAX - 3].map(BFieldElement::new));
823
824        poly_sum = XFieldElement::new([BFieldElement::MAX, 45012, 0].map(BFieldElement::new));
825        assert_eq!(poly_sum, poly9 + poly10);
826    }
827
828    #[test]
829    fn x_field_sub_test() {
830        let poly1 = XFieldElement::new([2, 0, 0].map(BFieldElement::new));
831        let poly2 = XFieldElement::new([3, 0, 0].map(BFieldElement::new));
832
833        let mut poly_diff = XFieldElement::new([1, 0, 0].map(BFieldElement::new));
834        assert_eq!(poly_diff, poly2 - poly1);
835
836        let poly3 = XFieldElement::new([0, 5, 0].map(BFieldElement::new));
837        let poly4 = XFieldElement::new([0, 7, 0].map(BFieldElement::new));
838
839        poly_diff = XFieldElement::new([0, 2, 0].map(BFieldElement::new));
840        assert_eq!(poly_diff, poly4 - poly3);
841
842        let poly5 = XFieldElement::new([0, 0, 14].map(BFieldElement::new));
843        let poly6 = XFieldElement::new([0, 0, 23].map(BFieldElement::new));
844
845        poly_diff = XFieldElement::new([0, 0, 9].map(BFieldElement::new));
846        assert_eq!(poly_diff, poly6 - poly5);
847
848        let poly7 = XFieldElement::new([0, 0, BFieldElement::MAX].map(BFieldElement::new));
849        let poly8 = XFieldElement::new([0, 0, 23].map(BFieldElement::new));
850
851        poly_diff = XFieldElement::new([0, 0, 24].map(BFieldElement::new));
852        assert_eq!(poly_diff, poly8 - poly7);
853
854        let poly9 = XFieldElement::new([BFieldElement::MAX - 2, 12, 4].map(BFieldElement::new));
855        let poly10 = XFieldElement::new([2, 45000, BFieldElement::MAX - 3].map(BFieldElement::new));
856
857        poly_diff = XFieldElement::new([5, 44988, BFieldElement::MAX - 7].map(BFieldElement::new));
858        assert_eq!(poly_diff, poly10 - poly9);
859    }
860
861    #[test]
862    fn x_field_mul_test() {
863        let poly1 = XFieldElement::new([2, 0, 0].map(BFieldElement::new));
864        let poly2 = XFieldElement::new([3, 0, 0].map(BFieldElement::new));
865
866        let poly12_product = XFieldElement::new([6, 0, 0].map(BFieldElement::new));
867        assert_eq!(poly12_product, poly1 * poly2);
868
869        let poly3 = XFieldElement::new([0, 3, 0].map(BFieldElement::new));
870        let poly4 = XFieldElement::new([0, 3, 0].map(BFieldElement::new));
871
872        let poly34_product = XFieldElement::new([0, 0, 9].map(BFieldElement::new));
873        assert_eq!(poly34_product, poly3 * poly4);
874
875        let poly5 = XFieldElement::new([125, 0, 0].map(BFieldElement::new));
876        let poly6 = XFieldElement::new([0, 0, 5].map(BFieldElement::new));
877
878        let poly56_product = XFieldElement::new([0, 0, 625].map(BFieldElement::new));
879        assert_eq!(poly56_product, poly5 * poly6);
880
881        // x^2 * x^2 = x^4 = x^2 - x mod (x^3 - x + 1)
882        let poly7 = XFieldElement::new([0, 0, 1].map(BFieldElement::new));
883        let poly8 = XFieldElement::new([0, 0, 1].map(BFieldElement::new));
884
885        let poly78_product = XFieldElement::new([0, BFieldElement::MAX, 1].map(BFieldElement::new));
886        assert_eq!(poly78_product, poly7 * poly8);
887
888        // x^2 * x = x^3 = x - 1 mod (x^3 - x + 1)
889        let poly9 = XFieldElement::new([0, 1, 0].map(BFieldElement::new));
890        let poly10 = XFieldElement::new([0, 0, 1].map(BFieldElement::new));
891
892        let poly910_product =
893            XFieldElement::new([BFieldElement::MAX, 1, 0].map(BFieldElement::new));
894        assert_eq!(poly910_product, poly9 * poly10);
895
896        // (13+2x+3x2)(19+5x2) = 247+122x^2+38x+10x^3+15x^4
897        let poly11 = XFieldElement::new([13, 2, 3].map(BFieldElement::new));
898        let poly12 = XFieldElement::new([19, 0, 5].map(BFieldElement::new));
899
900        let poly1112_product = XFieldElement::new([237, 33, 137].map(BFieldElement::new));
901        assert_eq!(poly1112_product, poly11 * poly12);
902    }
903
904    #[test]
905    fn x_field_overloaded_arithmetic_test() {
906        let mut rng = rand::rng();
907        for _ in 0..100 {
908            let xfe = rng.random::<XFieldElement>();
909            let bfe = rng.random::<BFieldElement>();
910
911            // 1. xfe + bfe.lift() = bfe.lift() + xfe
912            // 2. xfe + bfe = xfe + bfe.lift()
913            // 3. bfe + xfe = xfe + bfe.lift()
914            let expected_add = xfe + bfe.lift();
915            assert_eq!(expected_add, bfe.lift() + xfe);
916            assert_eq!(expected_add, xfe + bfe);
917            assert_eq!(expected_add, bfe + xfe);
918
919            // 4. xfe * bfe.lift() = bfe.lift() * xfe
920            // 5. xfe * bfe = xfe * bfe.lift()
921            // 6. bfe * xfe = xfe * bfe.lift()
922            let expected_mul = xfe * bfe.lift();
923            assert_eq!(expected_mul, bfe.lift() * xfe);
924            assert_eq!(expected_mul, xfe * bfe);
925            assert_eq!(expected_mul, bfe * xfe);
926
927            // 7. xfe - bfe = xfe - bfe.lift()
928            // 8. bfe - xfe = xfe - bfe.lift()
929            assert_eq!(xfe - bfe.lift(), xfe - bfe);
930            assert_eq!(bfe.lift() - xfe, bfe - xfe);
931        }
932    }
933
934    #[test]
935    fn x_field_into_test() {
936        let zero_poly: XFieldElement = Polynomial::<BFieldElement>::new(vec![]).into();
937        assert!(zero_poly.is_zero());
938
939        let shah_zero: XFieldElement = XFieldElement::shah_polynomial().into();
940        assert!(shah_zero.is_zero());
941
942        let neg_shah_zero: XFieldElement =
943            XFieldElement::shah_polynomial().scalar_mul(bfe!(-1)).into();
944        assert!(neg_shah_zero.is_zero());
945    }
946
947    #[test]
948    fn x_field_xgcp_test() {
949        // Verify expected properties of XGCP: symmetry and that gcd is always
950        // one. gcd is always one for all field elements.
951        let one = XFieldElement::new([1, 0, 0].map(BFieldElement::new));
952        let two = XFieldElement::new([2, 0, 0].map(BFieldElement::new));
953        let hundred = XFieldElement::new([100, 0, 0].map(BFieldElement::new));
954        let x = XFieldElement::new([0, 1, 0].map(BFieldElement::new));
955        let x_squared = XFieldElement::new([0, 0, 1].map(BFieldElement::new));
956        let one_one_one = XFieldElement::new([1, 1, 1].map(BFieldElement::new));
957        let complex0 = XFieldElement::new([450, 967, 21444444201].map(BFieldElement::new));
958        let complex1 = XFieldElement::new([456230, 0, 4563210789].map(BFieldElement::new));
959        let complex2 = XFieldElement::new([0, 96701, 456703214].map(BFieldElement::new));
960        let complex3 = XFieldElement::new([124504, 9654677, 0].map(BFieldElement::new));
961        let complex4 = XFieldElement::new(
962            [BFieldElement::MAX, BFieldElement::MAX, BFieldElement::MAX].map(BFieldElement::new),
963        );
964        let complex5 =
965            XFieldElement::new([0, BFieldElement::MAX, BFieldElement::MAX].map(BFieldElement::new));
966        let complex6 =
967            XFieldElement::new([BFieldElement::MAX, 0, BFieldElement::MAX].map(BFieldElement::new));
968        let complex7 =
969            XFieldElement::new([BFieldElement::MAX, BFieldElement::MAX, 0].map(BFieldElement::new));
970
971        let x_field_elements = vec![
972            one,
973            two,
974            hundred,
975            x,
976            x_squared,
977            one_one_one,
978            complex0,
979            complex1,
980            complex2,
981            complex3,
982            complex4,
983            complex5,
984            complex6,
985            complex7,
986        ];
987        for x_field_element in x_field_elements.iter() {
988            let x_field_element_poly: Polynomial<BFieldElement> = (*x_field_element).into();
989            // XGCP for x
990            let (gcd_0, a_0, b_0) = Polynomial::xgcd(
991                x_field_element_poly.clone(),
992                XFieldElement::shah_polynomial(),
993            );
994            let (gcd_1, b_1, a_1) =
995                Polynomial::xgcd(XFieldElement::shah_polynomial(), (*x_field_element).into());
996
997            // Verify symmetry, and that all elements are mutual primes, meaning that
998            // they form a field
999            assert!(gcd_0.is_one());
1000            assert!(gcd_1.is_one());
1001            assert_eq!(a_0, a_1);
1002            assert_eq!(b_0, b_1);
1003
1004            // Verify Bezout relations: ax + by = gcd
1005            assert_eq!(
1006                gcd_0,
1007                a_0 * x_field_element_poly + b_0 * XFieldElement::shah_polynomial()
1008            );
1009        }
1010    }
1011
1012    #[test]
1013    fn x_field_inv_test() {
1014        let one = XFieldElement::new([1, 0, 0].map(BFieldElement::new));
1015        let one_inv = one.inverse();
1016        assert!((one_inv * one).is_one());
1017        assert!((one * one_inv).is_one());
1018
1019        let two = XFieldElement::new([2, 0, 0].map(BFieldElement::new));
1020        let two_inv = two.inverse();
1021        assert!((two_inv * two).is_one());
1022        assert!((two * two_inv).is_one());
1023
1024        let three = XFieldElement::new([3, 0, 0].map(BFieldElement::new));
1025        let three_inv = three.inverse();
1026        assert!((three_inv * three).is_one());
1027        assert!((three * three_inv).is_one());
1028
1029        let hundred = XFieldElement::new([100, 0, 0].map(BFieldElement::new));
1030        let hundred_inv = hundred.inverse();
1031        assert!((hundred_inv * hundred).is_one());
1032        assert!((hundred * hundred_inv).is_one());
1033
1034        let x = XFieldElement::new([0, 1, 0].map(BFieldElement::new));
1035        let x_inv = x.inverse();
1036        assert!((x_inv * x).is_one());
1037        assert!((x * x_inv).is_one());
1038
1039        // Test batch inversion
1040        let mut inverses = XFieldElement::batch_inversion(vec![]);
1041        assert!(inverses.is_empty());
1042        inverses = XFieldElement::batch_inversion(vec![one]);
1043        assert_eq!(1, inverses.len());
1044        assert!(inverses[0].is_one());
1045        inverses = XFieldElement::batch_inversion(vec![two]);
1046        assert_eq!(1, inverses.len());
1047        assert_eq!(two_inv, inverses[0]);
1048        inverses = XFieldElement::batch_inversion(vec![x]);
1049        assert_eq!(1, inverses.len());
1050        assert_eq!(x_inv, inverses[0]);
1051        inverses = XFieldElement::batch_inversion(vec![two, x]);
1052        assert_eq!(2, inverses.len());
1053        assert_eq!(two_inv, inverses[0]);
1054        assert_eq!(x_inv, inverses[1]);
1055
1056        let input = vec![one, two, three, hundred, x];
1057        inverses = XFieldElement::batch_inversion(input.clone());
1058        let inverses_inverses = XFieldElement::batch_inversion(inverses.clone());
1059        assert_eq!(input.len(), inverses.len());
1060        for i in 0..input.len() {
1061            assert!((inverses[i] * input[i]).is_one());
1062            assert_eq!(input[i], inverses_inverses[i]);
1063        }
1064    }
1065
1066    #[proptest]
1067    fn field_element_inversion(
1068        #[filter(!#x.is_zero())] x: XFieldElement,
1069        #[filter(!#disturbance.is_zero())]
1070        #[filter(#x != #disturbance)]
1071        disturbance: XFieldElement,
1072    ) {
1073        let not_x = x - disturbance;
1074        prop_assert_eq!(XFieldElement::ONE, x * x.inverse());
1075        prop_assert_eq!(XFieldElement::ONE, not_x * not_x.inverse());
1076        prop_assert_ne!(XFieldElement::ONE, x * not_x.inverse());
1077    }
1078
1079    #[proptest]
1080    fn field_element_batch_inversion(
1081        #[filter(!#xs.iter().any(|x| x.is_zero()))] xs: Vec<XFieldElement>,
1082    ) {
1083        let inverses = XFieldElement::batch_inversion(xs.clone());
1084        for (x, inv) in xs.into_iter().zip(inverses) {
1085            prop_assert_eq!(XFieldElement::ONE, x * inv);
1086        }
1087    }
1088
1089    #[test]
1090    fn mul_xfe_with_bfe_pbt() {
1091        let test_iterations = 100;
1092        let rands_x: Vec<XFieldElement> = random_elements(test_iterations);
1093        let rands_b: Vec<BFieldElement> = random_elements(test_iterations);
1094        for (mut x, b) in izip!(rands_x, rands_b) {
1095            let res_mul = x * b;
1096            assert_eq!(res_mul.coefficients[0], x.coefficients[0] * b);
1097            assert_eq!(res_mul.coefficients[1], x.coefficients[1] * b);
1098            assert_eq!(res_mul.coefficients[2], x.coefficients[2] * b);
1099
1100            // Also verify that the `MulAssign` implementation agrees with the `Mul` implementation
1101            x *= b;
1102            let res_mul_assign = x;
1103            assert_eq!(res_mul, res_mul_assign);
1104        }
1105    }
1106
1107    #[proptest(cases = 1_000)]
1108    fn x_field_division_mul_pbt(a: XFieldElement, b: XFieldElement) {
1109        let a_b = a * b;
1110        let b_a = b * a;
1111        prop_assert_eq!(a_b, b_a);
1112        prop_assert_eq!(a_b / b, a);
1113        prop_assert_eq!(a_b / a, b);
1114        prop_assert_eq!(a * a, a.square());
1115
1116        // Test the add/sub/mul assign operators
1117        let mut a_minus_b = a;
1118        a_minus_b -= b;
1119        prop_assert_eq!(a - b, a_minus_b);
1120
1121        let mut a_plus_b = a;
1122        a_plus_b += b;
1123        prop_assert_eq!(a + b, a_plus_b);
1124
1125        let mut a_mul_b = a;
1126        a_mul_b *= b;
1127        prop_assert_eq!(a * b, a_mul_b);
1128
1129        // Test the add/sub/mul assign operators, when the higher coefficients are zero.
1130        // Also tests add/sub/mul operators and add/sub/mul assign operators when RHS has
1131        // the type of B field element. And add/sub/mul operators when LHS is a B-field
1132        // element and RHS is an X-field element.
1133        // mul-assign `*=`
1134        let b_field_b = XFieldElement::new_const(b.coefficients[0]);
1135        let mut a_mul_b_field_b_as_x = a;
1136        a_mul_b_field_b_as_x *= b_field_b;
1137        prop_assert_eq!(a * b_field_b, a_mul_b_field_b_as_x);
1138        prop_assert_eq!(a, a_mul_b_field_b_as_x / b_field_b);
1139        prop_assert_eq!(b_field_b, a_mul_b_field_b_as_x / a);
1140        prop_assert_eq!(a_mul_b_field_b_as_x, a * b.coefficients[0]);
1141        prop_assert_eq!(a_mul_b_field_b_as_x, b.coefficients[0] * a);
1142        let mut a_mul_b_field_b_as_b = a;
1143        a_mul_b_field_b_as_b *= b.coefficients[0];
1144        prop_assert_eq!(a_mul_b_field_b_as_b, a_mul_b_field_b_as_x);
1145
1146        // `+=`
1147        let mut a_plus_b_field_b_as_x = a;
1148        a_plus_b_field_b_as_x += b_field_b;
1149        prop_assert_eq!(a + b_field_b, a_plus_b_field_b_as_x);
1150        prop_assert_eq!(a, a_plus_b_field_b_as_x - b_field_b);
1151        prop_assert_eq!(b_field_b, a_plus_b_field_b_as_x - a);
1152        prop_assert_eq!(a_plus_b_field_b_as_x, a + b.coefficients[0]);
1153        prop_assert_eq!(a_plus_b_field_b_as_x, b.coefficients[0] + a);
1154        let mut a_plus_b_field_b_as_b = a;
1155        a_plus_b_field_b_as_b += b.coefficients[0];
1156        prop_assert_eq!(a_plus_b_field_b_as_b, a_plus_b_field_b_as_x);
1157
1158        // `-=`
1159        let mut a_minus_b_field_b_as_x = a;
1160        a_minus_b_field_b_as_x -= b_field_b;
1161        prop_assert_eq!(a - b_field_b, a_minus_b_field_b_as_x);
1162        prop_assert_eq!(a, a_minus_b_field_b_as_x + b_field_b);
1163        prop_assert_eq!(-b_field_b, a_minus_b_field_b_as_x - a);
1164        prop_assert_eq!(a_minus_b_field_b_as_x, a - b.coefficients[0]);
1165        prop_assert_eq!(-a_minus_b_field_b_as_x, b.coefficients[0] - a);
1166        let mut a_minus_b_field_b_as_b = a;
1167        a_minus_b_field_b_as_b -= b.coefficients[0];
1168        prop_assert_eq!(a_minus_b_field_b_as_b, a_minus_b_field_b_as_x);
1169    }
1170
1171    #[test]
1172    fn xfe_mod_pow_zero() {
1173        assert!(XFieldElement::ZERO.mod_pow_u32(0).is_one());
1174        assert!(XFieldElement::ZERO.mod_pow_u64(0).is_one());
1175        assert!(XFieldElement::ONE.mod_pow_u32(0).is_one());
1176        assert!(XFieldElement::ONE.mod_pow_u64(0).is_one());
1177    }
1178
1179    #[proptest]
1180    fn xfe_mod_pow(base: XFieldElement, #[strategy(0_u32..200)] exponent: u32) {
1181        let mut acc = XFieldElement::ONE;
1182        for i in 0..exponent {
1183            assert_eq!(acc, base.mod_pow_u32(i));
1184            acc *= base;
1185        }
1186    }
1187
1188    #[test]
1189    fn xfe_mod_pow_static() {
1190        let three_to_the_n = |n| xfe!(3).mod_pow_u64(n);
1191        let actual = [0, 1, 2, 3, 4, 5].map(three_to_the_n);
1192        let expected = xfe_array![1, 3, 9, 27, 81, 243];
1193        assert_eq!(expected, actual);
1194    }
1195
1196    #[proptest(cases = 100)]
1197    fn xfe_intt_is_inverse_of_xfe_ntt(
1198        #[strategy(1..=11)]
1199        #[map(|log| 1_usize << log)]
1200        _num_inputs: usize,
1201        #[strategy(vec(arb(), #_num_inputs))] inputs: Vec<XFieldElement>,
1202    ) {
1203        let mut rv = inputs.clone();
1204        ntt::<XFieldElement>(&mut rv);
1205        intt::<XFieldElement>(&mut rv);
1206        prop_assert_eq!(inputs, rv);
1207    }
1208
1209    #[proptest(cases = 40)]
1210    fn xfe_ntt_corresponds_to_polynomial_evaluation(
1211        #[strategy(1..=11)]
1212        #[map(|log_2| 1_u64 << log_2)]
1213        root_order: u64,
1214        #[strategy(vec(arb(), #root_order as usize))] inputs: Vec<XFieldElement>,
1215    ) {
1216        let root = XFieldElement::primitive_root_of_unity(root_order).unwrap();
1217        let mut rv = inputs.clone();
1218        ntt::<XFieldElement>(&mut rv);
1219
1220        let poly = Polynomial::new(inputs);
1221        let domain = root.get_cyclic_group_elements(None);
1222        let evaluations = poly.batch_evaluate(&domain);
1223        prop_assert_eq!(evaluations, rv);
1224    }
1225
1226    #[test]
1227    fn inverse_or_zero_of_zero_is_zero() {
1228        let zero = XFieldElement::ZERO;
1229        assert_eq!(zero, zero.inverse_or_zero());
1230    }
1231
1232    #[proptest]
1233    fn inverse_or_zero_of_non_zero_is_inverse(#[filter(!#xfe.is_zero())] xfe: XFieldElement) {
1234        let inv = xfe.inverse_or_zero();
1235        prop_assert_ne!(XFieldElement::ZERO, inv);
1236        prop_assert_eq!(XFieldElement::ONE, xfe * inv);
1237    }
1238
1239    #[test]
1240    #[should_panic(expected = "Cannot invert the zero element in the extension field.")]
1241    fn multiplicative_inverse_of_zero() {
1242        let zero = XFieldElement::ZERO;
1243        let _ = zero.inverse();
1244    }
1245
1246    #[proptest]
1247    fn xfe_to_digest_to_xfe_is_invariant(xfe: XFieldElement) {
1248        let digest: Digest = xfe.into();
1249        let xfe2: XFieldElement = digest.try_into().unwrap();
1250        assert_eq!(xfe, xfe2);
1251    }
1252
1253    #[proptest]
1254    fn converting_random_digest_to_xfield_element_fails(digest: Digest) {
1255        if XFieldElement::try_from(digest).is_ok() {
1256            let reason = "Should not be able to convert random `Digest` to an `XFieldElement`.";
1257            return Err(TestCaseError::Fail(reason.into()));
1258        }
1259    }
1260
1261    #[test]
1262    fn xfe_macro_can_be_used() {
1263        let x = xfe!(42);
1264        let _ = xfe!(42u32);
1265        let _ = xfe!(-1);
1266        let _ = xfe!(x);
1267        let _ = xfe!([x.coefficients[0], x.coefficients[1], x.coefficients[2]]);
1268        let y = xfe!(bfe!(42));
1269        assert_eq!(x, y);
1270
1271        let a = xfe!([bfe!(42), bfe!(43), bfe!(44)]);
1272        let b = xfe!([42, 43, 44]);
1273        assert_eq!(a, b);
1274
1275        let m: [XFieldElement; 3] = xfe_array![[1, 2, 3], [4, 5, 6], [7, 8, 9]];
1276        let n: Vec<XFieldElement> = xfe_vec![[1, 2, 3], [4, 5, 6], [7, 8, 9]];
1277        assert_eq!(m.to_vec(), n);
1278    }
1279
1280    #[proptest]
1281    fn xfe_macro_produces_same_result_as_calling_new(coeffs: [BFieldElement; EXTENSION_DEGREE]) {
1282        let xfe = XFieldElement::new(coeffs);
1283        prop_assert_eq!(xfe, xfe!(coeffs));
1284    }
1285
1286    #[proptest]
1287    fn xfe_macro_produces_same_result_as_calling_new_const(scalar: BFieldElement) {
1288        let xfe = XFieldElement::new_const(scalar);
1289        prop_assert_eq!(xfe, xfe!(scalar));
1290    }
1291
1292    #[proptest]
1293    fn as_flat_slice_produces_expected_slices(xfes: Vec<XFieldElement>) {
1294        let bfes = xfes.iter().flat_map(|&x| x.coefficients).collect_vec();
1295        prop_assert_eq!(&bfes, as_flat_slice(&xfes));
1296    }
1297}
twenty_first/math/x_field_element.rs

twenty_first/math/
x_field_element.rs
