Efficient verification of Tunnell's criterion
type: Item
instance of: scholarly article
title: Efficient verification of Tunnell's criterion
zbMATH Open document ID: 1183.11015
DOI: 10.1007/BF03167537
author: Eric Bach
author: Nathan Ryan
published in: Japan Journal of Industrial and Applied Mathematics
publication date: 2008-12-01T00:00:00Z
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\).
reviewed by: Fumio Hazama
Mathematics Subject Classification ID: 11D25
Mathematics Subject Classification ID: 11G05
Mathematics Subject Classification ID: 11D45
Mathematics Subject Classification ID: 11Y16
Mathematics Subject Classification ID: 11E25
zbMATH DE Number: 5375421
zbMATH Keywords: congruent numbers
zbMATH Keywords: quadratic forms
zbMATH Keywords: complexity
describes a project that uses: NTL
MaRDI profile type: Publication
cites work: An improved Monte Carlo factorization algorithm
cites work: Lattice points on ellipses
cites work: The Jacobi symbol algorithm
cites work: History of the theory of numbers. Vol. I: Divisibility and primality. Vol. II: Diophantine analysis. Vol. III: Quadratic and higher forms.
cites work: Asymptotically Fast Factorization of Integers
cites work: Q4737489
cites work: Q5535018
cites work: Determining acceptance possibility for a quantum computation is hard for the polynomial hierarchy
cites work: Q4359457
cites work: Q3710578
cites work: Q3941473
cites work: Q3999066
cites work: Q3346401
cites work: Q2706552
cites work: Q4046106
cites work: Q3728066
cites work: Q4822945
cites work: Q3043255
cites work: Q4063214
cites work: Q3710637
cites work: Q4210105
cites work: A classical Diophantine problem and modular forms of weight \(3/2\)
cites work: The complexity of combinatorial problems with succinct input representation
description: scientific article; zbMATH DE number 5375421