Faster integer multiplication using short lattice vectors

DOI10.2140/OBS.2019.2.293arXiv1802.07932OpenAlexW3102645309WikidataQ128417242 ScholiaQ128417242MaRDI QIDQ6165872FDOQ6165872

Authors: David Harvey, Joris van der Hoeven 

Publication date: 2 August 2023

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

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.

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

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)\)

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)

Cites Work

• Faster integer multiplication
• An Algorithm for the Machine Calculation of Complex Fourier Series
• Title not available (Why is that?)
• Factoring polynomials with rational coefficients
• Fast multiplication of large numbers
• Modular Multiplication Without Trial Division
• Title not available (Why is that?)
• Approximate formulas for some functions of prime 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 \(\mathbb{F}_{2^{60}}\)
• Even faster integer multiplication
• On the least prime in an arithmetic progression and estimates for the zeros of Dirichlet L-functions
• Faster integer multiplication
• Modern computer algebra
• Discrete Weighted Transforms and Large-Integer Arithmetic
• Linear Recurrences with Polynomial Coefficients and Application to Integer Factorization and Cartier–Manin Operator
• Selected Areas in Cryptography
• Generalised Mersenne numbers revisited
• Faster integer multiplication using plain vanilla FFT primes
• Implementation of the DKSS algorithm for multiplication of large numbers
• Implementing fast carryless multiplication
• Low-Weight Polynomial Form Integers for Efficient Modular Multiplication

Cited In (10)

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

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)