PaperlayerView exact revision on arXiv

Source-linked AI summary

On the Additive FFT Techniques over Binary Extension Fields

Susanta Samanta, Mohammadtaghi Badakhshan, Guang Gong

arXiv:2608.20855v1cs.CR

TL;DR

The paper develops additive FFT techniques for polynomial evaluation over affine subspaces of binary extension fields, including a general-basis framework and Cantor-special-basis specializations. The resulting algorithm is faster than the LCH AFFT in 37 of 42 tested configurations, while partial Cantor special bases reduce operation counts for two AFFT algorithms.

  • Problem

    Over binary extension fields, the evaluation points of interest form affine subspaces rather than multiplicative subgroups.

  • Method

    The paper develops an additive counterpart of Bailey’s four-step FFT, presenting a general-basis AFFT and Cantor-special-basis specializations.

  • Results

    37 of the 42 configurations tested across two hardware platforms were faster than the LCH AFFT over a Cantor special basis.

  • Takeaways & Limitations

    Partial Cantor special-basis structure reduces the addition and multiplication counts of both the von zur Gathen–Gerhard AFFT and the general-basis AFFT.

  • Takeaways & Limitations

    The von zur Gathen–Gerhard AFFT has limited advantage because its evaluation basis changes during the recursion.

Abstract

from arXiv · show

Motivated by Bailey's four-step FFT algorithm (1989), we develop additive FFT techniques for polynomial evaluation over affine subspaces of binary extension fields. Our key insight is that the Taylor expansion with respect to vanishing polynomials of subspaces provides a structural counterpart to Bailey's matrix formulation. It decomposes an additive FFT (AFFT) into independent sub-AFFTs associated with the columns and rows of a matrix. We first present a general-basis AFFT that applies to any ordered basis and any split of the dimension, providing a unified baseline for measuring the gains from specialization. We then specialize the framework to the Cantor special basis and obtain two AFFT algorithms. The first supports an arbitrary decomposition of the AFFT dimension and exploits the Cantor special basis structure to perform the Taylor expansion stage without finite field multiplications. The second uses a decomposition that preserves the binomial form of the relevant subspace polynomials. It requires exactly $\frac{1}{2}n\log_2 n$ multiplications, together with a closed-form addition count determined by the binary representation of $m$. Our implementation results show that this algorithm is faster than the LCH AFFT over a Cantor special basis in 37 of the 42 configurations tested across two hardware platforms. This performance advantage stems from its fully recursive structure, which provides memory locality by design and avoids separate basis-conversion and evaluation stages. Finally, in a separate analysis, we formalize the notion of partial Cantor special bases and identify parameter regimes in which both the von zur Gathen-Gerhard algorithm and our general-basis AFFT require fewer additions and multiplications than the first Gao-Mateer algorithm.

I. INTRODUCTION

The paper develops additive FFTs for polynomial evaluation on affine subspaces of binary extension fields, replacing multiplicative-root structure with additive subspace structure. Its Bailey-inspired matrix decomposition yields general-basis and Cantor-basis algorithms, with competitive operation counts and strong benchmark results.

  • Motivation: Additive FFTs evaluate polynomials on affine subspaces of binary extension fields, where classical DFT roots-of-unity structure is unavailable.For n = 2^m, the evaluation domain is θ + W_m, with W_m an m-dimensional subspace.
  • Core framework: Taylor expansion with respect to subspace vanishing polynomials provides the structural counterpart to Bailey’s four-step FFT matrix decomposition.The decomposition separates column and row sub-AFFTs within a unified framework.
  • General-basis algorithm: The general-basis AFFT supports arbitrary dimension splits, allowing column and row sub-AFFT sizes to match the computational architecture.Its split-invariant structure preserves the arithmetic cost while permitting different organizational choices.
  • Cantor special basis: Cantor special-basis specialization produces two algorithms: one supports arbitrary splits, while the other preserves binomial subspace-polynomial structure.The specialization targets lower-cost Taylor expansion and recursive evaluation.
  • Cantor special basis: 1/2 n log_2 n multiplications are required by the recursively split Cantor-basis algorithm, with additions determined in closed form by the binary representation of m.When m is a power of two, the addition count becomes n log_2 n + 1.
  • Evaluation: 37 of 42 tested configurations were faster than the LCH AFFT across two hardware platforms.The algorithm was faster at every tested dimension on one platform.
  • Partial bases: Partial Cantor special bases yield parameter regimes where the proposed general-basis AFFT and von zur Gathen–Gerhard algorithm outperform the first Gao–Mateer algorithm.The analysis also identifies substantially wider regimes for the proposed algorithm than for von zur Gathen–Gerhard.

II. PRELIMINARIES

The preliminaries define affine-subspace evaluation and additive Fourier transforms over binary extension fields, then introduce vanishing polynomials, Taylor expansion, and Cantor special bases.

  • An m-dimensional subspace of F2k has 2^m elements, and θ + W denotes its corresponding affine subspace.
  • The vanishing polynomial Z_Wm is a monic F2-linearized polynomial of degree 2^m with at most m + 1 nonzero terms.
  • Taylor expansion represents a polynomial in powers of a monic polynomial, with each remainder polynomial having degree below the divisor degree.
  • The additive DFT evaluates f at the ordered points of W_m, while AFFT denotes an efficient method for computing those evaluations.
  • For a Cantor special basis, subspace vanishing polynomials are iterated compositions of S(x) = x^2 + x and have coefficients in F2.
  • Division by these Cantor-basis vanishing polynomials requires zero F2k-multiplications.

III. A NEW ADDITIVE FFT OVER GENERAL BASIS

The paper develops a general-basis AFFT that decomposes evaluation over an affine subspace into independent column and row sub-AFFTs using Taylor expansion and projected evaluation points.

  • The algorithm applies to any ordered basis and any split m = m1 + m2, providing a general additive analogue of Bailey’s four-step FFT.
  • Taylor expansion with respect to Z_Wm1 arranges coefficients into a 2^m2 × 2^m1 matrix.
  • The restriction of Z_Wm1 to U is injective, so distinct cosets map to distinct projected evaluation points.
  • The row-column organization evaluates each row polynomial on its corresponding coset, and concatenating row results yields the full affine-space evaluation.
  • The column sub-AFFTs evaluate over Z_Wm1(θ) + Z_Wm1(U), while the row sub-AFFTs evaluate over cosets θ_k + W_m1.
  • Unlike Bailey’s classical algorithm, the general AFFT uses no separate twiddle-factor multiplication; Taylor expansion and projected points encode the stage interaction.

A. Detailed Cost Analysis

The general-basis algorithm’s cost is dominated by Taylor expansion, yielding split-independent operation counts and motivating Cantor-basis specialization to eliminate its multiplication overhead.

  • Algorithm 2 performs m1m2 2^(m−1) multiplications and the same number of additions during Taylor expansion.
  • Algorithm 1 evaluates degree-below-2^m polynomials with 1/4 n(log2 n)^2 + 3/4 n log2 n multiplications and the same additions.
  • The total operation count is invariant under the split m = m1 + m2.
  • When the domain is W_m rather than θ + W_m, Algorithm 1 saves exactly n − 1 multiplications and n − 1 additions.
  • The Taylor expansion dominates the general-basis cost with O(n(log2 n)^2) multiplications because vanishing-polynomial coefficients introduce field multiplications.
  • Choosing a Cantor special basis removes this Taylor-expansion multiplication overhead because its relevant vanishing polynomials have coefficients in F2.

IV. NEW ADDITIVE FFTS BASED ON CANTOR SPECIAL BASIS

Cantor special bases yield two AFFT specializations with multiplication-free Taylor expansion; one permits arbitrary splits, while the other preserves binomial vanishing polynomials for lower addition cost.

  • Algorithm 3: For Algorithm 3, each Taylor-division step requires 2wt(m1) − 1 additions, so addition cost depends on the Hamming weight of m1.
  • Algorithm 4: When m1 = 2^t, S_m1(x) = x^(2^m1) + x, so each Taylor-division step requires exactly one addition.
  • Both Cantor-basis algorithms require zero F2k-multiplications in the Taylor expansion stage.
  • Algorithm 3: Algorithm 3 supports an arbitrary split m = m1 + m2 and requires exactly 1/2 n log2 n multiplications.
  • Algorithm 3 matches the Cantor AFFT arithmetic cost when the recursive choices use m1 = m − 1 and m2 = 1.
  • Algorithm 4: Choosing m1 as the largest power of two strictly below m preserves the binomial form of S_m1 throughout the recursion.

A. Detailed Cost Analysis

Algorithm 4’s arithmetic cost is determined by recursive sub-AFFTs and a Taylor expansion whose structure depends on the binary representation of m. Over a Cantor special basis, it uses exactly 1/2 n log_2 n multiplications and has lower asymptotic addition complexity than Cantor’s AFFT.

  • Multiplication cost: 1/2 n log_2 n multiplications are required by Algorithm 4.The Taylor expansion is multiplication-free, so all multiplications arise from recursive sub-FFTs.
  • Addition cost: The Taylor-expansion addition cost has a closed form determined by the binary expansion of m.The analysis writes m as a sum of distinct powers of two and derives the cost from the successive splits.
  • Addition cost: When m is a power of two, Algorithm 4 requires n log_2 n + 1/4 n log_2 n log_2 log_2 n additions.This follows from combining recursive sub-FFT additions with Taylor-expansion additions.
  • Special evaluation domain: Evaluation over W_m saves exactly n − 1 multiplications and n − 1 additions compared with evaluation over a general affine subspace θ + W_m.The savings arise when θ = 0.
  • Comparisons: Algorithm 4 requires fewer additions than the second Gao–Mateer algorithm under the power-of-two comparison reported.The comparison uses the stated addition counts for both algorithms.
  • Implementation comparison: Over a Cantor special basis, Algorithm 4 and the LCH AFFT use the same multiplication count, but Algorithm 4 avoids basis conversion and its memory-access overhead.Algorithm 4 accepts standard monomial-basis coefficients directly, whereas LCH first converts to the novel polynomial basis.

V. GENERALIZED BUTTERFLY PHASE OF THE LCH ADDITIVE FFT

The generalized butterfly phase extends LCH evaluation to arbitrary decompositions of the AFFT dimension by using Taylor expansion and a column-row sub-AFFT decomposition. Its arithmetic cost is invariant under the split, but it still assumes prior conversion to the novel polynomial basis.

  • Generalized decomposition: The generalized butterfly phase supports any decomposition m = m_1 + m_2.It factors the novel polynomial basis and evaluates column polynomials before row polynomials on corresponding affine spaces.
  • Limitation: Algorithm 5 does not eliminate the polynomial basis conversion required by the LCH framework.The generalized phase assumes input coefficients have already been converted to the novel polynomial basis.
  • Arithmetic cost: Algorithm 5 uses n log_2 n additions and 1/2 n log_2 n multiplications, independently of the decomposition.The result follows from recursive column and row FFT counts.
  • Relation to LCH: Algorithm 5 generalizes the LCH butterfly phase while preserving its arithmetic cost for arbitrary decompositions.The LCH butterfly is recovered by choosing m_1 = m − 1 and m_2 = 1.

VI. ADDITIVE FFTS IN PARTIAL CANTOR SPECIAL BASIS

The paper studies AFFTs when only a prefix of the ordered basis has Cantor special structure. It shows that this partial structure can improve arithmetic costs even when it does not span the full evaluation subspace.

  • Comparison: When a full Cantor special basis is unavailable, the von zur Gathen–Gerhard AFFT and Algorithm 1 can outperform the first Gao–Mateer AFFT.Both algorithms exploit partial structure to reduce additions and multiplications, whereas Gao–Mateer cannot obtain those reductions.
  • Cost analysis: The analysis characterizes parameter regimes where partial Cantor structure changes the arithmetic costs of the von zur Gathen–Gerhard AFFT and Algorithm 1.The focus includes evaluation subspaces whose dimension exceeds the available Cantor special basis.
  • Setting: A partial Cantor special basis consists of a Cantor-recursive prefix followed by generic basis vectors.The available special dimension may be smaller than the evaluation-subspace dimension.

A. Comparing Gao–Mateer and von zur Gathen–Gerhard AFFTs

The comparison derives exact arithmetic costs for the von zur Gathen–Gerhard AFFT and identifies when partial Cantor structure makes it cheaper than the first Gao–Mateer AFFT. The reported cases show reductions in both multiplications and additions.

  • Baseline cost: The von zur Gathen–Gerhard AFFT has total cost 1/4 n(log_2 n)^2 + 3/4 n log_2 n for both additions and multiplications.This count comes from summing the costs across recursive iterations.
  • Multiplication comparison: If the available Cantor special dimension is ℓ, the von zur Gathen–Gerhard AFFT uses fewer multiplications than first Gao–Mateer exactly when ℓ ≥ m − 2.The condition applies to an m-dimensional evaluation subspace with a maximum available Cantor-special prefix of dimension ℓ.
  • Multiplication comparison: The von zur Gathen–Gerhard AFFT requires strictly fewer multiplications than first Gao–Mateer whenever ℓ ≥ m − 2.The comparison is stated under the paper’s assumed Gao–Mateer multiplication cost.
  • Reported cases: The von zur Gathen–Gerhard AFFT requires fewer additions and multiplications than first Gao–Mateer in every listed Table II case.For F_2^10 with ℓ = 2 and m = 4, multiplications decrease from 81 to 72 and additions from 112 to 104.
  • Reported cases: For F_2^48 with ℓ = 16 and m = 18, multiplications decrease from 6,815,745 to 4,849,664 and additions from 24,772,608 to 15,597,568.The example illustrates larger savings at larger parameters.
  • Conclusion: Partial Cantor special structure can reduce both arithmetic costs without spanning the entire evaluation subspace.This is the paper’s stated conclusion from the comparison.

B. Comparing Gao–Mateer and Algorithm 1

Under a partial Cantor special basis, Algorithm 1 has explicit addition and multiplication costs and can outperform the first Gao–Mateer AFFT in admissible parameter ranges.

  • Cost analysis: Algorithm 1 evaluates degree-less-than-2^m polynomials over an m-dimensional affine subspace using a split m = m1 + m2.The first m1 basis elements are assumed to form a Cantor special basis.
  • Cost analysis: Algorithm 1 requires the stated closed-form number of finite field multiplications, 2 + 3m2 + 2m1.The count applies to evaluation over the specified affine subspace under the partial-basis assumption.
  • Cost analysis: The Taylor expansion on the Cantor-special side requires no finite field multiplications because its vanishing polynomial has binary coefficients.This removes the corresponding multiplication term from the expansion cost.
  • Comparison with Gao–Mateer: For m1 ≥ 2, Algorithm 1 requires strictly fewer additions than Gao–Mateer for every admissible m2, so multiplication is the binding constraint for joint dominance.The multiplication condition is m2^2 − 3m2 + 4 ≤ 4m1.

SUFFICIENT CONDITION m2

The partial Cantor-basis condition yields concrete dimension ranges where Algorithm 1 reduces arithmetic cost, while the Dyadic AFFT’s recursive organization improves locality and benchmark performance against LCH.

  • Partial-basis comparison: The admissible range generally expands as the available Cantor special-basis dimension m1 increases.This range concerns dimensions where Algorithm 1 beats first Gao–Mateer in both additions and multiplications.
  • Partial-basis comparison: Over F2^48 with m1 = 16, Algorithm 1 outperforms first Gao–Mateer for 17 ≤ m ≤ 25.The partial basis need not span the full evaluation subspace for a nontrivial advantage range.
  • Implementation: Algorithm 4 uses a fully recursive, in-place organization that provides cache locality and reduces memory-access overhead.Descendant subproblems can be processed largely from cache once a working set fits.
  • Benchmarking: Algorithm 4 is faster than LCH in 37 of 42 measured cases, including all 20 Platform A cases and 17 of 22 Platform B cases.Relative performance still depends on transform dimension and target platform.

VIII. CONCLUDING REMARKS

The paper develops a matrix-decomposition framework for AFFTs, specializes it to Cantor bases, and reports fixed multiplication cost, benchmark gains, and partial-basis advantages.

  • Framework: The framework decomposes AFFT evaluation into independent column and row sub-AFFTs and applies to any ordered basis and dimension split.The split can be selected for implementation requirements without changing arithmetic complexity.
  • Cantor specialization: Cantor specialization makes the Taylor expansion multiplication-free, while the recursive choice of m1 preserves binomial vanishing polynomials.The second algorithm chooses m1 as the largest power of two smaller than m.
  • Complexity: The generalized butterfly phase has split-invariant cost of n log2 n additions and 1/2 n log2 n multiplications.This result applies to arbitrary decompositions m = m1 + m2.
  • Partial bases: A partial Cantor special basis reduces arithmetic costs for von zur Gathen–Gerhard and Algorithm 1, whereas first Gao–Mateer cannot generally exploit the same structure.Algorithm 1 outperforms first Gao–Mateer over F2^48 with m1 = 16 for 17 ≤ m ≤ 25.
  • Future work: Extending the framework to truncated AFFTs, Frobenius variants, and lower arithmetic complexity remains future work.The paper also identifies the need for lower bounds over a Cantor special basis.

APPENDIX A

The appendix reviews von zur Gathen–Gerhard and Cantor AFFTs, contrasting general ordered bases with the simpler vanishing polynomials induced by Cantor special bases.

  • Comparison: The von zur Gathen–Gerhard generalization supports arbitrary ordered bases but incurs additional finite field operations compared with Cantor’s specialization.The appendix’s recursion computes the two subspace remainders at each step.
  • Von zur Gathen–Gerhard AFFT: The von zur Gathen–Gerhard AFFT recursively reduces a polynomial to remainders on two affine subspaces and continues until constants remain.The method applies to any ordered basis of the binary extension field.
  • Cantor AFFT: Cantor’s AFFT specializes this recursion to affine subspaces generated by a Cantor special basis.Its subspace vanishing polynomials have a particularly simple form.
  • Cantor AFFT: For a Cantor special basis, the vanishing polynomial of Wi equals the i-fold composition Si(x) of the mapping S.These polynomials are linearized with coefficients in F2.
  • Cantor AFFT: Polynomial division by a Cantor vanishing polynomial requires zero F2k-multiplications.This is the arithmetic simplification distinguishing the Cantor-special setting.
Loading 2608.20855v1…