A fast algorithm for finding ``small'' solutions of \(F(x,y)= G(x,y)\) over imaginary quadratic fields
In an earlier paper [J. Symb. Comput. 16, 295-303 (1993; Zbl 0789.11022)] the author dealt with the ``small'' integral solutions of equations of the form \(F(x,y)= G(x,y)\), where \(F,G\in \mathbb{Z}[x,y]\) and \(F\) is homogeneous with \(\deg F-\deg G\geq 3\). Here ``small'' means \(\max\{| x|,| y|\}<C\), with \(C\) a constant, which, in real world terms is not very small, say, of the size of \(10^{500}\). He developed a fast algorithm for determining all solutions as above. In the present paper he extends that algorithm to a more general situation, i.e. when \(F,G\in \mathbb{Z}_ K[x,y]\), \(\mathbb{Z}_ K\) the ring of integers of an imaginary quadratic field \(K\), and the solutions \(x\), \(y\) belong to \(\mathbb{Z}_ K\) (again, it is assumed that \(F\) is homogeneous and now \(\deg F-\deg G\geq 4\)). A basic ingredient for his method is the LLL- basis reduction algorithm. He applies his method to a specific example, in which \(K= \mathbb{Q}(i)\), \(\deg F=8\), \(\deg G=2\) and \(C= 10^{200}\). The computations were performed on an IBM compatible PC 386 AT and took something more than 2 hours. Reviewer's remark: In both his papers the author speaks about the applications of solving equations \(F(x,y)= G(x,y)\) in integers (respectively, in algebraic integers of a fixed imaginary quadratic field), up to a certain bound for \(| x|\), \(| y|\), but, unfortunately, he does not mention any such application.
scientific article; zbMATH DE number 541171