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
- \(p\)-adic numbers. An introduction
- 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 integer multiplication using modular arithmetic
- Fast Multiple-Precision Evaluation of Elementary Functions
- 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?
- 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?)
- 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
- Parameter Determination for Complex Number-Theoretic Transforms Using Cyclotomic Polynomials
- PRIMES is in P
- 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
Cited in
(46)- On the complexity of integer matrix multiplication
- Fast on-line integer multiplication
- Computing the depth distribution of a set of boxes
- Improved method for finding optimal formulas for bilinear maps in a finite field
- Faster polynomial multiplication over finite fields using cyclotomic coefficient rings
- Fast multivariate multi-point evaluation revisited
- Linear differential equations as a data structure
- Accelerated tower arithmetic
- Bounded-degree factors of lacunary multivariate polynomials
- Integer multiplication in time \(O(n\log n)\)
- Fast computation of the \(N\)-th term of a \(q\)-holonomic sequence and applications
- Solving projected model counting by utilizing treewidth and its limits
- A fresh look at research strategies in computational cognitive science: the case of enculturated mathematical problem solving
- Representation of numbers with negative digits and multiplication of small integers
- A framework for deterministic primality proving using elliptic curves with complex multiplication
- Schönhage-Strassen algorithm with MapReduce for multiplying terabit integers
- Fast integer multiplication using modular arithmetic
- Computing L-series of geometrically hyperelliptic curves of genus three
- Deterministic root finding over finite fields using Graeffe transforms
- A babystep-giantstep method for faster deterministic integer factorization
- The Borwein brothers, pi and the AGM
- Tighter Fourier transform lower bounds
- On Faster Integer Calculations Using Non-arithmetic Primitives
- Faster integer multiplication
- Faster integer multiplication
- scientific article; zbMATH DE number 4104356 (Why is no real title available?)
- The Karatsuba integer middle product
- More on squaring and multiplying large integers
- Dirichlet’s proof of the three-square theorem: An algorithmic perspective
- Linear-Time Algorithm for Quantum 2SAT
- Fast integer multiplication using generalized Fermat primes
- Faster integer multiplication using plain vanilla FFT primes
- Polynomial multiplication over finite fields in time O(n n)
- On the Complexity of Bounded Context Switching.
- scientific article; zbMATH DE number 7250154 (Why is no real title available?)
- Derivation and analysis of fast bilinear algorithms for convolution
- On the hardness of approximate and exact (bichromatic) maximum inner product
- Multiplication
- How fast can we multiply large integers on an actual computer?
- A reduction of integer factorization to modular tetration
- Fast on-line integer multiplication
- Faster integer multiplication using short lattice vectors
- Faster truncated integer multiplication
- Scalable multiparty computation from non-linear secret sharing
- Backtracking-assisted multiplication
- Fast modular composition using spiroids
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)
