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 ax^{2}+bxy+cy^{2}.
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 ax^{2}+bxy+cy^{2} 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.