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


FFT-based polynomial evaluation and interpolation.

Finite field implementations.

Basic polynomial operations.


Defines an element in a finite field.

Defines an element in a STARK-friendly finite field.


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.