p3_field_testing/
extension_testing.rs

1use alloc::vec::Vec;
2
3use p3_field::{ExtensionField, Field, PackedFieldExtension, PackedValue};
4use rand::distr::{Distribution, StandardUniform};
5use rand::rngs::SmallRng;
6use rand::{Rng, SeedableRng};
7
8use crate::exp_biguint;
9
10/// Ensure that the methods `is_in_basefield` and `as_base` work as expected.
11pub fn test_to_from_extension_field<F, EF>()
12where
13    F: Field,
14    EF: ExtensionField<F>,
15    StandardUniform: Distribution<F> + Distribution<EF>,
16{
17    let mut rng = SmallRng::seed_from_u64(1);
18
19    let base_elem: F = rng.random();
20    let base_elem_in_ext: EF = base_elem.into();
21    assert!(base_elem_in_ext.is_in_basefield());
22    assert_eq!(base_elem_in_ext.as_base(), Some(base_elem));
23
24    let extension_elem: EF = rng.random();
25    let ext_degree = EF::DIMENSION;
26
27    if ext_degree == 1 {
28        assert!(
29            extension_elem.is_in_basefield(),
30            "The element {} does not lie in the base field, but it should.",
31            extension_elem
32        );
33    } else {
34        // In principle it's possible that a randomly chosen element does lie in the base field.
35        // But this is very unlikely. If this comes up regularly, we can change the test.
36        assert!(
37            !extension_elem.is_in_basefield(),
38            "The randomly chosen element {} lies in the base field, but it (likely) should not.",
39            extension_elem
40        );
41        assert!(extension_elem.as_base().is_none());
42    }
43}
44
45/// Test that products and sums of galois conjugates lie in the base field.
46///
47/// This test can be skipped for extension fields of degree 1 as it is trivial.
48pub fn test_galois_extension<F, EF>()
49where
50    F: Field,
51    EF: ExtensionField<F>,
52    StandardUniform: Distribution<EF>,
53{
54    let mut rng = SmallRng::seed_from_u64(1);
55
56    let extension_elem = rng.random();
57    let ext_degree = EF::DIMENSION;
58
59    let field_order = F::order();
60
61    // Let |F| = p and |EF| = p^d.
62    // Then `(|EF| - 1)/(|F| - 1) = 1 + p + ... + p^(d-1)`.
63    // Given any element `x`, any symmetric function of `x, x^p, ... x^{p^(d-1)}` must lie in the base field.
64    // In particular:
65    //
66    // `Norm(x)  = x^{(|EF| - 1)/(|F| - 1)} = x^{1 + p + ... + p^(d-1)}`
67    // `Trace(x) = x + x^p + ... + x^{p^{d - 1}}`
68    // `x^{p^d}  = x`
69    // We could test other symmetric functions but that seems unnecessary for now.
70    let (trace, norm, power) = (1..ext_degree).fold(
71        (extension_elem, extension_elem, extension_elem),
72        |(acc, prod, power), _| {
73            let next_power = exp_biguint(power, &field_order);
74            (acc + next_power, prod * next_power, next_power)
75        },
76    );
77
78    let ext_power_p_d = exp_biguint(power, &field_order);
79
80    assert!(
81        norm.is_in_basefield(),
82        "The product of Galois conjugates {} of the element {} does not lie in the base field.",
83        norm,
84        extension_elem
85    );
86    assert!(
87        trace.is_in_basefield(),
88        "The sum of Galois conjugates {} of the element {} does not lie in the base field.",
89        trace,
90        extension_elem
91    );
92    assert_eq!(
93        extension_elem, ext_power_p_d,
94        "The element {} raised to the power of p^d does not equal itself.",
95        extension_elem
96    );
97}
98
99/// Ensure that the methods `from_ext_slice`, `to_ext_iter`, `packed_ext_powers` and `packed_ext_powers_capped`
100/// all work as expected.
101pub fn test_packed_extension<F, EF>()
102where
103    F: Field,
104    EF: ExtensionField<F>,
105    StandardUniform: Distribution<EF>,
106{
107    let mut rng = SmallRng::seed_from_u64(1);
108    let width = F::Packing::WIDTH;
109    let extension_elements: Vec<EF> = (0..width).map(|_| rng.random()).collect();
110
111    let packed_extension = EF::ExtensionPacking::from_ext_slice(&extension_elements);
112    let unpacked_extension: Vec<EF> =
113        EF::ExtensionPacking::to_ext_iter([packed_extension]).collect();
114
115    assert_eq!(extension_elements, unpacked_extension);
116
117    let base_powers: Vec<EF> = extension_elements[0].powers().take(10 * width).collect();
118
119    let packed_powers = EF::ExtensionPacking::packed_ext_powers(extension_elements[0]);
120    let unpacked_powers: Vec<EF> = EF::ExtensionPacking::to_ext_iter(packed_powers)
121        .take(10 * width)
122        .collect();
123    assert_eq!(base_powers, unpacked_powers);
124
125    let packed_powers_capped =
126        EF::ExtensionPacking::packed_ext_powers_capped(extension_elements[0], 10 * width);
127
128    let unpacked_powers: Vec<EF> =
129        EF::ExtensionPacking::to_ext_iter(packed_powers_capped).collect();
130    assert_eq!(base_powers, unpacked_powers);
131}
p3_field_testing/extension_testing.rs

p3_field_testing/
extension_testing.rs
