Function create_poly

compressed_sigma/src/partial_knowledge.rs:29–45

Create polynomial referred to p(X) in the paper. p(0) = 1 and p(X) = 0 for all X in given vector `x`, thus its a polynomial of degree `x.len()`. From Lagrange interpolation, the polynomial is \sum_{j in 0..=k}(y_j * l_j(x)). Since all except one y_j is 1 and the non-zero equals 1, the polynomial equals the basis polynomial l_0(x) and l_0(x) = \prod_{j in 1..=k}(x-x_j) / \prod_{j in 1..=k}(0-x_j)

(x: Vec<F>)

/// \sum_{j in 0..=k}(y_j * l_j(x)). Since all except one y_j is 1 and the non-zero equals 1, the
/// polynomial equals the basis polynomial l_0(x) and l_0(x) = \prod_{j in 1..=k}(x-x_j) / \prod_{j in 1..=k}(0-x_j)
fn create_poly<F: PrimeField>(x: Vec<F>) -> DensePolynomial<F> {
    assert!(x.iter().all(|x_| !x_.is_zero()));

    // Get all -x_j
    let neg_x = x.into_iter().map(|i| -i).collect::<Vec<_>>();
    // Create terms of the form (x - x_j) and multiply them
    let polys = neg_x
        .iter()
        .map(|i| DensePolynomial::from_coefficients_slice(&[*i, F::one()]))
        .collect();
    let poly = multiply_many_polys(polys);

    // Take product of all -x_j and invert the result
    let inv_neg_x_product = neg_x.iter().fold(F::one(), |a, b| a * b).inverse().unwrap();

    &poly * inv_neg_x_product
}

/// Return a new vector `y` whose first `d` elements are coefficients of degree `d` polynomial `poly` and
/// rest of the elements are of `t`, i.e. `y = [a_1, a_2, ..., a_d, t_1, t_2, ..., t_n]`