ps_ecc/polynomial/methods/
eval_coefficients_derivative_at.rs

1use crate::{
2    finite_field::{add, mul},
3    Polynomial,
4};
5
6impl Polynomial {
7    /// Evaluates the formal derivative of a polynomial at the given point.
8    ///
9    /// In characteristic 2, only odd-degree terms contribute to the derivative:
10    /// p'(x) = a₁ + a₃x² + a₅x⁴ + ...
11    ///
12    /// Coefficients are ordered from degree 0 (constant term) to the leading term.
13    #[must_use]
14    pub fn eval_coefficients_derivative_at(coefficients: &[u8], x: u8) -> u8 {
15        let mut result = 0u8;
16        let x_sq = mul(x, x);
17        let mut x_pow = 1u8;
18
19        for k in 0..=coefficients.len() / 2 {
20            let idx = 2 * k + 1;
21
22            if idx < coefficients.len() {
23                result = add(result, mul(coefficients[idx], x_pow));
24                x_pow = mul(x_pow, x_sq);
25            }
26        }
27
28        result
29    }
30}
31
32#[cfg(test)]
33mod tests {
34    use crate::{
35        finite_field::{add, mul},
36        Polynomial,
37    };
38
39    /// Computes expected derivative value using naive evaluation.
40    fn naive_eval_deriv(coefficients: &[u8], x: u8) -> u8 {
41        let mut result = 0u8;
42        let x_sq = mul(x, x);
43        let mut x_pow = 1u8;
44
45        for k in 0..=coefficients.len() / 2 {
46            let idx = 2 * k + 1;
47
48            if idx < coefficients.len() {
49                result = add(result, mul(coefficients[idx], x_pow));
50                x_pow = mul(x_pow, x_sq);
51            }
52        }
53
54        result
55    }
56
57    /// Asserts that `eval_coefficients_derivative_at` matches naive evaluation for all x.
58    fn assert_exhaustive(coefficients: &[u8]) {
59        for x in 0..=255u8 {
60            assert_eq!(
61                Polynomial::eval_coefficients_derivative_at(coefficients, x),
62                naive_eval_deriv(coefficients, x)
63            );
64        }
65    }
66
67    #[test]
68    fn empty_slice() {
69        assert_exhaustive(&[]);
70    }
71
72    #[test]
73    fn zero_polynomial() {
74        assert_exhaustive(&[0]);
75    }
76
77    #[test]
78    fn constant_polynomial_has_zero_derivative() {
79        for c in [1u8, 42, 128, 255] {
80            for x in 0..=255u8 {
81                assert_eq!(Polynomial::eval_coefficients_derivative_at(&[c], x), 0);
82            }
83        }
84    }
85
86    #[test]
87    fn linear_polynomial() {
88        // p(x) = a + bx, p'(x) = b
89        for x in 0..=255u8 {
90            assert_eq!(Polynomial::eval_coefficients_derivative_at(&[5, 3], x), 3);
91            assert_eq!(Polynomial::eval_coefficients_derivative_at(&[0, 1], x), 1);
92            assert_eq!(
93                Polynomial::eval_coefficients_derivative_at(&[255, 255], x),
94                255
95            );
96        }
97    }
98
99    #[test]
100    fn quadratic_polynomial() {
101        // p(x) = a + bx + cx², p'(x) = b (c*2x = 0 in char 2)
102        assert_exhaustive(&[1, 0, 1]);
103        assert_exhaustive(&[0, 5, 1]);
104        assert_exhaustive(&[255, 128, 64]);
105    }
106
107    #[test]
108    fn cubic_polynomial() {
109        // p(x) = a + bx + cx² + dx³, p'(x) = b + dx²
110        assert_exhaustive(&[0x12, 0x34, 0x56, 0x78]);
111        assert_exhaustive(&[1, 1, 1, 1]);
112        assert_exhaustive(&[0, 0, 0, 1]);
113    }
114
115    #[test]
116    fn high_degree_polynomial() {
117        assert_exhaustive(&[1, 2, 3, 4, 5, 6, 7, 8]);
118        assert_exhaustive(&[0, 0, 0, 0, 0, 0, 0, 1]);
119    }
120
121    #[test]
122    fn only_even_powers() {
123        // p(x) = 1 + x² + x⁴, p'(x) = 0
124        for x in 0..=255u8 {
125            assert_eq!(
126                Polynomial::eval_coefficients_derivative_at(&[1, 0, 1, 0, 1], x),
127                0
128            );
129        }
130    }
131
132    #[test]
133    fn only_odd_powers() {
134        // p(x) = x + x³, p'(x) = 1 + x²
135        let coefficients = [0u8, 1, 0, 1];
136
137        for x in 0..=255u8 {
138            let x2 = mul(x, x);
139            let expected = add(1, x2);
140
141            assert_eq!(
142                Polynomial::eval_coefficients_derivative_at(&coefficients, x),
143                expected
144            );
145        }
146    }
147
148    #[test]
149    fn max_degree_polynomial() {
150        let mut coefficients = [0u8; Polynomial::MAX_COEFFICIENTS as usize];
151
152        coefficients[Polynomial::MAX_DEGREE as usize] = 1;
153
154        assert_exhaustive(&coefficients);
155    }
156
157    #[test]
158    fn matches_naive_eval_deriv() {
159        let coefficients = [0x12u8, 0x34, 0x56, 0x78, 0x9A];
160
161        for x in 0..=255u8 {
162            assert_eq!(
163                Polynomial::eval_coefficients_derivative_at(&coefficients, x),
164                naive_eval_deriv(&coefficients, x)
165            );
166        }
167    }
168}
ps_ecc/polynomial/methods/eval_coefficients_derivative_at.rs

ps_ecc/polynomial/methods/
eval_coefficients_derivative_at.rs
