Anzeige
Erschienen in:
2008 | OriginalPaper | Buchkapitel
A New Look at an Old Equation
verfasst von : R. E. Sawilla, A. K. Silvester, H. C. Williams
Erschienen in: Algorithmic Number Theory
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
The general binary quadratic Diophantine equation
$$ ax^2 + bxy + cy^2 + dx + ey + f = 0 $$
was first solved by Lagrange over 200 years ago. Since that time little improvement has been made to Lagrange’s technique. In this paper we show how to reduce this problem to that of determining whether or not an ideal of a certain quadratic order is principal and if so exhibiting a generator of that ideal. In the difficult case of the discriminant
$\ensuremath{\Delta}$
of this order being positive, we develop a Las Vegas algorithm for solving the principal ideal problem that executes in expected time bounded by
$O(\ensuremath{\Delta}^{1/6 + \epsilon})$
, whereas the complexity of Lagrange’s (unconditional) technique for solving this problem is
$O(\ensuremath{\Delta}^{1/2 + \epsilon})$
.