Greedy basis reduction for a rank-2 lattice repeats the following step as long as it makes progress: replace the larger basis element u by its remainder modulo the smaller basis element v; i.e., find n with nv as close as possible to u, and replace u with u-nv. (If u and v have the same size, declare either to be larger. If n is 0, the algorithm stops.)
Greedy basis reduction is typically called "Gauss reduction". A citation, if provided, is typically to Carl Friedrich Gauss, Disquisitiones arithmeticae, 1801.
However, the same algorithm was already presented in 1773 by Joseph-Louis Lagrange, Recherches d’arithmétique, Nouveaux Mémoires de l’Académie royale des Sciences et Belles-Lettres de Berlin. See pages 723 through 728.
Lagrange used this algorithm in the context of simplifying quadratic forms ax2+bxy+cy2. To see the relationship, note that the length of a linear combination of u,v is a quadratic form in the coefficients of the combination: in formulas, the length of xu+yv is ax2+bxy+cy2 for some numbers a,b,c that you can compute from u,v.
Version: This is version 2023.11.27 of the "Greedy basis reduction for rank-2 lattices ("Gauss reduction")" web page.