Module arithmetic

Help

Expand description

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

Structs§

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.
SqrtRatio: A trait that exposes additional operations related to calculating square roots of prime-order finite fields.

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.