Even faster integer multiplication
From MaRDI portal
Publication:306687
DOI10.1016/j.jco.2016.03.001zbMath1350.68145arXiv1407.3360OpenAlexW1754110195WikidataQ62597856 ScholiaQ62597856MaRDI QIDQ306687
David I. Harvey, Joris van der Hoeven, Grégoire Lecerf
Publication date: 1 September 2016
Published in: Journal of Complexity (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1407.3360
Analysis of algorithms and problem complexity (68Q25) Number-theoretic algorithms; complexity (11Y16) Numerical methods for discrete and fast Fourier transforms (65T50)
Related Items
Tighter Fourier Transform Lower Bounds ⋮ Deterministic root finding over finite fields using Graeffe transforms ⋮ On the complexity of integer matrix multiplication ⋮ A babystep-giantstep method for faster deterministic integer factorization ⋮ Bounded-degree factors of lacunary multivariate polynomials ⋮ Polynomial Multiplication over Finite Fields in Time \( O(n \log n \) ⋮ Dirichlet’s proof of the three-square theorem: An algorithmic perspective ⋮ 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 ⋮ Faster integer multiplication using short lattice vectors ⋮ Faster truncated integer multiplication ⋮ A fresh look at research strategies in computational cognitive science: the case of enculturated mathematical problem solving ⋮ Computing -series of geometrically hyperelliptic curves of genus three ⋮ Fast integer multiplication using generalized Fermat primes ⋮ Derivation and Analysis of Fast Bilinear Algorithms for Convolution ⋮ The Borwein Brothers, Pi and the AGM ⋮ Backtracking-assisted multiplication ⋮ Linear-Time Algorithm for Quantum 2SAT ⋮ Improved method for finding optimal formulas for bilinear maps in a finite field ⋮ Faster polynomial multiplication over finite fields using cyclotomic coefficient rings ⋮ Faster integer multiplication using plain vanilla FFT primes ⋮ A framework for deterministic primality proving using elliptic curves with complex multiplication ⋮ Fast multivariate multi-point evaluation revisited ⋮ Computing the depth distribution of a set of boxes ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On the Complexity of Bounded Context Switching. ⋮ Linear differential equations as a data structure ⋮ Unnamed Item ⋮ Accelerated tower arithmetic ⋮ A Reduction of Integer Factorization to Modular Tetration
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fast Fourier transform: algorithms and applications
- Gauss and the history of the fast Fourier transform
- Recent developments in primality testing
- On finding primitive roots in finite fields
- PRIMES is in P
- Multiplikation großer Zahlen
- On the computational power of pushdown automata
- Fast multiplication of large numbers
- Fast Integer Multiplication Using Modular Arithmetic
- Modern Computer Algebra
- Fast Polynomial Multiplication over F 2 60
- On the least prime in an arithmetic progression and estimates for the zeros of Dirichlet L-functions
- Faster Integer Multiplication
- Parameter Determination for Complex Number-Theoretic Transforms Using Cyclotomic Polynomials
- Storage Modification Machines
- The use of finite fields to compute convolutions
- Fast Multiple-Precision Evaluation of Elementary Functions
- Almost-primes in arithmetic progressions and short intervals
- Discrete Weighted Transforms and Large-Integer Arithmetic
- Zero-Free Regions for Dirichlet L-Functions, and the Least Prime in an Arithmetic Progression
- Divisors of Mersenne Numbers
- Handbook of Elliptic and Hyperelliptic Curve Cryptography
- An Algorithm for the Machine Calculation of Complex Fourier Series
- 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
- Exponential error bounds for discrete memoryless channels with sequential decision feedback
- The Fast Fourier Transform in a Finite Field
- \(p\)-adic numbers. An introduction
