Faster integer multiplication using plain vanilla FFT primes

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

Mathematics Subject Classification ID

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

• gmp
• NTL

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