p3_binary_dft/
domain.rs

1//! The additive NTT domain: `F_2`-linear subspaces spanned by the Cantor basis.
2
3use p3_binary_field::TowerLevel;
4
5/// The `index`-th point of the additive NTT domain, `Σ_r bit_r(index) · v_r`.
6///
7/// The domain `S_ℓ` is the span of the first `ℓ` Cantor basis vectors, so this is well
8/// defined for any `ℓ > log2(index)` and does not depend on which level evaluates it.
9///
10/// # Panics
11/// Panics if `index` has a set bit at or above the bit width of `F`.
12#[must_use]
13pub fn domain_point<F: TowerLevel>(index: usize) -> F {
14    let mut point = F::ZERO;
15    let mut remaining = index;
16    let mut r = 0;
17    while remaining != 0 {
18        if remaining & 1 == 1 {
19            point += F::cantor_basis(r);
20        }
21        remaining >>= 1;
22        r += 1;
23    }
24    point
25}
26
27/// The subspace polynomial `W_j` of `S_j`, defined by `W_0(x) = x` and
28/// `W_j(x) = W_{j−1}(x)² + W_{j−1}(x)`.
29///
30/// `W_j` is `F_2`-linear, vanishes exactly on `S_j`, and satisfies `W_j(v_j) = v_0 = 1`, so it
31/// is already the normalised subspace polynomial `Ŵ_j` for the Cantor basis (D8).
32#[must_use]
33pub fn subspace_polynomial<F: TowerLevel>(j: usize, x: F) -> F {
34    let mut value = x;
35    for _ in 0..j {
36        value = value.square() + value;
37    }
38    value
39}
40
41#[cfg(test)]
42mod tests {
43    use p3_binary_field::{BinaryField8, BinaryField16, BinaryField128, TowerLevel};
44    use p3_field::PrimeCharacteristicRing;
45
46    use super::{domain_point, subspace_polynomial};
47
48    /// The image of every single-bit index is the matching Cantor basis vector, which pins the
49    /// basis itself and not merely some graded `F_2`-linear reparametrisation of it.
50    #[test]
51    fn domain_point_images_are_the_cantor_basis() {
52        for r in 0..8 {
53            assert_eq!(
54                domain_point::<BinaryField8>(1 << r),
55                BinaryField8::cantor_basis(r),
56                "r={r}"
57            );
58        }
59        for r in 0..usize::BITS as usize {
60            assert_eq!(
61                domain_point::<BinaryField128>(1 << r),
62                BinaryField128::cantor_basis(r),
63                "r={r}"
64            );
65        }
66    }
67
68    /// An index reaching past the basis of its level is rejected rather than silently masked.
69    #[test]
70    #[should_panic = "Cantor basis index out of range"]
71    fn domain_point_rejects_an_index_past_the_basis() {
72        let _ = domain_point::<BinaryField8>(1 << 8);
73    }
74
75    /// `domain_point` is `F_2`-linear in its index.
76    #[test]
77    fn domain_point_is_linear_in_the_index() {
78        for a in 0..1usize << 8 {
79            for b in 0..1usize << 8 {
80                assert_eq!(
81                    domain_point::<BinaryField8>(a ^ b),
82                    domain_point::<BinaryField8>(a) + domain_point::<BinaryField8>(b)
83                );
84            }
85        }
86    }
87
88    /// `W_j` vanishes exactly on `S_j`, the span of the first `j` basis vectors.
89    #[test]
90    fn subspace_polynomial_vanishes_on_its_subspace() {
91        for j in 0..=8 {
92            for m in 0..1usize << 8 {
93                let value = subspace_polynomial::<BinaryField8>(j, domain_point(m));
94                assert_eq!(value == BinaryField8::ZERO, m < 1 << j, "j={j} m={m}");
95            }
96        }
97    }
98
99    /// D8's index-shift identity: `W_j(v_i) = v_{i−j}` for `i ≥ j`.
100    #[test]
101    fn subspace_polynomial_shifts_the_basis() {
102        for j in 0..16 {
103            for i in j..16 {
104                assert_eq!(
105                    subspace_polynomial::<BinaryField16>(j, BinaryField16::cantor_basis(i)),
106                    BinaryField16::cantor_basis(i - j),
107                    "j={j} i={i}"
108                );
109            }
110        }
111    }
112
113    /// A point of the domain does not depend on the level it is computed at.
114    #[test]
115    fn domain_points_agree_across_levels() {
116        for m in 0..1usize << 8 {
117            let small: u128 = domain_point::<BinaryField8>(m).to_repr().into();
118            let large: u128 = domain_point::<BinaryField128>(m).to_repr();
119            assert_eq!(small, large, "index {m}");
120        }
121    }
122}
p3_binary_dft/domain.rs

p3_binary_dft/
domain.rs
