Module halo2_proofs::arithmetic

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

Structs

• Coordinates
  The affine coordinates of a point on an elliptic curve.

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.
• FftGroup
  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.
• Field
  This trait represents an element of a field.

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.
• 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.