The LLL algorithm to factor polynomials with integer coefficients. Previously people had been fussing with Hensel lifting and tons of other methods that (imo) were far too complicated. (For a good reference on LLL and factoring polynomials, also see Yap's excellent book and his chapter on lattice reduction ).

LLL solved the more general problem of finding short (or 'short enough') vectors on integer lattices in higher dimensional spaces. This was then used to to encode the problem of factoring polynomials with integer coefficients in it. As an added bonus, the lattice reduction techniques presented also solved the simultaneous Diophantine approximation problem, but that somehow doesn't seem as striking as integer polynomial factorization.