1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102

// Copyright (c) Facebook, Inc. and its affiliates.
//
// This source code is licensed under the MIT license found in the
// LICENSE file in the root directory of this source tree.

//! This crate contains modules with mathematical operations needed in STARK proof generation
//! and verification.
//!
//! Unless otherwise stated, all operations happen in [finite fields](https://en.wikipedia.org/wiki/Finite_field).
//!
//! # Finite fields
//! [Finite field](fields) 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<sup>128</sup> - 45 * 2<sup>40</sup> + 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<sup>62</sup> - 111 * 2<sup>39</sup> + 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<sup>2</sup> - x - 1, and α and β are base field elements.
//!
//! Support for cubic extension fields is not yet available.
//!
//! # Polynomials
//! [Polynomials](polynom) 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](https://en.wikipedia.org/wiki/Lagrange_polynomial) interpolation).
//! * Addition, multiplication, subtraction, and division of polynomials.
//! * Synthetic polynomial division (using
//!   [Ruffini's](https://en.wikipedia.org/wiki/Ruffini%27s_rule) method).
//!
//! # Fast Fourier transform
//! [FFT](fft) module contains operations for computing Fast Fourier transform in a prime
//! field (also called [Number-theoretic transform](https://en.wikipedia.org/wiki/Discrete_Fourier_transform_(general)#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:
//!   - [get_power_series()]
//!   - [get_power_series_with_offset()]
//!   - [add_in_place()]
//!   - [mul_acc()]
//!   - [batch_inversion()]
//! * `fft` module:
//!   - [evaluate_poly()](fft::evaluate_poly())
//!   - [evaluate_poly_with_offset()](fft::evaluate_poly_with_offset())
//!   - [interpolate_poly()](fft::interpolate_poly())
//!   - [interpolate_poly_with_offset()][fft::interpolate_poly_with_offset()]
//!   - [get_twiddles()](fft::get_twiddles())
//!   - [get_inv_twiddles()](fft::get_twiddles())
//!
//! Number of threads can be configured via `RAYON_NUM_THREADS` environment variable

#![cfg_attr(not(feature = "std"), no_std)]

#[cfg(not(feature = "std"))]
#[macro_use]
extern crate alloc;

pub mod fft;
pub mod polynom;

mod field;
pub use field::{FieldElement, StarkField};
pub mod fields {
    //! Finite field implementations.
    //!
    //! This module contains concrete implementations of base STARK fields as well as extensions
    //! of these field.

    pub use super::field::f128;
    pub use super::field::f62;
    pub use super::field::QuadExtensionA;
}

mod utils;
pub use crate::utils::{
    add_in_place, batch_inversion, get_power_series, get_power_series_with_offset, log2, mul_acc,
};