Paper 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.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint.
- Keywords
- Hermite Normal FormHNF
- Contact author(s)
- leon damer @ edu rub de
- History
- 2025-09-09: revised
- 2024-12-28: received
- See all versions
- Short URL
- https://ia.cr/2024/2089
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/2089,
author = {Leon Damer},
title = {Computing the Hermite Normal Form: A Survey},
howpublished = {Cryptology {ePrint} Archive, Paper 2024/2089},
year = {2024},
url = {https://eprint.iacr.org/2024/2089}
}
