Faster integer multiplication using short lattice vectors
David Harvey, Joris van der Hoeven · The Open Book Series · 2019
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.