An integer $n$ is congruent if there is a triangle with rational
sides whose area is $n$. In the 1980s Tunnell gave an algorithm to
test congruence which relied on counting integral points on the
ellipsoids $2x^2+y^2+8z^2 = n$ and $2x^2+y^2+32z^2=n$. The
correctness of this algorithm is conditional on the conjecture of
Birch and Swinnerton-Dyer. The known methods for testing Tunnell's
criterion use $O(n)$ operations. In this paper we give several
methods with smaller exponents, including a randomized algorithm
using time $n^{1/2 + o(1)}$ and space $n^{o(1)}$, and a
deterministic algorithm using space and time $n^{1/2 + o(1)}$.
Publié le : 2007-10-14
Classification:
congruent numbers,
quadratic forms,
class field theory,
algorithms,
complexity
@article{1197909110,
author = {Bach, Eric and Ryan, Nathan C.},
title = {Efficient Verification of Tunnell's Criterion},
journal = {Japan J. Indust. Appl. Math.},
volume = {24},
number = {1},
year = {2007},
pages = { 229-239},
language = {en},
url = {http://dml.mathdoc.fr/item/1197909110}
}
Bach, Eric; Ryan, Nathan C. Efficient Verification of Tunnell's Criterion. Japan J. Indust. Appl. Math., Tome 24 (2007) no. 1, pp. 229-239. http://gdmltest.u-ga.fr/item/1197909110/