Efficient solution of rational conics
Diophantine equationefficient algorithmshomogeneous quadratic polynomial with integer coefficientslattice basis reductionLegendre's equationrational conics
Quadratic and bilinear Diophantine equations (11D09) [https://duckduckgo.com/?q=MSC%2011G30%20%22Curves+of+arbitrary+genus+or+genus+%28%0D%0Ae+1%29+over+global+fields%22 Curves of arbitrary genus or genus ( e 1) over global fields (11G30)]
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\}\).
- A classical introduction to modern number theory. (Rev. and expand. version of 1972)
- A course in computational algebraic number theory
- An efficient solution of the congruence<tex>x^2 + ky^2 = mpmod{n}</tex>
- scientific article; zbMATH DE number 3841940 (Why is no real title available?)
- scientific article; zbMATH DE number 3977090 (Why is no real title available?)
- scientific article; zbMATH DE number 51845 (Why is no real title available?)
- scientific article; zbMATH DE number 1200746 (Why is no real title available?)
- scientific article; zbMATH DE number 3221502 (Why is no real title available?)
- scientific article; zbMATH DE number 3300651 (Why is no real title available?)
- Notes on elliptic curves. II.
- On Legendre's equation over number fields
- On the number of divisions of the Euclidean algorithm applied to Gaussian integers
- On the passage from local to global in number theory
- Simultaneous representation of integers by a pair of ternary quadratic forms -- with an application to index form equations in quartic number fields
- Small solutions of the Legendre equation
- A fast algorithm for finding ``small solutions of \(F(x,y)= G(x,y)\) over imaginary quadratic fields
- Explicit equivalence of quadratic forms over \(\mathbb{F}_q(t)\)
- Computing with quadratic forms over number fields
- On the solution of \(x^2+dy^2=m\)
- Improved torsion-point attacks on SIDH variants
- Complete and computable orbit invariants in the geometry of the affine group over the integers
- Splitting quaternion algebras over quadratic number fields
- On the number of solutions of the equation Rx^2 + Sy^2 1 N
- On the parametrization of solutions of quadratic equations
- Trivializing a central simple algebra of degree 4 over the rational numbers.
- Brauer groups of diagonal quartic surfaces
- Cyclic polygons with rational sides and area
- Algorithms for quadratic forms
- Solving conics over functions fields
- The anisotropic part of a quadratic form over a number field
- How many rational points does a random curve have?
- Uniformly counting rational points on conics
- Computing L-series of geometrically hyperelliptic curves of genus three
- Higher descents on an elliptic curve with a rational 2-torsion point
- Solving Bivariate Quadratic Congruences in Random Polynomial Time
- scientific article; zbMATH DE number 4089637 (Why is no real title available?)
- Splitting full matrix algebras over algebraic number fields.
- Computing the Cassels-Tate pairing on 3-isogeny Selmer groups via cubic norm equations
- Solving quadratic equations using reduced unimodular quadratic forms
- A Thue Equation with Quadratic Integers as Variables
- Selected applications of LLL in number theory
- A parametric version of the Hilbert-Hurwitz theorem using hypercircles
- Identifying the matrix ring: algorithms for quaternion algebras and quadratic forms
- Optimal affine reparametrization of rational curves
- Factorization and root-finding for polynomials over division quaternion algebras
- Hashing to elliptic curves through Cipolla-Lehmer-Müller's square root algorithm
- The anisotropic part of a quadratic form over a global function field
- Efficient computations in central simple algebras using Amitsur cohomology
- Isotropic vectors over global fields
- Linear loop synthesis for quadratic invariants
- Near-optimal parameterization of the intersection of quadrics. III. Parameterizing singular intersections
This page was built for publication: Efficient solution of rational conics
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4806396)