Crate p3_dft 

p3-dft

Discrete Fourier transform implementations over finite fields, used for low-degree extensions of trace matrices.

Key items:

• TwoAdicSubgroupDft — the core trait: (inverse) DFTs and coset LDEs over two-adic subgroups, batched column-wise over matrices
• Radix2Dit, Radix2DitParallel, Radix2Bowers, Radix2DFTSmallBatch — radix-2 variants with different parallelism and cache trade-offs
• NaiveDft — a quadratic reference implementation for testing

Part of Plonky3, dual-licensed under MIT and Apache 2.0.

Structs

DifButterfly

DIF (Decimation-In-Frequency) butterfly operation.

DifButterflyZeros

DIF (Decimation-In-Frequency) butterfly operation where x_2 is guaranteed to be zero.

DitButterfly

DIT (Decimation-In-Time) butterfly operation.

NaiveDft

Radix2Bowers

The Bowers G FFT algorithm. See: “Improved Twiddle Access for Fast Fourier Transforms”

Radix2DFTSmallBatch

An FFT algorithm which divides a butterfly network’s layers into two halves.

Radix2Dit

Radix-2 Decimation-in-Time FFT over a two-adic subgroup.

Radix2DitParallel

A parallel FFT algorithm which divides a butterfly network’s layers into two halves.

ScaledDitButterfly

DIT (Decimation-In-Time) butterfly operation with a post-multiplication scale factor.

TwiddleFreeButterfly

Butterfly with no twiddle factor (twiddle = 1).

Enums

Layout

Memory layout of the coefficient buffer passed to a transform closure in TwoAdicSubgroupDft::coset_lde_batch_with_transform.

Traits

Butterfly

A butterfly operation used in NTT to combine two values into a new pair.

TwoAdicSubgroupDft

This trait gives an interface for computing discrete fourier transforms (DFT’s) and their inverses over cosets of two-adic subgroups of a field F. It also contains combined methods which allow you to take the evaluation vector of a polynomial on a coset gH and extend it to a coset g'K for some possibly larger subgroup K and different shift g'.

Functions

divide_by_height

Divide each coefficient of the given matrix by its height.