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        let Self { coefficients } = self;
368        let [bfe, BFieldElement::ZERO, BFieldElement::ZERO] = coefficients else {
369            return None;
370        };
371
372        Some(*bfe)
373    }
374
375    #[deprecated(since = "2.0.0")]
376    #[doc(hidden)]
377    pub fn increment(&mut self, index: usize) {
378        self.coefficients[index].increment();
379    }
380
381    #[deprecated(since = "2.0.0")]
382    #[doc(hidden)]
383    pub fn decrement(&mut self, index: usize) {
384        self.coefficients[index].decrement();
385    }
386}
387
388impl Inverse for XFieldElement {
389    fn inverse(&self) -> Self {
390        self.inverse()
391    }
392}
393
394impl PrimitiveRootOfUnity for XFieldElement {
395    fn primitive_root_of_unity(n: u64) -> Option<XFieldElement> {
396        let b_root = BFieldElement::primitive_root_of_unity(n);
397        b_root.map(XFieldElement::new_const)
398    }
399}
400
401impl Distribution<XFieldElement> for StandardUniform {
402    fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> XFieldElement {
403        XFieldElement::new(rng.random())
404    }
405}
406
407impl CyclicGroupGenerator for XFieldElement {
408    fn get_cyclic_group_elements(&self, max: Option<usize>) -> Vec<Self> {
409        let mut val = *self;
410        let mut ret: Vec<Self> = vec![Self::one()];
411
412        loop {
413            ret.push(val);
414            val *= *self;
415            if val.is_one() || max.is_some() && ret.len() >= max.unwrap() {
416                break;
417            }
418        }
419        ret
420    }
421}
422
423impl Display for XFieldElement {
424    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
425        if let Some(bfe) = self.unlift() {
426            return write!(f, "{bfe}_xfe");
427        }
428
429        let [c0, c1, c2] = self.coefficients;
430        write!(f, "({c2:>020}·x² + {c1:>020}·x + {c0:>020})")
431    }
432}
433
434impl Zero for XFieldElement {
435    fn zero() -> Self {
436        Self::ZERO
437    }
438
439    fn is_zero(&self) -> bool {
440        self == &Self::ZERO
441    }
442}
443
444impl ConstZero for XFieldElement {
445    const ZERO: Self = Self::new([BFieldElement::ZERO; EXTENSION_DEGREE]);
446}
447
448impl One for XFieldElement {
449    fn one() -> Self {
450        Self::ONE
451    }
452
453    fn is_one(&self) -> bool {
454        self == &Self::ONE
455    }
456}
457
458impl ConstOne for XFieldElement {
459    const ONE: Self = Self::new([BFieldElement::ONE, BFieldElement::ZERO, BFieldElement::ZERO]);
460}
461
462impl FiniteField for XFieldElement {}
463
464impl Add<XFieldElement> for XFieldElement {
465    type Output = Self;
466
467    #[inline]
468    fn add(self, other: Self) -> Self {
469        let [s0, s1, s2] = self.coefficients;
470        let [o0, o1, o2] = other.coefficients;
471        let coefficients = [s0 + o0, s1 + o1, s2 + o2];
472        Self { coefficients }
473    }
474}
475
476impl Add<BFieldElement> for XFieldElement {
477    type Output = Self;
478
479    #[inline]
480    fn add(mut self, other: BFieldElement) -> Self {
481        self.coefficients[0] += other;
482        self
483    }
484}
485
486/// The `bfe + xfe -> xfe` instance belongs to BFieldElement.
487impl Add<XFieldElement> for BFieldElement {
488    type Output = XFieldElement;
489
490    #[inline]
491    fn add(self, mut other: XFieldElement) -> XFieldElement {
492        other.coefficients[0] += self;
493        other
494    }
495}
496
497impl Mul<XFieldElement> for XFieldElement {
498    type Output = Self;
499
500    #[inline]
501    fn mul(self, other: Self) -> Self {
502        // XField * XField means:
503        //
504        // (ax^2 + bx + c) * (dx^2 + ex + f)   (mod x^3 - x + 1)
505        //
506        // =   adx^4 + aex^3 + afx^2
507        //   + bdx^3 + bex^2 + bfx
508        //   + cdx^2 + cex   + cf
509        //
510        // = adx^4 + (ae + bd)x^3 + (af + be + cd)x^2 + (bf + ce)x + cf   (mod x^3 - x + 1)
511
512        let [c, b, a] = self.coefficients;
513        let [f, e, d] = other.coefficients;
514
515        let r0 = c * f - a * e - b * d;
516        let r1 = b * f + c * e - a * d + a * e + b * d;
517        let r2 = a * f + b * e + c * d + a * d;
518
519        Self::new([r0, r1, r2])
520    }
521}
522
523/// XField * BField means scalar multiplication of the
524/// BFieldElement onto each coefficient of the XField.
525impl Mul<BFieldElement> for XFieldElement {
526    type Output = Self;
527
528    #[inline]
529    fn mul(self, other: BFieldElement) -> Self {
530        let coefficients = self.coefficients.map(|c| c * other);
531        Self { coefficients }
532    }
533}
534
535impl Mul<XFieldElement> for BFieldElement {
536    type Output = XFieldElement;
537
538    #[inline]
539    fn mul(self, other: XFieldElement) -> XFieldElement {
540        let coefficients = other.coefficients.map(|c| c * self);
541        XFieldElement { coefficients }
542    }
543}
544
545impl Neg for XFieldElement {
546    type Output = Self;
547
548    #[inline]
549    fn neg(self) -> Self {
550        let coefficients = self.coefficients.map(Neg::neg);
551        Self { coefficients }
552    }
553}
554
555impl Sub<XFieldElement> for XFieldElement {
556    type Output = Self;
557
558    #[inline]
559    fn sub(self, other: Self) -> Self {
560        self + (-other)
561    }
562}
563
564impl Sub<BFieldElement> for XFieldElement {
565    type Output = Self;
566
567    #[inline]
568    fn sub(self, other: BFieldElement) -> Self {
569        self + (-other)
570    }
571}
572
573impl Sub<XFieldElement> for BFieldElement {
574    type Output = XFieldElement;
575
576    #[inline]
577    fn sub(self, other: XFieldElement) -> XFieldElement {
578        self + (-other)
579    }
580}
581
582impl AddAssign<XFieldElement> for XFieldElement {
583    #[inline]
584    fn add_assign(&mut self, rhs: Self) {
585        self.coefficients[0] += rhs.coefficients[0];
586        self.coefficients[1] += rhs.coefficients[1];
587        self.coefficients[2] += rhs.coefficients[2];
588    }
589}
590
591impl AddAssign<BFieldElement> for XFieldElement {
592    #[inline]
593    fn add_assign(&mut self, rhs: BFieldElement) {
594        self.coefficients[0] += rhs;
595    }
596}
597
598impl MulAssign<XFieldElement> for XFieldElement {
599    #[inline]
600    fn mul_assign(&mut self, rhs: Self) {
601        *self = *self * rhs;
602    }
603}
604
605impl MulAssign<BFieldElement> for XFieldElement {
606    #[inline]
607    fn mul_assign(&mut self, rhs: BFieldElement) {
608        *self = *self * rhs;
609    }
610}
611
612impl SubAssign<XFieldElement> for XFieldElement {
613    #[inline]
614    fn sub_assign(&mut self, rhs: Self) {
615        self.coefficients[0] -= rhs.coefficients[0];
616        self.coefficients[1] -= rhs.coefficients[1];
617        self.coefficients[2] -= rhs.coefficients[2];
618    }
619}
620
621impl SubAssign<BFieldElement> for XFieldElement {
622    #[inline]
623    fn sub_assign(&mut self, rhs: BFieldElement) {
624        self.coefficients[0] -= rhs;
625    }
626}
627
628impl Div for XFieldElement {
629    type Output = Self;
630
631    #[expect(clippy::suspicious_arithmetic_impl)]
632    fn div(self, other: Self) -> Self {
633        self * other.inverse()
634    }
635}
636
637impl ModPowU64 for XFieldElement {
638    #[inline]
639    fn mod_pow_u64(&self, exponent: u64) -> Self {
640        let mut x = *self;
641        let mut result = Self::one();
642        let mut i = exponent;
643
644        while i > 0 {
645            if i & 1 == 1 {
646                result *= x;
647            }
648
649            x *= x;
650            i >>= 1;
651        }
652
653        result
654    }
655}
656
657impl ModPowU32 for XFieldElement {
658    #[inline]
659    fn mod_pow_u32(&self, exp: u32) -> Self {
660        self.mod_pow_u64(exp as u64)
661    }
662}
663
664#[cfg(test)]
665#[cfg_attr(coverage_nightly, coverage(off))]
666mod tests {
667    use itertools::Itertools;
668    use itertools::izip;
669    use num_traits::ConstOne;
670    use proptest::collection::vec;
671    use proptest::prelude::*;
672
673    use super::*;
674    use crate::bfe;
675    use crate::math::b_field_element::*;
676    use crate::math::ntt::intt;
677    use crate::math::ntt::ntt;
678    use crate::math::other::random_elements;
679    use crate::proptest_arbitrary_interop::arb;
680    use crate::tests::proptest;
681    use crate::tests::test;
682
683    impl proptest::arbitrary::Arbitrary for XFieldElement {
684        type Parameters = ();
685
686        fn arbitrary_with(_: Self::Parameters) -> Self::Strategy {
687            arb().boxed()
688        }
689
690        type Strategy = BoxedStrategy<Self>;
691    }
692
693    #[macro_rules_attr::apply(test)]
694    fn display_is_as_expected() {
695        assert_eq!("42_xfe", xfe!(42).to_string());
696        assert_eq!("(3·x² + 2·x + 1)", xfe!([1, 2, 3]).to_string());
697    }
698
699    #[macro_rules_attr::apply(test)]
700    fn one_zero_test() {
701        let one = XFieldElement::one();
702        assert!(one.is_one());
703        assert!(one.coefficients[0].is_one());
704        assert!(one.coefficients[1].is_zero());
705        assert!(one.coefficients[2].is_zero());
706        assert_eq!(one, XFieldElement::ONE);
707        let zero = XFieldElement::zero();
708        assert!(zero.is_zero());
709        assert!(zero.coefficients[0].is_zero());
710        assert!(zero.coefficients[1].is_zero());
711        assert!(zero.coefficients[2].is_zero());
712        assert_eq!(zero, XFieldElement::ZERO);
713        let two = XFieldElement::new([
714            BFieldElement::new(2),
715            BFieldElement::ZERO,
716            BFieldElement::ZERO,
717        ]);
718        assert!(!two.is_one());
719        assert!(!zero.is_one());
720        let one_as_constant_term_0 = XFieldElement::new([
721            BFieldElement::new(1),
722            BFieldElement::ONE,
723            BFieldElement::ZERO,
724        ]);
725        let one_as_constant_term_1 = XFieldElement::new([
726            BFieldElement::new(1),
727            BFieldElement::ZERO,
728            BFieldElement::ONE,
729        ]);
730        assert!(!one_as_constant_term_0.is_one());
731        assert!(!one_as_constant_term_1.is_one());
732        assert!(!one_as_constant_term_0.is_zero());
733        assert!(!one_as_constant_term_1.is_zero());
734    }
735
736    #[macro_rules_attr::apply(test)]
737    fn x_field_random_element_generation_test() {
738        let rand_xs: Vec<XFieldElement> = random_elements(14);
739        assert_eq!(14, rand_xs.len());
740
741        // TODO: Consider doing a statistical test.
742        assert!(rand_xs.into_iter().all_unique());
743    }
744
745    #[macro_rules_attr::apply(proptest)]
746    fn unlifting_random_xfe_doesnt_work(xfe: XFieldElement) {
747        prop_assert!(xfe.unlift().is_none());
748    }
749
750    #[macro_rules_attr::apply(test)]
751    fn summing_gives_expected_result() {
752        let empty_sum = [].into_iter().sum();
753        assert_eq!(XFieldElement::ZERO, empty_sum);
754
755        let a = xfe!([1, 0, 0]);
756        let b = xfe!([0, 2, 0]);
757        let c = xfe!([0, 0, 3]);
758        let d = xfe!([40, 50, 60]);
759        let sum = [a, b, c, d].into_iter().sum();
760
761        assert_eq!(xfe!([41, 52, 63]), sum);
762    }
763
764    #[macro_rules_attr::apply(proptest)]
765    fn bfe_vector_of_correct_length_can_become_xfe(
766        #[strategy(vec(arb(), EXTENSION_DEGREE))] bfes: Vec<BFieldElement>,
767    ) {
768        prop_assert!(XFieldElement::try_from(bfes).is_ok());
769    }
770
771    #[macro_rules_attr::apply(proptest)]
772    fn bfe_vector_of_incorrect_length_cannot_become_xfe(
773        #[filter(#bfes.len() != EXTENSION_DEGREE)] bfes: Vec<BFieldElement>,
774    ) {
775        prop_assert!(XFieldElement::try_from(bfes).is_err());
776    }
777
778    /// To be removed once [XFieldElement::increment] and
779    /// [XFieldElement::decrement] are gone.
780    #[macro_rules_attr::apply(test)]
781    #[expect(deprecated)]
782    fn incr_decr_test() {
783        let one_const = XFieldElement::new([1, 0, 0].map(BFieldElement::new));
784        let two_const = XFieldElement::new([2, 0, 0].map(BFieldElement::new));
785        let one_x = XFieldElement::new([0, 1, 0].map(BFieldElement::new));
786        let two_x = XFieldElement::new([0, 2, 0].map(BFieldElement::new));
787        let one_x_squared = XFieldElement::new([0, 0, 1].map(BFieldElement::new));
788        let two_x_squared = XFieldElement::new([0, 0, 2].map(BFieldElement::new));
789        let max_const = XFieldElement::new([BFieldElement::MAX, 0, 0].map(BFieldElement::new));
790        let max_x = XFieldElement::new([0, BFieldElement::MAX, 0].map(BFieldElement::new));
791        let max_x_squared = XFieldElement::new([0, 0, BFieldElement::MAX].map(BFieldElement::new));
792        let mut val = XFieldElement::ZERO;
793        val.increment(0);
794        assert!(val.is_one());
795        val.increment(0);
796        assert_eq!(two_const, val);
797        val.decrement(0);
798        assert!(val.is_one());
799        val.decrement(0);
800        assert!(val.is_zero());
801        val.decrement(0);
802        assert_eq!(max_const, val);
803        val.decrement(0);
804        assert_eq!(max_const - XFieldElement::ONE, val);
805        val.decrement(0);
806        assert_eq!(max_const - XFieldElement::ONE - XFieldElement::ONE, val);
807        val.increment(0);
808        val.increment(0);
809        val.increment(0);
810        assert!(val.is_zero());
811        val.increment(1);
812        assert_eq!(one_x, val);
813        val.increment(1);
814        assert_eq!(two_x, val);
815        val.decrement(1);
816        val.decrement(1);
817        assert!(val.is_zero());
818        val.decrement(1);
819        assert_eq!(max_x, val);
820        val.increment(1);
821        val.increment(2);
822        assert_eq!(one_x_squared, val);
823        val.increment(2);
824        assert_eq!(two_x_squared, val);
825        val.decrement(2);
826        val.decrement(2);
827        assert!(val.is_zero());
828        val.decrement(2);
829        assert_eq!(max_x_squared, val);
830        val.decrement(1);
831        val.decrement(0);
832        assert_eq!(max_x_squared + max_x + max_const, val);
833        val.decrement(2);
834        val.decrement(1);
835        val.decrement(0);
836        assert_eq!(
837            max_x_squared + max_x + max_const - one_const - one_x - one_x_squared,
838            val
839        );
840    }
841
842    #[macro_rules_attr::apply(test)]
843    fn x_field_add_test() {
844        let poly1 = XFieldElement::new([2, 0, 0].map(BFieldElement::new));
845        let poly2 = XFieldElement::new([3, 0, 0].map(BFieldElement::new));
846
847        let mut poly_sum = XFieldElement::new([5, 0, 0].map(BFieldElement::new));
848        assert_eq!(poly_sum, poly1 + poly2);
849
850        let poly3 = XFieldElement::new([0, 5, 0].map(BFieldElement::new));
851        let poly4 = XFieldElement::new([0, 7, 0].map(BFieldElement::new));
852
853        poly_sum = XFieldElement::new([0, 12, 0].map(BFieldElement::new));
854        assert_eq!(poly_sum, poly3 + poly4);
855
856        let poly5 = XFieldElement::new([0, 0, 14].map(BFieldElement::new));
857        let poly6 = XFieldElement::new([0, 0, 23].map(BFieldElement::new));
858
859        poly_sum = XFieldElement::new([0, 0, 37].map(BFieldElement::new));
860        assert_eq!(poly_sum, poly5 + poly6);
861
862        let poly7 = XFieldElement::new([0, 0, BFieldElement::MAX].map(BFieldElement::new));
863        let poly8 = XFieldElement::new([0, 0, 23].map(BFieldElement::new));
864
865        poly_sum = XFieldElement::new([0, 0, 22].map(BFieldElement::new));
866        assert_eq!(poly_sum, poly7 + poly8);
867
868        let poly9 = XFieldElement::new([BFieldElement::MAX - 2, 12, 4].map(BFieldElement::new));
869        let poly10 = XFieldElement::new([2, 45000, BFieldElement::MAX - 3].map(BFieldElement::new));
870
871        poly_sum = XFieldElement::new([BFieldElement::MAX, 45012, 0].map(BFieldElement::new));
872        assert_eq!(poly_sum, poly9 + poly10);
873    }
874
875    #[macro_rules_attr::apply(test)]
876    fn x_field_sub_test() {
877        let poly1 = XFieldElement::new([2, 0, 0].map(BFieldElement::new));
878        let poly2 = XFieldElement::new([3, 0, 0].map(BFieldElement::new));
879
880        let mut poly_diff = XFieldElement::new([1, 0, 0].map(BFieldElement::new));
881        assert_eq!(poly_diff, poly2 - poly1);
882
883        let poly3 = XFieldElement::new([0, 5, 0].map(BFieldElement::new));
884        let poly4 = XFieldElement::new([0, 7, 0].map(BFieldElement::new));
885
886        poly_diff = XFieldElement::new([0, 2, 0].map(BFieldElement::new));
887        assert_eq!(poly_diff, poly4 - poly3);
888
889        let poly5 = XFieldElement::new([0, 0, 14].map(BFieldElement::new));
890        let poly6 = XFieldElement::new([0, 0, 23].map(BFieldElement::new));
891
892        poly_diff = XFieldElement::new([0, 0, 9].map(BFieldElement::new));
893        assert_eq!(poly_diff, poly6 - poly5);
894
895        let poly7 = XFieldElement::new([0, 0, BFieldElement::MAX].map(BFieldElement::new));
896        let poly8 = XFieldElement::new([0, 0, 23].map(BFieldElement::new));
897
898        poly_diff = XFieldElement::new([0, 0, 24].map(BFieldElement::new));
899        assert_eq!(poly_diff, poly8 - poly7);
900
901        let poly9 = XFieldElement::new([BFieldElement::MAX - 2, 12, 4].map(BFieldElement::new));
902        let poly10 = XFieldElement::new([2, 45000, BFieldElement::MAX - 3].map(BFieldElement::new));
903
904        poly_diff = XFieldElement::new([5, 44988, BFieldElement::MAX - 7].map(BFieldElement::new));
905        assert_eq!(poly_diff, poly10 - poly9);
906    }
907
908    #[macro_rules_attr::apply(test)]
909    fn x_field_mul_test() {
910        let poly1 = XFieldElement::new([2, 0, 0].map(BFieldElement::new));
911        let poly2 = XFieldElement::new([3, 0, 0].map(BFieldElement::new));
912
913        let poly12_product = XFieldElement::new([6, 0, 0].map(BFieldElement::new));
914        assert_eq!(poly12_product, poly1 * poly2);
915
916        let poly3 = XFieldElement::new([0, 3, 0].map(BFieldElement::new));
917        let poly4 = XFieldElement::new([0, 3, 0].map(BFieldElement::new));
918
919        let poly34_product = XFieldElement::new([0, 0, 9].map(BFieldElement::new));
920        assert_eq!(poly34_product, poly3 * poly4);
921
922        let poly5 = XFieldElement::new([125, 0, 0].map(BFieldElement::new));
923        let poly6 = XFieldElement::new([0, 0, 5].map(BFieldElement::new));
924
925        let poly56_product = XFieldElement::new([0, 0, 625].map(BFieldElement::new));
926        assert_eq!(poly56_product, poly5 * poly6);
927
928        // x^2 * x^2 = x^4 = x^2 - x mod (x^3 - x + 1)
929        let poly7 = XFieldElement::new([0, 0, 1].map(BFieldElement::new));
930        let poly8 = XFieldElement::new([0, 0, 1].map(BFieldElement::new));
931
932        let poly78_product = XFieldElement::new([0, BFieldElement::MAX, 1].map(BFieldElement::new));
933        assert_eq!(poly78_product, poly7 * poly8);
934
935        // x^2 * x = x^3 = x - 1 mod (x^3 - x + 1)
936        let poly9 = XFieldElement::new([0, 1, 0].map(BFieldElement::new));
937        let poly10 = XFieldElement::new([0, 0, 1].map(BFieldElement::new));
938
939        let poly910_product =
940            XFieldElement::new([BFieldElement::MAX, 1, 0].map(BFieldElement::new));
941        assert_eq!(poly910_product, poly9 * poly10);
942
943        // (13+2x+3x2)(19+5x2) = 247+122x^2+38x+10x^3+15x^4
944        let poly11 = XFieldElement::new([13, 2, 3].map(BFieldElement::new));
945        let poly12 = XFieldElement::new([19, 0, 5].map(BFieldElement::new));
946
947        let poly1112_product = XFieldElement::new([237, 33, 137].map(BFieldElement::new));
948        assert_eq!(poly1112_product, poly11 * poly12);
949    }
950
951    #[macro_rules_attr::apply(test)]
952    fn x_field_overloaded_arithmetic_test() {
953        let mut rng = rand::rng();
954        for _ in 0..100 {
955            let xfe = rng.random::<XFieldElement>();
956            let bfe = rng.random::<BFieldElement>();
957
958            // 1. xfe + bfe.lift() = bfe.lift() + xfe
959            // 2. xfe + bfe = xfe + bfe.lift()
960            // 3. bfe + xfe = xfe + bfe.lift()
961            let expected_add = xfe + bfe.lift();
962            assert_eq!(expected_add, bfe.lift() + xfe);
963            assert_eq!(expected_add, xfe + bfe);
964            assert_eq!(expected_add, bfe + xfe);
965
966            // 4. xfe * bfe.lift() = bfe.lift() * xfe
967            // 5. xfe * bfe = xfe * bfe.lift()
968            // 6. bfe * xfe = xfe * bfe.lift()
969            let expected_mul = xfe * bfe.lift();
970            assert_eq!(expected_mul, bfe.lift() * xfe);
971            assert_eq!(expected_mul, xfe * bfe);
972            assert_eq!(expected_mul, bfe * xfe);
973
974            // 7. xfe - bfe = xfe - bfe.lift()
975            // 8. bfe - xfe = xfe - bfe.lift()
976            assert_eq!(xfe - bfe.lift(), xfe - bfe);
977            assert_eq!(bfe.lift() - xfe, bfe - xfe);
978        }
979    }
980
981    #[macro_rules_attr::apply(test)]
982    fn x_field_into_test() {
983        let zero_poly: XFieldElement = Polynomial::<BFieldElement>::new(vec![]).into();
984        assert!(zero_poly.is_zero());
985
986        let shah_zero: XFieldElement = XFieldElement::shah_polynomial().into();
987        assert!(shah_zero.is_zero());
988
989        let neg_shah_zero: XFieldElement =
990            XFieldElement::shah_polynomial().scalar_mul(bfe!(-1)).into();
991        assert!(neg_shah_zero.is_zero());
992    }
993
994    #[macro_rules_attr::apply(test)]
995    fn x_field_xgcp_test() {
996        // Verify expected properties of XGCP: symmetry and that gcd is always
997        // one. gcd is always one for all field elements.
998        let one = XFieldElement::new([1, 0, 0].map(BFieldElement::new));
999        let two = XFieldElement::new([2, 0, 0].map(BFieldElement::new));
1000        let hundred = XFieldElement::new([100, 0, 0].map(BFieldElement::new));
1001        let x = XFieldElement::new([0, 1, 0].map(BFieldElement::new));
1002        let x_squared = XFieldElement::new([0, 0, 1].map(BFieldElement::new));
1003        let one_one_one = XFieldElement::new([1, 1, 1].map(BFieldElement::new));
1004        let complex0 = XFieldElement::new([450, 967, 21444444201].map(BFieldElement::new));
1005        let complex1 = XFieldElement::new([456230, 0, 4563210789].map(BFieldElement::new));
1006        let complex2 = XFieldElement::new([0, 96701, 456703214].map(BFieldElement::new));
1007        let complex3 = XFieldElement::new([124504, 9654677, 0].map(BFieldElement::new));
1008        let complex4 = XFieldElement::new(
1009            [BFieldElement::MAX, BFieldElement::MAX, BFieldElement::MAX].map(BFieldElement::new),
1010        );
1011        let complex5 =
1012            XFieldElement::new([0, BFieldElement::MAX, BFieldElement::MAX].map(BFieldElement::new));
1013        let complex6 =
1014            XFieldElement::new([BFieldElement::MAX, 0, BFieldElement::MAX].map(BFieldElement::new));
1015        let complex7 =
1016            XFieldElement::new([BFieldElement::MAX, BFieldElement::MAX, 0].map(BFieldElement::new));
1017
1018        let x_field_elements = vec![
1019            one,
1020            two,
1021            hundred,
1022            x,
1023            x_squared,
1024            one_one_one,
1025            complex0,
1026            complex1,
1027            complex2,
1028            complex3,
1029            complex4,
1030            complex5,
1031            complex6,
1032            complex7,
1033        ];
1034        for x_field_element in x_field_elements.iter() {
1035            let x_field_element_poly: Polynomial<BFieldElement> = (*x_field_element).into();
1036            // XGCP for x
1037            let (gcd_0, a_0, b_0) = Polynomial::xgcd(
1038                x_field_element_poly.clone(),
1039                XFieldElement::shah_polynomial(),
1040            );
1041            let (gcd_1, b_1, a_1) =
1042                Polynomial::xgcd(XFieldElement::shah_polynomial(), (*x_field_element).into());
1043
1044            // Verify symmetry, and that all elements are mutual primes, meaning that
1045            // they form a field
1046            assert!(gcd_0.is_one());
1047            assert!(gcd_1.is_one());
1048            assert_eq!(a_0, a_1);
1049            assert_eq!(b_0, b_1);
1050
1051            // Verify Bezout relations: ax + by = gcd
1052            assert_eq!(
1053                gcd_0,
1054                a_0 * x_field_element_poly + b_0 * XFieldElement::shah_polynomial()
1055            );
1056        }
1057    }
1058
1059    #[macro_rules_attr::apply(test)]
1060    fn x_field_inv_test() {
1061        let one = XFieldElement::new([1, 0, 0].map(BFieldElement::new));
1062        let one_inv = one.inverse();
1063        assert!((one_inv * one).is_one());
1064        assert!((one * one_inv).is_one());
1065
1066        let two = XFieldElement::new([2, 0, 0].map(BFieldElement::new));
1067        let two_inv = two.inverse();
1068        assert!((two_inv * two).is_one());
1069        assert!((two * two_inv).is_one());
1070
1071        let three = XFieldElement::new([3, 0, 0].map(BFieldElement::new));
1072        let three_inv = three.inverse();
1073        assert!((three_inv * three).is_one());
1074        assert!((three * three_inv).is_one());
1075
1076        let hundred = XFieldElement::new([100, 0, 0].map(BFieldElement::new));
1077        let hundred_inv = hundred.inverse();
1078        assert!((hundred_inv * hundred).is_one());
1079        assert!((hundred * hundred_inv).is_one());
1080
1081        let x = XFieldElement::new([0, 1, 0].map(BFieldElement::new));
1082        let x_inv = x.inverse();
1083        assert!((x_inv * x).is_one());
1084        assert!((x * x_inv).is_one());
1085
1086        // Test batch inversion
1087        let mut inverses = XFieldElement::batch_inversion(vec![]);
1088        assert!(inverses.is_empty());
1089        inverses = XFieldElement::batch_inversion(vec![one]);
1090        assert_eq!(1, inverses.len());
1091        assert!(inverses[0].is_one());
1092        inverses = XFieldElement::batch_inversion(vec![two]);
1093        assert_eq!(1, inverses.len());
1094        assert_eq!(two_inv, inverses[0]);
1095        inverses = XFieldElement::batch_inversion(vec![x]);
1096        assert_eq!(1, inverses.len());
1097        assert_eq!(x_inv, inverses[0]);
1098        inverses = XFieldElement::batch_inversion(vec![two, x]);
1099        assert_eq!(2, inverses.len());
1100        assert_eq!(two_inv, inverses[0]);
1101        assert_eq!(x_inv, inverses[1]);
1102
1103        let input = vec![one, two, three, hundred, x];
1104        inverses = XFieldElement::batch_inversion(input.clone());
1105        let inverses_inverses = XFieldElement::batch_inversion(inverses.clone());
1106        assert_eq!(input.len(), inverses.len());
1107        for i in 0..input.len() {
1108            assert!((inverses[i] * input[i]).is_one());
1109            assert_eq!(input[i], inverses_inverses[i]);
1110        }
1111    }
1112
1113    #[macro_rules_attr::apply(proptest)]
1114    fn field_element_inversion(
1115        #[filter(!#x.is_zero())] x: XFieldElement,
1116        #[filter(!#disturbance.is_zero())]
1117        #[filter(#x != #disturbance)]
1118        disturbance: XFieldElement,
1119    ) {
1120        let not_x = x - disturbance;
1121        prop_assert_eq!(XFieldElement::ONE, x * x.inverse());
1122        prop_assert_eq!(XFieldElement::ONE, not_x * not_x.inverse());
1123        prop_assert_ne!(XFieldElement::ONE, x * not_x.inverse());
1124    }
1125
1126    #[macro_rules_attr::apply(proptest)]
1127    fn field_element_batch_inversion(
1128        #[filter(!#xs.iter().any(|x| x.is_zero()))] xs: Vec<XFieldElement>,
1129    ) {
1130        let inverses = XFieldElement::batch_inversion(xs.clone());
1131        for (x, inv) in xs.into_iter().zip(inverses) {
1132            prop_assert_eq!(XFieldElement::ONE, x * inv);
1133        }
1134    }
1135
1136    #[macro_rules_attr::apply(test)]
1137    fn mul_xfe_with_bfe_pbt() {
1138        let test_iterations = 100;
1139        let rands_x: Vec<XFieldElement> = random_elements(test_iterations);
1140        let rands_b: Vec<BFieldElement> = random_elements(test_iterations);
1141        for (mut x, b) in izip!(rands_x, rands_b) {
1142            let res_mul = x * b;
1143            assert_eq!(res_mul.coefficients[0], x.coefficients[0] * b);
1144            assert_eq!(res_mul.coefficients[1], x.coefficients[1] * b);
1145            assert_eq!(res_mul.coefficients[2], x.coefficients[2] * b);
1146
1147            // Also verify that the `MulAssign` implementation agrees with the `Mul` implementation
1148            x *= b;
1149            let res_mul_assign = x;
1150            assert_eq!(res_mul, res_mul_assign);
1151        }
1152    }
1153
1154    #[macro_rules_attr::apply(proptest(cases = 1_000))]
1155    fn x_field_division_mul_pbt(a: XFieldElement, b: XFieldElement) {
1156        let a_b = a * b;
1157        let b_a = b * a;
1158        prop_assert_eq!(a_b, b_a);
1159        prop_assert_eq!(a_b / b, a);
1160        prop_assert_eq!(a_b / a, b);
1161        prop_assert_eq!(a * a, a.square());
1162
1163        // Test the add/sub/mul assign operators
1164        let mut a_minus_b = a;
1165        a_minus_b -= b;
1166        prop_assert_eq!(a - b, a_minus_b);
1167
1168        let mut a_plus_b = a;
1169        a_plus_b += b;
1170        prop_assert_eq!(a + b, a_plus_b);
1171
1172        let mut a_mul_b = a;
1173        a_mul_b *= b;
1174        prop_assert_eq!(a * b, a_mul_b);
1175
1176        // Test the add/sub/mul assign operators, when the higher coefficients are zero.
1177        // Also tests add/sub/mul operators and add/sub/mul assign operators when RHS has
1178        // the type of B field element. And add/sub/mul operators when LHS is a B-field
1179        // element and RHS is an X-field element.
1180        // mul-assign `*=`
1181        let b_field_b = XFieldElement::new_const(b.coefficients[0]);
1182        let mut a_mul_b_field_b_as_x = a;
1183        a_mul_b_field_b_as_x *= b_field_b;
1184        prop_assert_eq!(a * b_field_b, a_mul_b_field_b_as_x);
1185        prop_assert_eq!(a, a_mul_b_field_b_as_x / b_field_b);
1186        prop_assert_eq!(b_field_b, a_mul_b_field_b_as_x / a);
1187        prop_assert_eq!(a_mul_b_field_b_as_x, a * b.coefficients[0]);
1188        prop_assert_eq!(a_mul_b_field_b_as_x, b.coefficients[0] * a);
1189        let mut a_mul_b_field_b_as_b = a;
1190        a_mul_b_field_b_as_b *= b.coefficients[0];
1191        prop_assert_eq!(a_mul_b_field_b_as_b, a_mul_b_field_b_as_x);
1192
1193        // `+=`
1194        let mut a_plus_b_field_b_as_x = a;
1195        a_plus_b_field_b_as_x += b_field_b;
1196        prop_assert_eq!(a + b_field_b, a_plus_b_field_b_as_x);
1197        prop_assert_eq!(a, a_plus_b_field_b_as_x - b_field_b);
1198        prop_assert_eq!(b_field_b, a_plus_b_field_b_as_x - a);
1199        prop_assert_eq!(a_plus_b_field_b_as_x, a + b.coefficients[0]);
1200        prop_assert_eq!(a_plus_b_field_b_as_x, b.coefficients[0] + a);
1201        let mut a_plus_b_field_b_as_b = a;
1202        a_plus_b_field_b_as_b += b.coefficients[0];
1203        prop_assert_eq!(a_plus_b_field_b_as_b, a_plus_b_field_b_as_x);
1204
1205        // `-=`
1206        let mut a_minus_b_field_b_as_x = a;
1207        a_minus_b_field_b_as_x -= b_field_b;
1208        prop_assert_eq!(a - b_field_b, a_minus_b_field_b_as_x);
1209        prop_assert_eq!(a, a_minus_b_field_b_as_x + b_field_b);
1210        prop_assert_eq!(-b_field_b, a_minus_b_field_b_as_x - a);
1211        prop_assert_eq!(a_minus_b_field_b_as_x, a - b.coefficients[0]);
1212        prop_assert_eq!(-a_minus_b_field_b_as_x, b.coefficients[0] - a);
1213        let mut a_minus_b_field_b_as_b = a;
1214        a_minus_b_field_b_as_b -= b.coefficients[0];
1215        prop_assert_eq!(a_minus_b_field_b_as_b, a_minus_b_field_b_as_x);
1216    }
1217
1218    #[macro_rules_attr::apply(test)]
1219    fn xfe_mod_pow_zero() {
1220        assert!(XFieldElement::ZERO.mod_pow_u32(0).is_one());
1221        assert!(XFieldElement::ZERO.mod_pow_u64(0).is_one());
1222        assert!(XFieldElement::ONE.mod_pow_u32(0).is_one());
1223        assert!(XFieldElement::ONE.mod_pow_u64(0).is_one());
1224    }
1225
1226    #[macro_rules_attr::apply(proptest)]
1227    fn xfe_mod_pow(base: XFieldElement, #[strategy(0_u32..200)] exponent: u32) {
1228        let mut acc = XFieldElement::ONE;
1229        for i in 0..exponent {
1230            assert_eq!(acc, base.mod_pow_u32(i));
1231            acc *= base;
1232        }
1233    }
1234
1235    #[macro_rules_attr::apply(test)]
1236    fn xfe_mod_pow_static() {
1237        let three_to_the_n = |n| xfe!(3).mod_pow_u64(n);
1238        let actual = [0, 1, 2, 3, 4, 5].map(three_to_the_n);
1239        let expected = xfe_array![1, 3, 9, 27, 81, 243];
1240        assert_eq!(expected, actual);
1241    }
1242
1243    #[macro_rules_attr::apply(proptest(cases = 100))]
1244    fn xfe_intt_is_inverse_of_xfe_ntt(
1245        #[strategy(1..=11)]
1246        #[map(|log| 1_usize << log)]
1247        _num_inputs: usize,
1248        #[strategy(vec(arb(), #_num_inputs))] inputs: Vec<XFieldElement>,
1249    ) {
1250        let mut rv = inputs.clone();
1251        ntt::<XFieldElement>(&mut rv);
1252        intt::<XFieldElement>(&mut rv);
1253        prop_assert_eq!(inputs, rv);
1254    }
1255
1256    #[macro_rules_attr::apply(proptest(cases = 40))]
1257    fn xfe_ntt_corresponds_to_polynomial_evaluation(
1258        #[strategy(1..=11)]
1259        #[map(|log_2| 1_u64 << log_2)]
1260        root_order: u64,
1261        #[strategy(vec(arb(), #root_order as usize))] inputs: Vec<XFieldElement>,
1262    ) {
1263        let root = XFieldElement::primitive_root_of_unity(root_order).unwrap();
1264        let mut rv = inputs.clone();
1265        ntt::<XFieldElement>(&mut rv);
1266
1267        let poly = Polynomial::new(inputs);
1268        let domain = root.get_cyclic_group_elements(None);
1269        let evaluations = poly.batch_evaluate(&domain);
1270        prop_assert_eq!(evaluations, rv);
1271    }
1272
1273    #[macro_rules_attr::apply(test)]
1274    fn inverse_or_zero_of_zero_is_zero() {
1275        let zero = XFieldElement::ZERO;
1276        assert_eq!(zero, zero.inverse_or_zero());
1277    }
1278
1279    #[macro_rules_attr::apply(proptest)]
1280    fn inverse_or_zero_of_non_zero_is_inverse(#[filter(!#xfe.is_zero())] xfe: XFieldElement) {
1281        let inv = xfe.inverse_or_zero();
1282        prop_assert_ne!(XFieldElement::ZERO, inv);
1283        prop_assert_eq!(XFieldElement::ONE, xfe * inv);
1284    }
1285
1286    #[macro_rules_attr::apply(test)]
1287    #[should_panic(expected = "Cannot invert the zero element in the extension field.")]
1288    fn multiplicative_inverse_of_zero() {
1289        let zero = XFieldElement::ZERO;
1290        let _ = zero.inverse();
1291    }
1292
1293    #[macro_rules_attr::apply(proptest)]
1294    fn xfe_to_digest_to_xfe_is_invariant(xfe: XFieldElement) {
1295        let digest: Digest = xfe.into();
1296        let xfe2: XFieldElement = digest.try_into().unwrap();
1297        assert_eq!(xfe, xfe2);
1298    }
1299
1300    #[macro_rules_attr::apply(proptest)]
1301    fn converting_random_digest_to_xfield_element_fails(digest: Digest) {
1302        if XFieldElement::try_from(digest).is_ok() {
1303            let reason = "Should not be able to convert random `Digest` to an `XFieldElement`.";
1304            return Err(TestCaseError::Fail(reason.into()));
1305        }
1306    }
1307
1308    #[macro_rules_attr::apply(test)]
1309    fn xfe_macro_can_be_used() {
1310        let x = xfe!(42);
1311        let _ = xfe!(42u32);
1312        let _ = xfe!(-1);
1313        let _ = xfe!(x);
1314        let _ = xfe!([x.coefficients[0], x.coefficients[1], x.coefficients[2]]);
1315        let y = xfe!(bfe!(42));
1316        assert_eq!(x, y);
1317
1318        let a = xfe!([bfe!(42), bfe!(43), bfe!(44)]);
1319        let b = xfe!([42, 43, 44]);
1320        assert_eq!(a, b);
1321
1322        let m: [XFieldElement; 3] = xfe_array![[1, 2, 3], [4, 5, 6], [7, 8, 9]];
1323        let n: Vec<XFieldElement> = xfe_vec![[1, 2, 3], [4, 5, 6], [7, 8, 9]];
1324        assert_eq!(m.to_vec(), n);
1325    }
1326
1327    #[macro_rules_attr::apply(proptest)]
1328    fn xfe_macro_produces_same_result_as_calling_new(coeffs: [BFieldElement; EXTENSION_DEGREE]) {
1329        let xfe = XFieldElement::new(coeffs);
1330        prop_assert_eq!(xfe, xfe!(coeffs));
1331    }
1332
1333    #[macro_rules_attr::apply(proptest)]
1334    fn xfe_macro_produces_same_result_as_calling_new_const(scalar: BFieldElement) {
1335        let xfe = XFieldElement::new_const(scalar);
1336        prop_assert_eq!(xfe, xfe!(scalar));
1337    }
1338
1339    #[macro_rules_attr::apply(proptest)]
1340    fn as_flat_slice_produces_expected_slices(xfes: Vec<XFieldElement>) {
1341        let bfes = xfes.iter().flat_map(|&x| x.coefficients).collect_vec();
1342        prop_assert_eq!(&bfes, as_flat_slice(&xfes));
1343    }
1344}
twenty_first/math/x_field_element.rs

twenty_first/math/
x_field_element.rs
