Efficient verification of Tunnell's criterion

DOI10.1007/BF03167537MaRDI QIDQ957686zbMATH OpenFDO

Publication date 1 December 2008

Published in Japan Journal of Industrial and Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF03167537

complexity congruent numbers quadratic forms

Cubic and quartic Diophantine equations (11D25) Counting solutions of Diophantine equations (11D45) Sums of squares and representations by other particular quadratic forms (11E25) Elliptic curves over global fields (11G05) Number-theoretic algorithms; complexity (11Y16)

Review text

A positive integer \(n\) is said to be a congruent number if there is a right triangle with rational sides whose area is \(n\). It is well known that \(n\) is congruent if and only if the Mordell-Weil group \(E_n(\mathbb Q)\) of the elliptic curve \(E_n:y^2=x^3-n^2x\) is of positive rank. Based on \textit{J. B. Tunnell}'s result in [Invent. Math., 72, 323--334 (1983; Zbl 0515.10013)], \textit{N. Koblitz} derived in [Introduction to elliptic curves and modular forms. New York: Springer (1984; Zbl 0553.10019)] the following: An odd squarefree positive integer \(n\) is congruent if and only if \(\#\{(x,y,z)\in \mathbb{Z}^3;Q_1(x,y,z)=n\) with \(z\) odd\}=\(\#\{(x,y,z) \in\mathbb Z^3;Q_1 (x,y,z)=n\) with \(z\) even\}, where \(Q(x,y,z)=2x^2+y^2+8z^2\). (When \(n\) is even, replace \(n\) by \(n/2\) and \(Q_1\) by \(Q_3(x,y,z)=4x^2+y^2 +8z^2\).) Relying on this result and assuming the Birch and Swinnerton-Dyer conjecture, the authors give an algorithm to test congruence which uses \(n^{1/2+o(1)}\) arithmetic operations, where those previously known use \(O(n)\). Their algorithm proceeds roughly as follows. Factor \(n-8z^2\) for \(0\leq z\leq\sqrt{n/8}\), count the number of solutions of \(x^2+2y^2= m\), and examine whether the total for even \(z\) equals to that for odd \(z\).

Recommendations

Cites work

Cited in

(4)

Describes a project that uses

Uses Software

NTL

This page was built for publication: Efficient verification of Tunnell's criterion

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q957686)