Module snarkvm_algorithms::fft::domain

This module contains an EvaluationDomain abstraction for performing various kinds of polynomial arithmetic on top of the scalar field.

In pairing-based SNARKs like GM17, we need to calculate a quotient polynomial over a target polynomial with roots at distinct points associated with each constraint of the constraint system. In order to be efficient, we choose these roots to be the powers of a 2^n root of unity in the field. This allows us to perform polynomial operations in O(n) by performing an O(n log n) FFT over such a domain.

Structs

• Elements
  An iterator over the elements of the domain.
• EvaluationDomain
  Defines a domain over which finite field (I)FFTs can be performed. Works only for fields that have a large multiplicative subgroup of size that is a power-of-2.
• FFTPrecomputation
  An iterator over the elements of the domain.
• IFFTPrecomputation
  An iterator over the elements of the domain.

Functions

• log2
  Returns the ceiling of the base-2 logarithm of x.