Vol. 2, 2019

Download this article
Download this article For screen
For printing
Recent Volumes
2: ANTS XIII
1: ANTS X
The Open Book Series
About the Series
Ethics Statement
 
Other MSP Publications
Faster integer multiplication using short lattice vectors

David Harvey and Joris van der Hoeven

Vol. 2 (2019), No. 1, 293–310
Abstract

We prove that n-bit integers may be multiplied in O(nlogn4log n ) bit operations. This complexity bound had been achieved previously by several authors, assuming various unproved number-theoretic hypotheses. Our proof is unconditional and is based on a new representation for integers modulo a fixed modulus, which we call the θ-representation. The existence of such representations is ensured by Minkowski’s theorem concerning lattice vectors in symmetric convex sets.

Keywords
integer multiplication, efficient algorithm, fast Fourier transform
Mathematical Subject Classification 2010
Primary: 68W30, 68W40
Milestones
Received: 26 February 2018
Revised: 17 September 2018
Accepted: 24 September 2018
Published: 13 February 2019
Authors
David Harvey
School of Mathematics and Statistics
University of New South Wales
Sydney
Australia
Joris van der Hoeven
Centre national de la recherche scientifique
Laboratoire d’informatique
École Polytechnique
Palaiseau
France