Trait mvpoly::MVPoly

pub trait MVPoly<F: PrimeField, const N: usize, const D: usize>: Add<Self, Output = Self> + for<'a> Add<&'a Self, Output = Self> + Mul<Self, Output = Self> + Neg<Output = Self> + Sub<Self, Output = Self> + for<'a> Sub<&'a Self, Output = Self> + One + Zero + Debug + Clone + PartialEq + Eq + From<F> + Sized {
    // Required methods
    unsafe fn random<RNG: RngCore>(
        rng: &mut RNG,
        max_degree: Option<usize>
    ) -> Self;
    fn double(&self) -> Self;
    fn is_constant(&self) -> bool;
    fn mul_by_scalar(&self, scalar: F) -> Self;
    unsafe fn degree(&self) -> usize;
    fn eval(&self, x: &[F; N]) -> F;
    fn from_variable<Column: Into<usize>>(
        var: Variable<Column>,
        offset_next_row: Option<usize>
    ) -> Self;
    fn is_homogeneous(&self) -> bool;
    fn homogeneous_eval(&self, x: &[F; N], u: F) -> F;
    fn add_monomial(&mut self, exponents: [usize; N], coeff: F);
    fn compute_cross_terms(
        &self,
        eval1: &[F; N],
        eval2: &[F; N],
        u1: F,
        u2: F
    ) -> HashMap<usize, F>;
    fn compute_cross_terms_scaled(
        &self,
        eval1: &[F; N],
        eval2: &[F; N],
        u1: F,
        u2: F,
        scalar1: F,
        scalar2: F
    ) -> HashMap<usize, F>;
    fn modify_monomial(&mut self, exponents: [usize; N], coeff: F);
    fn is_multilinear(&self) -> bool;

    // Provided methods
    fn from_constant<ChallengeTerm: Clone>(
        op: Operations<ConstantExprInner<F, ChallengeTerm>>
    ) -> Self { ... }
    fn from_expr<Column: Into<usize>, ChallengeTerm: Clone>(
        expr: Expr<ConstantExpr<F, ChallengeTerm>, Column>,
        offset_next_row: Option<usize>
    ) -> Self { ... }
}

Generic trait to represent a multi-variate polynomial

Required Methods

unsafe fn random<RNG: RngCore>(rng: &mut RNG, max_degree: Option<usize>) -> Self

Generate a random polynomial of maximum degree max_degree.

If None is provided as the maximum degree, the polynomial will be generated with a maximum degree of D.

Safety

Marked as unsafe to warn the user to use it with caution and to not necessarily rely on it for security/randomness in cryptographic protocols. The user is responsible for providing its own secure polynomial random generator, if needed.

For now, the function is only used for testing.

fn double(&self) -> Self

fn is_constant(&self) -> bool

fn mul_by_scalar(&self, scalar: F) -> Self

unsafe fn degree(&self) -> usize

Returns the degree of the polynomial.

The degree of the polynomial is the maximum degree of the monomials that have a non-zero coefficient.

Safety

The zero polynomial as a degree equals to 0, as the degree of the constant polynomials. We do use the unsafe keyword to warn the user for this specific case.

fn eval(&self, x: &[F; N]) -> F

Evaluate the polynomial at the vector point x.

This is a dummy implementation. A cache can be used for the monomials to speed up the computation.

fn from_variable<Column: Into<usize>>( var: Variable<Column>, offset_next_row: Option<usize> ) -> Self

Build the univariate polynomial x_i from the variable i. The conversion into the type usize is unspecified by this trait. It is left to the trait implementation. For instance, in the case of crate::prime, the output must be a prime number, starting at 2. crate::utils::PrimeNumberGenerator can be used. For crate::monomials, the output must be the index of the variable, starting from 0.

The parameter offset_next_row is an optional argument that is used to support the case where the “next row” is used. In this case, the type parameter N must include this offset (i.e. if 4 variables are in ued, N should be at least 8 = 2 * 4).

fn is_homogeneous(&self) -> bool

Returns true if the polynomial is homogeneous (of degree D). As a reminder, a polynomial is homogeneous if all its monomials have the same degree.

fn homogeneous_eval(&self, x: &[F; N], u: F) -> F

Evaluate the polynomial at the vector point x and the extra variable u using its homogeneous form of degree D.

fn add_monomial(&mut self, exponents: [usize; N], coeff: F)

Add the monomial coeff * x_1^{e_1} * ... * x_N^{e_N} to the polynomial, where e_i are the values given by the array exponents.

For instance, to add the monomial 3 * x_1^2 * x_2^3 to the polynomial, one would call add_monomial([2, 3], 3).

fn compute_cross_terms( &self, eval1: &[F; N], eval2: &[F; N], u1: F, u2: F ) -> HashMap<usize, F>

Compute the cross-terms as described in Behind Nova: cross-terms computation for high degree gates

The polynomial must not necessarily be homogeneous. For this reason, the values u1 and u2 represents the extra variable that is used to make the polynomial homogeneous.

The homogeneous degree is supposed to be the one defined by the type of the polynomial, i.e. D.

The output is a map of D - 1 values that represents the cross-terms for each power of r.

fn compute_cross_terms_scaled( &self, eval1: &[F; N], eval2: &[F; N], u1: F, u2: F, scalar1: F, scalar2: F ) -> HashMap<usize, F>

Compute the cross-terms of the given polynomial, scaled by the given scalar.

More explicitly, given a polynomial P(X1, ..., Xn) and a scalar α, the method computes the the cross-terms of the polynomial Q(X1, ..., Xn, α) = α * P(X1, ..., Xn). For this reason, the method takes as input the two different scalars scalar1 and scalar2 as we are considering the scaling factor as a variable.

This method is particularly useful when you need to compute a (possibly random) combinaison of polynomials P1(X1, ..., Xn), ..., Pm(X1, ..., Xn), like when computing a quotient polynomial in the PlonK PIOP, as the result is the sum of individual “scaled” polynomials:

Q(X_1, ..., X_n, α_1, ..., α_m) =
  α_1 P1(X_1, ..., X_n) +
  ...
  α_m Pm(X_1, ..., X_n) +

The polynomial must not necessarily be homogeneous. For this reason, the values u1 and u2 represents the extra variable that is used to make the polynomial homogeneous.

The homogeneous degree is supposed to be the one defined by the type of the polynomial P, i.e. D.

The output is a map of D values that represents the cross-terms for each power of r.

fn modify_monomial(&mut self, exponents: [usize; N], coeff: F)

Modify the monomial in the polynomial to the new value coeff.

fn is_multilinear(&self) -> bool

Return true if the multi-variate polynomial is multilinear, i.e. if each variable in each monomial is of maximum degree 1.

Provided Methods

fn from_constant<ChallengeTerm: Clone>( op: Operations<ConstantExprInner<F, ChallengeTerm>> ) -> Self

fn from_expr<Column: Into<usize>, ChallengeTerm: Clone>( expr: Expr<ConstantExpr<F, ChallengeTerm>, Column>, offset_next_row: Option<usize> ) -> Self

Build a value from an expression. This method aims to be used to be retro-compatible with what we call “the expression framework”. In the near future, the “expression framework” should be moved also into this library.

The mapping from variable to the user is left unspecified by this trait and is left to the implementation. The conversion of a variable into an index is done by the trait requirement Into<usize> on the column type.

The parameter offset_next_row is an optional argument that is used to support the case where the “next row” is used. In this case, the type parameter N must include this offset (i.e. if 4 variables are in ued, N should be at least 8 = 2 * 4).

Implementors

impl<F: PrimeField, const N: usize, const D: usize> MVPoly<F, N, D> for Dense<F, N, D>

impl<const N: usize, const D: usize, F: PrimeField> MVPoly<F, N, D> for Sparse<F, N, D>