Dear Sergey, dear Frank, just a short additional comment on this:
Actually, I did not know either that this Lemma has a name attached to it, in my eyes it was part of mathematical folklore. Anyway, the standard algorithmic solution (which is the one Frank has implemented, as far as I see) is also known as Gauss's algorithm finding a shortest vector in a lattice of rank 2 in Euclidean space (applied to the lattice spanned by [n,0] and [x,1]). As such, it as a variant of the Euclidean algorithm in Z, and a predecessor of the LLL algorithm. And indeed, as it is essentially the Euclidean algorithm running, this works efficiently for HUGE numbers, as you have observed. For more details, see for example Algorithm 1.3.14 in Cohen's book `A course in computational algebraic number theory'. Best wishes, Jürgen (Müller) _______________________________________________ Forum mailing list Forum@mail.gap-system.org http://mail.gap-system.org/mailman/listinfo/forum
