risc0_zkp/core/
poly.rs

1// Copyright 2024 RISC Zero, Inc.
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15//! Polynomial utilities (currently only those used in polynomial evaluation).
16
17use alloc::vec;
18
19use risc0_core::field::ExtElem;
20
21/// Evaluate a polynomial whose coefficients are in the extension field at a
22/// point.
23pub fn poly_eval<E: ExtElem>(coeffs: &[E], x: E) -> E {
24    let mut mul = E::ONE;
25    let mut tot = E::ZERO;
26    for coeff in coeffs {
27        tot += *coeff * mul;
28        mul *= x;
29    }
30    tot
31}
32
33/// General purpose polynomial interpolation.
34///
35/// Given the goal value f(x) at a set of evaluation points x, compute
36/// coefficients.
37pub fn poly_interpolate<E: ExtElem>(out: &mut [E], x: &[E], fx: &[E], size: usize) {
38    // Special case the very easy ones
39    if size == 1 {
40        out[0] = fx[0];
41        return;
42    }
43    if size == 2 {
44        out[1] = (fx[1] - fx[0]) * (x[1] - x[0]).inv();
45        out[0] = fx[0] - out[1] * x[0];
46        return;
47    }
48    // Compute ft = product of (x - x_i) for all i
49    let mut ft = vec![E::ZERO; size + 1];
50    ft[0] = E::ONE;
51    for (i, x) in x.iter().enumerate().take(size) {
52        for j in (0..i + 1).rev() {
53            let value = ft[j];
54            ft[j + 1] += value;
55            ft[j] *= -*x;
56        }
57    }
58    // Clear output
59    for x in &mut *out {
60        *x = E::ZERO;
61    }
62    for i in 0..size {
63        // Compute fr = ft / (x - x_i)
64        let mut fr = ft.clone();
65        poly_divide(&mut fr, x[i]);
66        // Evaluate at x[i]
67        let fr_xi = poly_eval(&fr, x[i]);
68        // Compute multiplier (fx[i] / fr_xi)
69        let mul = fx[i] * fr_xi.inv();
70        // Multiply into output
71        for j in 0..size {
72            out[j] += mul * fr[j];
73        }
74    }
75}
76
77/// In-place polynomial division.
78///
79/// Take the coefficients in P, and divide by (X - z) for some z, return the
80/// remainder.
81pub fn poly_divide<E: ExtElem>(p: &mut [E], z: E) -> E {
82    let mut cur = E::ZERO;
83    for i in (0..p.len()).rev() {
84        let next = z * cur + p[i];
85        p[i] = cur;
86        cur = next;
87    }
88    cur
89}
risc0_zkp/core/poly.rs

risc0_zkp/core/
poly.rs
