lambdaworks_math/field/fields/fft_friendly/
quartic_babybear.rs

1use crate::field::{
2    element::FieldElement,
3    errors::FieldError,
4    fields::fft_friendly::babybear::Babybear31PrimeField,
5    traits::{HasDefaultTranscript, IsFFTField, IsField, IsSubFieldOf},
6};
7
8use crate::traits::ByteConversion;
9
10#[cfg(feature = "alloc")]
11use crate::traits::AsBytes;
12
13/// We are implementig the extension of Baby Bear of degree 4 using the irreducible polynomial x^4 + 11.
14/// BETA = 11 and -BETA = -11 is the non-residue.
15pub const BETA: FieldElement<Babybear31PrimeField> =
16    FieldElement::<Babybear31PrimeField>::from_hex_unchecked("b");
17
18#[derive(Clone, Debug)]
19pub struct Degree4BabyBearExtensionField;
20
21impl IsField for Degree4BabyBearExtensionField {
22    type BaseType = [FieldElement<Babybear31PrimeField>; 4];
23
24    fn add(a: &Self::BaseType, b: &Self::BaseType) -> Self::BaseType {
25        [&a[0] + &b[0], &a[1] + &b[1], &a[2] + &b[2], &a[3] + &b[3]]
26    }
27
28    /// Result of multiplying two polynomials a = a0 + a1 * x + a2 * x^2 + a3 * x^3 and
29    /// b = b0 + b1 * x + b2 * x^2 + b3 * x^3 by applying distribution and taking
30    /// the remainder of the division by x^4 + 11.
31    fn mul(a: &Self::BaseType, b: &Self::BaseType) -> Self::BaseType {
32        [
33            &a[0] * &b[0] - BETA * (&a[1] * &b[3] + &a[3] * &b[1] + &a[2] * &b[2]),
34            &a[0] * &b[1] + &a[1] * &b[0] - BETA * (&a[2] * &b[3] + &a[3] * &b[2]),
35            &a[0] * &b[2] + &a[2] * &b[0] + &a[1] * &b[1] - BETA * (&a[3] * &b[3]),
36            &a[0] * &b[3] + &a[3] * &b[0] + &a[1] * &b[2] + &a[2] * &b[1],
37        ]
38    }
39
40    fn square(a: &Self::BaseType) -> Self::BaseType {
41        [
42            &a[0].square() - BETA * ((&a[1] * &a[3]).double() + &a[2].square()),
43            (&a[0] * &a[1] - BETA * (&a[2] * &a[3])).double(),
44            (&a[0] * &a[2]).double() + &a[1].square() - BETA * (&a[3].square()),
45            (&a[0] * &a[3] + &a[1] * &a[2]).double(),
46        ]
47    }
48
49    fn sub(a: &Self::BaseType, b: &Self::BaseType) -> Self::BaseType {
50        [&a[0] - &b[0], &a[1] - &b[1], &a[2] - &b[2], &a[3] - &b[3]]
51    }
52
53    fn neg(a: &Self::BaseType) -> Self::BaseType {
54        [-&a[0], -&a[1], -&a[2], -&a[3]]
55    }
56
57    /// Return te inverse of a fp4 element if exist.
58    /// This algorithm is inspired by Risc0 implementation:
59    /// <https://github.com/risc0/risc0/blob/4c41c739779ef2759a01ebcf808faf0fbffe8793/risc0/core/src/field/baby_bear.rs#L460>
60    fn inv(a: &Self::BaseType) -> Result<Self::BaseType, FieldError> {
61        let mut b0 = &a[0] * &a[0] + BETA * (&a[1] * (&a[3] + &a[3]) - &a[2] * &a[2]);
62        let mut b2 = &a[0] * (&a[2] + &a[2]) - &a[1] * &a[1] + BETA * (&a[3] * &a[3]);
63        let c = &b0.square() + BETA * b2.square();
64        let c_inv = c.inv()?;
65        b0 *= &c_inv;
66        b2 *= &c_inv;
67        Ok([
68            &a[0] * &b0 + BETA * &a[2] * &b2,
69            -&a[1] * &b0 - BETA * &a[3] * &b2,
70            -&a[0] * &b2 + &a[2] * &b0,
71            &a[1] * &b2 - &a[3] * &b0,
72        ])
73    }
74
75    fn div(a: &Self::BaseType, b: &Self::BaseType) -> Result<Self::BaseType, FieldError> {
76        let b_inv = &Self::inv(b).map_err(|_| FieldError::DivisionByZero)?;
77        Ok(<Self as IsField>::mul(a, b_inv))
78    }
79
80    fn eq(a: &Self::BaseType, b: &Self::BaseType) -> bool {
81        a[0] == b[0] && a[1] == b[1] && a[2] == b[2] && a[3] == b[3]
82    }
83
84    fn zero() -> Self::BaseType {
85        Self::BaseType::default()
86    }
87
88    fn one() -> Self::BaseType {
89        [
90            FieldElement::one(),
91            FieldElement::zero(),
92            FieldElement::zero(),
93            FieldElement::zero(),
94        ]
95    }
96
97    fn from_u64(x: u64) -> Self::BaseType {
98        [
99            FieldElement::from(x),
100            FieldElement::zero(),
101            FieldElement::zero(),
102            FieldElement::zero(),
103        ]
104    }
105
106    /// Takes as input an element of BaseType and returns the internal representation
107    /// of that element in the field.
108    /// Note: for this case this is simply the identity, because the components
109    /// already have correct representations.
110    fn from_base_type(x: Self::BaseType) -> Self::BaseType {
111        x
112    }
113
114    fn double(a: &Self::BaseType) -> Self::BaseType {
115        <Degree4BabyBearExtensionField as IsField>::add(a, a)
116    }
117
118    fn pow<T>(a: &Self::BaseType, mut exponent: T) -> Self::BaseType
119    where
120        T: crate::unsigned_integer::traits::IsUnsignedInteger,
121    {
122        let zero = T::from(0);
123        let one = T::from(1);
124
125        if exponent == zero {
126            return Self::one();
127        }
128        if exponent == one {
129            return a.clone();
130        }
131
132        let mut result = a.clone();
133
134        // Fast path for powers of 2
135        while exponent & one == zero {
136            result = Self::square(&result);
137            exponent >>= 1;
138            if exponent == zero {
139                return result;
140            }
141        }
142
143        let mut base = result.clone();
144        exponent >>= 1;
145
146        while exponent != zero {
147            base = Self::square(&base);
148            if exponent & one == one {
149                result = <Degree4BabyBearExtensionField as IsField>::mul(&result, &base);
150            }
151            exponent >>= 1;
152        }
153
154        result
155    }
156}
157
158impl IsSubFieldOf<Degree4BabyBearExtensionField> for Babybear31PrimeField {
159    fn mul(
160        a: &Self::BaseType,
161        b: &<Degree4BabyBearExtensionField as IsField>::BaseType,
162    ) -> <Degree4BabyBearExtensionField as IsField>::BaseType {
163        let c0 = FieldElement::from_raw(<Self as IsField>::mul(a, b[0].value()));
164        let c1 = FieldElement::from_raw(<Self as IsField>::mul(a, b[1].value()));
165        let c2 = FieldElement::from_raw(<Self as IsField>::mul(a, b[2].value()));
166        let c3 = FieldElement::from_raw(<Self as IsField>::mul(a, b[3].value()));
167
168        [c0, c1, c2, c3]
169    }
170
171    fn add(
172        a: &Self::BaseType,
173        b: &<Degree4BabyBearExtensionField as IsField>::BaseType,
174    ) -> <Degree4BabyBearExtensionField as IsField>::BaseType {
175        let c0 = FieldElement::from_raw(<Self as IsField>::add(a, b[0].value()));
176        let c1 = FieldElement::from_raw(*b[1].value());
177        let c2 = FieldElement::from_raw(*b[2].value());
178        let c3 = FieldElement::from_raw(*b[3].value());
179
180        [c0, c1, c2, c3]
181    }
182
183    fn div(
184        a: &Self::BaseType,
185        b: &<Degree4BabyBearExtensionField as IsField>::BaseType,
186    ) -> Result<<Degree4BabyBearExtensionField as IsField>::BaseType, FieldError> {
187        let b_inv =
188            Degree4BabyBearExtensionField::inv(b).map_err(|_| FieldError::DivisionByZero)?;
189        Ok(<Self as IsSubFieldOf<Degree4BabyBearExtensionField>>::mul(
190            a, &b_inv,
191        ))
192    }
193
194    fn sub(
195        a: &Self::BaseType,
196        b: &<Degree4BabyBearExtensionField as IsField>::BaseType,
197    ) -> <Degree4BabyBearExtensionField as IsField>::BaseType {
198        let c0 = FieldElement::from_raw(<Self as IsField>::sub(a, b[0].value()));
199        let c1 = FieldElement::from_raw(<Self as IsField>::neg(b[1].value()));
200        let c2 = FieldElement::from_raw(<Self as IsField>::neg(b[2].value()));
201        let c3 = FieldElement::from_raw(<Self as IsField>::neg(b[3].value()));
202        [c0, c1, c2, c3]
203    }
204
205    fn embed(a: Self::BaseType) -> <Degree4BabyBearExtensionField as IsField>::BaseType {
206        [
207            FieldElement::from_raw(a),
208            FieldElement::zero(),
209            FieldElement::zero(),
210            FieldElement::zero(),
211        ]
212    }
213
214    #[cfg(feature = "alloc")]
215    fn to_subfield_vec(
216        b: <Degree4BabyBearExtensionField as IsField>::BaseType,
217    ) -> alloc::vec::Vec<Self::BaseType> {
218        b.into_iter().map(|x| x.to_raw()).collect()
219    }
220}
221
222impl ByteConversion for [FieldElement<Babybear31PrimeField>; 4] {
223    #[cfg(feature = "alloc")]
224    fn to_bytes_be(&self) -> alloc::vec::Vec<u8> {
225        let mut byte_slice = ByteConversion::to_bytes_be(&self[0]);
226        byte_slice.extend(ByteConversion::to_bytes_be(&self[1]));
227        byte_slice.extend(ByteConversion::to_bytes_be(&self[2]));
228        byte_slice.extend(ByteConversion::to_bytes_be(&self[3]));
229        byte_slice
230    }
231
232    #[cfg(feature = "alloc")]
233    fn to_bytes_le(&self) -> alloc::vec::Vec<u8> {
234        let mut byte_slice = ByteConversion::to_bytes_le(&self[0]);
235        byte_slice.extend(ByteConversion::to_bytes_le(&self[1]));
236        byte_slice.extend(ByteConversion::to_bytes_le(&self[2]));
237        byte_slice.extend(ByteConversion::to_bytes_le(&self[3]));
238        byte_slice
239    }
240
241    fn from_bytes_be(bytes: &[u8]) -> Result<Self, crate::errors::ByteConversionError>
242    where
243        Self: Sized,
244    {
245        const BYTES_PER_FIELD: usize = 64;
246
247        let x0 = FieldElement::from_bytes_be(&bytes[0..BYTES_PER_FIELD])?;
248        let x1 = FieldElement::from_bytes_be(&bytes[BYTES_PER_FIELD..BYTES_PER_FIELD * 2])?;
249        let x2 = FieldElement::from_bytes_be(&bytes[BYTES_PER_FIELD * 2..BYTES_PER_FIELD * 3])?;
250        let x3 = FieldElement::from_bytes_be(&bytes[BYTES_PER_FIELD * 3..BYTES_PER_FIELD * 4])?;
251
252        Ok([x0, x1, x2, x3])
253    }
254
255    fn from_bytes_le(bytes: &[u8]) -> Result<Self, crate::errors::ByteConversionError>
256    where
257        Self: Sized,
258    {
259        const BYTES_PER_FIELD: usize = 64;
260
261        let x0 = FieldElement::from_bytes_le(&bytes[0..BYTES_PER_FIELD])?;
262        let x1 = FieldElement::from_bytes_le(&bytes[BYTES_PER_FIELD..BYTES_PER_FIELD * 2])?;
263        let x2 = FieldElement::from_bytes_le(&bytes[BYTES_PER_FIELD * 2..BYTES_PER_FIELD * 3])?;
264        let x3 = FieldElement::from_bytes_le(&bytes[BYTES_PER_FIELD * 3..BYTES_PER_FIELD * 4])?;
265
266        Ok([x0, x1, x2, x3])
267    }
268}
269
270impl ByteConversion for FieldElement<Degree4BabyBearExtensionField> {
271    #[cfg(feature = "alloc")]
272    fn to_bytes_be(&self) -> alloc::vec::Vec<u8> {
273        let mut byte_slice = ByteConversion::to_bytes_be(&self.value()[0]);
274        byte_slice.extend(ByteConversion::to_bytes_be(&self.value()[1]));
275        byte_slice.extend(ByteConversion::to_bytes_be(&self.value()[2]));
276        byte_slice.extend(ByteConversion::to_bytes_be(&self.value()[3]));
277        byte_slice
278    }
279
280    #[cfg(feature = "alloc")]
281    fn to_bytes_le(&self) -> alloc::vec::Vec<u8> {
282        let mut byte_slice = ByteConversion::to_bytes_le(&self.value()[0]);
283        byte_slice.extend(ByteConversion::to_bytes_le(&self.value()[1]));
284        byte_slice.extend(ByteConversion::to_bytes_le(&self.value()[2]));
285        byte_slice.extend(ByteConversion::to_bytes_le(&self.value()[3]));
286        byte_slice
287    }
288
289    fn from_bytes_be(bytes: &[u8]) -> Result<Self, crate::errors::ByteConversionError>
290    where
291        Self: Sized,
292    {
293        const BYTES_PER_FIELD: usize = 8;
294        let x0 = FieldElement::from_bytes_be(&bytes[0..BYTES_PER_FIELD])?;
295        let x1 = FieldElement::from_bytes_be(&bytes[BYTES_PER_FIELD..BYTES_PER_FIELD * 2])?;
296        let x2 = FieldElement::from_bytes_be(&bytes[BYTES_PER_FIELD * 2..BYTES_PER_FIELD * 3])?;
297        let x3 = FieldElement::from_bytes_be(&bytes[BYTES_PER_FIELD * 3..BYTES_PER_FIELD * 4])?;
298
299        Ok(Self::new([x0, x1, x2, x3]))
300    }
301
302    fn from_bytes_le(bytes: &[u8]) -> Result<Self, crate::errors::ByteConversionError>
303    where
304        Self: Sized,
305    {
306        const BYTES_PER_FIELD: usize = 8;
307        let x0 = FieldElement::from_bytes_le(&bytes[0..BYTES_PER_FIELD])?;
308        let x1 = FieldElement::from_bytes_le(&bytes[BYTES_PER_FIELD..BYTES_PER_FIELD * 2])?;
309        let x2 = FieldElement::from_bytes_le(&bytes[BYTES_PER_FIELD * 2..BYTES_PER_FIELD * 3])?;
310        let x3 = FieldElement::from_bytes_le(&bytes[BYTES_PER_FIELD * 3..BYTES_PER_FIELD * 4])?;
311
312        Ok(Self::new([x0, x1, x2, x3]))
313    }
314}
315
316#[cfg(feature = "alloc")]
317impl AsBytes for FieldElement<Degree4BabyBearExtensionField> {
318    fn as_bytes(&self) -> alloc::vec::Vec<u8> {
319        self.to_bytes_be()
320    }
321}
322
323impl IsFFTField for Degree4BabyBearExtensionField {
324    const TWO_ADICITY: u64 = 29;
325    const TWO_ADIC_PRIMITVE_ROOT_OF_UNITY: Self::BaseType = [
326        FieldElement::from_hex_unchecked("0"),
327        FieldElement::from_hex_unchecked("0"),
328        FieldElement::from_hex_unchecked("0"),
329        FieldElement::from_hex_unchecked("771F1C8"),
330    ];
331}
332
333impl HasDefaultTranscript for Degree4BabyBearExtensionField {
334    fn get_random_field_element_from_rng(rng: &mut impl rand::Rng) -> FieldElement<Self> {
335        //Babybear Prime p = 2^31 - 2^27 + 1
336        const MODULUS: u64 = 2013265921;
337
338        //Babybear prime needs 31 bits and is represented with 32 bits.
339        //The mask is used to remove the first bit.
340        const MASK: u64 = 0x7FFF_FFFF;
341
342        let mut sample = [0u8; 8];
343
344        let mut coeffs = [
345            FieldElement::from(0u64),
346            FieldElement::from(0u64),
347            FieldElement::from(0u64),
348            FieldElement::from(0u64),
349        ];
350
351        for coeff in &mut coeffs {
352            loop {
353                rng.fill(&mut sample);
354                let int_sample = u64::from_be_bytes(sample) & MASK;
355                if int_sample < MODULUS {
356                    *coeff = FieldElement::from(int_sample);
357                    break;
358                }
359            }
360        }
361
362        FieldElement::<Self>::new(coeffs)
363    }
364}
365
366#[cfg(test)]
367mod tests {
368    use super::*;
369
370    type FpE = FieldElement<Babybear31PrimeField>;
371    type Fp4E = FieldElement<Degree4BabyBearExtensionField>;
372
373    #[test]
374    fn test_add() {
375        let a = Fp4E::new([FpE::from(0), FpE::from(1), FpE::from(2), FpE::from(3)]);
376        let b = Fp4E::new([-FpE::from(2), FpE::from(4), FpE::from(6), -FpE::from(8)]);
377        let expected_result = Fp4E::new([
378            FpE::from(0) - FpE::from(2),
379            FpE::from(1) + FpE::from(4),
380            FpE::from(2) + FpE::from(6),
381            FpE::from(3) - FpE::from(8),
382        ]);
383        assert_eq!(a + b, expected_result);
384    }
385
386    #[test]
387    fn test_sub() {
388        let a = Fp4E::new([FpE::from(0), FpE::from(1), FpE::from(2), FpE::from(3)]);
389        let b = Fp4E::new([-FpE::from(2), FpE::from(4), FpE::from(6), -FpE::from(8)]);
390        let expected_result = Fp4E::new([
391            FpE::from(0) + FpE::from(2),
392            FpE::from(1) - FpE::from(4),
393            FpE::from(2) - FpE::from(6),
394            FpE::from(3) + FpE::from(8),
395        ]);
396        assert_eq!(a - b, expected_result);
397    }
398
399    #[test]
400    fn test_mul_by_0() {
401        let a = Fp4E::new([FpE::from(4), FpE::from(1), FpE::from(2), FpE::from(3)]);
402        let b = Fp4E::new([FpE::zero(), FpE::zero(), FpE::zero(), FpE::zero()]);
403        assert_eq!(&a * &b, b);
404    }
405
406    #[test]
407    fn test_mul_by_1() {
408        let a = Fp4E::new([FpE::from(4), FpE::from(1), FpE::from(2), FpE::from(3)]);
409        let b = Fp4E::new([FpE::one(), FpE::zero(), FpE::zero(), FpE::zero()]);
410        assert_eq!(&a * b, a);
411    }
412
413    #[test]
414    fn test_mul() {
415        let a = Fp4E::new([FpE::from(0), FpE::from(1), FpE::from(2), FpE::from(3)]);
416        let b = Fp4E::new([FpE::from(2), FpE::from(4), FpE::from(6), FpE::from(8)]);
417        let expected_result = Fp4E::new([
418            -FpE::from(352),
419            -FpE::from(372),
420            -FpE::from(256),
421            FpE::from(20),
422        ]);
423        assert_eq!(a * b, expected_result);
424    }
425
426    #[test]
427    fn test_pow() {
428        let a = Fp4E::new([FpE::from(0), FpE::from(1), FpE::from(2), FpE::from(3)]);
429        let expected_result = &a * &a * &a;
430        assert_eq!(a.pow(3u64), expected_result);
431    }
432
433    #[test]
434    fn test_inv_of_one_is_one() {
435        let a = Fp4E::one();
436        assert_eq!(a.inv().unwrap(), a);
437    }
438
439    #[test]
440    fn test_inv_of_zero_error() {
441        let result = Fp4E::zero().inv();
442        assert!(result.is_err());
443    }
444
445    #[test]
446    fn test_mul_by_inv_is_identity() {
447        let a = Fp4E::from(123456);
448        assert_eq!(&a * a.inv().unwrap(), Fp4E::one());
449    }
450
451    #[test]
452    fn test_mul_as_subfield() {
453        let a = FpE::from(2);
454        let b = Fp4E::new([FpE::from(2), FpE::from(4), FpE::from(6), FpE::from(8)]);
455        let expected_result = Fp4E::new([
456            FpE::from(2) * FpE::from(2),
457            FpE::from(4) * FpE::from(2),
458            FpE::from(6) * FpE::from(2),
459            FpE::from(8) * FpE::from(2),
460        ]);
461        assert_eq!(a * b, expected_result);
462    }
463
464    #[test]
465    fn test_double_equals_sum_two_times() {
466        let a = Fp4E::new([FpE::from(2), FpE::from(4), FpE::from(6), FpE::from(8)]);
467
468        assert_eq!(a.double(), &a + &a);
469    }
470
471    #[test]
472    fn test_mul_group_generator_pow_order_is_one() {
473        let generator = Fp4E::new([FpE::from(8), FpE::from(1), FpE::zero(), FpE::zero()]);
474        let extension_order: u128 = 2013265921_u128.pow(4);
475        assert_eq!(generator.pow(extension_order), generator);
476    }
477
478    #[test]
479    fn test_two_adic_primitve_root_of_unity() {
480        let generator = Fp4E::new(Degree4BabyBearExtensionField::TWO_ADIC_PRIMITVE_ROOT_OF_UNITY);
481        assert_eq!(
482            generator.pow(2u64.pow(Degree4BabyBearExtensionField::TWO_ADICITY as u32)),
483            Fp4E::one()
484        );
485    }
486
487    #[cfg(all(feature = "std", not(feature = "instruments")))]
488    mod test_babybear_31_fft {
489        use super::*;
490        #[cfg(not(feature = "cuda"))]
491        use crate::fft::cpu::roots_of_unity::{
492            get_powers_of_primitive_root, get_powers_of_primitive_root_coset,
493        };
494        #[cfg(not(feature = "cuda"))]
495        use crate::field::element::FieldElement;
496        #[cfg(not(feature = "cuda"))]
497        use crate::field::traits::{IsFFTField, RootsConfig};
498        use crate::polynomial::Polynomial;
499        use proptest::{collection, prelude::*, std_facade::Vec};
500
501        #[cfg(not(feature = "cuda"))]
502        fn gen_fft_and_naive_evaluation<F: IsFFTField>(
503            poly: Polynomial<FieldElement<F>>,
504        ) -> (Vec<FieldElement<F>>, Vec<FieldElement<F>>) {
505            let len = poly.coeff_len().next_power_of_two();
506            let order = len.trailing_zeros();
507            let twiddles =
508                get_powers_of_primitive_root(order.into(), len, RootsConfig::Natural).unwrap();
509
510            let fft_eval = Polynomial::evaluate_fft::<F>(&poly, 1, None).unwrap();
511            let naive_eval = poly.evaluate_slice(&twiddles);
512
513            (fft_eval, naive_eval)
514        }
515
516        #[cfg(not(feature = "cuda"))]
517        fn gen_fft_coset_and_naive_evaluation<F: IsFFTField>(
518            poly: Polynomial<FieldElement<F>>,
519            offset: FieldElement<F>,
520            blowup_factor: usize,
521        ) -> (Vec<FieldElement<F>>, Vec<FieldElement<F>>) {
522            let len = poly.coeff_len().next_power_of_two();
523            let order = (len * blowup_factor).trailing_zeros();
524            let twiddles =
525                get_powers_of_primitive_root_coset(order.into(), len * blowup_factor, &offset)
526                    .unwrap();
527
528            let fft_eval =
529                Polynomial::evaluate_offset_fft::<F>(&poly, blowup_factor, None, &offset).unwrap();
530            let naive_eval = poly.evaluate_slice(&twiddles);
531
532            (fft_eval, naive_eval)
533        }
534
535        #[cfg(not(feature = "cuda"))]
536        fn gen_fft_and_naive_interpolate<F: IsFFTField>(
537            fft_evals: &[FieldElement<F>],
538        ) -> (Polynomial<FieldElement<F>>, Polynomial<FieldElement<F>>) {
539            let order = fft_evals.len().trailing_zeros() as u64;
540            let twiddles =
541                get_powers_of_primitive_root(order, 1 << order, RootsConfig::Natural).unwrap();
542
543            let naive_poly = Polynomial::interpolate(&twiddles, fft_evals).unwrap();
544            let fft_poly = Polynomial::interpolate_fft::<F>(fft_evals).unwrap();
545
546            (fft_poly, naive_poly)
547        }
548
549        #[cfg(not(feature = "cuda"))]
550        fn gen_fft_and_naive_coset_interpolate<F: IsFFTField>(
551            fft_evals: &[FieldElement<F>],
552            offset: &FieldElement<F>,
553        ) -> (Polynomial<FieldElement<F>>, Polynomial<FieldElement<F>>) {
554            let order = fft_evals.len().trailing_zeros() as u64;
555            let twiddles = get_powers_of_primitive_root_coset(order, 1 << order, offset).unwrap();
556
557            let naive_poly = Polynomial::interpolate(&twiddles, fft_evals).unwrap();
558            let fft_poly = Polynomial::interpolate_offset_fft(fft_evals, offset).unwrap();
559
560            (fft_poly, naive_poly)
561        }
562
563        #[cfg(not(feature = "cuda"))]
564        fn gen_fft_interpolate_and_evaluate<F: IsFFTField>(
565            poly: Polynomial<FieldElement<F>>,
566        ) -> (Polynomial<FieldElement<F>>, Polynomial<FieldElement<F>>) {
567            let eval = Polynomial::evaluate_fft::<F>(&poly, 1, None).unwrap();
568            let new_poly = Polynomial::interpolate_fft::<F>(&eval).unwrap();
569
570            (poly, new_poly)
571        }
572
573        prop_compose! {
574            fn powers_of_two(max_exp: u8)(exp in 1..max_exp) -> usize { 1 << exp }
575            // max_exp cannot be multiple of the bits that represent a usize, generally 64 or 32.
576            // also it can't exceed the test field's two-adicity.
577        }
578        prop_compose! {
579            fn field_element()(coeffs in [any::<u64>(); 4]) -> Fp4E {
580                Fp4E::new([
581                    FpE::from(coeffs[0]),
582                    FpE::from(coeffs[1]),
583                    FpE::from(coeffs[2]),
584                    FpE::from(coeffs[3])]
585                )
586            }
587        }
588        prop_compose! {
589            fn offset()(num in field_element(), factor in any::<u64>()) -> Fp4E { num.pow(factor) }
590        }
591
592        prop_compose! {
593            fn field_vec(max_exp: u8)(vec in collection::vec(field_element(), 0..1 << max_exp)) -> Vec<Fp4E> {
594                vec
595            }
596        }
597        prop_compose! {
598            fn non_power_of_two_sized_field_vec(max_exp: u8)(vec in collection::vec(field_element(), 2..1<<max_exp).prop_filter("Avoid polynomials of size power of two", |vec| !vec.len().is_power_of_two())) -> Vec<Fp4E> {
599                vec
600            }
601        }
602        prop_compose! {
603            fn poly(max_exp: u8)(coeffs in field_vec(max_exp)) -> Polynomial<Fp4E> {
604                Polynomial::new(&coeffs)
605            }
606        }
607        prop_compose! {
608            fn poly_with_non_power_of_two_coeffs(max_exp: u8)(coeffs in non_power_of_two_sized_field_vec(max_exp)) -> Polynomial<Fp4E> {
609                Polynomial::new(&coeffs)
610            }
611        }
612
613        proptest! {
614            // Property-based test that ensures FFT eval. gives same result as a naive polynomial evaluation.
615            #[test]
616            #[cfg(not(feature = "cuda"))]
617            fn test_fft_matches_naive_evaluation(poly in poly(8)) {
618                let (fft_eval, naive_eval) = gen_fft_and_naive_evaluation(poly);
619                prop_assert_eq!(fft_eval, naive_eval);
620            }
621
622            // Property-based test that ensures FFT eval. with coset gives same result as a naive polynomial evaluation.
623            #[test]
624            #[cfg(not(feature = "cuda"))]
625            fn test_fft_coset_matches_naive_evaluation(poly in poly(4), offset in offset(), blowup_factor in powers_of_two(4)) {
626                let (fft_eval, naive_eval) = gen_fft_coset_and_naive_evaluation(poly, offset, blowup_factor);
627                prop_assert_eq!(fft_eval, naive_eval);
628            }
629
630            // Property-based test that ensures FFT interpolation is the same as naive..
631            #[test]
632            #[cfg(not(feature = "cuda"))]
633            fn test_fft_interpolate_matches_naive(fft_evals in field_vec(4)
634                                                           .prop_filter("Avoid polynomials of size not power of two",
635                                                                        |evals| evals.len().is_power_of_two())) {
636                let (fft_poly, naive_poly) = gen_fft_and_naive_interpolate(&fft_evals);
637                prop_assert_eq!(fft_poly, naive_poly);
638            }
639
640            // Property-based test that ensures FFT interpolation with an offset is the same as naive.
641            #[test]
642            #[cfg(not(feature = "cuda"))]
643            fn test_fft_interpolate_coset_matches_naive(offset in offset(), fft_evals in field_vec(4)
644                                                           .prop_filter("Avoid polynomials of size not power of two",
645                                                                        |evals| evals.len().is_power_of_two())) {
646                let (fft_poly, naive_poly) = gen_fft_and_naive_coset_interpolate(&fft_evals, &offset);
647                prop_assert_eq!(fft_poly, naive_poly);
648            }
649
650            // Property-based test that ensures interpolation is the inverse operation of evaluation.
651            #[test]
652            #[cfg(not(feature = "cuda"))]
653            fn test_fft_interpolate_is_inverse_of_evaluate(
654                poly in poly(4).prop_filter("Avoid non pows of two", |poly| poly.coeff_len().is_power_of_two())) {
655                let (poly, new_poly) = gen_fft_interpolate_and_evaluate(poly);
656                prop_assert_eq!(poly, new_poly);
657            }
658        }
659    }
660}
lambdaworks_math/field/fields/fft_friendly/quartic_babybear.rs

lambdaworks_math/field/fields/fft_friendly/
quartic_babybear.rs
