Approximate common divisor problem and lattice sieving

A heuristic algorithm for computing common divisors of two integers (one of which is known only approximately) is described. We reduce this computational problem to the solution of a system of integer linear inequalities. This system with two unknowns is solved by the method suggested by J. Franke and T. Kleinjung for lattice sieving. In some cases our algorithm is faster than other methods.