Struct GaoMateerOnTheFly

pub struct GaoMateerOnTheFly<F> { /* private fields */ }

Produces a specific “Gao-Mateer” $S^{(0)}$ and computes twiddles on-the-fly. Only works for binary fields whose degree over $\mathbb{F}_2$ is a power of two.

A Gao-Mateer basis of the binary field $\mathbb{F}_{2^{2^k}}$ is any $\mathbb{F}2$-basis $(\beta_0, \beta_1,…, \beta{2^k - 1})$ with the following properties:

• $\beta_{2^k-1}$ has trace 1
• $\beta_i = \beta_{i+1}^2 + \beta_{i+1}$

This implies some nice properties:

• the basis elements with a small index are in a small subfield, in fact $(\beta_0,…,\beta_{2^l - 1})$ is a basis of $\mathbb{F}_{2^{2^l}}$ for any $l$, and in particular $\beta_0 = 1$
• The subspace polynomial $W_i$ of $\operatorname{span} {\beta_0, …, \beta_{i-1}}$ is defined over $\mathbb{F}_2$, i.e., its coefficients are just $0$ or $1$.
• The subspace polynomial is “auto-normalized”, meaning $W_i (\beta_i) = 1$ so that $\hat{W}_i = W_i$.
• The evaluations of the subspace polynomials are just the basis elements: $W_i (\beta_{i + r}) = \beta_r$ for any $i$ and $r$.
• The previous point together with the first point implies that twiddles in early layers lie in a small subfield. This could potentially be used to speed up the NTT if one can implement multiplication with an element from a small subfield more efficiently.
• The folding maps for FRI are all $x \mapsto x^2 + x$, no normalization factors needed.

On-the-fly twiddle computation should not be used for running a big NTT or for a complete FRI folding. In both cases, all twiddles will be accessed eventually, so they might as well be precomputed. But it could possibly be used e.g. in the FRI verifier, which only accesses a few selected twiddles.

Implementations

impl<F: BinaryField + TraceOneElement> GaoMateerOnTheFly<F>

pub fn generate(log_domain_size: usize) -> Self

Given the intended size of $S^{(0)}$, computes a “nice” Gao-Mateer DomainContext.

This will not precompute the twiddles; instead they will be computed on-the-fly.

Preconditions

• The degree (over $\mathbb{F}2$) of the field needs to be a tower of two. For example, it does not work with $\mathbb{F}{2^3}$, but it works with $\mathbb{F}_{2^4}$.
• log_domain_size must be nonzero

Trait Implementations

impl<F: Debug> Debug for GaoMateerOnTheFly<F>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<F: BinaryField> DomainContext for GaoMateerOnTheFly<F>

type Field = F

fn log_domain_size(&self) -> usize

Base 2 logarithm of the size of $S^{(0)}$, i.e., $\ell$.

fn subspace(&self, i: usize) -> BinarySubspace<F>

Returns the binary subspace with dimension $i$.

fn twiddle(&self, _layer: usize, block: usize) -> F

Returns the twiddle of a certain block in a certain layer.