# 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 2
^{128}- 45 * 2^{40}+ 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 2
^{62}- 111 * 2^{39}+ 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
x^{2} - 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:

- crate:
`fft`

module:

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.