Even faster integer multiplication
From MaRDI portal
Publication:306687
DOI10.1016/J.JCO.2016.03.001zbMATH Open1350.68145arXiv1407.3360OpenAlexW1754110195WikidataQ62597856 ScholiaQ62597856MaRDI QIDQ306687FDOQ306687
Authors: Joris van der Hoeven, Grégoire Lecerf, David Harvey 
Publication date: 1 September 2016
Published in: Journal of Complexity (Search for Journal in Brave)
Abstract: We give a new proof of F"urer's bound for the cost of multiplying n-bit integers in the bit complexity model. Unlike F"urer, our method does not require constructing special coefficient rings with "fast" roots of unity. Moreover, we prove the more explicit bound O(n log n K^(log^* n))$ with K = 8. We show that an optimised variant of F"urer's algorithm achieves only K = 16, suggesting that the new algorithm is faster than F"urer's by a factor of 2^(log^* n). Assuming standard conjectures about the distribution of Mersenne primes, we give yet another algorithm that achieves K = 4.
Full work available at URL: https://arxiv.org/abs/1407.3360
Recommendations
Analysis of algorithms and problem complexity (68Q25) Number-theoretic algorithms; complexity (11Y16) Numerical methods for discrete and fast Fourier transforms (65T50)
Cites Work
- Title not available (Why is that?)
- 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
- Almost-primes in arithmetic progressions and short intervals
- Title not available (Why is that?)
- PRIMES is in P
- On the computational power of pushdown automata
- Title not available (Why is that?)
- Title not available (Why is that?)
- Handbook of Elliptic and Hyperelliptic Curve Cryptography
- Modern computer algebra
- Storage Modification Machines
- Title not available (Why is that?)
- Gauss and the history of the fast Fourier transform
- Recent developments in primality testing
- On finding primitive roots in finite fields
- Multiplikation großer Zahlen
- Fast integer multiplication using modular arithmetic
- Introduction to analyzable functions and constructive proof of the Dulac conjecture
- Fast polynomial multiplication over \(\mathbb{F}_{2^{60}}\)
- On the least prime in an arithmetic progression and estimates for the zeros of Dirichlet L-functions
- Title not available (Why is that?)
- Title not available (Why is that?)
- Faster integer multiplication
- Parameter Determination for Complex Number-Theoretic Transforms Using Cyclotomic Polynomials
- The use of finite fields to compute convolutions
- Fast Multiple-Precision Evaluation of Elementary Functions
- Discrete Weighted Transforms and Large-Integer Arithmetic
- Title not available (Why is that?)
- Title not available (Why is that?)
- Zero-Free Regions for Dirichlet L-Functions, and the Least Prime in an Arithmetic Progression
- Divisors of Mersenne Numbers
- How fast can we multiply large integers on an actual computer?
- Linear Recurrences with Polynomial Coefficients and Application to Integer Factorization and Cartier–Manin Operator
- Title not available (Why is that?)
- Exponential error bounds for discrete memoryless channels with sequential decision feedback
- The Fast Fourier Transform in a Finite Field
- Title not available (Why is that?)
- Title not available (Why is that?)
- \(p\)-adic numbers. An introduction
- Fast Fourier transform: algorithms and applications
Cited In (45)
- Tighter Fourier transform lower bounds
- Linear-Time Algorithm for Quantum 2SAT
- Dirichlet’s proof of the three-square theorem: An algorithmic perspective
- Accelerated tower arithmetic
- Faster integer multiplication
- On the hardness of approximate and exact (bichromatic) maximum inner product
- The Karatsuba integer middle product
- Schönhage-Strassen algorithm with MapReduce for multiplying terabit integers
- Improved method for finding optimal formulas for bilinear maps in a finite field
- On the complexity of integer matrix multiplication
- On Faster Integer Calculations Using Non-arithmetic Primitives
- Faster integer multiplication using short lattice vectors
- Solving projected model counting by utilizing treewidth and its limits
- Fast on-line integer multiplication
- Representation of numbers with negative digits and multiplication of small integers
- Fast on-line integer multiplication
- Deterministic root finding over finite fields using Graeffe transforms
- Computing \(L\)-series of geometrically hyperelliptic curves of genus three
- Faster polynomial multiplication over finite fields using cyclotomic coefficient rings
- Integer multiplication in time \(O(n\log n)\)
- Derivation and analysis of fast bilinear algorithms for convolution
- Fast computation of the \(N\)-th term of a \(q\)-holonomic sequence and applications
- Faster integer multiplication using plain vanilla FFT primes
- Polynomial multiplication over finite fields in time \(O(n\log n)\)
- Computing the depth distribution of a set of boxes
- Faster truncated integer multiplication
- More on squaring and multiplying large integers
- Title not available (Why is that?)
- A babystep-giantstep method for faster deterministic integer factorization
- Faster integer multiplication
- Linear differential equations as a data structure
- How fast can we multiply large integers on an actual computer?
- Multiplication
- Scalable multiparty computation from non-linear secret sharing
- Title not available (Why is that?)
- Fast multivariate multi-point evaluation revisited
- A reduction of integer factorization to modular tetration
- A fresh look at research strategies in computational cognitive science: the case of enculturated mathematical problem solving
- Fast integer multiplication using generalized Fermat primes
- A framework for deterministic primality proving using elliptic curves with complex multiplication
- Bounded-degree factors of lacunary multivariate polynomials
- On the Complexity of Bounded Context Switching.
- The Borwein brothers, pi and the AGM
- Fast integer multiplication using modular arithmetic
- Backtracking-assisted multiplication
Uses Software
This page was built for publication: Even faster integer multiplication
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q306687)
