A New Look at an Old Equation
A New Look at an Old Equation
复制标题
对旧方程的新看法
DOI：
10.1007/978-3-540-79456-1_2
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
H. Williams
中科院分区：
文献类型：
--
作者：
Reginald E. Sawilla;Alan K. Silvester;H. Williams
一般的二元二次丢番图方程ax2+bxy+cy2+dx+ey+f=0在200多年前由拉格朗日首先求解。从那时起，拉格朗日的技术几乎没有什么进步。在本文中，我们如何将这个问题归结为确定某一二次阶的理想是否为主理想的问题，如果是，则给出该理想的生成元。在此阶判别式Δ为正的困难情况下，给出了求解期望时间有界的主理想问题的拉斯维加斯算法(Δ1/6+Ɛ)，而求解该问题的拉格朗日(无条件)技巧的复杂度为O(Δ1/2+Ɛ)。
The general binary quadratic Diophantine equationax2 + bxy + cy2 + dx + ey + f = 0was first solved by Lagrange over 200 years ago. Since that time littleimprovement has been made to Lagrange's technique. In this paper weshow how to reduce this problem to that of determining whether or notan ideal of a certain quadratic order is principal and if so exhibitinga generator of that ideal. In the difficult case of the discriminant Δ ofthis order being positive, we develop a Las Vegas algorithm for solvingthe principal ideal problem that executes in expected time bounded byO(Δ1/6+Ɛ), whereas the complexity of Lagrange's (unconditional) techniquefor solving this problem is O(Δ1/2+Ɛ).