Integer multiplication in time \(O(n\log n)\)
From MaRDI portal
Publication:2662018
DOI10.4007/annals.2021.193.2.4zbMath1480.11162OpenAlexW2941010932WikidataQ114022320 ScholiaQ114022320MaRDI QIDQ2662018
Joris van der Hoeven, David I. Harvey
Publication date: 8 April 2021
Published in: Annals of Mathematics. Second Series (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.4007/annals.2021.193.2.4
Symbolic computation and algebraic computation (68W30) Number-theoretic algorithms; complexity (11Y16) Numerical methods for discrete and fast Fourier transforms (65T50) Mathematical problems of computer architecture (68M07)
Related Items (30)
A unified FFT-based approach to maximum assignment problems related to transitive finite group actions ⋮ Tensors in computations ⋮ Fast exact algorithms using Hadamard product of polynomials ⋮ Polynomial Multiplication over Finite Fields in Time \( O(n \log n \) ⋮ A fast algorithm for computing the number of magic series ⋮ A log-log speedup for exponent one-fifth deterministic integer factorisation ⋮ Root repulsion and faster solving for very sparse polynomials over \(p\)-adic fields ⋮ Straight-line drawings of 1-planar graphs ⋮ Quantum attribute-based encryption: a comprehensive study ⋮ Beating binary powering for polynomial matrices ⋮ New ways to garble arithmetic circuits ⋮ Summing \(\mu(n)\): a faster elementary algorithm ⋮ Efficient Generic Quotients Using Exact Arithmetic ⋮ Computational Number Theory, Past, Present, and Future ⋮ Addition machines, automatic functions and open problems of Floyd and Knuth ⋮ Characterization of the imbalance problem on complete bipartite graphs ⋮ Homomorphic encryption: a mathematical survey ⋮ Fast norm computation in smooth-degree abelian number fields ⋮ The quantum detection of projectors in finite-dimensional algebras and holography ⋮ Faster truncated integer multiplication ⋮ The numerical solution of fractional integral equations via orthogonal polynomials in fractional powers ⋮ On the structure of random graphs with constant \(r\)-balls ⋮ On oracle factoring of integers ⋮ A hybrid classical-quantum algorithm for solution of nonlinear ordinary differential equations ⋮ Unnamed Item ⋮ Unnamed Item ⋮ An exponent one-fifth algorithm for deterministic integer factorisation ⋮ Polynomial modular product verification and its implications ⋮ Counting points on smooth plane quartics ⋮ Computing 𝐿-polynomials of Picard curves from Cartier–Manin matrices
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Even faster integer multiplication
- Gauss and the history of the fast Fourier transform
- On the complexity of integer matrix multiplication
- Faster polynomial multiplication over finite fields using cyclotomic coefficient rings
- Fast multiplication of large numbers
- Approximate formulas for some functions of prime numbers
- Fast Integer Multiplication Using Modular Arithmetic
- Modern Computer Algebra
- Fast polynomial transform algorithms for digital convolution
- New algorithms for digital convolution
- Modern Computer Arithmetic
- On the least prime in an arithmetic progression and estimates for the zeros of Dirichlet L-functions
- Faster Polynomial Multiplication over Finite Fields
- Faster relaxed multiplication
- Faster Integer Multiplication
- Fast computation of discrete Fourier transforms using polynomial transforms
- Computation of Convolutions and Discrete Fourier Transforms by Polynomial Transforms
- Fast Fourier Transforms for Nonequispaced Data
- Discrete Weighted Transforms and Large-Integer Arithmetic
- Fast integer multiplication using generalized Fermat primes
- Fast Chinese Remaindering in Practice
- Faster integer multiplication using plain vanilla FFT primes
- An Algorithm for the Machine Calculation of Complex Fourier Series
- Linear Recurrences with Polynomial Coefficients and Application to Integer Factorization and Cartier–Manin Operator
- On the Minimum Computation Time of Functions
- The Fast Fourier Transform in a Finite Field
- Faster integer multiplication using short lattice vectors
This page was built for publication: Integer multiplication in time \(O(n\log n)\)
