An algorithm is presented that probabilistically computes the exact inverse of a nonsingular n × n integer matrix A using $${({n^3(\log||A||+\log \kappa(A)))}^{1+o(1)}}$$ ( n 3 ( log | | A | | + log κ ( A ) ) ) 1 + o ( 1 ) bit operations. Here, $${||A||= \max_{ij}|A_{ij}|}$$ | | A | | = max i j | A i j | denotes the largest entry in absolute value, $${\kappa(A) := n ||A^{-1}||\,||A||}$$ κ ( A ) : = n | | A - 1 | | | | A | | is the condition number of the input matrix, and the “+o(1)” in the exponent indicates a missing factor $${c_1 {(\log n)}^{c_2}{({\rm loglog} ||A||)}^{c_3}}$$ c 1 ( log n ) c 2 ( loglog | | A | | ) c 3 for positive real constants c 1, c 2, c 3. A variation of the algorithm is presented for polynomial matrices that computes the inverse of a nonsingular n × n matrix whose entries are polynomials of degree d over a field using $${{(n^3d)}^{1+o(1)}}$$ ( n 3 d ) 1 + o ( 1 ) field operations. Both algorithms are randomized of the Las Vegas type: failure may be reported with probability at most 1/2, and if failure is not reported, then the output is certified to be correct in the same running time bound.