2023/11/27 by Kim-Manuel Klein, Klein, Kim-Manuel, Janina Reuter +1
Computer Science · #Coding theory and cryptography #Cryptography and Residue Arithmetic #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics #G.2.1 #Number Theory (math.NT) #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2311.15902
openalex publication_date 2023/11/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
The Euclidean algorithm is one of the oldest algorithms known to mankind. Given two integral numbers a1 and a2, it computes the greatest common divisor (gcd) of a1 and a2 in a very elegant way. From a lattice perspective, it computes a basis of the sum of two one-dimensional lattices a1 ℤ and a2 ℤ as gcd(a1,a2) ℤ = a1 ℤ + a2 ℤ. 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(a1, … , am) given vectors a1, … , am ∈ ℤn with m> rank(a1, … ,am). 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 O((m-n)nlog(det B) + mnω-1log(||A||_∞)) arithmetic operations, where ω is the matrix multiplication exponent and A = (a1, …, am). 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 O(n2⋅ ||A||∞) 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.