#### Vol. 2, 2019

 Download this article For screen For printing
 Recent Volumes 5: Gauge Theory and Low-Dimensional Topology 4: ANTS XIV 3: Hillman: Poincaré Duality 2: ANTS XIII 1: ANTS X
 The Open Book Series All Volumes About the Series Ethics Statement Purchase Printed Copies Author Index ISSN (electronic): 2329-907X ISSN (print): 2329-9061 MSP Books and Monographs 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\left(nlogn\phantom{\rule{0.3em}{0ex}}{4}^{{log}^{\ast }n}\right)$ 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 $\theta$-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