ark-poly

此crate实现了多项式、域（称为"域"）的FFT友好子集以及这些域的FFT的特性和实现。

多项式

polynomial模块提供了以下特性，用于以系数形式定义多项式

• Polynomial：要求实现者支持多项式的常见操作，如Add、Sub、Zero、在一点上的评估、次数等，并定义了将多项式序列化和反序列化为系数表示的方法。
• DenseUVPolynomial：指定一个Polynomial实际上是一个一元多项式。
• DenseMVPolynomial：指定一个Polynomial实际上是一个多元多项式。

此crate还提供了以下实现这些特性的数据结构

• univariate/DensePolynomial：通过一个包含d + 1个系数的列表表示次数为d的一元多项式。此结构实现了DenseUVPolynomial特性。
• univariate/SparsePolynomial：通过包含所有非零单项式的列表表示度数为 d 的单项式多项式。这应该只在多项式的大多数系数为零时使用。此结构体实现了 Polynomial 特性（但 不 实现 DenseUVPolynomial 特性）。
• multivariate/SparsePolynomial：通过包含所有非零单项式的列表表示多元多项式。

此crate还提供了 univariate/DenseOrSparsePolynomial 枚举，允许用户抽象底层单项式多项式的类型（密集或稀疏）。

示例

use ark_poly::{
    polynomial::multivariate::{SparsePolynomial, SparseTerm, Term},
    DenseMVPolynomial, Polynomial,
};
use ark_test_curves::bls12_381::Fq;
// Create a multivariate polynomial in 3 variables, with 4 terms:
// f(x_0, x_1, x_2) = 2*x_0^3 + x_0*x_2 + x_1*x_2 + 5
let poly = SparsePolynomial::from_coefficients_vec(
    3,
    vec![
        (Fq::from(2), SparseTerm::new(vec![(0, 3)])),
        (Fq::from(1), SparseTerm::new(vec![(0, 1), (2, 1)])),
        (Fq::from(1), SparseTerm::new(vec![(1, 1), (2, 1)])),
        (Fq::from(5), SparseTerm::new(vec![])),
    ],
);
assert_eq!(poly.evaluate(&vec![Fq::from(2), Fq::from(3), Fq::from(6)]), Fq::from(51));

评估

evaluations 模块提供数据结构来表示拉格朗日形式的多项式。

• univariate/Evaluations 表示用于FFT的评估形式的单项式多项式。

evaluations 模块还提供了以下特性来定义拉格朗日形式的多元多项式

• multivariate/multilinear/MultilinearExtension 指定在布尔超立方体上评估的多线性多项式。

此crate提供了一些数据结构来实现这些特性。

• multivariate/multilinear/DenseMultilinearExtension 通过布尔超立方体上的评估列表表示多线性扩展。

• multivariate/multilinear/SparseMultilinearExtension 通过布尔超立方体上的非零评估列表表示多线性扩展。

示例

use ark_test_curves::bls12_381::Fq;
use ark_poly::{DenseMultilinearExtension, MultilinearExtension, SparseMultilinearExtension};
use ark_poly::{
    polynomial::multivariate::{SparsePolynomial, SparseTerm, Term},
    DenseMVPolynomial, Polynomial,
};
use ark_std::One;

// Create a multivariate polynomial in 3 variables:
// f(x_0, x_1, x_2) = 2*x_0^3 + x_0*x_2 + x_1*x_2 
let f = SparsePolynomial::from_coefficients_vec(
    3,
    vec![
        (Fq::from(2), SparseTerm::new(vec![(0, 3)])),
        (Fq::from(1), SparseTerm::new(vec![(0, 1), (2, 1)])),
        (Fq::from(1), SparseTerm::new(vec![(1, 1), (2, 1)])),
        (Fq::from(0), SparseTerm::new(vec![])),
    ],
);
// g is the multilinear extension of f, defined by the evaluations of f on the Boolean hypercube:
// f(0, 0, 0) = 2*0^3 + 0*0 + 0*0 = 0
// f(1, 0, 0) = 2*1^3 + 0*0 + 0*0 = 2
// ...
// f(1, 1, 1) = 2*1^3 + 1*1 + 1*1 = 4
let g: DenseMultilinearExtension<Fq> = DenseMultilinearExtension::from_evaluations_vec(
    3, 
    vec![
        Fq::from(0),
        Fq::from(2),
        Fq::from(0),
        Fq::from(2),
        Fq::from(0),
        Fq::from(3),
        Fq::from(1),
        Fq::from(4),
    ]
);
// when evaluated at any point within the Boolean hypercube, f and g should be equal
let point_within_hypercube = &vec![Fq::from(0), Fq::from(1), Fq::from(1)];
assert_eq!(f.evaluate(&point_within_hypercube), g.evaluate(&point_within_hypercube));

// We can also define a MLE g'(x_0, x_1, x_2) by providing the list of non-zero evaluations:
let g_prime: SparseMultilinearExtension<Fq> = SparseMultilinearExtension::from_evaluations(
    3,
    &vec![
        (1, Fq::from(2)),
        (3, Fq::from(2)),
        (5, Fq::from(3)),
        (6, Fq::from(1)),
        (7, Fq::from(4)),
    ]
);
// at any random point (X0, X1, X2), g == g' with negligible probability, unless they are the same function
let random_point = &vec![Fq::from(123), Fq::from(456), Fq::from(789)];
assert_eq!(g_prime.evaluate(&random_point), g.evaluate(&random_point));

域

待办事项