Abstract

We prove that $n$-bit integers may be multiplied in $O\left(nlogn{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

Mathematical Subject Classification 2010

Milestones

Authors