Efficient verification of Tunnell's criterion (Q957686)

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\).