# Crate winter_math[−][src]

Expand description

This crate contains modules with mathematical operations needed in STARK proof generation and verification.

Unless otherwise stated, all operations happen in finite fields.

# Finite fields

Finite field modules implements arithmetic operations in STARK-friendly finite fields. The operation include:

• Basic arithmetic operations: addition, multiplication, subtraction, division, inversion.
• Drawing random and pseudo-random elements from the field.
• Computing roots of unity of a given order.

Currently, there are two implementations of finite fields:

• A 128-bit field with modulus 2128 - 45 * 240 + 1. This field was not chosen with any significant thought given to performance, and the implementation of most operations is sub-optimal as well. Proofs generated in this field can support security level of ~100 bits. If higher level of security is desired, proofs must be generated in a quadratic extension of the field.
• A 62-bit field with modulus 262 - 111 * 239 + 1. This field supports very fast modular arithmetic including branchless multiplication and addition. To achieve adequate security (i.e. ~100 bits), proofs must be generated in a quadratic extension of this field. For higher levels of security, a cubic extension field should be used.

## Extension fields

Currently, the library provides a generic way to create quadratic extensions of STARK fields. An extension element is defined as α + β * φ, where φ is a root of the polynomial x2 - x - 1, and α and β are base field elements.

Support for cubic extension fields is not yet available.

# Polynomials

Polynomials module implements basic polynomial operations such as:

• Evaluation of a polynomial at a single or multiple point.
• Interpolation of a polynomial from a set of points (using Lagrange interpolation).
• Addition, multiplication, subtraction, and division of polynomials.
• Synthetic polynomial division (using Ruffini’s method).

# Fast Fourier transform

FFT module contains operations for computing Fast Fourier transform in a prime field (also called Number-theoretic transform). This can be used to interpolate and evaluate polynomials in O(n log n) time as long as the domain of the polynomial is a multiplicative subgroup with size which is a power of 2.

# Concurrent execution

When the crate is compiled with `concurrent` feature enabled, some operations will be executed in multiple threads (usually, as many threads as there are logical cores on the machine). These operations are:

Number of threads can be configured via `RAYON_NUM_THREADS` environment variable

## Modules

FFT-based polynomial evaluation and interpolation.

Finite field implementations.

Basic polynomial operations.

## Traits

Defines an element in a finite field.

Defines an element in a STARK-friendly finite field.

## Functions

Computes element-wise sum of the provided vectors, and stores the result in the first vector.

Computes a multiplicative inverse of a sequence of elements using batch inversion method.

Returns a vector containing successive powers of a given base.

Returns a vector containing successive powers of a given base offset by the specified value.

Returns base 2 logarithm of `n`, where `n` is a power of two.

Multiplies a sequence of values by a scalar and accumulates the results.