ps_ecc/polynomial/methods/
eval_coefficients_at.rs

1use crate::{
2    finite_field::{add, mul},
3    Polynomial,
4};
5
6impl Polynomial {
7    /// Evaluates a polynomial given its coefficients at the given point using Horner's method.
8    ///
9    /// Coefficients are ordered from degree 0 (constant term) to the leading term.
10    #[must_use]
11    pub fn eval_coefficients_at(coefficients: &[u8], x: u8) -> u8 {
12        let mut result = 0u8;
13
14        for &coef in coefficients.iter().rev() {
15            result = add(mul(result, x), coef);
16        }
17
18        result
19    }
20}
21
22#[cfg(test)]
23mod tests {
24    use crate::{
25        finite_field::{add, mul},
26        Polynomial,
27    };
28
29    /// Computes expected value using naive polynomial evaluation.
30    fn naive_eval(coefficients: &[u8], x: u8) -> u8 {
31        let mut result = 0u8;
32        let mut x_pow = 1u8;
33
34        for &c in coefficients {
35            result = add(result, mul(c, x_pow));
36            x_pow = mul(x_pow, x);
37        }
38
39        result
40    }
41
42    /// Asserts that `eval_coefficients_at` matches naive evaluation for all x in 0..=255.
43    fn assert_exhaustive(coefficients: &[u8]) {
44        for x in 0..=255u8 {
45            assert_eq!(
46                Polynomial::eval_coefficients_at(coefficients, x),
47                naive_eval(coefficients, x)
48            );
49        }
50    }
51
52    #[test]
53    fn empty_slice() {
54        assert_exhaustive(&[]);
55    }
56
57    #[test]
58    fn zero_polynomial() {
59        assert_exhaustive(&[0]);
60    }
61
62    #[test]
63    fn constant_polynomial() {
64        assert_exhaustive(&[1]);
65        assert_exhaustive(&[42]);
66        assert_exhaustive(&[128]);
67        assert_exhaustive(&[255]);
68    }
69
70    #[test]
71    fn linear_polynomial() {
72        assert_exhaustive(&[5, 3]);
73        assert_exhaustive(&[0, 1]);
74        assert_exhaustive(&[255, 255]);
75    }
76
77    #[test]
78    fn quadratic_polynomial() {
79        assert_exhaustive(&[1, 0, 1]);
80        assert_exhaustive(&[0, 0, 1]);
81        assert_exhaustive(&[255, 128, 64]);
82    }
83
84    #[test]
85    fn cubic_polynomial() {
86        assert_exhaustive(&[0x12, 0x34, 0x56, 0x78]);
87        assert_exhaustive(&[1, 1, 1, 1]);
88        assert_exhaustive(&[0, 0, 0, 1]);
89    }
90
91    #[test]
92    fn high_degree_polynomial() {
93        assert_exhaustive(&[1, 2, 3, 4, 5, 6, 7, 8]);
94        assert_exhaustive(&[0, 0, 0, 0, 0, 0, 0, 1]);
95    }
96
97    #[test]
98    fn sparse_polynomial() {
99        assert_exhaustive(&[1, 0, 0, 0, 1]);
100        assert_exhaustive(&[0, 1, 0, 1, 0]);
101    }
102
103    #[test]
104    fn all_coefficients_max() {
105        assert_exhaustive(&[255, 255, 255, 255]);
106    }
107
108    #[test]
109    fn max_degree_monomial() {
110        let mut coefficients = [0u8; Polynomial::MAX_COEFFICIENTS as usize];
111
112        coefficients[Polynomial::MAX_DEGREE as usize] = 1;
113
114        assert_exhaustive(&coefficients);
115    }
116
117    #[test]
118    fn max_degree_all_ones() {
119        let coefficients = [1u8; Polynomial::MAX_COEFFICIENTS as usize];
120
121        assert_exhaustive(&coefficients);
122    }
123
124    #[test]
125    fn max_degree_all_max() {
126        let coefficients = [255u8; Polynomial::MAX_COEFFICIENTS as usize];
127
128        assert_exhaustive(&coefficients);
129    }
130}
ps_ecc/polynomial/methods/eval_coefficients_at.rs

ps_ecc/polynomial/methods/
eval_coefficients_at.rs
