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
      0 references
      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
      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

      Identifiers