fft

Documentation

Overview

Package fft provides in-place discrete Fourier transform on powers-of-two subgroups of 𝔽ᵣˣ (the multiplicative group (ℤ/rℤ, x) ).

Index

• func BitReverse(v []fr.Element)
• func BuildExpTable(w fr.Element, table []fr.Element)
• func Generator(m uint64) (fr.Element, error)
• func GeneratorFullMultiplicativeGroup() fr.Element
• type Decimation
• type Domain
  • func NewDomain(m uint64, opts ...DomainOption) *Domain
  • func (d *Domain) CosetTable() ([]fr.Element, error)
  • func (d *Domain) CosetTableInv() ([]fr.Element, error)
  • func (domain *Domain) FFT(a []fr.Element, decimation Decimation, opts ...Option)
  • func (domain *Domain) FFTInverse(a []fr.Element, decimation Decimation, opts ...Option)
  • func (d *Domain) ReadFrom(r io.Reader) (int64, error)
  • func (d *Domain) Twiddles() ([][]fr.Element, error)
  • func (d *Domain) TwiddlesInv() ([][]fr.Element, error)
  • func (d *Domain) WriteTo(w io.Writer) (int64, error)
• type DomainOption
  • func WithShift(shift fr.Element) DomainOption
  • func WithoutPrecompute() DomainOption
• type Option
  • func OnCoset() Option
  • func WithNbTasks(nbTasks int) Option

Functions

func BitReverse

func BitReverse(v []fr.Element)

BitReverse applies the bit-reversal permutation to v. len(v) must be a power of 2

func BuildExpTable

func BuildExpTable(w fr.Element, table []fr.Element)

BuildExpTable precomputes the first n powers of w in parallel table[0] = w^0 table[1] = w^1 ...

func Generator

func Generator(m uint64) (fr.Element, error)

Generator returns a generator for Z/2^(log(m))Z or an error if m is too big (required root of unity doesn't exist)

func GeneratorFullMultiplicativeGroup

func GeneratorFullMultiplicativeGroup() fr.Element

GeneratorFullMultiplicativeGroup returns a generator of 𝔽ᵣˣ

Types

type Decimation

type Decimation uint8

Decimation is used in the FFT call to select decimation in time or in frequency

const (
	DIT Decimation = iota
	DIF
)

type Domain

type Domain struct {
	Cardinality            uint64
	CardinalityInv         fr.Element
	Generator              fr.Element
	GeneratorInv           fr.Element
	FrMultiplicativeGen    fr.Element // generator of Fr*
	FrMultiplicativeGenInv fr.Element
	// contains filtered or unexported fields
}

Domain with a power of 2 cardinality compute a field element of order 2x and store it in FinerGenerator all other values can be derived from x, GeneratorSqrt

func NewDomain

func NewDomain(m uint64, opts ...DomainOption) *Domain

NewDomain returns a subgroup with a power of 2 cardinality cardinality >= m shift: when specified, it's the element by which the set of root of unity is shifted.

func (*Domain) CosetTable

func (d *Domain) CosetTable() ([]fr.Element, error)

CosetTable returns the cosetTable u*<1,g,..,g^(n-1)> or an error if the domain was created with the WithoutPrecompute option

func (*Domain) CosetTableInv

func (d *Domain) CosetTableInv() ([]fr.Element, error)

CosetTableInv returns the cosetTableInv u*<1,g,..,g^(n-1)> or an error if the domain was created with the WithoutPrecompute option

func (*Domain) FFT

func (domain *Domain) FFT(a []fr.Element, decimation Decimation, opts ...Option)

FFT computes (recursively) the discrete Fourier transform of a and stores the result in a if decimation == DIT (decimation in time), the input must be in bit-reversed order if decimation == DIF (decimation in frequency), the output will be in bit-reversed order

func (*Domain) FFTInverse

func (domain *Domain) FFTInverse(a []fr.Element, decimation Decimation, opts ...Option)

FFTInverse computes (recursively) the inverse discrete Fourier transform of a and stores the result in a if decimation == DIT (decimation in time), the input must be in bit-reversed order if decimation == DIF (decimation in frequency), the output will be in bit-reversed order coset sets the shift of the fft (0 = no shift, standard fft) len(a) must be a power of 2, and w must be a len(a)th root of unity in field F.

func (*Domain) ReadFrom

func (d *Domain) ReadFrom(r io.Reader) (int64, error)

ReadFrom attempts to decode a domain from Reader

func (*Domain) Twiddles

func (d *Domain) Twiddles() ([][]fr.Element, error)

Twiddles returns the twiddles factor for the FFT using Generator for each stage of the recursive FFT or an error if the domain was created with the WithoutPrecompute option

func (*Domain) TwiddlesInv

func (d *Domain) TwiddlesInv() ([][]fr.Element, error)

TwiddlesInv returns the twiddles factor for the FFT using GeneratorInv for each stage of the recursive FFT or an error if the domain was created with the WithoutPrecompute option

func (*Domain) WriteTo

func (d *Domain) WriteTo(w io.Writer) (int64, error)

WriteTo writes a binary representation of the domain (without the precomputed twiddle factors) to the provided writer

type DomainOption

type DomainOption func(*domainConfig)

DomainOption defines option for altering the definition of the FFT domain See the descriptions of functions returning instances of this type for particular options.

func WithShift

func WithShift(shift fr.Element) DomainOption

WithShift sets the FrMultiplicativeGen of the domain. Default is generator of the largest 2-adic subgroup.

func WithoutPrecompute

func WithoutPrecompute() DomainOption

WithoutPrecompute disables precomputation of twiddles in the domain. When this option is set, FFTs will be slower, but will use less memory.

type Option

type Option func(*fftConfig)

Option defines option for altering the behavior of FFT methods. See the descriptions of functions returning instances of this type for particular options.

func OnCoset

func OnCoset() Option

OnCoset if provided, FFT(a) returns the evaluation of a on a coset.

func WithNbTasks

func WithNbTasks(nbTasks int) Option

WithNbTasks sets the max number of task (go routine) to spawn. Must be between 1 and 512.