Even faster integer multiplication
From MaRDI portal
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 3888913 (Why is no real title available?)
- scientific article; zbMATH DE number 3132714 (Why is no real title available?)
- scientific article; zbMATH DE number 3137333 (Why is no real title available?)
- scientific article; zbMATH DE number 641702 (Why is no real title available?)
- scientific article; zbMATH DE number 976329 (Why is no real title available?)
- scientific article; zbMATH DE number 1042857 (Why is no real title available?)
- scientific article; zbMATH DE number 1052006 (Why is no real title available?)
- scientific article; zbMATH DE number 2206373 (Why is no real title available?)
- scientific article; zbMATH DE number 3281219 (Why is no real title available?)
- scientific article; zbMATH DE number 3290249 (Why is no real title available?)
- scientific article; zbMATH DE number 3303655 (Why is no real title available?)
- scientific article; zbMATH DE number 3322464 (Why is no real title available?)
- scientific article; zbMATH DE number 3105562 (Why is no real title available?)
- scientific article; zbMATH DE number 3105563 (Why is no real title available?)
- Almost-primes in arithmetic progressions and short intervals
- An Algorithm for the Machine Calculation of Complex Fourier Series
- Discrete Weighted Transforms and Large-Integer Arithmetic
- Divisors of Mersenne Numbers
- Exponential error bounds for discrete memoryless channels with sequential decision feedback
- Fast Fourier transform: algorithms and applications
- Fast Multiple-Precision Evaluation of Elementary Functions
- Fast integer multiplication using modular arithmetic
- Fast multiplication of large numbers
- Fast polynomial multiplication over \(\mathbb{F}_{2^{60}}\)
- Faster integer multiplication
- Faster integer multiplication
- Gauss and the history of the fast Fourier transform
- Handbook of Elliptic and Hyperelliptic Curve Cryptography
- How fast can we multiply large integers on an actual computer?
- Introduction to analyzable functions and constructive proof of the Dulac conjecture
- Linear Recurrences with Polynomial Coefficients and Application to Integer Factorization and Cartier–Manin Operator
- Modern computer algebra
- Multiplikation großer Zahlen
- On finding primitive roots in finite fields
- On the computational power of pushdown automata
- On the least prime in an arithmetic progression and estimates for the zeros of Dirichlet L-functions
- PRIMES is in P
- Parameter Determination for Complex Number-Theoretic Transforms Using Cyclotomic Polynomials
- Recent developments in primality testing
- Storage Modification Machines
- The Fast Fourier Transform in a Finite Field
- The use of finite fields to compute convolutions
- Zero-Free Regions for Dirichlet L-Functions, and the Least Prime in an Arithmetic Progression
- \(p\)-adic numbers. An introduction
Cited in
(45)- Dirichlet’s proof of the three-square theorem: An algorithmic perspective
- Derivation and analysis of fast bilinear algorithms for convolution
- The Borwein brothers, pi and the AGM
- Faster integer multiplication
- Scalable multiparty computation from non-linear secret sharing
- Multiplication
- Representation of numbers with negative digits and multiplication of small integers
- Schönhage-Strassen algorithm with MapReduce for multiplying terabit integers
- On Faster Integer Calculations Using Non-arithmetic Primitives
- A reduction of integer factorization to modular tetration
- Faster polynomial multiplication over finite fields using cyclotomic coefficient rings
- Faster integer multiplication using plain vanilla FFT primes
- The Karatsuba integer middle product
- Faster truncated integer multiplication
- Integer multiplication in time \(O(n\log n)\)
- Fast integer multiplication using modular arithmetic
- Improved method for finding optimal formulas for bilinear maps in a finite field
- scientific article; zbMATH DE number 7250154 (Why is no real title available?)
- Accelerated tower arithmetic
- On the Complexity of Bounded Context Switching.
- A framework for deterministic primality proving using elliptic curves with complex multiplication
- Fast integer multiplication using generalized Fermat primes
- Backtracking-assisted multiplication
- A babystep-giantstep method for faster deterministic integer factorization
- Faster integer multiplication
- Tighter Fourier transform lower bounds
- Faster integer multiplication using short lattice vectors
- Fast on-line integer multiplication
- Deterministic root finding over finite fields using Graeffe transforms
- scientific article; zbMATH DE number 4104356 (Why is no real title available?)
- Solving projected model counting by utilizing treewidth and its limits
- Fast multivariate multi-point evaluation revisited
- More on squaring and multiplying large integers
- Linear-Time Algorithm for Quantum 2SAT
- Linear differential equations as a data structure
- On the hardness of approximate and exact (bichromatic) maximum inner product
- Fast on-line integer multiplication
- Fast computation of the \(N\)-th term of a \(q\)-holonomic sequence and applications
- Polynomial multiplication over finite fields in time \(O(n\log n)\)
- Computing \(L\)-series of geometrically hyperelliptic curves of genus three
- On the complexity of integer matrix multiplication
- How fast can we multiply large integers on an actual computer?
- Bounded-degree factors of lacunary multivariate polynomials
- A fresh look at research strategies in computational cognitive science: the case of enculturated mathematical problem solving
- Computing the depth distribution of a set of boxes
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)
