Thirteenth Algorithmic Number Theory Symposium ANTS-XIII University of Wisconsin, Madison July 16 – 20, 2018 Thirteenth Algorithmic Number Theory Symposium (ANTS-XIII) July 16 – 20, 2018

Faster integer multiplication using short lattice vectors

David Harvey and Joris van der Hoeven

Abstract: We prove that n-bit integers may be multiplied in O(n log n 4 ^{log∗ 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.

Published Paper
Talk Slides