Efficient solution of rational conics (Q4806396)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1910550
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Efficient solution of rational conics |
scientific article; zbMATH DE number 1910550 |
Statements
Efficient solution of rational conics (English)
0 references
14 May 2003
0 references
rational conics
0 references
Legendre's equation
0 references
lattice basis reduction
0 references
efficient algorithms
0 references
Diophantine equation
0 references
homogeneous quadratic polynomial with integer coefficients
0 references
0 references
0.8021644353866577
0 references
0.793825626373291
0 references
0.7882003784179688
0 references
0.7748013138771057
0 references
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\}\).
0 references