Paper 2024/2089 Original: eprint.iacr.org/2024/2089 ↗

Computing the Hermite Normal Form: A Survey

Abstract

The Hermite Normal Form (HNF) of a matrix is an analogue of the echolon form over the integers. A common obstacle in computing the HNF is the extensive blow up of intermediate values. We survey algorithms, deterministically computing the HNF. After presenting a naive algorithm, we discuss the MODULO DETERMINANT ALGORITHM from [DKT87]. It keeps the entries bounded by d, the determinant of the lattice, and has a time complexity of O(n^3 log2 d), where n is the dimension of the matrix. Although this algorithm is very useful if the determinant is small, in the general case the entries still become extremely large. Secondly, we survey the LINEAR SPACE ALGORITHM from [MW01]. It has a time complexity of O(n^5 polylog(M, n)), where M denotes the largest absolute value of the input matrix. This is as fast as the best previously known algorithms, but in contrast, it assures space complexity linear in the input size, i.e. O(n^2 log M). As last algorithm to compute the HNF we discuss the HEURISTIC ALGORITHM from [MW01], which is based on the first two algorithms. It achieves a much faster runtime in practice, yielding a heuristic runtime of O(n^4 polylog(M, n)), while keeping the linear space complexity.