The Algorithmic Solution of Simultaneous Diophantine Equations

A new method is presented for solving pairs of simultaneous Diophantine equations, such as those which result from the 2-descent process on elliptic curves. The method works by determining a set of solutions modulo a prime P, raising each of these solutions to a set of P solutions modulo p2, and then determining a solution modulo p6 for each of the solutions modulo p2. These solutions modulo p6 lie on a lattice which is then reduced using a suitable lattice reduction algorithm. The required solution can then be written as a linear combination of the basis vectors for the lattice, and the coefficients in this combination are determined. The running time of this algorithm is O(N213) where N is a bound on the size of the solution required. Variations on the method are also presented. Following a 2-descent on elliptic curves of the form y2 = X3 +pX, where p =- 5 (mod 8) originally described by Bremner and Cassels [8], the methods are applied to various pairs of equations. Generators for the free abelian part of the group of rational points on each of these curves are presented, including the case p= 16421 which has a canonical height of 137.2290. By combining the method with existing techniques, we also find a generator for the set of points of infinite order on the curve y2 = X3 + 17477X. This point has canonical height h(P) = 406.4797. We also find a generator on the Mordell curve y2 = X3 + 7823, which is the only case missing from the tables of Gebel, Peth6 and Zimmer for the curves y2=x3+k with IkI :ý! 10000 [20].

Grantor dc:publisher

Oxford Brookes University

Year dc:date

2005

Author dc:creator

• Long, Rachel L.

Contributors dc:contributor

• Hobbs, Catherine
• Pidcock, Mike
• Heath-Brown, Roger

Statement dc:rights

• All rights reserved

Language dc:language

en

DOI dc:identifier

https://doi.org/https://doi.datacite.org/dois/10.24384%2Fzy0h-9782

OAI identifier oai:identifier

tle:5b3c63d3-c971-454d-b7d0-7bd10601c48e:d6bd9758-527a-46cd-bfe2-c433766e8fca:1