Module halo2_proofs::arithmetic

This module provides common utilities, traits and structures for group, field and polynomial arithmetic.

Traits

CurveAffine

This trait is the affine counterpart to Curve and is used for serialization, storage in memory, and inspection of $x$ and $y$ coordinates.

CurveExt

This trait is a common interface for dealing with elements of an elliptic curve group in a “projective” form, where that arithmetic is usually more efficient.

Field

This trait represents an element of a field.

FieldExt

This trait is a common interface for dealing with elements of a finite field.

Group

This represents an element of a group with basic operations that can be performed. This allows an FFT implementation (for example) to operate generically over either a field or elliptic curve group.

Functions

best_fft

Performs a radix-$2$ Fast-Fourier Transformation (FFT) on a vector of size $n = 2^k$, when provided log_n = $k$ and an element of multiplicative order $n$ called omega ($\omega$). The result is that the vector a, when interpreted as the coefficients of a polynomial of degree $n - 1$, is transformed into the evaluations of this polynomial at each of the $n$ distinct powers of $\omega$. This transformation is invertible by providing $\omega^{-1}$ in place of $\omega$ and dividing each resulting field element by $n$.

best_multiexp

Performs a multi-exponentiation operation.

compute_inner_product

This computes the inner product of two vectors a and b.

eval_polynomial

This evaluates a provided polynomial (in coefficient form) at point.

g_to_lagrange

Convert coefficient bases group elements to lagrange basis by inverse FFT.

kate_division

Divides polynomial a in X by X - b with no remainder.

lagrange_interpolate

Returns coefficients of an n - 1 degree polynomial given a set of n points and their evaluations. This function will panic if two values in points are the same.

parallelize

This simple utility function will parallelize an operation that is to be performed over a mutable slice.

recursive_butterfly_arithmetic

This perform recursive butterfly arithmetic

small_multiexp

Performs a small multi-exponentiation operation. Uses the double-and-add algorithm with doublings shared across points.