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

twenty_first/math/
x_field_element.rs
