#### Vol. 2, 2019

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