RECORD
Simple Lattice Basis Computation -- The Generalization of the Euclidean Algorithm
Data Structures and Algorithms · Submitted 27 Nov 2023
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim In this paper, we show that the classical Euclidean algorithm can be adapted in a very natural way to compute a basis of a general lattice $L(a_1, \ldots , a_m)$ given vectors $a_1, \ldots , a_m \in \mathbb{Z}^n$ with $m> \mathrm{rank}(a_1, \ldots ,a_m)$.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
The Euclidean algorithm is one of the oldest algorithms known to mankind. Given two integral numbers $a_1$ and $a_2$, it computes the greatest common divisor (gcd) of $a_1$ and $a_2$ in a very elegant way. From a lattice perspective, it computes a basis of the sum of two one-dimensional lattices $a_1 \mathbb{Z}$ and $a_2 \mathbb{Z}$ as $\gcd(a_1,a_2) \mathbb{Z} = a_1 \mathbb{Z} + a_2 \mathbb{Z}$. In this paper, we show that the classical Euclidean algorithm can be adapted in a very natural way to compute a basis of a general lattice $L(a_1, \ldots , a_m)$ given vectors $a_1, \ldots , a_m \in \mathbb{Z}^n$ with $m> \mathrm{rank}(a_1, \ldots ,a_m)$. Similar to the Euclidean algorithm, our algorithm is very easy to describe and implement and can be written within 12 lines of pseudocode. While the Euclidean algorithm halves the largest number in every iteration, our generalized algorithm halves the determinant of a full rank subsystem leading to at most $\log (\det B)$ many iterations, for some initial subsystem $B$. Therefore, we can compute a basis of the lattice using at most $\tilde{O}((m-n)n\log(\det B) + mn^{\omega-1}\log(||A||_\infty))$ arithmetic operations, where $\omega$ is the matrix multiplication exponent and $A = (a_1, \ldots, a_m)$. Even using the worst case Hadamard bound for the determinant, our algorithm improves upon existing algorithm. Another major advantage of our algorithm is that we can bound the entries of the resulting lattice basis by $\tilde{O}(n^2\cdot ||A||_{\infty})$ using a simple pivoting rule. This is in contrast to the typical approach for computing lattice basis, where the Hermite normal form (HNF) is used. In the HNF, entries can be as large as the determinant and hence can only be bounded by an exponential term.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | The Euclidean algorithm is one of the oldest algorithms known to mankind. | background 1.00 | 0.03 | 0.01 | asserted 1.00 |
| s1 | Given two integral numbers $a_1$ and $a_2$, it computes the greatest common divisor (gcd) of $a_1$ and $a_2$ in a very elegant way. | background 1.00 | 0.04 | 0.02 | asserted 1.00 |
| s2 | From a lattice perspective, it computes a basis of the sum of two one-dimensional lattices $a_1 \mathbb{Z}$ and $a_2 \mathbb{Z}$ as $\gcd(a_1,a_2) \mathbb{Z} = a_1 \mathbb{Z} + a_2 \mathbb{Z}$. | background 0.78 | 0.09 | 0.03 | asserted 1.00 |
| s3 | In this paper, we show that the classical Euclidean algorithm can be adapted in a very natural way to compute a basis of a general lattice $L(a_1, \ldots , a_m)$ given vectors $a_1, \ldots , a_m \in \mathbb{Z}^n$ with $m> \mathrm{rank}(a_1, \ldots ,a_m)$. | contribution 1.00 | 0.94 | 0.83 | asserted 1.00 |
| s4 | Similar to the Euclidean algorithm, our algorithm is very easy to describe and implement and can be written within 12 lines of pseudocode. | method 0.51 | 0.85 | 0.07 | asserted 1.00 |
| s5 | While the Euclidean algorithm halves the largest number in every iteration, our generalized algorithm halves the determinant of a full rank subsystem leading to at most $\log (\det B)$ many iterations, for some initial subsystem $B$. | result 0.61 | 0.86 | 0.12 | asserted 1.00 |
| s6 | Therefore, we can compute a basis of the lattice using at most $\tilde{O}((m-n)n\log(\det B) + mn^{\omega-1}\log(||A||_\infty))$ arithmetic operations, where $\omega$ is the matrix multiplication exponent and $A = (a_1, \ldots, a_m)$. | result 0.95 | 0.91 | 0.31 | asserted 0.97 |
| s7 | Even using the worst case Hadamard bound for the determinant, our algorithm improves upon existing algorithm. | result 0.83 | 0.83 | 0.18 | asserted 1.00 |
| s8 | Another major advantage of our algorithm is that we can bound the entries of the resulting lattice basis by $\tilde{O}(n^2\cdot ||A||_{\infty})$ using a simple pivoting rule. | result 0.69 | 0.93 | 0.13 | asserted 0.99 |
| s9 | This is in contrast to the typical approach for computing lattice basis, where the Hermite normal form (HNF) is used. | background 0.63 | 0.08 | 0.05 | asserted 0.99 |
| s10 | In the HNF, entries can be as large as the determinant and hence can only be bounded by an exponential term. | background 0.81 | 0.05 | 0.04 | asserted 0.94 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
The Euclidean algorithm is one of the oldest algorithms known to mankind. Given two integral numbers $a_1$ and $a_2$, it computes the greatest common divisor (gcd) of $a_1$ and $a_2$ in a very elegant way. From a lattice perspective, it computes a basis of the sum of two one-dimensional lattices $a_1 \mathbb{Z}$ and $a_2 \mathbb{Z}$ as $\gcd(a_1,a_2) \mathbb{Z} = a_1 \mathbb{Z} + a_2 \mathbb{Z}$. In this paper, we show that the classical Euclidean algorithm can be adapted in a very natural way to compute a basis of a general lattice $L(a_1, \ldots , a_m)$ given vectors $a_1, \ldots , a_m \in \mathbb{Z}^n$ with $m> \mathrm{rank}(a_1, \ldots ,a_m)$. Similar to the Euclidean algorithm, our algorithm is very easy to describe and implement and can be written within 12 lines of pseudocode. While the Euclidean algorithm halves the largest number in every iteration, our generalized algorithm halves the determinant of a full rank subsystem leading to at most $\log (\det B)$ many iterations, for some initial subsystem $B$. Therefore, we can compute a basis of the lattice using at most $\tilde{O}((m-n)n\log(\det B) + mn^{\omega-1}\log(||A||_\infty))$ arithmetic operations, where $\omega$ is the matrix multiplication exponent and $A = (a_1, \ldots, a_m)$. Even using the worst case Hadamard bound for the determinant, our algorithm improves upon existing algorithm. Another major advantage of our algorithm is that we can bound the entries of the resulting lattice basis by $\tilde{O}(n^2\cdot ||A||_{\infty})$ using a simple pivoting rule. This is in contrast to the typical approach for computing lattice basis, where the Hermite normal form (HNF) is used. In the HNF, entries can be as large as the determinant and hence can only be bounded by an exponential term.
Human review
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.