Faster integer multiplication using short lattice vectors

David Harvey, Joris van der Hoeven

We prove that $n$-bit integers may be multiplied in $O(n\log n{4}^{{\log }^{\ast }n})$ bit operations. This complexity bound had been achieved previously by several authors, assuming va…