×

zbMATH — the first resource for mathematics

Efficient solution of rational conics. (English) Zbl 1022.11031
The aim of the present paper is to give efficient algorithms to find a non-trivial solution and the parametrisation of the solutions of the Diophantine equation \[ f(X,Y,Z) =0, \] where \(f(X,Y,Z)\) denotes a homogeneous quadratic polynomial with integer coefficients. The problem is classical, because the left hand side of the equation can be transformed by a linear transformation to Legendre’s equation \(aX^2 + bY^2 + cZ^2 =0\), where it can be assumed without loss of generality that the integers \(a,b,c\) are pairwise coprime and \(abc\) is square-free. Another equivalent form of the starting equation is \(X^2 - aZ^2 = bY^2\). To find a non-trivial solution of the last equation Legendre gave a descent method which uses the prime power factorization of the integer \(b\).
In the first method Legendre’s classical method is modified such that after finding a solution \((x_0,z_0)\) of the congruence \(X^2 -aZ^2 \equiv 0 \pmod b\) one tries to find a solution with \(x_0^2 + |a|z_0^2\) as small as possible. This can be done by using lattice base reduction. It is shown through an example that the extra step improves the algorithm considerably.
The second half of the paper is dealing with algorithms which (almost) avoid factorization. The basic idea is that having a solubility certificate of the system of congruences \[ X_1^2 \equiv -bc \pmod a, \qquad X_2^2 \equiv -ca \pmod b, \qquad X_3^2 \equiv -ab \pmod c, \] one can use these data in a later stage of the algorithm without factorization of the occurring integers. The tools here are lattice base reduction procedures in dimensions two and three. I shall call the reader’s attention to Lemma 2.7. It states that if \(b_1,b_2,b_3\) is an LLL-reduced basis of a three dimensional lattice \(\mathcal L\), then the shortest non-zero vector of \(\mathcal L\) has the form \(n_1b_1 + n_ 2b_2 + n_3b_3\), where \(n_i \in \{-1,0,1\}\).

MSC:
11G30 Curves of arbitrary genus or genus \(\ne 1\) over global fields
11D09 Quadratic and bilinear Diophantine equations
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] B. J. Birch and H. P. F. Swinnerton-Dyer, Notes on elliptic curves. II, J. Reine Angew. Math. 218 (1965), 79 – 108. · Zbl 0147.02506
[2] J. W. S. Cassels, Lectures on elliptic curves, London Mathematical Society Student Texts, vol. 24, Cambridge University Press, Cambridge, 1991. · Zbl 0752.14033
[3] Todd Cochrane and Patrick Mitchell, Small solutions of the Legendre equation, J. Number Theory 70 (1998), no. 1, 62 – 66. · Zbl 0908.11012
[4] Henri Cohen, A course in computational algebraic number theory, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993. · Zbl 0786.11071
[5] J. E. Cremona, Higher descents on elliptic curves, preprint: see http://www.maths.nott.ac.uk/personal/jec/papers/d2.ps.
[6] István Gaál, Attila Pethő, and Michael Pohst, Simultaneous representation of integers by a pair of ternary quadratic forms — with an application to index form equations in quartic number fields, J. Number Theory 57 (1996), no. 1, 90 – 104. · Zbl 0853.11023
[7] Carl Friedrich Gauss, Disquisitiones arithmeticae, Springer-Verlag, New York, 1986. Translated and with a preface by Arthur A. Clarke; Revised by William C. Waterhouse, Cornelius Greither and A. W. Grootendorst and with a preface by Waterhouse. · Zbl 0136.32301
[8] Kenneth F. Ireland and Michael I. Rosen, A classical introduction to modern number theory, Graduate Texts in Mathematics, vol. 84, Springer-Verlag, New York-Berlin, 1982. Revised edition of Elements of number theory. · Zbl 0482.10001
[9] B. Mazur, On the passage from local to global in number theory, Bull. Amer. Math. Soc. (N.S.) 29 (1993), no. 1, 14 – 50. · Zbl 0813.14016
[10] L. J. Mordell, Diophantine equations, Pure and Applied Mathematics, Vol. 30, Academic Press, London-New York, 1969. · Zbl 0188.34503
[11] Michael E. Pohst, On Legendre’s equation over number fields, Publ. Math. Debrecen 56 (2000), no. 3-4, 535 – 546. Dedicated to Professor Kálmán Győry on the occasion of his 60th birthday. · Zbl 0980.11020
[12] John M. Pollard and Claus-P. Schnorr, An efficient solution of the congruence \?²+\?\?²=\?\pmod\?, IEEE Trans. Inform. Theory 33 (1987), no. 5, 702 – 709. · Zbl 0636.94008
[13] Heinrich Rolletschek, On the number of divisions of the Euclidean algorithm applied to Gaussian integers, J. Symbolic Comput. 2 (1986), no. 3, 261 – 291. · Zbl 0609.12001
[14] D. Simon, Équations dans les corps de nombres et discriminants minimaux, Ph.D. thesis, Université Bordeaux I, 1998.
[15] Nigel P. Smart, The algorithmic resolution of Diophantine equations, London Mathematical Society Student Texts, vol. 41, Cambridge University Press, Cambridge, 1998. · Zbl 0907.11001
[16] Brigitte Vallée, Algorithmique dans les réseaux de petite dimension: un point de vue affine sur la recherche des minima, Séminaire de théorie des nombres, 1985 – 1986 (Talence, 1985 – 1986) Univ. Bordeaux I, Talence, 1986, pp. Exp. No. 13, 15 (French). · Zbl 0605.10017
[17] H.-J. Weber, Algorithmische Konstruktion hyperelliptischer Kurven mit kryptographischer Relevanz und einem Endomorphismenring echt größer als Z, Ph.D. thesis, Institut für Experimentelle Mathematik, University of Essen, 1997.
[18] André Weil, Number theory, Birkhäuser Boston, Inc., Boston, MA, 1984. An approach through history; From Hammurapi to Legendre. · Zbl 0531.10001
[19] J. Wilson, Curves of genus 2 with real multiplication by a square root of 5, Ph.D. thesis, University of Oxford, 1998.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.