Faster integer multiplication using short lattice vectors

DOI10.2140/OBS.2019.2.293MaRDI QIDQ6165872zbMATH OpenOpenAlexWikidataFDO

Authors David Harvey, Joris van der Hoeven

Publication date 2 August 2023

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

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

zbMATH Keywords

efficient algorithmfast Fourier transforminteger multiplication

Mathematics Subject Classification ID

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

Abstract: We prove that $n$-bit integers may be multiplied in $O(nlogn,4^{lo{g}^{\ast }n})$ bit operations. This complexity bound had been achieved previously by several authors, assuming various unproved number-theoretic hypotheses. Our proof is unconditional, and depends in an essential way on Minkowski's theorem concerning lattice vectors in symmetric convex sets.

Recommendations

• Even faster integer multiplication
• Faster integer multiplication
• Faster integer multiplication
• Fast integer multiplication using modular arithmetic
• Integer multiplication in time \(O(n\log n)\)

Cites work

• A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations
• An Algorithm for the Machine Calculation of Complex Fourier Series
• Approximate formulas for some functions of prime numbers
• Discrete Weighted Transforms and Large-Integer Arithmetic
• Even faster integer multiplication
• Factoring polynomials with rational coefficients
• Fast integer multiplication using modular arithmetic
• Fast multiplication of large numbers
• Fast polynomial multiplication over \(\mathbb{F}_{2^{60}}\)
• Faster integer multiplication
• Faster integer multiplication
• Faster integer multiplication using plain vanilla FFT primes
• Generalised Mersenne numbers revisited
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 3335234 (Why is no real title available?)
• Implementation of the DKSS algorithm for multiplication of large numbers
• Implementing fast carryless multiplication
• Linear Recurrences with Polynomial Coefficients and Application to Integer Factorization and Cartier–Manin Operator
• Low-Weight Polynomial Form Integers for Efficient Modular Multiplication
• Modern computer algebra
• Modular Multiplication Without Trial Division
• On the least prime in an arithmetic progression and estimates for the zeros of Dirichlet L-functions
• Selected Areas in Cryptography

Cited in

(10)

• Faster polynomial multiplication over finite fields using cyclotomic coefficient rings
• Fast multivariate multi-point evaluation revisited
• Accelerated tower arithmetic
• Integer multiplication in time \(O(n\log n)\)
• Shortest Integer Vectors
• scientific article; zbMATH DE number 4104356 (Why is no real title available?)
• Polynomial multiplication over finite fields in time O(n n)
• Multiplication
• Faster truncated integer multiplication
• On polynomial modular number systems over \(\mathbb{Z}/p\mathbb{Z}\)

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6165872)