#finite-fields #polynomial #fft

no-std ark-poly

A library for efficient polynomial arithmetic via FFTs over finite fields

12 releases

0.4.2 Mar 18, 2023
0.4.1 Feb 21, 2023
0.4.0-alpha.7 Dec 29, 2022
0.4.0-alpha.3 Nov 5, 2022
0.2.0 Mar 24, 2021

#325 in Cryptography

Download history 82875/week @ 2023-11-21 90933/week @ 2023-11-28 84396/week @ 2023-12-05 81755/week @ 2023-12-12 66195/week @ 2023-12-19 36824/week @ 2023-12-26 70215/week @ 2024-01-02 81265/week @ 2024-01-09 91805/week @ 2024-01-16 91863/week @ 2024-01-23 84463/week @ 2024-01-30 90117/week @ 2024-02-06 84234/week @ 2024-02-13 91619/week @ 2024-02-20 88351/week @ 2024-02-27 68456/week @ 2024-03-05

349,113 downloads per month
Used in 1,498 crates (37 directly)

MIT/Apache

530KB
11K SLoC

ark-poly

This crate implements traits and implementations for polynomials, FFT-friendly subsets of a field (dubbed "domains"), and FFTs for these domains.

Polynomials

The polynomial module provides the following traits for defining polynomials in coefficient form:

  • Polynomial: Requires implementors to support common operations on polynomials, such as Add, Sub, Zero, evaluation at a point, degree, etc, and defines methods to serialize to and from the coefficient representation of the polynomial.
  • DenseUVPolynomial : Specifies that a Polynomial is actually a univariate polynomial.
  • DenseMVPolynomial: Specifies that a Polynomial is actually a multivariate polynomial.

This crate also provides the following data structures that implement these traits:

  • univariate/DensePolynomial: Represents degree d univariate polynomials via a list of d + 1 coefficients. This struct implements the DenseUVPolynomial trait.
  • univariate/SparsePolynomial: Represents degree d univariate polynomials via a list containing all non-zero monomials. This should only be used when most coefficients of the polynomial are zero. This struct implements the Polynomial trait (but not the DenseUVPolynomial trait).
  • multivariate/SparsePolynomial: Represents multivariate polynomials via a list containing all non-zero monomials.

This crate also provides the univariate/DenseOrSparsePolynomial enum, which allows the user to abstract over the type of underlying univariate polynomial (dense or sparse).

Example

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

The evaluations module provides data structures to represent univariate polynomials in lagrange form.

The evaluations module also provides the following traits for defining multivariate polynomials in lagrange form:

This crate provides some data structures to implement these traits.

Example

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).unwrap());

// 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).unwrap(), g.evaluate(&random_point).unwrap());

Domains

TODO

Dependencies

~5MB
~96K SLoC