Integer multiplication in time O(n n)
From MaRDI portal
Publication:2662018
DOI10.4007/ANNALS.2021.193.2.4zbMATH Open1480.11162OpenAlexW2941010932WikidataQ114022320 ScholiaQ114022320MaRDI QIDQ2662018FDOQ2662018
Authors: David I. Harvey, Joris van der Hoeven 
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
Recommendations
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)
Cites Work
- Faster integer multiplication
- An Algorithm for the Machine Calculation of Complex Fourier Series
- Title not available (Why is that?)
- Title not available (Why is that?)
- Fast multiplication of large numbers
- Modern computer arithmetic
- Fast Fourier Transforms for Nonequispaced Data
- Title not available (Why is that?)
- Approximate formulas for some functions of prime numbers
- Modern computer algebra
- Title not available (Why is that?)
- Gauss and the history of the fast Fourier transform
- Fast integer multiplication using modular arithmetic
- Even faster integer multiplication
- On the least prime in an arithmetic progression and estimates for the zeros of Dirichlet L-functions
- Faster integer multiplication
- Discrete Weighted Transforms and Large-Integer Arithmetic
- Linear Recurrences with Polynomial Coefficients and Application to Integer Factorization and Cartier–Manin Operator
- The Fast Fourier Transform in a Finite Field
- A GMP-based implementation of Schönhage-Strassen's large integer multiplication algorithm
- Title not available (Why is that?)
- Faster relaxed multiplication
- New algorithms for digital convolution
- Title not available (Why is that?)
- On the Minimum Computation Time of Functions
- Faster Polynomial Multiplication over Finite Fields
- Faster integer multiplication using plain vanilla FFT primes
- Faster polynomial multiplication over finite fields using cyclotomic coefficient rings
- Fast polynomial transform algorithms for digital convolution
- Fast computation of discrete Fourier transforms using polynomial transforms
- On the complexity of integer matrix multiplication
- Faster integer multiplication using short lattice vectors
- Computation of Convolutions and Discrete Fourier Transforms by Polynomial Transforms
- Fast integer multiplication using generalized Fermat primes
- Fast Chinese Remaindering in Practice
Cited In (58)
- Fast interpolation of multivariate polynomials with sparse exponents
- Computing characteristic polynomials of p-curvatures in average polynomial time
- A unified FFT-based approach to maximum assignment problems related to transitive finite group actions
- Fast multiplication and its applications
- Polynomial modular product verification and its implications
- Title not available (Why is that?)
- Fast exact algorithms using Hadamard product of polynomials
- Quantum generalized least squares method in system identification
- Faster integer multiplication
- Polynomial Multiplication over Finite Fields in Time \( O(n \log n \)
- Complexity analysis of algorithm for multiplication of superlarge numbers based on Walsh coefficients
- Computational Number Theory, Past, Present, and Future
- The Karatsuba integer middle product
- Tensors in computations
- Discrete Weighted Transforms and Large-Integer Arithmetic
- An exponent one-fifth algorithm for deterministic integer factorisation
- Time-space tradeoffs for matrix multiplication and the discrete Fourier transform on any general sequential random-access computer
- Counting points on smooth plane quartics
- A hybrid classical-quantum algorithm for solution of nonlinear ordinary differential equations
- Fast norm computation in smooth-degree abelian number fields
- A generalized MSST algorithm for counting points of elliptic curves over \(\mathbb{F}_{p^n}\)
- Straight-line drawings of 1-planar graphs
- Quantum attribute-based encryption: a comprehensive study
- Representation of numbers with negative digits and multiplication of small integers
- Large integer multiplication on hypercubes
- On oracle factoring of integers
- Efficient and validated numerical evaluation of abelian integrals
- Beating binary powering for polynomial matrices
- Efficient Generic Quotients Using Exact Arithmetic
- A fast algorithm for computing the number of magic series
- New ways to garble arithmetic circuits
- Algorithmic counting of nonequivalent compact Huffman codes
- A log-log speedup for exponent one-fifth deterministic integer factorisation
- Computing 𝐿-polynomials of Picard curves from Cartier–Manin matrices
- Random generation of subgroups of the modular group with a fixed isomorphism type
- Efficient quantum multi-authority attribute-based encryption and generalizations
- Fast multiplication of large numbers
- The quantum detection of projectors in finite-dimensional algebras and holography
- Root repulsion and faster solving for very sparse polynomials over \(p\)-adic fields
- Faster truncated integer multiplication
- Efficient arithmetic in garbled circuits
- Faster integer multiplication
- Summing \(\mu(n)\): a faster elementary algorithm
- CryptAttackTester: high-assurance attack analysis
- Computing modular polynomials by deformation
- Scalable multiparty computation from non-linear secret sharing
- Space-efficient and noise-robust quantum factoring
- A new fast root-finder for black box polynomials
- A GMP-based implementation of Schönhage-Strassen's large integer multiplication algorithm
- On iterated integer product
- Addition machines, automatic functions and open problems of Floyd and Knuth
- Characterization of the imbalance problem on complete bipartite graphs
- Title not available (Why is that?)
- On the structure of random graphs with constant \(r\)-balls
- Space- and time-efficient polynomial multiplication
- Efficient Multiplication of Somewhat Small Integers Using Number-Theoretic Transforms
- Homomorphic encryption: a mathematical survey
- The numerical solution of fractional integral equations via orthogonal polynomials in fractional powers
This page was built for publication: Integer multiplication in time \(O(n\log n)\)
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2662018)
