A fast algorithm for finding ``small'' solutions of \(F(x,y)= G(x,y)\) over imaginary quadratic fields
type: Item
instance of: scholarly article
title: A fast algorithm for finding ``small'' solutions of \(F(x,y)= G(x,y)\) over imaginary quadratic fields
zbMATH Open document ID: 0806.11018
author: István Gaál
published in: Journal of Symbolic Computation
publication date: 1995-02-13T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 11D25
Mathematics Subject Classification ID: 11D99
Mathematics Subject Classification ID: 11D75
Mathematics Subject Classification ID: 11Y16
zbMATH DE Number: 541171
zbMATH Keywords: ring of integers
zbMATH Keywords: imaginary quadratic field
zbMATH Keywords: LLL-basis reduction algorithm
reviewed by: Nikos Tzanakis
MaRDI profile type: Publication
full work available at URL: jsco.1993.1050
OpenAlex ID: W1972947556
DOI: 10.1006/JSCO.1993.1050
Recommended article: Efficient solution of rational conics
Recommended article: Q3804775
Recommended article: Q3699763
Recommended article: Small solutions of congruences over algebraic number fields
Recommended article: Selected Applications of LLL in Number Theory
Recommended article: On a kind of superelliptic Diophantine equations
Recommended article: On the resolution of \(F(x,y)=G(x,y)\)
Recommended article: An Elementary Algorithm for Solving a Diophantine Equation of Degree Fourth with Runge’s Condition
Recommended article: Q3474707
description: scientific article; zbMATH DE number 541171