Polynomial time algorithms for finding integer relations among real numbers.

We study the computational problem of finding a short integer relation m for a real vector x in R sup N, which is a nonzero vector m in ZZ sup n such that x sup T m = 0, or else proving that no such short integer relation exists. This problem has been long studied under the names "generalized Euclidean algorithm" and multi-dimensional continued fraction algorithm." The first algorithm of this kind proved to find integer relations in all dimensions when they exist is due to Ferguson and Forcade, who-did not give a complexity analysis.