1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

//! This module contains a type [ChunkedPolynomial],
//! and a number of helper methods to deal with chunked polynomials.
//! Polynomials that cut in several polynomials of the same length.

use ark_ff::Field;
use ark_poly::polynomial::{univariate::DensePolynomial, Polynomial};

/// This struct contains multiple chunk polynomials with degree `size-1`.
pub struct ChunkedPolynomial<F: Field> {
    /// The chunk polynomials.
    pub polys: Vec<DensePolynomial<F>>,

    /// Each chunk polynomial has degree `size-1`.
    pub size: usize,
}

impl<F: Field> ChunkedPolynomial<F> {
    /// This function evaluates polynomial in chunks.
    pub fn evaluate_chunks(&self, elm: F) -> Vec<F> {
        let mut res: Vec<F> = vec![];
        for poly in &self.polys {
            let eval = poly.evaluate(&elm);
            res.push(eval);
        }
        res
    }

    /// Multiplies the chunks of a polynomial with powers of zeta^n to make it of degree n-1.
    /// For example, if a polynomial can be written `f = f0 + x^n f1 + x^2n f2`
    /// (where f0, f1, f2 are of degree n-1), then this function returns the new semi-evaluated
    /// `f'(x) = f0(x) + zeta^n f1(x) + zeta^2n f2(x)`.
    pub fn linearize(&self, zeta_n: F) -> DensePolynomial<F> {
        let mut scale = F::one();
        let mut coeffs = vec![F::zero(); self.size];

        for poly in &self.polys {
            for (coeff, poly_coeff) in coeffs.iter_mut().zip(&poly.coeffs) {
                *coeff += scale * poly_coeff;
            }

            scale *= zeta_n;
        }

        while coeffs.last().map_or(false, |c| c.is_zero()) {
            coeffs.pop();
        }

        DensePolynomial { coeffs }
    }
}

#[cfg(test)]
mod tests {
    use crate::ExtendedDensePolynomial;

    use super::*;
    use ark_ff::One;
    use ark_poly::{univariate::DensePolynomial, UVPolynomial};
    use mina_curves::pasta::Fp;

    #[test]

    fn test_chunk_poly() {
        let one = Fp::one();
        let zeta = one + one;
        let zeta_n = zeta.square();
        let num_chunks = 4;
        let res = (one + zeta)
            * (one + zeta_n + zeta_n * zeta.square() + zeta_n * zeta.square() * zeta.square());

        // 1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 = (1+x) + x^2 (1+x) + x^4 (1+x) + x^6 (1+x)
        let coeffs = [one, one, one, one, one, one, one, one];
        let f = DensePolynomial::from_coefficients_slice(&coeffs);

        let eval = f
            .to_chunked_polynomial(num_chunks, 2)
            .linearize(zeta_n)
            .evaluate(&zeta);

        assert!(eval == res);
    }
}