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 ) c2 (loglog|| A ||) c3 for positive real constants c 1 ,c 2 ,c 3 .

We present a Las Vegas randomized algorithm to compute the Smith normal form of a nonsingular integer matrix. For an A ∈ Zn×n, the algorithm requires O(n3(log n + log ||A||)2 (log n)2) bit operations using standard integer and matrix arithmetic, where ||A|| = maxij |Aij | denotes the largest entry in absolute value. Fast integer and matrix multiplication can also be used, establishing that the Smith form can be computed in about the same number of bit operations as required to multiply two matrices of the same dimension and size of entries as the input matrix.

We present a deterministic reduction to matrix multiplication for the problem of linear system solving: given as input a nonsingular A \in \Z^n \times n and b \in \Z^n \times 1 , compute A^-1 b. We give an algorithm that computes the minimal integer e such that all denominators of the entries in 2^eA^-1 are relatively prime to 2. Then, for a b that has entries with bitlength O(n) times as large as the bitlength of entries in A, we give an algorithm to produce the 2-adic expansion of 2^eA^-1 b up to a precision high enough such that A^-1 b over \Q can be recovered using rational number reconstruction. Both e and the 2-adic expansion can be computed in O(\MM(n,łog n + łog ||A||) \times (łog n) (łog n + łoglog ||A||)) bit operations. Here, ||A||= \max_ij |A_ij | and \MM(n,d) is the cost to multiply together, modulo 2^d, two n \times n integer matrices. Our approach is based on the previously known reductions of linear system solving to matrix multiplication which use randomization to find an integer lifting modulus X that is relatively prime to \det A. Here, we derandomize by first computing a permutation P, a unit upper triangular M, and a diagonal S with \det S a power of two, such that U := APMS^-1 is an integer matrix with 2 \perp \det U. This allows our modulus X to be chosen a power of 2.