Computing bases in Hermite normal form of lattices of integer relations
This provides an efficient algorithm for a fundamental problem in integer linear algebra, with potential impact on computational number theory and cryptography.
The paper presents a randomized Las Vegas algorithm to compute a basis in Hermite normal form for a lattice of integer relations, achieving bit complexity comparable to matrix multiplication. For square M and F=I, it computes the Hermite normal form with failure probability ≤1/2.
Given a full column rank $M \in \Z^{\ell \times m}$ and an $F \in \Z^{n \times m}$ we present an algorithm to compute the $n \times n$ basis in Hermite form of the integer lattice comprised of all rows $p \in \Z^{1 \times n}$ such that $pF \in \Z^{1 \times m}$ is in the integer lattice generated by the rows of $M$. The algorithm is randomized of the Las Vegas type, that is, it can fail with probability at most $1/2$, but if fail is not returned it guarantees to produce the correct result. When $M$ is square and $F=I_m$, then the computed basis is the Hermite normal form of $M$, and the algorithm uses about the same number of bit operations as required to multiply together two matrices of the same dimension and size of entries as $M$.