Abstract
Additive Fourier Transform is sdudied. A fast multiplication algorithm for polynomials over the binary field is given. The bit complexity of the algorithm is $O(n(log n)(\log\log n)^2)$.
Multiplication of polynomials over the binary field
Related papers
Ranked by semantic similarity β how closely each paper's abstract matches this one (100% = near-identical topic).
- (Approximate) Matrix Multiplication via Convolutions (2025)57% match
- Solving Polynomial Equations Over Finite Fields (2024)56% match
- Fast computation of permanents over $\mathbbF_3$ via $\mathbbF_2$ arithmetic (2024)53% match
- Dyadically resolving trinomials for fast modular arithmetic (2025)53% match
- Did Fourier Really Meet MΓΆbius? Fast Subset Convolution via FFT (2024)52% match
- A more accurate rational non-commutative algorithm for multiplying 4x4 matrices using 48 multiplications (2026)52% match
- Pseudo-Deterministic Construction of Irreducible Polynomials over Finite Fields (2024)52% match
- Finding a solution to the ErdΕs-Ginzburg-Ziv theorem in $O(nΕogΕogΕog n)$ time (2025)51% match