Faster integer multiplication using plain vanilla FFT primes
From MaRDI portal
Publication:4683179
DOI10.1090/mcom/3328zbMath1394.68182arXiv1611.07144OpenAlexW2550792289MaRDI QIDQ4683179
David I. Harvey, Joris van der Hoeven
Publication date: 20 September 2018
Published in: Mathematics of Computation (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1611.07144
Analysis of algorithms and problem complexity (68Q25) Number-theoretic algorithms; complexity (11Y16)
Related Items (12)
Lattice-based zero-knowledge arguments for additive and multiplicative relations ⋮ Polynomial Multiplication over Finite Fields in Time \( O(n \log n \) ⋮ On the complexity exponent of polynomial system solving ⋮ Integer multiplication in time \(O(n\log n)\) ⋮ Fast algorithms for solving equations of degree \(\le 4\) in some finite fields ⋮ On a fast algorithm for computing the Fourier transform ⋮ Faster integer multiplication using short lattice vectors ⋮ Fast multivariate multi-point evaluation revisited ⋮ A time-space tradeoff for Lehman’s deterministic integer factorization method ⋮ A new characterization of \(\mathcal{V} \)-posets ⋮ Unnamed Item ⋮ Accelerated tower arithmetic
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Even faster integer multiplication
- Short character sums for composite moduli
- On fast multiplication of polynomials over arbitrary algebras
- On finding primitive roots in finite fields
- PRIMES is in P
- Faster arithmetic for number-theoretic transforms
- Fast multiplication of large numbers
- 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 Polynomial Multiplication over Finite Fields
- SIEGEL ZEROS AND THE LEAST PRIME IN AN ARITHMETIC PROGRESSION
- Faster Integer Multiplication
- On the Least Prime in Certain Arithmetic Progressions
- Almost-primes in arithmetic progressions and short intervals
- Greatest of the Least Primes in Arithmetic Progressions Having a Given Modulus
- Discrete Weighted Transforms and Large-Integer Arithmetic
- A lower bound for the least prime in an Arithmetic progression
- Fast integer multiplication using generalized Fermat primes
- Implementing Fast Carryless Multiplication
- Zero-Free Regions for Dirichlet L-Functions, and the Least Prime in an Arithmetic Progression
- An Algorithm for the Machine Calculation of Complex Fourier Series
- The Fast Fourier Transform in a Finite Field
This page was built for publication: Faster integer multiplication using plain vanilla FFT primes
