  A Las Vegas randomized algorithm is given to compute the Hermite normal form
of a nonsingular integer matrix $A$ of dimension $n$. The algorithm uses
quadratic integer multiplication and cubic matrix multiplication and has
running time bounded by $O(n^3 (\log n + \log ||A||)^2(\log n)^2)$ bit
operations, where $||A||= \max_{ij} |A_{ij}|$ denotes the largest entry of $A$
in absolute value. A variant of the algorithm that uses pseudo-linear integer
multiplication is given that has running time $(n^3 \log ||A||)^{1+o(1)}$ bit
operations, where the exponent $"+o(1)"$ captures additional factors $c_1 (\log
n)^{c_2} (\log \log ||A||)^{c_3}$ for positive real constants $c_1,c_2,c_3$.
