A fast algorithm for finding ``small'' solutions of \(F(x,y)= G(x,y)\) over imaginary quadratic fields (Q1318848): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claim: reviewed by (P1447): Item:Q795859 |
||
Property / reviewed by | |||
Property / reviewed by: Nicholas Tzanakis / rank | |||
Revision as of 05:24, 21 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A fast algorithm for finding ``small'' solutions of \(F(x,y)= G(x,y)\) over imaginary quadratic fields |
scientific article |
Statements
A fast algorithm for finding ``small'' solutions of \(F(x,y)= G(x,y)\) over imaginary quadratic fields (English)
0 references
13 February 1995
0 references
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.
0 references
ring of integers
0 references
imaginary quadratic field
0 references
LLL-basis reduction algorithm
0 references