### 4 releases (breaking)

Uses new Rust 2021

0.4.0 | Apr 29, 2022 |
---|---|

0.3.0 | Jan 5, 2022 |

0.2.0 | Aug 24, 2021 |

0.1.0 | Aug 4, 2021 |

#**116** in Cryptography

**2,083** downloads per month

Used in **17** crates
(9 directly)

**MIT**license

255KB

4.5K
SLoC

# Winter math

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

## Finite field

Finite field module 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. - A 64-bit field with modulus 2
^{64}- 2^{32}+ 1. This field is about 15% slower than the 62-bit field described above, but it has a number of other attractive properties. 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 and cubic extensions of supported STARK fields. This can be done by implementing 'ExtensibleField' trait for degrees 2 and 3.

Quadratic extension fields are defined using the following irreducible polynomials:

- For

field, the polynomial is x`f62`^{2}- x - 1. - For

field, the polynomial is x`f64`^{2}- x + 2. - For

field, the polynomial is x`f128`^{2}- x - 1.

Cubic extension fields are defined using the following irreducible polynomials:

- For

field, the polynomial is x`f62`^{3}+ 2x + 2. - For

field, the polynomial is x`f64`^{3}- x - 1. - For

field, cubic extensions are not supported.`f128`

## Polynomials

Polynomials module implements basic polynomial operations such as:

- Evaluation of a polynomial at a single 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.

## Crate features

This crate can be compiled with the following features:

- enabled by default and relies on the Rust standard library.`std`

- implies`concurrent`

and also enables multi-threaded execution for some of the crate functions.`std`

- does not rely on Rust's standard library and enables compilation to WebAssembly.`no_std`

To compile with

, disable default features via `no_std`

flag.`--no-default-features`

### Concurrent execution

When compiled with

feature enabled, the following operations will be executed in multiple threads:`concurrent`

- fft module:
`evaluate_poly``(``)``evaluate_poly_with_offset``(``)``interpolate_poly``(``)``interpolate_poly_with_offset``(``)``get_twiddles``(``)``get_inv_twiddles``(``)`

- utils module:
`get_power_series``(``)``get_power_series_with_offset``(``)``add_in_place``(``)``mul_acc``(``)``batch_inversion``(``)`

The number of threads can be configured via

environment variable, and usually defaults to the number of logical cores on the machine.`RAYON_NUM_THREADS`

## License

This project is MIT licensed.