Approximate common divisor problem and lattice sieving

Описан эвристический алгоритм вычисления общего делителя двух целых чисел, одно из которых известно приближенно. Эта задача сводится к задаче решения системы целочисленных линейных неравенств. Такая система с двумя неизвестными может быть решена с помощью метода решеточного просеивания, предложенного Й. Франке и Т. Клейнюнгом. Разработанный алгоритм в некоторых случаях оказывается быстрее других известных методов.