Faster integer multiplication using short lattice vectors

DOI10.2140/obs.2019.2.293arXiv1802.07932OpenAlexW3102645309MaRDI QIDQ6165872

Joris van der Hoeven, David Harvey

Publication date: 2 August 2023

Published in: The Open Book Series (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1802.07932

zbMATH Keywords

fast Fourier transformefficient algorithminteger multiplication

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Lattices and convex bodies in (n) dimensions (aspects of discrete geometry) (52C07) Lattices and convex bodies (number-theoretic aspects) (11H06)

Related Items (7)

Polynomial Multiplication over Finite Fields in Time \( O(n \log n \) ⋮ Integer multiplication in time \(O(n\log n)\) ⋮ Faster truncated integer multiplication ⋮ Faster polynomial multiplication over finite fields using cyclotomic coefficient rings ⋮ Fast multivariate multi-point evaluation revisited ⋮ Unnamed Item ⋮ Accelerated tower arithmetic

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Even faster integer multiplication
• Factoring polynomials with rational coefficients
• Fast multiplication of large numbers
• Approximate formulas for some functions of prime numbers
• Implementation of the DKSS Algorithm for Multiplication of Large Numbers
• Fast Integer Multiplication Using Modular Arithmetic
• A Deterministic Single Exponential Time Algorithm for Most Lattice Problems Based on Voronoi Cell Computations
• Fast Polynomial Multiplication over F _{2 60}
• On the least prime in an arithmetic progression and estimates for the zeros of Dirichlet L-functions
• Modular Multiplication Without Trial Division
• Faster Integer Multiplication
• Discrete Weighted Transforms and Large-Integer Arithmetic
• Low-Weight Polynomial Form Integers for Efficient Modular Multiplication
• Implementing Fast Carryless Multiplication
• Faster integer multiplication using plain vanilla FFT primes
• Generalised Mersenne numbers revisited
• An Algorithm for the Machine Calculation of Complex Fourier Series
• Linear Recurrences with Polynomial Coefficients and Application to Integer Factorization and Cartier–Manin Operator
• Selected Areas in Cryptography

This page was built for publication: Faster integer multiplication using short lattice vectors